IA机群节点内并行编程模式性能分析
【网学提醒】：本文主要为网上学习者提供IA机群节点内并行编程模式性能分析，希望对需要IA机群节点内并行编程模式性能分析网友有所帮助，学习一下吧!
资料包括： 论文(6页5135字) 图纸
说明：
摘要：本文分析了IA机群节点内并行应用性能的影响因素，深入研究编程模式对性能影响的机理，并指出Cache命中率是最显著的影响因素。
关键字：IA 机群 MPI OpenMP Cache
Performance Analysis of Parallel Programming Models
for the Intra-node of IA Cluster
Cao Zhennan1 Feng Shengzhong2 Wang Qin1
1 University of Science and Technology Beijing, BeiJing
2 Institute of Computing Technology, Chinese Academy of Sciences, BeiJing
E-mail：czn@ncic.ac.cn
Abstract: In this paper, we study the factors that affect the performance of parallel programming applications in the intra-nodes of IA cluster and investigate the mechanism of how parallel programming models affect the performance. We draw the conclusion that the rate of Cache hits is a vital element.
Key Words：IA Cluster MPI OpenMP Cache
1 引言
近年来，Intel架构Linux机群系统(IA机群)以其廉价、开放、高效等优点发展极为迅速。在TOP 500排名中，三年前IA机群只有2套，但在2003年6月达到119套，且在前10名中占据三席，其比例还在迅速扩大。世界各大厂商纷纷把目光转向IA架构，研究相关配套产品。IA机群与传统的RISC架构的UNIX机群系统在体系结构、操作系统等方面有不小的差异。目前，人们对于如何在IA架构Linux机群系统上开发高效的并行程序研究较少，了解的还不是很透彻。
IA机群节点一般采用两个CPU的SMP，可以采用共享存储和消息传递这两种编程模式。本文比较和分析IA机群节点内两种常用并行编程模式性能的影响因素，并以高性能计算中较常用的矩阵乘作为基准测试程序展开测试。得出结论：大部分应用程序在IA机群上，采用消息传递编程模式的性能优于采用混合编程模式的性能，Cache命中率下降是导致混合模式性能较差的最主要原因。
2 编程模式及其性能影响机理
2.1 两种常用的并行编程模式
在机群系统上，目前广泛使用的并行编程模型主要有两类，消息传递程序设计模式(如：MPI、PVM)和消息传递、共享存储混合编程模式(如：MPI＋OpenMP)。对于单个节点，混合编程模式等同于共享存储编程模式。
消息传递编程模式的两种广泛使用的标准库PVM和MPI使消息传递程序大大地增强了可移植性。其中MPI是目前最重要的并行编程工具，它具有移植性好、功能强大、效率高等优点，而且有多种不同的免费、高效、实用的实现版本。消息传递程序不仅可以执行在共享存储的多处理机上，而且可以执行在分布存储的多计算机上。但消息传递程序编程相对比较复杂，尤其对于一些不规则并行程序来说，消息传递模型很难描述所需要的交互。
混合编程模式是在节点内采用共享存储程序设计，节点间采用消息传递程序设计。对于单个节点，混合编程模式等同于共享存储编程模式。混合编程模式适用于分布存储的多计算机系统。共享存储编程模式主要适用于共享存储的多处理机。它比消息传递编程更加容易，而且它对于开发不规则并行程序有优越之处。但是，基于共享存储程序模型的并行编程目前没有统一的标准，程序可移植性较差，不适用于分布存储的多计算机系统。OpenMP是共享存储程序设计中比较常用的一种标准。
2.2 Linux下Threads库的实现原理
在共享存储编程模式中，OpenMP在Linux系统下是利用Linuxthreads库实现的。Linux的内核线程和其它操作系统的内核实现不同。Linux内核本身并不涉及到线程处理，而是纯粹以进程为处理器调度单位。Linux提供了Linuxthreads库，它实现了符合POSIX 1003.1c标准的多线程支持，而且是内核级方式。Linuxthreads中的每个线程实际上仍然是一个单独的进程，但该进程却具有和线程一样的轻负载特性。
Linux系统中的内核级线程在表示格式、管理、调度等方面与进程没有严格的区分，都当作进程来统一对待，在内核中统称为task。控制结构都采用task_struct的结构体来描述，在系统中都放在统一的队列当中，都按照进程的模式来统一调度。Linux系统级线程和进程的区别主要在于资源管理方面，子进程与父进程基本不共享任何内容，但线程可以共享父进程的部分资源。派生新的进程使用函数fork()，而派生新的线程使用函数clone()。Linux中clone()和fork()在核心都是通过do_fork()函数实现的，只是根据clone_flag的不同而决定是共享还是复制父进程的共享存储空间、文件描述表、文件系统信息、信号控制表和进程号。
2.3 编程模式对性能的影响机理
消息传递编程模式和混合编程模式这两者的主要区别在于节点内部的实现方式。消息传递模式在节点内部是采用多进程方式实现，进程间通讯采用消息传递的方式；而后者在节点内部采用多线程的方式实现，线程间的通讯是通过共享内存地址空间的方式实现的。这两种实现方式对应用程序的性能各有利弊。
混合编程模式采用多线程的实现方式带来以下几个优势：1）线程之间是共享内存地址空间的，这样就省去了消息传递模式下，节点内实体之间数据通讯和同步的过程；2）线程是轻量级进程，具有轻负载的特性；3）整个系统中的进程数量减少了(一般来说一个节点只有一个进程)，使得节点间的通讯次数减少，参与通讯的进程数也减少，尤其可以提高全局通讯的性能。其中，1)和2)主要涉及节点内的性能，3)主要涉及节点间的性能。混合编程模式带来的好处很明显，使大家都觉得其性能肯定优于纯消息传递模式。但在实际中，其性能往往没有想象的那么好，而且有些情况下还不如纯消息传递模式，特别在Linux系统中优势更是不明显。
混合编程模式采用多线程的实现方式具有上述优势的同时，也不可避免的存在一些弊端，这些同时也是消息传递模式的优势。1）采用多线程的实现方式会带来一些额外的开销，如线程的创建和消亡、线程之间的同步、循环调度等等；2）采用共享存储方式虽然可以减少节点内部实体间的通讯，但却使得Cache命中率大为降低，这对于计算密集型的应用程序来说是很致命的；3）应用程序中总有一些临界区是无法采用多线程的方式实现；4）内存和CPU之间的带宽会限制多线程程序的性能；5）在Linux系统下，线程和进程并没有严格意义上的区分，这导致在Linux下并没有充分体现线程是轻量级进程这一优势，反而带来了一些其他的开销。这几点主要涉及节点内的性能，其中5)主要针IA架构系统。
在以下部分中，我们以矩阵乘作为基准测试程序，分别对混合模式性能影响因子和操作系统对性能的影响作详细的分析。
3 性能测试与分析
3．1 实验环境
本文中采用的实验平台是IA架构Linux机群系统的曙光4000L超级计算机(以下简称D4000L)和RISC架构UNIX机群系统的曙光3000超级计算机(以下简称D3000)。D4000L的每个节点采用两个Intel Xeon 2.4G处理器和1G内存，每个处理器上有512K二级Cache，操作系统为Redhat Linux 7.3。D3000的每个节点采用4个375MHz Power3 RS64处理器和3G内存，每个处理器上有4M二级Cache，操作系统为AIX 4.3.3。在消息传递编程模式中，比较有代表性的规范是MPI(Message Passing Interface)，本文采用的是MPICH 1.2.3。混合编程模式使用的是MPI＋OpenMP的方式，即在节点内采用OpenMP实现，节点间通过MPI实现。
矩阵乘是高性能计算中较常用的运算之一，本文采用矩阵乘作为基准测试程序。矩阵采用带状划分方法，如图1所示。矩阵中元素为32位浮点数，主要测试32位浮点运算性能。本文中采用两种基准测试程序：不分块矩阵乘(NBMM)和分块矩阵乘(BMM)。NBMM是指在每一带状块中直接采用三重循环矩阵乘法；BMM是指在每一带状块中在细分为小块，在每一小块内采用三重循环矩阵乘法。为了具有可比性，矩阵的分块大小一律为25×25，这一分块大小对于实验中各个大小的矩阵规模的性能都是比较好的。
IA 机群 MPI OpenMP Cache
目录：
1 引言
2 编程模式及其性能影响机理
3 性能测试与分析
4 结束语
参考文献：
陈国良.并行计算－结构,算法,编程.北京.高等教育出版社.1999.
Hwang K, Xu Z. Scalable Parallel Computing: Technology, Architecture, Programming. WCB/McGraw-Hill Companies. 1998.
F. Cappelo, O. Richard, D. Etiemble. Investigating the Performance of Two Programming Models for Clusters of SMP PCs. In Proc. of the 6th IEEE Symposium On High-Performance Computer Architecture(HPCA-6). January 2000.
F. Cappelo, D. Etiemble. MPI versus MPI+OpenMP on the IBM SP for the NAS Benchmarks. In Proc. Supercomputing 2000(SC2000). November 2000.
H. Shan, J.P.Singh, R. Biswas. Message Passing Vs. Shared Address Space on Cluster of SMPs. In Proc. of the 15th International Parallel and Distributed Processing Symposium(IPDPS 2001). April 2001.
资料包括： 论文(6页5135字) 图纸
说明：
摘要：本文分析了IA机群节点内并行应用性能的影响因素，深入研究编程模式对性能影响的机理，并指出Cache命中率是最显著的影响因素。
关键字：IA 机群 MPI OpenMP Cache
Performance Analysis of Parallel Programming Models
for the Intra-node of IA Cluster
Cao Zhennan1 Feng Shengzhong2 Wang Qin1
1 University of Science and Technology Beijing, BeiJing
2 Institute of Computing Technology, Chinese Academy of Sciences, BeiJing
E-mail：czn@ncic.ac.cn
Abstract: In this paper, we study the factors that affect the performance of parallel programming applications in the intra-nodes of IA cluster and investigate the mechanism of how parallel programming models affect the performance. We draw the conclusion that the rate of Cache hits is a vital element.
Key Words：IA Cluster MPI OpenMP Cache
1 引言
近年来，Intel架构Linux机群系统(IA机群)以其廉价、开放、高效等优点发展极为迅速。在TOP 500排名中，三年前IA机群只有2套，但在2003年6月达到119套，且在前10名中占据三席，其比例还在迅速扩大。世界各大厂商纷纷把目光转向IA架构，研究相关配套产品。IA机群与传统的RISC架构的UNIX机群系统在体系结构、操作系统等方面有不小的差异。目前，人们对于如何在IA架构Linux机群系统上开发高效的并行程序研究较少，了解的还不是很透彻。
IA机群节点一般采用两个CPU的SMP，可以采用共享存储和消息传递这两种编程模式。本文比较和分析IA机群节点内两种常用并行编程模式性能的影响因素，并以高性能计算中较常用的矩阵乘作为基准测试程序展开测试。得出结论：大部分应用程序在IA机群上，采用消息传递编程模式的性能优于采用混合编程模式的性能，Cache命中率下降是导致混合模式性能较差的最主要原因。
2 编程模式及其性能影响机理
2.1 两种常用的并行编程模式
在机群系统上，目前广泛使用的并行编程模型主要有两类，消息传递程序设计模式(如：MPI、PVM)和消息传递、共享存储混合编程模式(如：MPI＋OpenMP)。对于单个节点，混合编程模式等同于共享存储编程模式。
消息传递编程模式的两种广泛使用的标准库PVM和MPI使消息传递程序大大地增强了可移植性。其中MPI是目前最重要的并行编程工具，它具有移植性好、功能强大、效率高等优点，而且有多种不同的免费、高效、实用的实现版本。消息传递程序不仅可以执行在共享存储的多处理机上，而且可以执行在分布存储的多计算机上。但消息传递程序编程相对比较复杂，尤其对于一些不规则并行程序来说，消息传递模型很难描述所需要的交互。
混合编程模式是在节点内采用共享存储程序设计，节点间采用消息传递程序设计。对于单个节点，混合编程模式等同于共享存储编程模式。混合编程模式适用于分布存储的多计算机系统。共享存储编程模式主要适用于共享存储的多处理机。它比消息传递编程更加容易，而且它对于开发不规则并行程序有优越之处。但是，基于共享存储程序模型的并行编程目前没有统一的标准，程序可移植性较差，不适用于分布存储的多计算机系统。OpenMP是共享存储程序设计中比较常用的一种标准。
2.2 Linux下Threads库的实现原理
在共享存储编程模式中，OpenMP在Linux系统下是利用Linuxthreads库实现的。Linux的内核线程和其它操作系统的内核实现不同。Linux内核本身并不涉及到线程处理，而是纯粹以进程为处理器调度单位。Linux提供了Linuxthreads库，它实现了符合POSIX 1003.1c标准的多线程支持，而且是内核级方式。Linuxthreads中的每个线程实际上仍然是一个单独的进程，但该进程却具有和线程一样的轻负载特性。
Linux系统中的内核级线程在表示格式、管理、调度等方面与进程没有严格的区分，都当作进程来统一对待，在内核中统称为task。控制结构都采用task_struct的结构体来描述，在系统中都放在统一的队列当中，都按照进程的模式来统一调度。Linux系统级线程和进程的区别主要在于资源管理方面，子进程与父进程基本不共享任何内容，但线程可以共享父进程的部分资源。派生新的进程使用函数fork()，而派生新的线程使用函数clone()。Linux中clone()和fork()在核心都是通过do_fork()函数实现的，只是根据clone_flag的不同而决定是共享还是复制父进程的共享存储空间、文件描述表、文件系统信息、信号控制表和进程号。
2.3 编程模式对性能的影响机理
消息传递编程模式和混合编程模式这两者的主要区别在于节点内部的实现方式。消息传递模式在节点内部是采用多进程方式实现，进程间通讯采用消息传递的方式；而后者在节点内部采用多线程的方式实现，线程间的通讯是通过共享内存地址空间的方式实现的。这两种实现方式对应用程序的性能各有利弊。
混合编程模式采用多线程的实现方式带来以下几个优势：1）线程之间是共享内存地址空间的，这样就省去了消息传递模式下，节点内实体之间数据通讯和同步的过程；2）线程是轻量级进程，具有轻负载的特性；3）整个系统中的进程数量减少了(一般来说一个节点只有一个进程)，使得节点间的通讯次数减少，参与通讯的进程数也减少，尤其可以提高全局通讯的性能。其中，1)和2)主要涉及节点内的性能，3)主要涉及节点间的性能。混合编程模式带来的好处很明显，使大家都觉得其性能肯定优于纯消息传递模式。但在实际中，其性能往往没有想象的那么好，而且有些情况下还不如纯消息传递模式，特别在Linux系统中优势更是不明显。
混合编程模式采用多线程的实现方式具有上述优势的同时，也不可避免的存在一些弊端，这些同时也是消息传递模式的优势。1）采用多线程的实现方式会带来一些额外的开销，如线程的创建和消亡、线程之间的同步、循环调度等等；2）采用共享存储方式虽然可以减少节点内部实体间的通讯，但却使得Cache命中率大为降低，这对于计算密集型的应用程序来说是很致命的；3）应用程序中总有一些临界区是无法采用多线程的方式实现；4）内存和CPU之间的带宽会限制多线程程序的性能；5）在Linux系统下，线程和进程并没有严格意义上的区分，这导致在Linux下并没有充分体现线程是轻量级进程这一优势，反而带来了一些其他的开销。这几点主要涉及节点内的性能，其中5)主要针IA架构系统。
在以下部分中，我们以矩阵乘作为基准测试程序，分别对混合模式性能影响因子和操作系统对性能的影响作详细的分析。
3 性能测试与分析
3．1 实验环境
本文中采用的实验平台是IA架构Linux机群系统的曙光4000L超级计算机(以下简称D4000L)和RISC架构UNIX机群系统的曙光3000超级计算机(以下简称D3000)。D4000L的每个节点采用两个Intel Xeon 2.4G处理器和1G内存，每个处理器上有512K二级Cache，操作系统为Redhat Linux 7.3。D3000的每个节点采用4个375MHz Power3 RS64处理器和3G内存，每个处理器上有4M二级Cache，操作系统为AIX 4.3.3。在消息传递编程模式中，比较有代表性的规范是MPI(Message Passing Interface)，本文采用的是MPICH 1.2.3。混合编程模式使用的是MPI＋OpenMP的方式，即在节点内采用OpenMP实现，节点间通过MPI实现。
矩阵乘是高性能计算中较常用的运算之一，本文采用矩阵乘作为基准测试程序。矩阵采用带状划分方法，如图1所示。矩阵中元素为32位浮点数，主要测试32位浮点运算性能。本文中采用两种基准测试程序：不分块矩阵乘(NBMM)和分块矩阵乘(BMM)。NBMM是指在每一带状块中直接采用三重循环矩阵乘法；BMM是指在每一带状块中在细分为小块，在每一小块内采用三重循环矩阵乘法。为了具有可比性，矩阵的分块大小一律为25×25，这一分块大小对于实验中各个大小的矩阵规模的性能都是比较好的。
IA 机群 MPI OpenMP Cache
目录：
1 引言
2 编程模式及其性能影响机理
3 性能测试与分析
4 结束语
参考文献：
陈国良.并行计算－结构,算法,编程.北京.高等教育出版社.1999.
Hwang K, Xu Z. Scalable Parallel Computing: Technology, Architecture, Programming. WCB/McGraw-Hill Companies. 1998.
F. Cappelo, O. Richard, D. Etiemble. Investigating the Performance of Two Programming Models for Clusters of SMP PCs. In Proc. of the 6th IEEE Symposium On High-Performance Computer Architecture(HPCA-6). January 2000.
F. Cappelo, D. Etiemble. MPI versus MPI+OpenMP on the IBM SP for the NAS Benchmarks. In Proc. Supercomputing 2000(SC2000). November 2000.
H. Shan, J.P.Singh, R. Biswas. Message Passing Vs. Shared Address Space on Cluster of SMPs. In Proc. of the 15th International Parallel and Distributed Processing Symposium(IPDPS 2001). April 2001.