高性能计算机的体系结构与程序优化

高性能计算机的

体系结构与程序优化

唐志敏

中国科学院计算技术研究所

InstituteofComputingTechnology,CAS

提纲

•应用编程与体系结构的关系

•高性能计算机体系结构概述

•CPU内的并行结构（指令级并行）

•存储器的层次结构

•多体交叉的并行存储系统

•分布存储系统中的通信优化

体系结构的位置

ProgrammingApplications

Models

SystemSoftware

Architecture

Hardware

•体系结构是硬件和系统软件之间的界面

一EnableHighPerformance

一SupportEaseProgramming

•编程模型是应用和计算机系统间的界面

-理想的模型:应用不必了解具体的结构特征

体系结构的主要研究内容

•如何提高性能？

-先进的工艺技术一一纯粹属于硬件的范围？

•技术方面的缺点需要通过结构来弥补

•DRAM慢，SRAIVH'=》存储器层次结构

-体系结构方面的革新

•各个级别上并行性的开发

•如何支持编程？

—共学内存

-承担一些软件较难完成的优化工作

•如动态执行,猜测执行，COMA等

三种类型的体系结构技术

•保守的结构

-硬件仅提供必需的设施,如大量的寄存器

-高性能能否最终达到，完全依赖软件

•折衷的结构

-硬件做一些动态的优化,如高速缓存

-软件仍有优化的余地

•包揽式的结构

-硬件试图做充分的动态优化，如COMA

-认为软件在动态分析和优化方面能力有限

结点内并行：超长指令字结构

•芯片面积主要用于功能部件和高速缓存

-完全依赖编译程序开发指令级并行性

•分支预测，循环展开，软件流水，踪迹调度

-指令系统结构不兼容

•显式并行指令结构（EPIC）

-ExplicitlyParallelInstructionComputer

-128位的Group包括3条指令

-设置专门的域指示指令间是否存在依赖关系

-可连接多个Group以支持更大范围内的并行

结点内并行：同时多线程结构

•由硬件提供快速的上下文切换机制

-引入了更多的指令级和线程级并行性

-容忍远程访问延迟和数据依赖的负面影响

•多个上下文之间的切换机制

-发生事件时切换（有点象进程的切换）

-每个时钟周期都切换:每次取不同线程的指令

•多个线程的指令在同一流水线中（无依赖）

•第一个多线程系统（Tera）已经问世

-多线程同时工作对cache干扰很大

结点内并行

超标量、动态调度、猜测执行

•硬件动态地分析指令流，同时执行多条指令

-在分析区间内，指令以数据流的方式执行

-弥补编译器在静态分析和调度方面的不足

-换代后目标码不重新编译也能获得较好的性能

•需要发掘指令级并行性的新来源

-精确的动态分支预测，消除分支损耗

-设置大量换名寄存器，消除虚假的数据依赖

-不等分支完成，就开始执行目标指令（猜测）

-同时执行分支的多个目标（多标量）

结点间并行：消息传递系统

•Tcomm-"^"startup+‘block+^comm^comm

•如何实现与处理能力匹配的通信带宽

-通信带宽、通信延迟对应用性能的影响

-光互连技术

•如何减少通信开销

-用户级通信

-硬件支持重试、保证通信的可靠性和顺序

,如何减少阻塞

-自适应路由、优化应用的通信结构

结点间并行：共享存储系统

•共享存储的好处

-易于编程、通用性强

-与SMP及其应用实现无缝衔接

•存储一致性模型与实现效率

-松（弱）一致性模型允许多种优化

-对系统软件设计或应用程序设计提出新的要求？

•如何避免、隐藏或容忍远程访问的开销

-0rigin2000:185周期；未来可能达数百万个周期

-缓存、预取、预送、多线程

结点间并行：COMA

•CC-NUMA的主要问题

-数据静态地分配在home结点上

-通过远程访问cache存取非本地的数据

-数据分配不当会造成大量的数据传输

•COMA中没有物理地址，数据可动态迁移

-经过“预热”，数据将被“吸引”到处理结点附

近

•主要问题：不命中时如何快速找到所需数据

-全系统的查找需大量时间

存储器的供数率跟得上吗?

•CPU消耗数据的速率远大于存储器供数率

-时钟频率增长的速度大于访存时间缩短的速度

-同时执行多条指令要求供数率进一步提高

