第2章第1节2004年11月25日

1、哈尔滨工业大学计算机科学与技术学院并行处理与体系结构并行处理与体系结构哈尔滨工业大学计算机科学与技术学院第第2 2章章 并行并行编程基础编程基础n 1 1 并行编程综述并行编程综述n 2 2 进程任务和线程进程任务和线程n 3 3 并行性问题并行性问题n 4 4 交互和通信问题交互和通信问题哈尔滨工业大学计算机科学与技术学院 1 并行编程综述并行编程综述n并行编程处于令人遗憾的状况：并行编程处于令人遗憾的状况：q并行软件开发远落后于并行硬件的进展。并行软件开发远落后于并行硬件的进展。缺少合适的并行软件是阻碍主流用户接缺少合适的并行软件是阻碍主流用户接纳并行计算的主要原因。纳并行计算的主要原因。

2、 q与顺序计算相比，当今的并行系统软件与顺序计算相比，当今的并行系统软件和应用软件不仅数量很少和应用软件不仅数量很少, ,而且功能性也而且功能性也相当原始。相当原始。 n隧道之末总有阳光。隧道之末总有阳光。哈尔滨工业大学计算机科学与技术学院一、一、并行编程缘何艰难并行编程缘何艰难n在并行编程中有许多不同的模型。是在并行编程中有许多不同的模型。是一个更复杂的智力活动。一个更复杂的智力活动。n并行程序的编译器、调试程序、以及并行程序的编译器、调试程序、以及特征分析器特征分析器(profiler)(profiler)要比串行程序要比串行程序落后得多。落后得多。哈尔滨工业大学计算机科学与技术学院哈尔滨

3、工业大学计算机科学与技术学院n1.1.顺序编程顺序编程q长期以来已建立了许多算法范例长期以来已建立了许多算法范例q一些实现指导用户从事算法设计。一些实现指导用户从事算法设计。哈尔滨工业大学计算机科学与技术学院2.2.并行编程并行编程 n并行编程处于初级阶段；并行编程处于初级阶段；q对于并行问题的应用，不太可对于并行问题的应用，不太可能有一个现成的并行代码；能有一个现成的并行代码；q并行代码的机器不同。并行代码的机器不同。哈尔滨工业大学计算机科学与技术学院q并行编程也不支持成熟、通用和稳并行编程也不支持成熟、通用和稳定的工具；定的工具；q并行算法范例仍未能被很好地理解并行算法范例仍未能被很好地理

4、解或被广泛地接受；或被广泛地接受；q不存在单一、通用的机器模型；不存在单一、通用的机器模型；q并行编程的模型有两级，而在每一并行编程的模型有两级，而在每一级上又有许多不同模型。级上又有许多不同模型。哈尔滨工业大学计算机科学与技术学院q与顺序语言在编程或自然模型级上与顺序语言在编程或自然模型级上缺少代可扩展和异构可扩展的能力缺少代可扩展和异构可扩展的能力n这些并行语言大多数在当前系统上使这些并行语言大多数在当前系统上使用的并行语言均是用的并行语言均是FortranFortran或或C C的某种的某种扩展。扩展。q一个编程模型即是程序员在开发一一个编程模型即是程序员在开发一个并行程序时所见到和使用

5、的模型。个并行程序时所见到和使用的模型。哈尔滨工业大学计算机科学与技术学院q一个自然模型是由一个特定并行计算机平一个自然模型是由一个特定并行计算机平台所提供的、用户可见的最低层的编程模台所提供的、用户可见的最低层的编程模型。其他的编程模型可在此自然模型上加型。其他的编程模型可在此自然模型上加以实现。以实现。n例如，在一个例如，在一个SGI SGI PowerChallengePowerChallenge计算机上计算机上( (它是它是SMP)SMP)， 自然模型为共享变量模型自然模型为共享变量模型( (如如SGIPowerCSGIPowerC) )。n数据并行数据并行( (如如HPF)HPF)和

