高性能计算机的 体系结构与程序优化 唐志敏 中国科学院计算技术研究所

提纲 应用编程与体系结构的关系 高性能计算机体系结构概述 CPU内的并行结构（指令级并行） 存储器的层次结构 多体交叉的并行存储系统 分布存储系统中的通信优化

体系结构的位置 体系结构是硬件和系统软件之间的界面 编程模型是应用和计算机系统间的界面 Enable High Performance Support Ease Programming 编程模型是应用和计算机系统间的界面 理想的模型: 应用不必了解具体的结构特征

体系结构的主要研究内容 如何提高性能? 如何支持编程? 先进的工艺技术－－纯粹属于硬件的范围？ 体系结构方面的革新 共享内存 技术方面的缺点需要通过结构来弥补 DRAM慢，SRAM小＝》存储器层次结构 体系结构方面的革新 各个级别上并行性的开发 如何支持编程? 共享内存 承担一些软件较难完成的优化工作 如动态执行, 猜测执行, COMA等

三种类型的体系结构技术 保守的结构 折衷的结构 包揽式的结构 硬件仅提供必需的设施, 如大量的寄存器 高性能能否最终达到, 完全依赖软件 硬件做一些动态的优化, 如高速缓存 软件仍有优化的余地 包揽式的结构 硬件试图做充分的动态优化, 如COMA 认为软件在动态分析和优化方面能力有限

结点内并行：超长指令字结构 芯片面积主要用于功能部件和高速缓存 显式并行指令结构（EPIC） 完全依赖编译程序开发指令级并行性 分支预测, 循环展开, 软件流水, 踪迹调度 指令系统结构不兼容 显式并行指令结构（EPIC） Explicitly Parallel Instruction Computer 128位的Group包括3条指令 设置专门的域指示指令间是否存在依赖关系 可连接多个Group以支持更大范围内的并行

结点内并行：同时多线程结构 由硬件提供快速的上下文切换机制 多个上下文之间的切换机制 第一个多线程系统(Tera)已经问世 引入了更多的指令级和线程级并行性 容忍远程访问延迟和数据依赖的负面影响 多个上下文之间的切换机制 发生事件时切换(有点象进程的切换) 每个时钟周期都切换: 每次取不同线程的指令 多个线程的指令在同一流水线中(无依赖) 第一个多线程系统(Tera)已经问世 多线程同时工作对cache干扰很大

结点内并行 超标量、动态调度、猜测执行 硬件动态地分析指令流，同时执行多条指令 需要发掘指令级并行性的新来源 在分析区间内，指令以数据流的方式执行 弥补编译器在静态分析和调度方面的不足 换代后目标码不重新编译也能获得较好的性能 需要发掘指令级并行性的新来源 精确的动态分支预测，消除分支损耗 设置大量换名寄存器，消除虚假的数据依赖 不等分支完成，就开始执行目标指令（猜测） 同时执行分支的多个目标（多标量）

结点间并行：消息传递系统 Tcomm = Tstartup + Tblock + Ncomm/Bcomm 如何实现与处理能力匹配的通信带宽 通信带宽、通信延迟对应用性能的影响 光互连技术 如何减少通信开销 用户级通信 硬件支持重试、保证通信的可靠性和顺序 如何减少阻塞 自适应路由、优化应用的通信结构

结点间并行：共享存储系统 共享存储的好处 存储一致性模型与实现效率 如何避免、隐藏或容忍远程访问的开销 易于编程、通用性强 与SMP及其应用实现无缝衔接 存储一致性模型与实现效率 松(弱)一致性模型允许多种优化 对系统软件设计或应用程序设计提出新的要求? 如何避免、隐藏或容忍远程访问的开销 Origin2000: 185周期; 未来可能达数百万个周期 缓存、预取、预送、多线程

结点间并行：COMA CC-NUMA的主要问题 COMA中没有物理地址, 数据可动态迁移 主要问题: 不命中时如何快速找到所需数据 数据静态地分配在home结点上 通过远程访问cache存取非本地的数据 数据分配不当会造成大量的数据传输 COMA中没有物理地址, 数据可动态迁移 经过“预热”, 数据将被“吸引”到处理结点附近 主要问题: 不命中时如何快速找到所需数据 全系统的查找需大量时间 ProbOwner目录, Approximate Copyset