-多线程或芯片内多处理器要求访问多组数据

­已知的解决方案：存储器层次结构

-片内cache的供数率能满足指令级并行的要求?

一片内cache的命中率足够高？

-为多个线程或处理器提供各自的cache?

-如何通过程序或算法的改进增强访存局部性？

性能不仅依赖于结构

•性能的提高依赖于体系结构上的革新

-硬件技术的发展对体系结构提出了新的要求

-各个层次并行性的开发是新体系结构的主要特征

•实际性能的提高更依赖于体系结构与编译技

术、操作系统、应用算法间的配合与协调

一ArchitecturalSupportforProgramming

LanguagesandOperatingSystems,Since1988

・未来系统中两大问题的解决也是如此

-①极长的等待时间；②极大的并行度

充分利用处理器内的并行

•提高单机性能是提高并行机性能的基础

•目前CPU内部常用的并行结构包括：

-指令流水线与运算流水线

-多个功能部件并行执行

•如：定点运算、存/取、浮点加、浮点乘、…

­充分流水、并行工作的条件

-指令间没有相关，即相互独立

-结构相关：两条指令要用同一个部件

-数据相关：一条指令要用另一条指令的结果

-控制相关：条件转移指令影响其它指令

发挥CPU内并行性的主要手段

•编译程序：静态指令调度

-分析程序中的指令流

-在不影响结果的前提下，对指令重新排序

-缺点：不能获得运行时的动态信息

-改进：基于profile的指令调度或优化

­硬件：超标量、动态指令调度

-由专用硬件检查即将执行的一段指令

-挑选出源操作数和功能部件都已齐备的指令

-缺点：硬件会变得很复杂、降低时钟频率

指令调度的例子

假设：取数时间较长，后续指令不能立即使用

源程序语句：a=b+c;d=e-f;

a,b,c,d,e,f都在存储器中.

Slowcode:

LWRb,bLWRb,b

LWRc,cLWRc,c

ADDRa,Rb,RcLWRe,e

SWa,Ra^^ADDRa,Rb,Rc

LWLWRf,f

LWRf,fSWa,Ra

SUBRd,Re,RfSUBRd,Re,Rf

SWd,RdSWd,Rd

应用程序员可以做什么？

•仔细地研究编译器的优化功能和选项

--02,-03,-finline-functions,-funroll-loops

•充分利用已经优化过的库函数

-如BLAS等

-如果可能，找或编适合自己需要的高效率库

•做一些源程序级的优化

-最典型的一种优化：循环展开

-为编译程序的优化提供更多的机会

循环展开的例子

•展开前的代码•展开4次后的代码

DO10I=1,NDO10I=1,N,4

10Y(l)=A*X(I)+Y(l)Y(I)=A*X(I)+Y(I)

•这是一种常见的写法Y(I+1)=A*X(I+1)+Y(I+1)

•循环体里包含的运算Y(l+2)=A*X(l+2)+Y(l+2)

量较小(1加、1乘)10Y(l+3)=A*X(l+3)+Y(l+3)

•循环控制意味着转移•暴露出了更多的可同时执行

•如果CPU一拍能做4的操作

个浮点运算，这个循­不好看，但实用

环的性能就不高了

运算顺序的调整

•通常的算法设计和程序实现中，人们习

惯在需要某数据的地方才计算出该数据

的值，紧接着使用该数据。

•这是很自然的思维习惯，但对于流水线

则会造成麻烦。

•两个运算相继进行，但后一个运算需要

的操作数还没有被计算出来，只有原地

等待，造成了流水线的停滞。

运算顺序的调整

如下例所示：

可。]二矶。「矶。];

c[0]=1/b[0];

b[1]=a[1]*a[1];

c[1]=1/b[1];

仇2]二矶2]*矶2];

c[2]=1/b[2];

是求一系列数的平方的倒数的操作。虽然因为c[0]

紧接着可0]计算，让计算的内在含义更明显，也更

符合通常的思维习惯，但对于流水线来说效率极差。

运算顺序的调整

现在变动如下:

可0]二矶0「矶0]；调整以后，先是整个的把

b[1]=a[1]*a[1];数组制计算出来，然后再

计算数组c[],此时，需要

仇2]二矶2]*矶2];

的b口数组中的数据都已经

计算出来了，就不会存在