6、消息传送和消息传送( (如如MPlMPl) )可在其可在其顶部实现。顶部实现。哈尔滨工业大学计算机科学与技术学院3.3.并行编程进展并行编程进展n尽管以上的回顾较为悲观，但在并行尽管以上的回顾较为悲观，但在并行编程领域已有了许多进步：编程领域已有了许多进步：n已开发了许多并行算法。已开发了许多并行算法。q尽管大多数算法基于非现实的尽管大多数算法基于非现实的PRAMPRAM模型，模型，但其中某些在作适当修正后可以实用。但其中某些在作适当修正后可以实用。n已涌现一小批简单的并行算法范例，已涌现一小批简单的并行算法范例，且已逐步为用户所接受。且已逐步为用户所接受。哈尔滨工业大学计算机科学与技术学院n

7、自然模型正集中趋向于两种模型：自然模型正集中趋向于两种模型：q适用于适用于PVPPVP、SMPSMP和和DSMDSM的单地址空间的单地址空间的共享变量模型；的共享变量模型；q适用于适用于MPPMPP和机群的多地址空间的消和机群的多地址空间的消息传递模型。息传递模型。qSIMDSIMD模型已从主流、通用并行计算模型已从主流、通用并行计算机淡出，但对于如同语言、图象和机淡出，但对于如同语言、图象和多媒体处理的专用嵌入式应用仍非多媒体处理的专用嵌入式应用仍非常有用常有用。哈尔滨工业大学计算机科学与技术学院n高层并行编程模型高层并行编程模型 趋向于趋向于3 3种标准模型：种标准模型：q数据并行数据并行

8、( (如如HPF)HPF)、q消息传递消息传递( (如如HPVMHPVM和和MPlMPl) )q共享变量共享变量( (如如HANSI X3H5)HANSI X3H5)。 此外还有一种模型此外还有一种模型-串转并；串转并；q用户只需编写顺序程序，其中的蕴式并行用户只需编写顺序程序，其中的蕴式并行性由并行化编译器性由并行化编译器( (如如KapKap) )进行析取进行析取。哈尔滨工业大学计算机科学与技术学院n4.4.吞吐率处理吞吐率处理 n在一个问题的处理上在一个问题的处理上, ,并行少并行少, ,串行串行多。多。n增加多个独立顺序作业的系统吞吐增加多个独立顺序作业的系统吞吐率。率。q顺序程序并行

9、系统顺序程序并行系统(SPPS)(SPPS)模型，也称模型，也称为吞吐率处理。为吞吐率处理。哈尔滨工业大学计算机科学与技术学院n二、并行编程环境二、并行编程环境n1. 1. 一个典型的并行处理系统一个典型的并行处理系统n如图所示的结构如图所示的结构n无论是算法还是源代码均需显式地并无论是算法还是源代码均需显式地并行化。行化。哈尔滨工业大学计算机科学与技术学院哈尔滨工业大学计算机科学与技术学院n编译器将源代码翻译成二进制代码编译器将源代码翻译成二进制代码在并行平台上运行，在并行平台上运行，q该平台包含操作系统和在它之下的并该平台包含操作系统和在它之下的并行计算机硬件。行计算机硬件。n任何编程语言

10、均有运行时间支持系任何编程语言均有运行时间支持系统，它是与用户代码连接程序。统，它是与用户代码连接程序。哈尔滨工业大学计算机科学与技术学院n2.2.环境工具环境工具 n一个环境工具是指任何硬件和软件的实用一个环境工具是指任何硬件和软件的实用程序，以帮助用户程序的开发和执行。程序，以帮助用户程序的开发和执行。n编程环境编程环境( (或简称环境或简称环境) )：所有这类工具集：所有这类工具集合。合。n工具的实例包括操作系统实用程序、程序工具的实例包括操作系统实用程序、程序设计语言、编译器以及运行时间库等。设计语言、编译器以及运行时间库等。n环境工具是那些通常与操作系统或程序设环境工具是那些通常与操