存储器的供数率跟得上吗？ CPU消耗数据的速率远大于存储器供数率 已知的解决方案：存储器层次结构 时钟频率增长的速度大于访存时间缩短的速度 同时执行多条指令要求供数率进一步提高 多线程或芯片内多处理器要求访问多组数据 已知的解决方案：存储器层次结构 片内cache的供数率能满足指令级并行的要求? 片内cache的命中率足够高? 为多个线程或处理器提供各自的cache? 如何通过程序或算法的改进增强访存局部性?

性能不仅依赖于结构 性能的提高依赖于体系结构上的革新 实际性能的提高更依赖于体系结构与编译技 术、操作系统、应用算法间的配合与协调 硬件技术的发展对体系结构提出了新的要求 各个层次并行性的开发是新体系结构的主要特征 实际性能的提高更依赖于体系结构与编译技 术、操作系统、应用算法间的配合与协调 Architectural Support for Programming Languages and Operating Systems, Since 1988 未来系统中两大问题的解决也是如此 ①极长的等待时间；②极大的并行度

充分利用处理器内的并行 提高单机性能是提高并行机性能的基础 目前CPU内部常用的并行结构包括： 充分流水、并行工作的条件 指令流水线与运算流水线 多个功能部件并行执行 如：定点运算、存/取、浮点加、浮点乘、… 充分流水、并行工作的条件 指令间没有相关，即相互独立 结构相关：两条指令要用同一个部件 数据相关：一条指令要用另一条指令的结果 控制相关：条件转移指令影响其它指令

发挥CPU内并行性的主要手段 编译程序：静态指令调度 硬件：超标量、动态指令调度 分析程序中的指令流 在不影响结果的前提下，对指令重新排序 缺点：不能获得运行时的动态信息 改进：基于profile的指令调度或优化 硬件：超标量、动态指令调度 由专用硬件检查即将执行的一段指令 挑选出源操作数和功能部件都已齐备的指令 缺点：硬件会变得很复杂、降低时钟频率

指令调度的例子 假设：取数时间较长，后续指令不能立即使用 源程序语句：a = b + c; d = e - f; Slow code: LW Rb,b LW Rc,c ADD Ra,Rb,Rc SW a,Ra LW Re,e LW Rf,f SUB Rd,Re,Rf SW d,Rd Fast code: LW Rb,b LW Rc,c LW Re,e ADD Ra,Rb,Rc LW Rf,f SW a,Ra SUB Rd,Re,Rf SW d,Rd

应用程序员可以做什么？ 仔细地研究编译器的优化功能和选项 充分利用已经优化过的库函数 做一些源程序级的优化 -O2, -O3, -finline-functions, -funroll-loops 充分利用已经优化过的库函数 如BLAS等 如果可能，找或编适合自己需要的高效率库 做一些源程序级的优化 最典型的一种优化：循环展开 为编译程序的优化提供更多的机会

循环展开的例子 展开前的代码 DO 10 I = 1, N 10 Y(I) = A*X(I) + Y(I) 这是一种常见的写法 循环体里包含的运算量较小（1加、1乘） 循环控制意味着转移 如果CPU一拍能做4个浮点运算，这个循环的性能就不高了 展开4次后的代码 DO 10 I = 1，N，4 Y(I)=A*X(I)+Y(I) Y(I+1)=A*X(I+1)+Y(I+1) Y(I+2)=A*X(I+2)+Y(I+2) 10 Y(I+3)=A*X(I+3)+Y(I+3) 暴露出了更多的可同时执行的操作 不好看，但实用

运算顺序的调整 通常的算法设计和程序实现中，人们习惯在需要某数据的地方才计算出该数据的值，紧接着使用该数据。 这是很自然的思维习惯，但对于流水线则会造成麻烦。 两个运算相继进行，但后一个运算需要的操作数还没有被计算出来，只有原地等待，造成了流水线的停滞。

运算顺序的调整 如下例所示： b[0]=a[0]*a[0]; c[0]=1/b[0]; b[1]=a[1]*a[1]; …… 是求一系列数的平方的倒数的操作。虽然因为c[0]紧接着b[0]计算，让计算的内在含义更明显，也更符合通常的思维习惯，但对于流水线来说效率极差。

运算顺序的调整 现在变动如下： b[0]=a[0]*a[0]; b[1]=a[1]*a[1]; …… c[0]=1/b[0]; c[1]=1/b[1]; c[2]=1/b[2]; 调整以后，先是整个的把数组b[]计算出来，然后再计算数组c[]，此时，需要的b[]数组中的数据都已经计算出来了，就不会存在流水线停滞的问题。

