高性能计算机的体系结构与程序优化(编辑修改稿)

高性能计算机的体系结构与程序优化(编辑修改稿)内容摘要：

+2)=A(I+2)*A(I+2) C(I) = 1 / B(I) C(I+1) = 1 / B(I+1) 10 C(I+2) = 1 / B(I+2) • 先展开，再调整顺序 存储器的层次结构 • 弥补 CPU与主存间的速度差异 • 各个层次间的访问速度和容量差别 –寄存器： 32个；几乎不需要时间 –一级 cache： 16KB128KB； 1个时钟周期 –二级 cache： 128KB4MB；几个时钟周期 –本地主存： 64MB1GB；几十个时期周期 –远程主存： 512MB以上；成百上千个周期 –硬盘对换区（虚存）：成千上万个周期 存储层次发挥作用的基本原理 • 程序的访存局部性（ locality） –时间局部性：最近访问的，将来还要访问 –空间局部性：访问了 A，则要访问 A的近邻 • 局部性使快速存储区的内容多次被访问 –比喻： 80%的时间花在 20%的代码上 • 工作集：最近程序集中访问的地址空间 –调整程序结构，使工作集小于 cache容量 寄存器的使用 • 寄存器的使用基本上是可以控制的 –在汇编子程序里完全可以控制 –在 C语言里用 register说明用得最多的变量 • 需要考虑 CPU内通用寄存器和浮点寄存器的数量 –编译程序在生成代码前，会进行寄存器分配 • 程序设计与优化时，可考虑寄存器利用 –最内层循环体不宜过长，寄存器会不够用 –循环展开的次数不能太多 寄存器的使用 • for ( k=0。 k10。 k++) • { • for (j=0。 j1000。 j++) • 执行运算过程 B； • } • 运算过程 B的大小也是我们必须考虑的。 如果 B过大 ，CPU内部寄存器的压力就会很大 ， 如果寄存器的数量不足以保存 B中出现的所有数据 ， 可能会出现颠簸的现象 ， 刚刚从寄存器中换出的数据也许就是下一个需要的数据 ， 还得重新读入寄存器 ， 这对效率显然是有影响的。 解决的办法是将循环体过大的循环拆分成若干循环体较小的循环 ， 这种方法叫做循环分布 ， 循环体拆分的粒度是以寄存器数量的多少为参考的。 寄存器的使用 • 根据运算过程 B的实际情况和并行环境的特点 ， 可以拆分为以下两种形式中的一种。 形式 A： • for(k=0。 k10。 k++) { • for(j=0。 j1000。 j++) • 执行运算过程 B1； • for(j=0。 j1000。 j++) • 执行运算过程 B2； • } 寄存器的使用 • 形式 B： • for(k=0。 k10。 k++){ • for(j=0。 j1000。 j++) • 执行运算过程 B1； • } • for(k=0。 k10。 k++){ • for(j=0。 j1000。 j++) • 执行运算过程 B2； • } • 形式 A比较符合人们的习惯思维方式 ， 形式 B对循环的拆分更彻底 ， 更加有利于并行执行。 高速缓冲存储器 (cache) • 自然地利用局部性，对程序员“透明” –存放最近最常用的数据和指令 • Cache的工作规则 –基本单位：块 (block)、行 (line) –放置策略：直接映射、组相联、全相联 • 衡量 cache效果的主要指标：命中率 –若命中率为 90%, 不命中时需要另花 10个周期 –则平均访存时间为： 1+10%*10 = 2 周期 –即存储系统的速度是 cache速度的 1/2 Cache中块 的放置策略 • Block 12 placed in 8 block cache: –全相联、直接映射、 2路组相联 –组号 = 块号 % 组数 Memory Cache 8路组相联 1路组相联 2路组相联 只有 1个组 共有 8个组 共有 4个组 Cache不命中的三个原因 (3C) • 首次访问 Compulsory Cache中没有这个块，必须从内存取入 – Misses in even an Infinite Cache • 容量不足 Capacity 换出后又被取入 cache – Misses in Fully Associative Size X Cache • 冲突 Conflict 组相联或直接映射 cache中，映射到同一组的内存块数过多，导致某些块换出后又被取入 – Misses in Nway Associative, Size X Cache 调整程序以提高 cache命中率 • 代码（指令） –重新安排程序中不同过程在内存中的位置 –更适合编译程序，在 profile的帮助下做 • 数据：程序设计者大有可为 –数组合并 : 利用块长，改善空间局部性 –循环交换 : 改变嵌套循环中访问内存的次序 –循环合并 : 增强数据的可重用性（时间局部性） –分块 : 集中访问可取入 cache的块状矩阵，避免全行或全列的读写，以增强时间局部性 数组合并的例子 /* Before: 2 sequential arrays */ int val[SIZE]。 int key[SIZE]。 /* After: 1 array of stuctures */ struc。