11、作系统或程序设计语言无关的工具集。计语言无关的工具集。哈尔滨工业大学计算机科学与技术学院n环境工具包括以下类型：环境工具包括以下类型：n作业管理工具作业管理工具 q包括网络排队系统包括网络排队系统(NQS)(NQS)和负载共享和负载共享工具工具(LSF(LSF) )。哈尔滨工业大学计算机科学与技术学院n调试工具调试工具 n性能工具性能工具q它们用来监控用户应用程序以识它们用来监控用户应用程序以识别性能瓶颈之所在。别性能瓶颈之所在。哈尔滨工业大学计算机科学与技术学院n三、并行编程方法三、并行编程方法目前在实际的并行计算机中广泛目前在实际的并行计算机中广泛使用的并行编程模型有使用的并行编程模型有4

12、 4种：种：q蕴式；蕴式；q数据并行；数据并行；q消息传递；消息传递；q共享变量。共享变量。哈尔滨工业大学计算机科学与技术学院n有三种扩展方法：有三种扩展方法：n库子程序、新语言构造以及编译库子程序、新语言构造以及编译器命令。器命令。 n库子程序库子程序q除了在顺序语言中可用的标准库外，除了在顺序语言中可用的标准库外，加入一组新的库函数，以支持并行加入一组新的库函数，以支持并行化和交互操作。化和交互操作。q这种库的实例包括这种库的实例包括MPIMPI消息传递以消息传递以及及POSIX POSIX PthreadsPthreads多线程库。多线程库。哈尔滨工业大学计算机科学与技术学院n新构造新构

13、造q扩展程序设计语言使其具有某些新扩展程序设计语言使其具有某些新构造，以支持并行化和交互。例如构造，以支持并行化和交互。例如Fortran 90Fortran 90中密集数据操作。中密集数据操作。n编译器命令编译器命令q程序设计语言不变，但加入称为编程序设计语言不变，但加入称为编译器命令译器命令( (或或pragmaspragmas) )的格式化注的格式化注解。解。哈尔滨工业大学计算机科学与技术学院n示例：示例：n用一段简单代码来说明这些方法。用一段简单代码来说明这些方法。n所有所有3 3个并行程序均执行相同的如图个并行程序均执行相同的如图所示的串行所示的串行C C代码的计算。代码的计算。哈尔

14、滨工业大学计算机科学与技术学院n串行代码段串行代码段nfor ( i = 0; i N; i + ) Ai = bi * bi+1;nfor(i=0;iN;i+) ci=Ai+Ai+1;n使用库例程的等效并行代码使用库例程的等效并行代码nid = my_process_id();np = number of processes();nfor(i=id;iN;i=i+p) Ai=bi*bi+1;nbarrier();nfor(i=id;iN;i=i+p) ci=Ai +Ai+1;哈尔滨工业大学计算机科学与技术学院n串行代码段串行代码段nfor ( i = 0; i N; i + ) Ai = b

15、i * bi+1;nfor(i=0;iN;i+) ci=Ai+Ai+1;nFortran90Fortran90中使用数组操作的等效代中使用数组操作的等效代码码nmy-processid(), number_of_processes(), and barrier()nA(0:N-1) = b(0:N-1) * b(1:N)nc = A(0:N-1) + A(1:N)哈尔滨工业大学计算机科学与技术学院n串行代码段串行代码段nfor ( i = 0; i N; i + ) Ai = bi * bi+1;nfor(i=0;iN;i+) ci=Ai+Ai+1;nSGI SGI powerCpowerC中

16、使用中使用pragmapragma的等效代码的等效代码n# pragma paralleln#pragma shared ( A,b,c)n#pragma local ( i )n#pragma pfor iterate (i=0; N:1)n for(i=0;iN;i+)n#pragma synchronizen#pragma pfor iterate (i=0; N:1)n for(i=0;iN;i+) ci=Ai+Ai+1;哈尔滨工业大学计算机科学与技术学院三种方法的比较：三种方法的比较：哈尔滨工业大学计算机科学与技术学院n可用可用3 3种方法实现任何编程模种方法实现任何编程模型型n在任何并行平台上，在任何并行平台上，3 3种方法和编种方法和编程模型可以各种方式组合。程模型可