c[0]=1/b[0];流水线停滞的问题。

c[1]=1/b[1];

c[2]=1/b[2];

更一般的形式

­原始循环•进一步优化

DO10I=1,NDO10I=1,N,3

B(l)=A(l)*A(l)B(l)=A(l)*A(l)

10C(l)=1/B(l)B(I+1)=A(I+1)*A(I+1)

•优化后的循环B(l+2)=A(l+2)*A(l+2)

DO10I=1,NC(l)=1/B(l)

10B(l)=A(l)*A(l)C(l+1)=1/B(l+1)

DO20I=1,N10C(l+2)=1/B(l+2)

20C(l)=1/B(l)•先展开，再调整顺序

•又称为循环拆分

存储器的层次结构

•弥补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++){

・forQ=0;j<1000;j++)

•执行运算过程B1；

•for(j=0;j<1000;j++)

•执行运算过程B2；

}

寄存器的使用

•形式B：

•for(k=0;k<10;k++){

•forG=0;j<1000;j++)

•执行运算过程B1；

•)

•for(k=0;k<10;k++){

•forG=0;j<1000;j++)

•执行运算过程B2；

•)

•形式A比较符合人们的习惯思维方式，形式B对

循环的拆分更彻底，更加有利于并行执行。

高速缓冲存储器(cache)

•自然地利用局部性，对程序员“透明”

-存放最近最常用的数据和指令

•Cache的工作规则

-基本单位：块(block)、行(line)

-放置策略：直接映射、组相联、全相联

•衡量cache效果的主要指标：命中率

一若命中率为90%,不命中时需要另花10个周期

一则平均访存时间为：1+10%*10=2周期

-即存储系统的速度是cache速度的1/2

Cache中块的放置策略

•Block12placedin8blockcache:

-全相联、直接映射、2路组相联

—组号二块号％组数

Memory

Cache不命中的三个原因（3C）

•首次访问CompulsoryCache中没有这个块,

必须从内存取入

一MissesinevenanInfiniteCache

•容量不足Capacity换出后又被取入cache

一MissesinFullyAssociativeSizeXCache

•冲突Conflict组相联或直接映射cache中,

映射到同一组的内存块数过多，导致某些

块换出后又被取入

-MissesinN-wayAssociative,SizeXCache

调整程序以提高cache命中率

•代码（指令）

-重新安排程序中不同过程在内存中的位置

-更适合编译程序，在pro巾Ie的帮助下做

•数据：程序设计者大有可为

-敦组合并利用块长，改善空间局部性

-循环交换:改变嵌套循环中访问内存的次序

-循环合分:增强数据的可重用性（时间局部性）

-分块:集中访问可取入cache的块状矩阵，避免全

行或全列的读写，以增强时间局部性

数组合并的例子

/*Before:2sequentialarrays*/

intval[SIZE];intkey[SIZE];

/*After:1arrayofstuctures*/

structmerge{

intval;

intkey;

）；

structmergemerged_array[SIZE];

Reducingconflictsbetweenval&key;

improvespatiallocality

循环交换的例子

/*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*/

for(k=0;k<100;k=k+1)

Tgr(i=0;i<5000;i=i+1)

for(j=0;j<100;j=j+1)

x[i][j]=2*x[i][j];

将步长为100字的跳跃式访问变为顺序访问,

增强了空间局部性

循环合并的例子

/*Before*/

for(i=0;i<N;i=i+1)

for(j=0;j<N;j=j+1)

a[i][j]=l/b[i][j]•c[i][j];

for(i=0;i<N;i=i+1)

for(j=0;j<N;j=j+1)

d[i][j]=aji][j]_+c[i][j];

/*After*/

for(i=0;i<N;i=i+1)

for(j=0;j<N;j=j+1)

{[j]=★^£11111；

d[i][j]=[j]+[j];}

访问a和C的2次不命中降为1次

分块的例子

/*Before*/

for(i=0;i<N;i=i+1)

for(j=0;j<N;j=j+1)

{r=0;

for(=0;k<N;k=k+1){

r=r+y[i][]*z[][j];};

x[i][j]=r;

)；

•两个内层循环中：

—读了z□的所有NxN个元素

-重复读y□的某一行N次，写x□的某一行1次

•不命中次数是N及cache大小的函数□

-当3NxNx4小于cache容量时，没有不命中

