《高性能计算机的体系结构与程序优化》由会员分享，可在线阅读，更多相关《高性能计算机的体系结构与程序优化（54页珍藏版）》请在金锄头文库上搜索。
1、Institute of Computing Technology, CAS高性能计算机的高性能计算机的体系结构与程序优化体系结构与程序优化唐志敏中国科学院计算技术研究所提纲提纲应用编程与体系结构的关系高性能计算机体系结构概述CPU内的并行结构（指令级并行）存储器的层次结构多体交叉的并行存储系统分布存储系统中的通信优化体系结构的位置体系结构的位置体系结构是硬件和系统软件之间的界面Enable High PerformanceSupport Ease Programming编程模型是应用和计算机系统间的界面理想的模型: 应用不必了解具体的结构特征体系结构的主要研究内容体系结构的主要研究内容如何提
2、高性能?先进的工艺技术纯粹属于硬件的范围？技术方面的缺点需要通过结构来弥补DRAM慢，SRAM小存储器层次结构体系结构方面的革新各个级别上并行性的开发如何支持编程?共享内存承担一些软件较难完成的优化工作如动态执行, 猜测执行, COMA等三种类型的体系结构技术三种类型的体系结构技术保守的结构硬件仅提供必需的设施, 如大量的寄存器高性能能否最终达到, 完全依赖软件折衷的结构硬件做一些动态的优化, 如高速缓存软件仍有优化的余地包揽式的结构硬件试图做充分的动态优化, 如COMA认为软件在动态分析和优化方面能力有限结点内并行：超长指令字结构结点内并行：超长指令字结构芯片面积主要用于功能部件和高速缓存完
3、全依赖编译程序开发指令级并行性分支预测, 循环展开, 软件流水, 踪迹调度指令系统结构不兼容 显式并行指令结构（EPIC）Explicitly Parallel Instruction Computer 128位的Group包括3条指令设置专门的域指示指令间是否存在依赖关系可连接多个Group以支持更大范围内的并行结点内并行：同时多线程结构结点内并行：同时多线程结构由硬件提供快速的上下文切换机制引入了更多的指令级和线程级并行性容忍远程访问延迟和数据依赖的负面影响多个上下文之间的切换机制发生事件时切换(有点象进程的切换)每个时钟周期都切换: 每次取不同线程的指令多个线程的指令在同一流水线中(无依
4、赖)第一个多线程系统(Tera)已经问世多线程同时工作对cache干扰很大结点内并行结点内并行超标量、动态调度、猜测执行超标量、动态调度、猜测执行硬件动态地分析指令流，同时执行多条指令在分析区间内，指令以数据流的方式执行弥补编译器在静态分析和调度方面的不足换代后目标码不重新编译也能获得较好的性能需要发掘指令级并行性的新来源精确的动态分支预测，消除分支损耗设置大量换名寄存器，消除虚假的数据依赖不等分支完成，就开始执行目标指令（猜测）同时执行分支的多个目标（多标量）结点间并行：消息传递系统结点间并行：消息传递系统Tcomm = Tstartup + Tblock + Ncomm/Bcomm如何实现
5、与处理能力匹配的通信带宽通信带宽、通信延迟对应用性能的影响光互连技术如何减少通信开销用户级通信硬件支持重试、保证通信的可靠性和顺序如何减少阻塞自适应路由、优化应用的通信结构结点间并行：共享存储系统结点间并行：共享存储系统共享存储的好处易于编程、通用性强与SMP及其应用实现无缝衔接存储一致性模型与实现效率松(弱)一致性模型允许多种优化对系统软件设计或应用程序设计提出新的要求?如何避免、隐藏或容忍远程访问的开销Origin2000: 185周期; 未来可能达数百万个周期缓存、预取、预送、多线程结点间并行：结点间并行：COMACOMACC-NUMA的主要问题数据静态地分配在home结点上通过远程访问
6、cache存取非本地的数据数据分配不当会造成大量的数据传输COMA中没有物理地址, 数据可动态迁移经过“预热”, 数据将被“吸引”到处理结点附近主要问题: 不命中时如何快速找到所需数据全系统的查找需大量时间ProbOwner目录, Approximate Copyset存储器的供数率跟得上吗？存储器的供数率跟得上吗？CPU消耗数据的速率远大于存储器供数率时钟频率增长的速度大于访存时间缩短的速度同时执行多条指令要求供数率进一步提高多线程或芯片内多处理器要求访问多组数据已知的解决方案：存储器层次结构片内cache的供数率能满足指令级并行的要求?片内cache的命中率足够高?为多个线程或处理器提供各
7、自的cache?如何通过程序或算法的改进增强访存局部性?性能不仅依赖于结构性能不仅依赖于结构性能的提高依赖于体系结构上的革新硬件技术的发展对体系结构提出了新的要求各个层次并行性的开发是新体系结构的主要特征实际性能的提高更依赖于体系结构与编译技 术、操作系统、应用算法间的配合与协调Architectural Support for Programming Languages and Operating Systems, Since 1988未来系统中两大问题的解决也是如此极长的等待时间；极大的并行度充分利用处理器内的并行提高单机性能是提高并行机性能的基础目前CPU内部常用的并行结构包括：指令流水
8、线与运算流水线多个功能部件并行执行如：定点运算、存/取、浮点加、浮点乘、充分流水、并行工作的条件指令间没有相关，即相互独立结构相关：两条指令要用同一个部件数据相关：一条指令要用另一条指令的结果控制相关：条件转移指令影响其它指令发挥CPU内并行性的主要手段编译程序：静态指令调度分析程序中的指令流在不影响结果的前提下，对指令重新排序缺点：不能获得运行时的动态信息改进：基于profile的指令调度或优化硬件：超标量、动态指令调度由专用硬件检查即将执行的一段指令挑选出源操作数和功能部件都已齐备的指令缺点：硬件会变得很复杂、降低时钟频率假设：取数时间较长，后续指令不能立即使用源程序语句：a = b +
9、c; d = e - f;a, b, c, d ,e, f 都在存储器中. Slow code:LW Rb,bLW Rc,cADD Ra,Rb,RcSW a,Ra LW Re,e LW Rf,fSUB Rd,Re,RfSWd,Rd指令调度的例子Fast code:LW Rb,bLW Rc,cLW Re,e ADD Ra,Rb,RcLW Rf,fSW a,Ra SUB Rd,Re,RfSWd,Rd应用程序员可以做什么？仔细地研究编译器的优化功能和选项-O2, -O3, -finline-functions, -funroll-loops充分利用已经优化过的库函数如BLAS等如果可能，找或编适合自
10、己需要的高效率库做一些源程序级的优化最典型的一种优化：循环展开为编译程序的优化提供更多的机会循环展开的例子展开前的代码DO 10 I = 1, N10 Y(I) = A*X(I) + Y(I)这是一种常见的写法循环体里包含的运算量较小（1加、1乘）循环控制意味着转移如果CPU一拍能做4个浮点运算，这个循环的性能就不高了展开4次后的代码DO 10 I = 1，N，4Y(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)暴露出了更多的可同时执行的操作不好看，但实用运算顺序的调整通常的
11、算法设计和程序实现中，人们习惯在需要某数据的地方才计算出该数据的值，紧接着使用该数据。这是很自然的思维习惯，但对于流水线则会造成麻烦。两个运算相继进行，但后一个运算需要的操作数还没有被计算出来，只有原地等待，造成了流水线的停滞。运算顺序的调整如下例所示：b0=a0*a0;c0=1/b0;b1=a1*a1;c1=1/b1;b2=a2*a2;c2=1/b2;是求一系列数的平方的倒数的操作。虽然因为c0紧接着b0计算，让计算的内在含义更明显，也更符合通常的思维习惯，但对于流水线来说效率极差。运算顺序的调整现在变动如下： b0=a0*a0;b1=a1*a1;b2=a2*a2;c0=1/b0;c1=1/
12、b1;c2=1/b2;调整以后，先是整个的把数组b计算出来，然后再计算数组c，此时，需要的b数组中的数据都已经计算出来了，就不会存在流水线停滞的问题。更一般的形式原始循环DO 10 I = 1, NB(I) = A(I) * A(I)10 C(I) = 1 / B(I)优化后的循环DO 10 I = 1, N10 B(I) = A(I) * A(I)DO 20 I = 1, N20 C(I) = 1 / B(I)又称为循环拆分进一步优化DO 10 I = 1, N, 3B(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)
13、= 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的近邻局部性使快速存储区的内容多
14、次被访问比喻：80%的时间花在20%的代码上工作集：最近程序集中访问的地址空间调整程序结构，使工作集小于cache容量寄存器的使用寄存器的使用基本上是可以控制的在汇编子程序里完全可以控制在C语言里用register说明用得最多的变量需要考虑CPU内通用寄存器和浮点寄存器的数量编译程序在生成代码前，会进行寄存器分配程序设计与优化时，可考虑寄存器利用最内层循环体不宜过长，寄存器会不够用循环展开的次数不能太多寄存器的使用for ( k=0;k10;k+) for (j=0;j1000;j+) 执行运算过程B；运算过程B的大小也是我们必须考虑的。如果B过大，CPU内部寄存器的压力就会很大，如果寄存器的
15、数量不足以保存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+)
16、 执行运算过程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/2Cache中块的放置策略 Block 12 placed i
17、n 8 block cache:全相联、直接映射、2路组相联组号 = 块号 % 组数MemoryCache8路组相联1路组相联2路组相联只有1个组共有8个组共有4个组Cache不命中的三个原因(3C)首次访问Compulsory Cache中没有这个块，必须从内存取入 Misses in even an Infinite Cache容量不足Capacity 换出后又被取入cacheMisses in Fully Associative Size X Cache冲突Conflict 组相联或直接映射cache中，映射到同一组的内存块数过多，导致某些块换出后又被取入 Misses in N-way
18、 Associative, Size X Cache调整程序以提高cache命中率代码（指令）重新安排程序中不同过程在内存中的位置更适合编译程序，在profile的帮助下做数据：程序设计者大有可为数组合并: 利用块长，改善空间局部性循环交换: 改变嵌套循环中访问内存的次序循环合并: 增强数据的可重用性（时间局部性）分块: 集中访问可取入cache的块状矩阵，避免全行或全列的读写，以增强时间局部性数组合并的例子/* Before: 2 sequential arrays */int valSIZE; int keySIZE;/* After: 1 array of stuctures */str
19、uct merge int val;int key;struct merge merged_arraySIZE;Reducing conflicts between val & key; improve spatial locality循环交换的例子/* 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)xij = 2 * xij;/* After */for (k = 0; k 100; k = k+1)for (i = 0; i 5000; i = i+1)f
20、or (j = 0; j 100; j = j+1)xij = 2 * xij;将步长为100字的跳跃式访问变为顺序访问，增强了空间局部性循环合并的例子/* Before */for (i = 0; i N; i = i+1)for (j = 0; j N; j = j+1)aij = 1/bij * cij;for (i = 0; i N; i = i+1)for (j = 0; j N; j = j+1)dij = aij + cij;/* After */for (i = 0; i N; i = i+1)for (j = 0; j N; j = j+1)aij = 1/bij * cij
21、;dij = aij + cij;访问a和c的2次不命中降为1次分块的例子/* 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 + yik*zkj; xij = r;两个内层循环中:读了z 的所有NxN个元素重复读y 的某一行N次，写x 的某一行1次不命中次数是N及cache大小的函数当3 NxNx4 小于cache容量时，没有不命中分块的思想：计算cache中放得下的 BxB子矩阵分块的例子/* After */for (jj = 0; jj N;
22、 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 + yik*zkj; xij = xij + r;B称为分块因子Blocking Factor不命中数从 2N3 + N2 降到 2N3/B +N2但还存在因冲突导致的不命中减少因分块导致的冲突不命中需要对分块后形成的子矩阵进行重新布置分块的性能提高矩阵乘法：N=500在i860上分块前
23、，运行时间为77.00秒分块后，运行时间为22.41秒，加速比3.44在Pentium 166MMX上分块前，运行时间为28.52秒分块后，运行时间为6.67秒，加速比4.22多体交叉并行存储系统提高主存带宽的重要途径多个独立的存储体，统一编址，同时工作访问均匀地分布在所有体内时，带宽线性提高地址分配方式：word interleave000000000001000002000003000004000005000006000007FFFFFFFFFFFEFFFFFDFFFFFCM0M1M2M3并行存储器中的访问冲突基本条件：体数不小于访存所需要的时钟周期数，以保证顺序访问时不会有体冲突体数增大
24、时，冲突的机会会少一些，但成本增加了体数正好等于访存周期数时，有下面的结论考虑固定步长的访问序列A, A+S, A+2S, A+3S, .若一共有N个存储模块，则该访问序列集中在若GCD(N, S) = 1, 则冲突访问的概率最小因为N一般是2的幂次，所以S最好不是2的幂次NGCD(N, S)个体内对数组元素的冲突访问在C语言中，数组元素按行存放，按列访问时会产生冲突在FORTRAN中，按列存放，按行访问时会产生冲突其它导致冲突的情形矩阵中的一个长方形块FFT算法中存取步长依次为2i, i = 0, 1, 2, 减少冲突的方法（与cache优化类似）循环交换、数组加边并行处理概述利用多个部件完
25、成同一个任务并行处理的好处提高性能：缩短解题时间，扩大解题规模降低成本：与同样性能的单机相比容错：更高的可用性并行处理的层次处理机内：指令级并行，多功能部件处理机间：多处理机，多计算机多机并行的基本形式按指令流与数据流的数量来划分单指令流多数据流（SIMD）多指令流多数据流（MIMD）按机间的互连方式来划分总线结构、交叉开关、网格结构、超立方体树型结构、星型结构按存储器的组织方式来划分集中式存储，通常是为多个处理机共享分布式存储，通常是各个处理机私有的两种基本的结构互连网络（总线、开关等）P1PnM1Mn分布存储的结构适合任务间并行互连网络（总线、开关等）P1PnM1Mn共享存储的结构适合任务
26、间、任务内并行并行处理的过程：矩阵乘法A B = C的过程可分为四个独立的部分：Ai B = Ci，i = 1, 2, 3, 4每部分包含的运算可由一台处理机单独完成在集中存储的系统中，同时访问B会导致冲突在分布存储的系统中，B的分散存储会导致通信ABCX=A1A2A3A4C1C2C3C4并行处理的性能加速比：串行计算时间除以并行计算时间加速比小于处理单元数目的原因：存在不可并行成分：Speedup 1/s负载不均衡：有些处理机没事做通信开销：包括传递消息、访存冲突等同步开销：为了步调一致，必须相互等待极端的情况：并行后的性能比单机还差也可能出现超线性的加速比并行粒度：在哪个级别上并行？子任务
27、级的并行（粗粒度）例如：方位FFT、距离FFT、距离IFFT、方位IFFT各由一个处理机完成，形成宏观流水子任务的运算量差别较大时，不易实现负载的平衡数据级的并行（中等粒度或细粒度）对问题相关的数据场进行划分，每个处理器负责整个数据场的一小部分各部分间耦合较多时，对存储器及互连网络的性能要求较高并行算法设计并行算法设计的目标开发问题求解过程中的并行性寻求并行算法与并行结构的最佳匹配合理地组织并行任务，减少额外的开销并行化的主要方法：分而治之根据问题的求解过程，把任务分成若干子任务根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理将一个循环分成多个循环并行地执行并行计算机设计程
28、序的三种方式串行程序的自动并行化用户提供常规的串行程序，编译器完成并行化由于编译器能力有限，只对部分应用有效使用全新的并行语言：函数型、数据流等已有应用程序需要全部改写新语言的实现效率有待进一步提高串行语言+并行化扩充增加支持并行性开发与通信同步的库调用增加新的语言成分，如数组运算、并行循环等SPMD (Single Program Multiple Data)编程模式例子：矩阵乘法（串行）double aNN,bNN,cNN;for (i=0; iN; i+)for (j=0; jN; j+)for (k=0; kN; k+)cij+=aik*bkj;例子：矩阵乘法（并行1）一开始就有P个并
29、行进程myid的值为0,1,.,P-1begin=N*myid/P;end=N*(myid+1)/P;for (i=begin; iend; i+)for (j=0; jN; j+)for (k=0; kN; k+) cij+=aik*bkj;例子：矩阵乘法（并行2）一开始只有一个进程在运行在main函数内：for (i=0; iP; i+)fork(subp,N*i/P,N*(i+1)/P)在subp(int begin, int end)函数内：for (i=begin; iend; i+)for (j=0; jN; j+)for (k=0; kN; k+) cij+=aik*bkj;例子：矩阵乘法（并行3）一开始只有一个进程在运行forall循环中的所有迭代均可并行执行forall (i=0; iN; i+)for (j=0; jN; j+)for (k=0; kN; k+) cij+=aik*bkj;程序首先由单个进程运行，遇forall时自动进入多进程运行，出forall后恢复单进程运行。处理机数不显式地给出。
