并行处理与体系结构

并行处理与体系结构1哈尔滨工业大学计算机科学与技术学院第3章性能指标和基准程序1系统和应用的基准程序2性能和成本3基本性能指标4并行计算机性能5并行程序性能6可扩展性和加速比分析2哈尔滨工业大学计算机科学与技术学院4并行计算机性能针对一个并行系统，需讨论计算和开销特征一、计算特征下表给出了3种商品化并行计算机系列的性能参数的历史值3哈尔滨工业大学计算机科学与技术学院4哈尔滨工业大学计算机科学与技术学院存储器层次结构：存储器容量存储器时延存储器带宽1996年前后计算机中这3个参数的典型值5哈尔滨工业大学计算机科学与技术学院6哈尔滨工业大学计算机科学与技术学院二、并行性和通信开销

并行程序中的开销可分为3类负载不平衡开销；并行性开销；通信开销(包括同步、通信和聚集)。

T=Tcomp+Tpar+Tinteract7哈尔滨工业大学计算机科学与技术学院说明：有3种类型的并行性操作。它们是并行性开销的来源:进程管理；分组操作进程查询操作8哈尔滨工业大学计算机科学与技术学院通信开销的来源有3种类型的操作同步聚集通信9哈尔滨工业大学计算机科学与技术学院巨大开销:注意有关并行性和通信开销的两个要点：通常比基本计算时间要大得多，在不同系统上变化很大。10哈尔滨工业大学计算机科学与技术学院11哈尔滨工业大学计算机科学与技术学院12哈尔滨工业大学计算机科学与技术学院三、开销定量化1.问题的提出应对计算的并行性和通信开销进行量化。13哈尔滨工业大学计算机科学与技术学院2.开销测量条件进行测量实验的确切条件必须清楚地加以说明。以下是部分列表:所使用的数据结构。所使用的编程语言、库以及编译器选择。一般地，开销测量应以批处理方式进行，都会被执行。14哈尔滨工业大学计算机科学与技术学院所使用的通信硬件和协议。因为在这种方式下大多数生成路径(productionrun)测量挂钟时间或是CPU时间。一般来讲，挂钟时间更有用。15哈尔滨工业大学计算机科学与技术学院3.开销测量方法虽然测量开销粗看起来非常简单，但要获得精确测量结果却是很具挑战性的任务主要的原因有3种16哈尔滨工业大学计算机科学与技术学院乒乓方案：是测量点对点通信常用的方法:结点0执行一个发送操作向结点1发送一个m字节的消息，后者执行一个接收操作收到此消息结点1立即发送相同消息给结点017哈尔滨工业大学计算机科学与技术学院例题：测量时延的乒乓方案：

for(i=0；i<Runs；i++)if(my_node_id==0){/*发送方*/Tmp=Second()；start_time=Second()；向结点1发送一个m字节消息；从结点1接收一个m字节消息；end_time=Second()；18哈尔滨工业大学计算机科学与技术学院timer_overhead=start_time-tmp；total_time=end_time-start_time-timer_overhead；communication_time[i]=total_time／2；}elseif(my_node_id==1){/*接收方*/从结点0接收一个m字节消息；向结点0发送一个m字节消息；}}19哈尔滨工业大学计算机科学与技术学院热土豆(hot_potato)方法(也称为救火队方法)。该方法面向n个结点；方法是个循环的发送接收。

20哈尔滨工业大学计算机科学与技术学院集合通信条件：设分布式存储器多计算机中n个结点中的每一个均执行以下的SPMD程序。使用路障来同步测量进程中的异步操作。21哈尔滨工业大学计算机科学与技术学院for(i=0；i<Runs；i++){

Barriersynchronization；Tmp=Second()；start_time=Second()；for(j=0；j<Iterations；j++)The_collective_routine_being_measured；End_time=Second()；22哈尔滨工业大学计算机科学与技术学院Timer_overhead=start_time-tmp；Total_time=end_time-start_time–timer_overhead；Local_time=total_time/Iterations；Communication_time[i]=maximumOfallnlocaltimevalues；}23哈尔滨工业大学计算机科学与技术学院改用集合操作的通用化乒乓方法：for(i=0；i<Runs；i++){if(my_node_id==0){tmp=Second()；start_time=Second();结点0向所有n个结点广播一个空消息；For(j=0；i<Iterations；j++)24哈尔滨工业大学计算机科学与技术学院thecollective_routine_being_measured；所有结点向结点0完成一个空归约；

if(my_node_id=0){end_time=Second()；timer_overhead=start_time-tmp；Communication_time[i]=end_time-start_time-

timer_overhead}25哈尔滨工业大学计算机科学与技术学院4.开销表达式经测量获得开销数据，有3种表示方法：用表格来表示数据。例如，下表给出了在SP2上运行专有MPL通信库所测得的点对点通信的定时结果。26哈尔滨工业大学计算机科学与技术学院27哈尔滨工业大学计算机科学与技术学院以曲线来表示数据如下图所示。其优点是曲线可示出通信开销增长趋向。

28哈尔滨工业大学计算机科学与技术学院29哈尔滨工业大学计算机科学与技术学院表达式表示例如，将所测得的定时数据用最小二乘法适当地加以拟合。就可将SP2上的点对点通信开销表示成消息长度的线性函数：t=46+0.035mμs如果加以拟合，它与曲线之间的误差是很小的，如上图所表明的那样。30哈尔滨工业大学计算机科学与技术学院5.点对点通信表达式Hockney提出操作通信时间(以μs表示)特征的1个模型，其中的通信开销t(m)是消息长度m(以字节表示)的线性函数：

t(m)=t0+m／r∞式中t0是以μs表示的启动时间，而r∞是渐近带宽，单位MB／s。31哈尔滨工业大学计算机科学与技术学院Hockney还引入了两个附加的参数。半峰值长度记为m1/2字节，是达到半渐近带宽所需的消息长度。特殊性能，记为0MB／s，用来表明短消息带宽。32哈尔滨工业大学计算机科学与技术学院4个参数t0、r∞

、

m1/2、

0MB中的两个是独立的。另两个可用以下关系推得：t0=m1/2

／r∞=1/0其中m1/2是表示系统支持短消息通信好坏程序的参数。

33哈尔滨工业大学计算机科学与技术学院例如：SP2的t(m)=46+0.035m。启动开销为t0=46μs；渐近带宽为：r∞=1／0.035=28.57MB／s，以及半峰值消息长度为：m1/2

=t0×r∞=1314字节。34哈尔滨工业大学计算机科学与技术学院6.集合通信

将式Hockney表达式扩展成如下：通信开销T(m,n)现改为是m和n两者的函数。但启动时延仍只依赖于n。渐近带宽变为r∞(n)。

T(m,n)=t0(n)+m/r∞(n)35哈尔滨工业大学计算机科学与技术学院在将测得的定时数据与不同的t0(n)和r∞(n)形式拟合可推得如表中所示的4个集合操作的公式36哈尔滨工业大学计算机科学与技术学院37哈尔滨工业大学计算机科学与技术学院7.集合计算测量了3种代表性的集合计算操作：路障、归约和扫描。它们拟合曲线开销表达式如下表所示。注意当处理器数超过256时，路障开销为762μs，相当于执行762x266=202,692flop所需的时间。现在可以回答这样问题，是否应使用同步算法?38哈尔滨工业大学计算机科学与技术学院39哈尔滨工业大学计算机科学与技术学院短消息和长消息全交换开销的方法作了比较：在下图中示出了当mn2=16MB(例如，m=1024