•分块的思想：计算cache中放得下的BxB子矩阵

分块的例子

/*After*/

for(jj=0;jj<N;jj=jj+B)

for(=0;<N;=+B)

for(=0;i<N;i=i+1)

for(j=jj;j<min(jj+B-1AN);j=j+1)

{r=0;

for(=;<min(+B-1,N);=+1)

{

r=r+y[][k]*z[k][j];};

x[][j]=x[][j]+r;

)；

B称为分块因子BlockingFactor

・不命中数从2N3+N2降至ij2N3/B+N2

•但还存在因冲突导致的不命中

减少因分块导致的冲突不命中

BlockingFactor

•需要对分块后形成的子矩阵进行重新布置

分块的性能提高

•矩阵乘法：N=500

・在i860上

-分块前，运行时间为77.00秒

-分块后，运行时间为22.41秒，加速比3.44

•在Pentium166MMX±

-分块前，运行时间为28.52秒

-分块后，运行时间为6.67秒，加速比4.22

多体交叉并行存储系统

•提高主存带宽的重要途径

-多个独立的存储体，统一编址，同时工作

-访问均匀地分布在所有体内时，带宽线性提高

•地址分配方式：wordinterleave

并行存储器中的访问冲突

•基本条件：体数不小于访存所需要的时钟周期数，

以保证顺序访问时不会有体冲突

・体数增大时，冲突的机会会少一些，但成本增加了

•体数正好等于访存周期数时，有下面的结论

•考虑固定步长的访问序列A,A+S,A+2S,A+3S,...

•若一共有N个存储模块，则该访问序列集中在

----------个体内

GCD(N,S)

•若GCD(N,S)=1,则冲突访问的概率最小

•因为N一般是2的累次，所以S最好不是2的事次

对数组元素的冲突访问

•在C语言中，数组元素按行存放，按列访

问时会产生冲突

•在FORTRAN中，按列存放，按行访问

时会产生冲突

•其它导致冲突的情形

-矩阵中的一个长方形块

-FFT算法中存取步长依次为21i=0,1,2,・・.

•减少冲突的方法（与cache优化类似）

-循环交换、数组加边

并行处理才既述

•利用多个部件完成同一个任务

­并行处理的好处

-提高性能：缩短解题时间，扩大解题规模

-降低成本：与同样性能的单机相比

-容错：更高的可用性

­并行处理的层次

-处理机内：指令级并行，多功能部件

-处理机间：多处理机，多计算机

多机并行的基本形式

•按指令流与数据流的数量来划分

-单指令流多数据流（SIMD）

-多指令流多数据流（MIMD）

•按机间的互连方式来划分

-总线结构、交叉开关、网格结构、超立方体

-树型结构、星型结构

•按存储器的组织方式来划分

-集中式存储，通常是为多个处理机共享

-分布式存储，通常是各个处理机私有的

两种基本的结构

分布存储的结构共享存储的结构

适合任务间并行适合任务间、任务内并行

并行处理的过程：矩阵乘法

B

•AxB=C的过程可分为四个独立的部分：

AixB=Ci,i=1,2,3,4

•每部分包含的运算可由一台处理机单独完成

•在集中存储的系统中，同时访问B会导致冲突

•在分布存储的系统中，B的分散存储会导致通信

并行处理的性能

­加速比：串行计算时间除以并行计算时间

•加速比小于处理单元数目的原因：

-存在不可并行成分：Speedup<1/s

-负载不均衡：有些处理机没事做

-通信开销：包括传递消息、访存冲突等

-同步开销：为了步调一致，必须相互等待

•极端的情况：并行后的性能比单机还差

•也可能出现超线性的加速比

并行粒度：在哪个级别上并行?

•子任务级的并行（粗粒度）

-例如：方位FFT、距离FFT、距离IFFT、方

位IFFT各由一个处理机完成，形成宏观流水

-子任务的运算量差别较大时，不易实现负载

的平衡

•数据级的并行（中等粒度或细粒度）

-对问题相关的数据场进行划分，每个处理器

负责整个数据场的一小部分

-各部分间耦合较多时，对存储器及互连网络

的性能要求较高

并行算法设计

・并行算法设计的目标

-开发问题求解过程中的并行性

-寻求并行算法与并行结构的最佳匹配

-合理地组织并行任务，减少额外的开销

­并行化的主要方法：