更一般的形式 原始循环 优化后的循环 又称为循环拆分 进一步优化 先展开，再调整顺序 DO 10 I = 1, N B(I) = A(I) * A(I) 10 C(I) = 1 / B(I) 优化后的循环 10 B(I) = A(I) * A(I) DO 20 I = 1, N 20 C(I) = 1 / B(I) 又称为循环拆分 进一步优化 DO 10 I = 1, N, 3 B(I) = A(I) * A(I) B(I+1)=A(I+1)*A(I+1) B(I+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：16KB-128KB；1个时钟周期 二级cache：128KB-4MB；几个时钟周期 本地主存：64MB-1GB；几十个时期周期 远程主存：512MB以上；成百上千个周期 硬盘对换区（虚存）：成千上万个周期

存储层次发挥作用的基本原理 程序的访存局部性（locality） 局部性使快速存储区的内容多次被访问 工作集：最近程序集中访问的地址空间 时间局部性：最近访问的，将来还要访问 空间局部性：访问了A，则要访问A的近邻 局部性使快速存储区的内容多次被访问 比喻：80%的时间花在20%的代码上 工作集：最近程序集中访问的地址空间 调整程序结构，使工作集小于cache容量

寄存器的使用 寄存器的使用基本上是可以控制的 程序设计与优化时，可考虑寄存器利用 在汇编子程序里完全可以控制 在C语言里用register说明用得最多的变量 需要考虑CPU内通用寄存器和浮点寄存器的数量 编译程序在生成代码前，会进行寄存器分配 程序设计与优化时，可考虑寄存器利用 最内层循环体不宜过长，寄存器会不够用 循环展开的次数不能太多

寄存器的使用 for ( k=0;k<10;k++) { for (j=0;j<1000;j++) 执行运算过程B； } 运算过程B的大小也是我们必须考虑的。如果B过大，CPU内部寄存器的压力就会很大，如果寄存器的数量不足以保存B中出现的所有数据，可能会出现颠簸的现象，刚刚从寄存器中换出的数据也许就是下一个需要的数据，还得重新读入寄存器，这对效率显然是有影响的。解决的办法是将循环体过大的循环拆分成若干循环体较小的循环，这种方法叫做循环分布，循环体拆分的粒度是以寄存器数量的多少为参考的。

寄存器的使用 根据运算过程B的实际情况和并行环境的特点，可以拆分为以下两种形式中的一种。 形式A： for(k=0;k<10;k++) { for(j=0;j<1000;j++) 执行运算过程B1； 执行运算过程B2； }

寄存器的使用 形式B： for(k=0;k<10;k++){ for(j=0;j<1000;j++) 执行运算过程B1； } 形式A比较符合人们的习惯思维方式，形式B对循环的拆分更彻底，更加有利于并行执行。

高速缓冲存储器(cache) 自然地利用局部性，对程序员“透明” Cache的工作规则 衡量cache效果的主要指标：命中率 存放最近最常用的数据和指令 Cache的工作规则 基本单位：块(block)、行(line) 放置策略：直接映射、组相联、全相联 衡量cache效果的主要指标：命中率 若命中率为90%, 不命中时需要另花10个周期 则平均访存时间为：1+10%*10 = 2 周期 即存储系统的速度是cache速度的1/2

Cache中块的放置策略 Block 12 placed in 8 block cache: 全相联、直接映射、2路组相联 组号 = 块号 % 组数 8路组相联 1路组相联 2路组相联 Cache 只有1个组 共有8个组 共有4个组 Memory

Cache不命中的三个原因(3C) 首次访问Compulsory Cache中没有这个块，必须从内存取入 Misses in even an Infinite Cache 容量不足Capacity 换出后又被取入cache Misses in Fully Associative Size X Cache 冲突Conflict 组相联或直接映射cache中，映射到同一组的内存块数过多，导致某些块换出后又被取入 Misses in N-way Associative, Size X Cache Intuitive Model by Mark Hill

调整程序以提高cache命中率 代码（指令） 数据：程序设计者大有可为 重新安排程序中不同过程在内存中的位置 更适合编译程序，在profile的帮助下做 数据：程序设计者大有可为 数组合并: 利用块长，改善空间局部性 循环交换: 改变嵌套循环中访问内存的次序 循环合并: 增强数据的可重用性（时间局部性） 分块: 集中访问可取入cache的块状矩阵，避免全行或全列的读写，以增强时间局部性

数组合并的例子 Reducing conflicts between val & key; improve spatial locality /* Before: 2 sequential arrays */ int val[SIZE]; int key[SIZE]; /* After: 1 array of stuctures */ struct merge { int val; int key; }; struct merge merged_array[SIZE]; Reducing conflicts between val & key; improve spatial locality

循环交换的例子 将步长为100字的跳跃式访问变为顺序访问，增强了空间局部性 /* Before */ for (k = 0; k < 100; k = k+1) for (j = 0; j < 100; j = j+1) for (i = 0; i < 5000; i = i+1) x[i][j] = 2 * x[i][j]; /* After */ 将步长为100字的跳跃式访问变为顺序访问，增强了空间局部性

循环合并的例子 /* Before */ for (i = 0; i < N; i = i+1) for (j = 0; j < N; j = j+1) a[i][j] = 1/b[i][j] * c[i][j]; d[i][j] = a[i][j] + c[i][j]; /* After */ { a[i][j] = 1/b[i][j] * c[i][j]; d[i][j] = a[i][j] + c[i][j];} 访问a和c的2次不命中降为1次

分块的例子 两个内层循环中: 不命中次数是N及cache大小的函数 分块的思想：计算cache中放得下的 BxB子矩阵 /* Before */ for (i = 0; i < N; i = i+1) for (j = 0; j < N; j = j+1) {r = 0; for (k = 0; k < N; k = k+1){ r = r + y[i][k]*z[k][j];}; x[i][j] = r; }; 两个内层循环中: 读了z[ ]的所有NxN个元素 重复读y[ ]的某一行N次，写x[ ]的某一行1次 不命中次数是N及cache大小的函数 当3 NxNx4 小于cache容量时，没有不命中 分块的思想：计算cache中放得下的 BxB子矩阵

分块的例子 不命中数从 2N3 + N2 降到 2N3/B +N2 但还存在因冲突导致的不命中 /* After */ for (jj = 0; jj < N; jj = jj+B) for (kk = 0; kk < N; kk = kk+B) for (i = 0; i < N; i = i+1) for (j = jj; j < min(jj+B-1,N); j = j+1) {r = 0; for (k = kk; k < min(kk+B-1,N); k = k+1) { r = r + y[i][k]*z[k][j];}; x[i][j] = x[i][j] + r; }; B称为分块因子Blocking Factor 不命中数从 2N3 + N2 降到 2N3/B +N2 但还存在因冲突导致的不命中

减少因分块导致的冲突不命中 需要对分块后形成的子矩阵进行重新布置

分块的性能提高 矩阵乘法：N=500 在i860上 在Pentium 166MMX上 分块前，运行时间为77.00秒 分块后，运行时间为22.41秒，加速比3.44 在Pentium 166MMX上 分块前，运行时间为28.52秒 分块后，运行时间为6.67秒，加速比4.22

多体交叉并行存储系统 提高主存带宽的重要途径 地址分配方式：word interleave 多个独立的存储体，统一编址，同时工作 访问均匀地分布在所有体内时，带宽线性提高 地址分配方式：word interleave 000000 000001 000002 000003 000004 000005 000006 000007 FFFFFF FFFFFE FFFFFD FFFFFC M0 M1 M2 M3

并行存储器中的访问冲突 基本条件：体数不小于访存所需要的时钟周期数，以保证顺序访问时不会有体冲突 体数增大时，冲突的机会会少一些，但成本增加了 体数正好等于访存周期数时，有下面的结论 考虑固定步长的访问序列A, A+S, A+2S, A+3S, ... 若一共有N个存储模块，则该访问序列集中在 若GCD(N, S) = 1, 则冲突访问的概率最小 因为N一般是2的幂次，所以S最好不是2的幂次 N GCD(N, S) 个体内

对数组元素的冲突访问 在C语言中，数组元素按行存放，按列访问时会产生冲突 在FORTRAN中，按列存放，按行访问时会产生冲突 其它导致冲突的情形 矩阵中的一个长方形块 FFT算法中存取步长依次为2i, i = 0, 1, 2, … 减少冲突的方法（与cache优化类似） 循环交换、数组加边

并行处理概述 利用多个部件完成同一个任务 并行处理的好处 并行处理的层次 提高性能：缩短解题时间，扩大解题规模 降低成本：与同样性能的单机相比 容错：更高的可用性 并行处理的层次 处理机内：指令级并行，多功能部件 处理机间：多处理机，多计算机

多机并行的基本形式 按指令流与数据流的数量来划分 按机间的互连方式来划分 按存储器的组织方式来划分 单指令流多数据流（SIMD） 多指令流多数据流（MIMD） 按机间的互连方式来划分 总线结构、交叉开关、网格结构、超立方体 树型结构、星型结构 按存储器的组织方式来划分 集中式存储，通常是为多个处理机共享 分布式存储，通常是各个处理机私有的

两种基本的结构 P1 P1 Pn Pn M1 Mn 互连网络（总线、开关等） 互连网络（总线、开关等） M1 Mn 分布存储的结构 适合任务间并行 共享存储的结构 适合任务间、任务内并行

并行处理的过程：矩阵乘法 A  B = C的过程可分为四个独立的部分： Ai  B = Ci，i = 1, 2, 3, 4 X = A3 C3 A4 C4 A  B = C的过程可分为四个独立的部分： Ai  B = Ci，i = 1, 2, 3, 4 每部分包含的运算可由一台处理机单独完成 在集中存储的系统中，同时访问B会导致冲突 在分布存储的系统中，B的分散存储会导致通信

并行处理的性能 加速比：串行计算时间除以并行计算时间 加速比小于处理单元数目的原因： 极端的情况：并行后的性能比单机还差 存在不可并行成分：Speedup < 1/s 负载不均衡：有些处理机没事做 通信开销：包括传递消息、访存冲突等 同步开销：为了步调一致，必须相互等待 极端的情况：并行后的性能比单机还差 也可能出现超线性的加速比

并行粒度：在哪个级别上并行？ 子任务级的并行（粗粒度） 数据级的并行（中等粒度或细粒度） 例如：方位FFT、距离FFT、距离IFFT、方位IFFT各由一个处理机完成，形成宏观流水 子任务的运算量差别较大时，不易实现负载的平衡 数据级的并行（中等粒度或细粒度） 对问题相关的数据场进行划分，每个处理器负责整个数据场的一小部分 各部分间耦合较多时，对存储器及互连网络的性能要求较高

并行算法设计 并行算法设计的目标 并行化的主要方法：分而治之 开发问题求解过程中的并行性 寻求并行算法与并行结构的最佳匹配 合理地组织并行任务，减少额外的开销 并行化的主要方法：分而治之 根据问题的求解过程，把任务分成若干子任务 根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理 将一个循环分成多个循环并行地执行

并行计算机设计程序的三种方式 串行程序的自动并行化 使用全新的并行语言：函数型、数据流等 串行语言+并行化扩充 用户提供常规的串行程序，编译器完成并行化 由于编译器能力有限，只对部分应用有效 使用全新的并行语言：函数型、数据流等 已有应用程序需要全部改写 新语言的实现效率有待进一步提高 串行语言+并行化扩充 增加支持并行性开发与通信同步的库调用 增加新的语言成分，如数组运算、并行循环等 SPMD (Single Program Multiple Data)编程模式

例子：矩阵乘法（串行） double a[N][N],b[N][N],c[N][N]; for (i=0; i<N; i++) for (j=0; j<N; j++) for (k=0; k<N; k++) c[i][j]+=a[i][k]*b[k][j];

例子：矩阵乘法（并行1） 一开始就有P个并行进程 myid的值为0,1,...,P-1 begin=N*myid/P; end=N*(myid+1)/P; for (i=begin; i<end; i++) for (j=0; j<N; j++) for (k=0; k<N; k++) c[i][j]+=a[i][k]*b[k][j];

例子：矩阵乘法（并行2） 一开始只有一个进程在运行 在main函数内： for (i=0; i<P; i++) fork(subp,N*i/P,N*(i+1)/P) 在subp(int begin, int end)函数内： for (i=begin; i<end; i++) for (j=0; j<N; j++) for (k=0; k<N; k++) c[i][j]+=a[i][k]*b[k][j];

例子：矩阵乘法（并行3） 一开始只有一个进程在运行 forall循环中的所有迭代均可并行执行 forall (i=0; i<N; i++) for (j=0; j<N; j++) for (k=0; k<N; k++) c[i][j]+=a[i][k]*b[k][j]; 程序首先由单个进程运行，遇forall时自动进入多进程运行，出forall后恢复单进程运行。处理机数不显式地给出。