中国科学技术大学：《计算机科学导论》课程教学资源（PPT课件讲稿）第七讲 面向计算机体系结构的程序优化

课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决；如何 比较模型的表达能力 本讲座以矩阵乘算法为例， 2.程序理论关心的问题介绍围绕体系结构的优化 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、 程序设计、 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题，解决该类问题需多少资源

课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源 本讲座以矩阵乘算法为例， 介绍围绕体系结构的优化 2

讲座提纲 基本知识 -内存分层结构、 多处理器的体系结构 并行计算 一并行计算的常见方式、 循环级并行 程序中的局部性 -时间局部性、空间局部性、代码和数据局部性 矩阵乘算法及其优化 矩阵乘算法及分析、分块的矩阵乘算法及分析 围绕计算机体系结构而不是抽象模型来讨论

讲 座 提 纲 • 基本知识 – 内存分层结构、多处理器的体系结构 • 并行计算 – 并行计算的常见方式、循环级并行 • 程序中的局部性 – 时间局部性、空间局部性、代码和数据局部性 • 矩阵乘算法及其优化 – 矩阵乘算法及分析、分块的矩阵乘算法及分析 围绕计算机体系结构而不是抽象模型来讨论 3

基本知识 ·计算机内存 允许声明递归函数， 1.初学编程时的认识 存储分配有什么变化 -计算机的重要组成部分， 由若卡内存单元组成， 用于存放程序和数据，可以按地址存取 2.学习递归函数时的认识 例：快速排序 int a[11]; void quickSort(int m,int n){ void readArray()fint i;... int i; int partition(int m,int n){...} if(n>m) mainO{ i partition(m,n); readArray();a[0]-9999; quickSort(m,i-1); a[10]=9999;quickSort(1,9); quickSort(i+1,n);

基 本 知 识 • 计算机内存 1. 初学编程时的认识 – 计算机的重要组成部分，由若干内存单元组成， 用于存放程序和数据，可以按地址存取 2. 学习递归函数时的认识 例：快速排序 int a[11]; void quickSort(int m, int n) { void readArray(){int i; …} int i; int partition(int m, int n){…} if(n > m) { main(){ i = partition(m, n); readArray(); a[0] = -9999; quickSort(m, i-1); a[10] = 9999; quickSort(1, 9); quickSort(i+1, n); } } } 允许声明递归函数， 存储分配有什么变化 4

基本知识 ·计算机内存 需要分出一块来作为数据栈 函数调用关系树 main 栈 main 5

基 本 知 识 • 计算机内存 需要分出一块来作为数据栈 main 函数调用关系树 main 栈 5

基本知识 ·计算机内存 需要分出一块来作为数据栈 函数调用关系树 main 栈 int i FO main 6

基 本 知 识 • 计算机内存 需要分出一块来作为数据栈 main r 函数调用关系树 main int i r ( ) 栈 6

基本知识 ·计算机内存 需要分出一块来作为数据栈 函数调用关系树 main q(1,9) int i 栈 q1,9)j int m,n main 7

基 本 知 识 • 计算机内存 需要分出一块来作为数据栈 main r q(1,9) 函数调用关系树 main int i q (1, 9) int m, n 栈 7

基本知识 ·计算机内存 需要分出一块来作为数据栈 函数调用关系树 main int i 9(1,9) 91,3) int m,n p(1,9)q(1,3) int i 栈 int m,n main 8

基 本 知 识 • 计算机内存 需要分出一块来作为数据栈 main r q(1,9) p(1,9) q(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n 栈 函数调用关系树 8

基本知识 。计算机内存 需要分出一块来作为数据栈 函数调用关系树 inti ,0 main int m,n int i 9(1,9) 91,3) int m,n p(1,9) q(1,3) int i 栈 q1,9)j p(1,3) q(1,0) int m,n main 9

基 本 知 识 • 计算机内存 需要分出一块来作为数据栈 main r q(1,9) p(1,9) q(1,3) p(1,3) q(1,0) main int i q (1, 9) int m, n int i q (1, 3) int m, n int i q (1, 0) int m, n 栈 函数调用关系树 9

基本知识 。计算机内存 1.初学编程时的认识 2.学习递归函数时的认识 代码 3.学习动态存储分配时的认识 静态数据 通过malloc等函数申请的空 间安排在堆上 堆 内存的这种划分是通过操作 系统和编译器实现的，不是在 硬件层面上的划分 栈 10

基 本 知 识 • 计算机内存 1. 初学编程时的认识 2. 学习递归函数时的认识 3. 学习动态存储分配时的认识 通过malloc等函数申请的空 间安排在堆上 内存的这种划分是通过操作 系统和编译器实现的，不是在 硬件层面上的划分 代 码 静 态 数 据 堆 栈 10

基本知识 ·计算机内存分层 内存方面的基本局限：构造非常快的存储器或者 非常大的存储器都是可能的，但是构造不出既快 又大的存储器 虚拟内存（磁盘） 内存分层是指整个内存由 几层不同速度和大小的存 物理内存 储器组成，并且最靠近处 理器的那一层最快最小 2级缓存 1级缓存 寄存器（处理器

基 本 知 识 • 计算机内存分层 – 内存方面的基本局限：构造非常快的存储器或者 非常大的存储器都是可能的，但是构造不出既快 又大的存储器 – 内存分层是指整个内存由 几层不同速度和大小的存 储器组成，并且最靠近处 理器的那一层最快最小 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 11