第2章并行编程基础精选文档.ppt

《第2章并行编程基础精选文档.ppt》由会员分享，可在线阅读，更多相关《第2章并行编程基础精选文档.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 并行编程基础本讲稿第一页，共八十二页第第2章章 并行编程基础并行编程基础2.1 2.1 并行编程综述并行编程综述2.2 2.2 进程、任务和线程进程、任务和线程2.3 2.3 并行性问题并行性问题2.4 2.4 交互交互/通信问题通信问题2.5 2.5 并行程序中的语义问题并行程序中的语义问题本讲稿第二页，共八十二页并行编程基础并行编程基础并行编程综述并行编程综述并行编程缘何艰难并行编程缘何艰难1、并行软件一直落后的主要原因是并行编程比起顺序编程来是一个更复杂的智并行软件一直落后的主要原因是并行编程比起顺序编程来是一个更复杂的智力活动。它包含了顺序编程中的所有问题，还要加上在智力上更具

2、挑战性的力活动。它包含了顺序编程中的所有问题，还要加上在智力上更具挑战性的许多其他问题。许多其他问题。2、顺序编程只有一个基本模型（冯诺依曼模型），而、顺序编程只有一个基本模型（冯诺依曼模型），而并行编程中却有许多不同并行编程中却有许多不同的模型。的模型。3、开发顺序程序的软件环境工具，如编译器、调试程序、以及特征分析器，要、开发顺序程序的软件环境工具，如编译器、调试程序、以及特征分析器，要比并行程序的先进得多。比并行程序的先进得多。4、比起并行编程来，有更多的人一直在从事顺序编程而且已有长得多的时间。、比起并行编程来，有更多的人一直在从事顺序编程而且已有长得多的时间。对顺序编程由于已积累了大

3、量知识，包括过去所发现的错误以及所得到的教对顺序编程由于已积累了大量知识，包括过去所发现的错误以及所得到的教训，因此更为成熟。训，因此更为成熟。本讲稿第三页，共八十二页2.1 并行编程综述并行编程进展并行编程进展面向超级计算机的编程模型正集中趋向于两种模型：面向超级计算机的编程模型正集中趋向于两种模型：1 1）适用于）适用于PVPPVP、SMPSMP、DSMDSM的单地址空间的的单地址空间的共享变量共享变量模型模型；2 2）适用于）适用于MPPMPP和机群的多地址空间的和机群的多地址空间的消息传递模型消息传递模型。SIMD模型原已从主流超级计算机中淡出，但对于如同语言、图模型原已从主流超级计算

4、机中淡出，但对于如同语言、图象和多媒体处理的专用嵌入式那些应用仍非常有用。象和多媒体处理的专用嵌入式那些应用仍非常有用。-尤其是多核芯片的问世，以尤其是多核芯片的问世，以SIMD模型模型为基础，未来的通用计算机编为基础，未来的通用计算机编程将带来很大的改进程将带来很大的改进。本讲稿第四页，共八十二页并行编程综述并行编程进展并行编程进展 高层并行编程模型正集中趋向于高层并行编程模型正集中趋向于4种标准模型：种标准模型：1 1）数据并行数据并行（如（如HPFHPF）2 2）消息传递消息传递（如（如PVMPVM和和MPIMPI）3 3）共享变量共享变量（如（如ANSI X3H5ANSI X3H5）4

5、 4）蕴式并行模型蕴式并行模型，用户只需编写顺序程序，其中的蕴式并行性由，用户只需编写顺序程序，其中的蕴式并行性由并行化编译器（如并行化编译器（如KapKap）进行析取。）进行析取。图图1吞吐率处理吞吐率处理 减少单个并行应用的响应时间减少单个并行应用的响应时间 增加多个独立顺序作业的系统吞吐率增加多个独立顺序作业的系统吞吐率本讲稿第五页，共八十二页并行编程基础并行编程基础并行编程环境并行编程环境 并行处理系统的组成部分并行处理系统的组成部分 图图2并行编程环境工具：并行编程环境工具：作业管理工具作业管理工具调试工具调试工具性能工具性能工具本讲稿第六页，共八十二页并行编程基础并行编程基础 并行

6、编程方法并行编程方法 目前在实际的并行计算中广泛使用的并行编程模型有目前在实际的并行计算中广泛使用的并行编程模型有4种：种：蕴蕴式并行模型、数据并行、式并行模型、数据并行、消息传递、共享变量消息传递、共享变量 这些并行编程模型均已在实际的并行编程系统中得到实现，绝这些并行编程模型均已在实际的并行编程系统中得到实现，绝大部分为扩展的大部分为扩展的Fortran或扩展或扩展C。对于顺序编程有三种扩展并行性的方法：对于顺序编程有三种扩展并行性的方法：库子程序、新语言构造库子程序、新语言构造、编译器命令编译器命令。本讲稿第七页，共八十二页并行编程基础并行编程基础 库子程序：库子程序：除了在顺序语言中可

7、用的标准库外，除了在顺序语言中可用的标准库外，加入一组新的库函数，加入一组新的库函数，以支持并行化和交互操作。以支持并行化和交互操作。这种库的实例包括这种库的实例包括:消息传递消息传递(MPI)和和 多线程库多线程库(POSIX Pthreads)。新构造：新构造：扩展程序设计语言扩展程序设计语言使其具有某些新构造，以支持并行化和交使其具有某些新构造，以支持并行化和交互。例如互。例如Fortran 90中密集数报操作。中密集数报操作。编译器命令：编译器命令：程序设计语言不变，但程序设计语言不变，但加入称为编译器命令加入称为编译器命令（或（或pragmas）的格式化注解的格式化注解。本讲稿第八页

8、，共八十二页三种并行化方式举例三种并行化方式举例:for(i=0;iN;i+)Ai=bi*bi+1;for(i=0;iN;i+)ci=Ai+Ai+1;(a)(a)串行代码段串行代码段三种并行化方式举例三种并行化方式举例本讲稿第九页，共八十二页并行编程基础并行编程基础所有所有3 3个程序均执行相同的如图个程序均执行相同的如图a a所示的串行所示的串行C C代码的计算。代码的计算。（1）图图b说明了说明了库方法库方法 其中两个循环被分配到其中两个循环被分配到P个过程并行执行个过程并行执行。由两个库函数：。由两个库函数：my_process_id()和和number_of_processes()开发

9、并行性。开发并行性。路障路障barrier()函数保证在第函数保证在第1个循环后，所有进程同步，个循环后，所有进程同步，这样第这样第2个循个循环将使用在第一个循环中已更新的数组环将使用在第一个循环中已更新的数组A的正确值。的正确值。本讲稿第十页，共八十二页 id=my_process_id();p=number_of_processes();for(i=id;iN;i=i+p)Ai=bi*bi+1;barrier();for(i=id;iN;i=i+p)ci=Ai+Ai+1;(b)(b)使用使用库例程库例程的等效并行代码的等效并行代码三种并行化方式三种并行化方式本讲稿第十一页，共八十二页并行编

10、程基础并行编程基础（2）若使用新的语言构造）若使用新的语言构造 使用新的语言构造使用新的语言构造,上述的这些并行操作就可变得相当简单，如图上述的这些并行操作就可变得相当简单，如图c所示。所示。Fortran 90的的数组赋值构造数组赋值构造A(0:N-1)=b(0:N-1)*b(1:N)可在可在1条数条数组赋值语句中完成组赋值语句中完成N个元素乘法和赋值个元素乘法和赋值。在两个数组赋值之间，不。在两个数组赋值之间，不需要显式同步，因为需要显式同步，因为Fortran 90语句是语句是松散同步松散同步：在下一语句开：在下一语句开始执行前，前一语句中的操作必须都已完成。始执行前，前一语句中的操作必

11、须都已完成。本讲稿第十二页，共八十二页my_process_id()，number_of_processes()，and;barrier();A（0：N1）=b（0：N1）*b（1：N）;C=A（0：N1）+A（1：N）;(c)Fortran 90 (c)Fortran 90 中使用中使用数组操作数组操作的等效代码的等效代码三种并行化方式三种并行化方式本讲稿第十三页，共八十二页并行编程基础并行编程基础（3）图图d编译器命令方法编译器命令方法 由并行由并行pragma指明下一语句（以块形式出现）应并行执行。指明下一语句（以块形式出现）应并行执行。由共由共享享(shared)pragma说明说明3

12、个数组变量为并行进程共享，而局部个数组变量为并行进程共享，而局部pragma则用来指明每个进程有一个局部的变量。则用来指明每个进程有一个局部的变量。SGI的的pfor pravgma命令系统命令系统以并行方式执行下一循环。而由同步以并行方式执行下一循环。而由同步pragma产生一个路障同步。产生一个路障同步。本讲稿第十四页，共八十二页#pragma parallel#pragma shared(A,b,c)#pragma local(i)#pragma pfor iterate(i=0;N;1)for(i=0;iN;i+)Ai=bi*bi+1;#pragma synchronize#pragm

13、a pfor iterate(i=0;N;1)for(i=0;iN;i+)ci=Ai+Ai+1;(d)SGI power C(d)SGI power C中使用中使用pragmapragma的等效代码的等效代码三种并行化方式三种并行化方式本讲稿第十五页，共八十二页并行编程基础并行编程基础 下表中总结了下表中总结了3 3种方法的优缺点。由于容易实现，种方法的优缺点。由于容易实现，库例程是目前使用最库例程是目前使用最广泛的方法广泛的方法所有并行化和交互功能由附加到顺序所有并行化和交互功能由附加到顺序C C或或FortranFortran的一组程的一组程序实现。因此就无需实现新的编译器。然而由于没有编

14、译器支持，用户序实现。因此就无需实现新的编译器。然而由于没有编译器支持，用户就丧失了编译时间分析、错误检查和优化的机会。就丧失了编译时间分析、错误检查和优化的机会。方法实例优点缺点库例程MPI,PVM,Cray Craft易于实现，不需要新编译器无编译器检查、分析和优化新构造Fortran90,Cray Craft允许编译器检查、分析和优化实现困难，需要新编译器命令HPF,Cray Craft介于库例程和新构造方法之间，在串行平台上不起作用本讲稿第十六页，共八十二页2.2 进程、任务和线程进程、任务和线程抽象进程的定义抽象进程的定义定义定义2.1 一个进程一个进程P是一个是一个4元组元组P=（

15、p,C,D,S）其中其中p是程序（或代码），是程序（或代码），C是控制状态，是控制状态，D为数据状态，为数据状态，S为进程为进程P的的状态。状态。进程是动态的，其中它不单是指代码和数据是动态的，而且还包含进程是动态的，其中它不单是指代码和数据是动态的，而且还包含正在执行的思想。正在执行的思想。本讲稿第十七页，共八十二页进程、任务和线程进程、任务和线程 任何进程与一个程序相关，作为一个例子，考虑如下的任何进程与一个程序相关，作为一个例子，考虑如下的C代码：代码：main（）（）int i=0;fork();fork();printf(“Hello！n”);我们可如下编译此程序（假设它在文件我们可

16、如下编译此程序（假设它在文件hello.c中）中）:cc-o Hi hello.c，并可用简单命令：并可用简单命令：Hi 执行它。执行它。本讲稿第十八页，共八十二页进程、任务和线程进程、任务和线程 操作系统将操作系统将创建一个输出创建一个输出hellohello的进程的进程。除了由用户提供的显式。除了由用户提供的显式代码外，进程还使用运行时间支持、库例程以及系统函数。上述进程称为代码外，进程还使用运行时间支持、库例程以及系统函数。上述进程称为Printf（），它是（），它是C语言标准语言标准I/O库中的例程，以及库中的例程，以及fork(),它是它是Unix系统的一个调系统的一个调用。用。控制

17、和数据状态控制和数据状态 大多数程序基于大多数程序基于命令式机器模型命令式机器模型，其中新概念，其中新概念是是状态更新状态更新。一个命令式程序可看成是一个状态机（或一个自动机），它将程序从初一个命令式程序可看成是一个状态机（或一个自动机），它将程序从初始状态映射到一个或多个最后状态。始状态映射到一个或多个最后状态。本讲稿第十九页，共八十二页进程、任务和线程进程、任务和线程 定义定义2.22.2 一个程序使用两个变量集：一个程序使用两个变量集：数据变量数据变量由程序员声明用来保存数据值的变量；由程序员声明用来保存数据值的变量；控制变控制变量量是保存控制信息的变量，它们不需要显式说明。换是保存控制

18、信息的变量，它们不需要显式说明。换言之，控制变量保存的是有关下一步应执行什么操作言之，控制变量保存的是有关下一步应执行什么操作的信息。的信息。数据变量集和控制变量集两者的合集形成了程序变数据变量集和控制变量集两者的合集形成了程序变量集。量集。本讲稿第二十页，共八十二页进程、任务和线程进程、任务和线程 定义定义2.32.3 在任何时候，一个程序的每个数据或控制变量需与一在任何时候，一个程序的每个数据或控制变量需与一个值配为一对，该值可能是一个未定义的特殊值。在时间个值配为一对，该值可能是一个未定义的特殊值。在时间t t时所时所有（数据变量、数据值）的配对集定义了有（数据变量、数据值）的配对集定义

19、了时间时间t t的程序数据状态的程序数据状态。类似地，时间类似地，时间t t的所有（控制变量，控制值）配对集定义了时间的所有（控制变量，控制值）配对集定义了时间t t的程序控制状态。因此，的程序控制状态。因此，时间时间t t的程序状态是的程序状态是t t时间的数据状态和时间的数据状态和控制状态的和。控制状态的和。或者我们可以说或者我们可以说t t时的程序状态是所有（程序变时的程序状态是所有（程序变量、值）的配对集。量、值）的配对集。本讲稿第二十一页，共八十二页进程、任务和线程进程、任务和线程 定义定义2.42.4 程序从初始状态启动。程序从初始状态启动。当执行了程序的一个原子操作后，程序当执行

20、了程序的一个原子操作后，程序就从当前状态转为下一状态就从当前状态转为下一状态。程序不断执行原子操作并不断更新其状。程序不断执行原子操作并不断更新其状态，直至终止。此时程序处在最后状态。态，直至终止。此时程序处在最后状态。这样一个命令式程序可视为是这样一个命令式程序可视为是产生一个或多个序列的原子操作产生一个或多个序列的原子操作，它们将状态机从初始状态转换到最后状态。它们将状态机从初始状态转换到最后状态。当一个程序进入一个被确认不会终结的状态时，则说该程序进当一个程序进入一个被确认不会终结的状态时，则说该程序进入了入了发散状态。发散状态。本讲稿第二十二页，共八十二页进程、任务和线程进程、任务和线

21、程 我们可把控制变量当作程序计数器。对具有单控制线程的进程来讲，我们可把控制变量当作程序计数器。对具有单控制线程的进程来讲，它只有一个控制变量：程序计数器；它只有一个控制变量：程序计数器；而对有多控制线程的进程而言，它而对有多控制线程的进程而言，它有有多个控制变量多个控制变量，每个线程有一个每个线程有一个，它含有该线程的程序计数器值；，它含有该线程的程序计数器值；对于对于多子进程情况，整个进程可有若干个控制变量，多子进程情况，整个进程可有若干个控制变量，每个子进程有一个。每个子进程有一个。在用户程序中，在用户程序中，数据变量可用蕴式或显式方式说明。数据变量可用蕴式或显式方式说明。例如，例如，U

22、nixUnix进程的数据变量含有隐藏的文件指针进程的数据变量含有隐藏的文件指针stdinstdin、stdoutstdout以及以及stderrstderr各自用作标准输入、标准输出和标准错误，它们可显式地各自用作标准输入、标准输出和标准错误，它们可显式地加以说明。加以说明。本讲稿第二十三页，共八十二页进程状态进程状态在任何时间，进程具有某个状态：在任何时间，进程具有某个状态：图图4 开始时，进程不存在（为开始时，进程不存在（为不存在状态不存在状态）。当它的创建者，父进程执）。当它的创建者，父进程执行进程创建操作后，它才出现。一个新创建的子进程准备执行，但仅行进程创建操作后，它才出现。一个新创

23、建的子进程准备执行，但仅在被调度后，它方可开始在被调度后，它方可开始运行运行（执行其代码）。在进程运行中可能发生（执行其代码）。在进程运行中可能发生以下几种情况：以下几种情况：由于页面失挂或其他情况，它无法继续执行时，就被挂起，从而进由于页面失挂或其他情况，它无法继续执行时，就被挂起，从而进入入挂起状态挂起状态。本讲稿第二十四页，共八十二页进程状态进程状态在任何时间，进程具有某个状态：在任何时间，进程具有某个状态：一个正在运行进程可能被具有更高优先级的另一进程抢占，或者它可一个正在运行进程可能被具有更高优先级的另一进程抢占，或者它可能已用完分配给它的能已用完分配给它的CPUCPU时间片（到时）

24、。不论是哪种情况，进程本身时间片（到时）。不论是哪种情况，进程本身能（准备）继续执行，但它被强制放弃能（准备）继续执行，但它被强制放弃CPUCPU资源并转换其状态成为资源并转换其状态成为就绪就绪。最后，一个正在运行的进程能终止本身，或是正常地在它完成代码最后，一个正在运行的进程能终止本身，或是正常地在它完成代码执行后，或是异常地（夭折）终止，并停止存在。执行后，或是异常地（夭折）终止，并停止存在。另一个经常使用的操作是另一个经常使用的操作是进程切换进程切换，它是指将一个正常运行的进程转换，它是指将一个正常运行的进程转换成或是成或是挂起挂起或是或是就绪就绪状态，并调度下一个就绪的进程运行。状态，

25、并调度下一个就绪的进程运行。本讲稿第二十五页，共八十二页进程状态进程状态 在实际的操作系统和并行编程环境中，由于还有附加在实际的操作系统和并行编程环境中，由于还有附加的其他状态，因而情况更为复杂。的其他状态，因而情况更为复杂。以上提及的进程概念很适合于需要使用并行语言的用以上提及的进程概念很适合于需要使用并行语言的用户。对于那些要实现进程并行概念者，就需要更为详细的户。对于那些要实现进程并行概念者，就需要更为详细的进程观。进程观。在实现进程并行运行时，还必须考虑以下各方面：在实现进程并行运行时，还必须考虑以下各方面：执执行方式、地址空间、现场进程描述符和进程控制。行方式、地址空间、现场进程描述

26、符和进程控制。本讲稿第二十六页，共八十二页进程状态进程状态寻找工作状态：寻找工作状态：一个进程根据其是否已完成执行，可以进入一个进程根据其是否已完成执行，可以进入寻找工作状寻找工作状态态，若向这个未被雇佣的进程分配某个新工作时，它就被，若向这个未被雇佣的进程分配某个新工作时，它就被激活了。激活了。可减少由于一个进程结束后接着再被创建去从事一项新工可减少由于一个进程结束后接着再被创建去从事一项新工作时所需的开销。作时所需的开销。适用于共享存储器模型的并行编程。适用于共享存储器模型的并行编程。本讲稿第二十七页，共八十二页线线 程程 概概 念念线线 程程：指控制线程：指控制线程逻辑组成由：程序代码、

27、逻辑组成由：程序代码、一个程序计数器、一个程序计数器、一个调用堆栈、适一个调用堆栈、适量的专用数据（包括通用寄存器）。量的专用数据（包括通用寄存器）。线线 程共享对存储器的访问，所以线程之间能够通过读或写对它们都可程共享对存储器的访问，所以线程之间能够通过读或写对它们都可见的存储器互相通信。见的存储器互相通信。线线 程也可共享对文件系统的访问。程也可共享对文件系统的访问。用线程进行程序设计被称为：用线程进行程序设计被称为：基于线程的并行程序设计基于线程的并行程序设计；或被称为：或被称为：共享存储器共享存储器并行程序设计并行程序设计 本讲稿第二十八页，共八十二页线程线程由进程创建的一种轻型进程，

28、线程相对于进程，犹如进由进程创建的一种轻型进程，线程相对于进程，犹如进程相对于机器。程相对于机器。同一进程的所有线程共享地址空间同一进程的所有线程共享地址空间有程序计数器和堆栈有程序计数器和堆栈像进程一样共享处理机像进程一样共享处理机线程可以创建子线程线程可以创建子线程当一个线程被阻塞时，可调度运行同一进程中的另一线程当一个线程被阻塞时，可调度运行同一进程中的另一线程每个线程能读写，甚至清除另一线程的堆栈，线程之间没有保护每个线程能读写，甚至清除另一线程的堆栈，线程之间没有保护线程的状态：运行、阻塞、就绪、结束线程的状态：运行、阻塞、就绪、结束下一页本讲稿第二十九页，共八十二页每个进程的项目地

29、址空间全局变量打开的文件子进程计时器标志信号量计算信息每个线程的项目程序计数器堆栈寄存器组子线程状态本讲稿第三十页，共八十二页引入线程是为了将并行性引入顺序执行的系统。引入线程是为了将并行性引入顺序执行的系统。下图是线程与进程的三种组织下图是线程与进程的三种组织派遣者派遣者/工作者模型团队模型管道线模型工作者模型团队模型管道线模型文件服务器进程工作者线程共享块cache工作请求到达邮箱派遣者线程内核 线程的用途线程的用途下一页用线程构造服务器进程的三种方法用线程构造服务器进程的三种方法本讲稿第三十一页，共八十二页模 式特性线程并行，阻塞系统调用单线程进程不并行，阻塞系统调用有限状态机并行，非阻

30、塞系统调用本讲稿第三十二页，共八十二页与线程相关的用户可得的原语集（即库调用）与线程相关的用户可得的原语集（即库调用）线 程 包：线程管理：静态设计，程序编写或编译时就确定线程个数。每个线程分配一个固定堆栈。静态设计，程序编写或编译时就确定线程个数。每个线程分配一个固定堆栈。动态设计，允许线程在运行过程中动态的创建和回收动态设计，允许线程在运行过程中动态的创建和回收线程结束：自己退出自己退出 被外界中止被外界中止共享数据：互斥变量，使用锁解决临界区数据共享问题互斥变量，使用锁解决临界区数据共享问题 条件变量，解决同步问题，避免死锁条件变量，解决同步问题，避免死锁全局变量：分配一块内存给全局变量

31、，并将它作为一个参数传递给线程中的每一个过程分配一块内存给全局变量，并将它作为一个参数传递给线程中的每一个过程引入新的库过程来创建、设置和读取这些线程全局变量引入新的库过程来创建、设置和读取这些线程全局变量线程调度：优先级法优先级法 轮转法轮转法线程包的设计问题线程包的设计问题本讲稿第三十三页，共八十二页有两种方法：在用户空间实现和在操作系统内核实现有两种方法：在用户空间实现和在操作系统内核实现线程包的实现线程包的实现用户空间内核空间运行期系统内核内核内核空间用户空间线程0线程1线程2线程3线程4线程0线程1线程2线程3线程4(a)用户级线程包(b)由内核管理的线程包下一页本讲稿第三十四页，共

32、八十二页在用户空间中实现线程在用户空间中实现线程在用户空间中实现线程：在用户空间中实现线程：将线程包完全放到用户空间中去，内核对此一无所知将线程包完全放到用户空间中去，内核对此一无所知线程运行在运行期系统的上层，运行期系统是一些管理线程的过程集线程运行在运行期系统的上层，运行期系统是一些管理线程的过程集线程执行系统调用时进入休眠，由运行期系统接管控制权，它负责线程的切换线程执行系统调用时进入休眠，由运行期系统接管控制权，它负责线程的切换优点优点：能够在不支持线程的操作系统中实现能够在不支持线程的操作系统中实现系统开销小，线程切换可用有限的几条指令完成系统开销小，线程切换可用有限的几条指令完成允

33、许每一个进程有自己定制的调度算法允许每一个进程有自己定制的调度算法难以实现阻塞系统调用难以实现阻塞系统调用线程调度是非抢先式调度，如果线程一直运行，运行期系统就得不到控制权线程调度是非抢先式调度，如果线程一直运行，运行期系统就得不到控制权缺点缺点：本讲稿第三十五页，共八十二页内核知道并管理线程。当一个线程想去创建一个新线程或撤销已存在的线程时，它发出内核知道并管理线程。当一个线程想去创建一个新线程或撤销已存在的线程时，它发出一个内核的调用，由它完成创建和回收工作一个内核的调用，由它完成创建和回收工作在内核中每个进程都有一张表，每个线程在表中有一个入口，每个入口保存着线程的寄存器、在内核中每个进

34、程都有一张表，每个线程在表中有一个入口，每个入口保存着线程的寄存器、状态、优先权和其他信息状态、优先权和其他信息当一线程阻塞时，内核可以调用同一进程中的其它线程，也可以调用另一个进程的线程当一线程阻塞时，内核可以调用同一进程中的其它线程，也可以调用另一个进程的线程按系统调用来实现线程的阻塞调用，但开销较大按系统调用来实现线程的阻塞调用，但开销较大在内核中实现线程：在内核中实现线程：优点：优点：缺点缺点：不需要任何新的非阻塞系统调用不需要任何新的非阻塞系统调用 不易产生死锁不易产生死锁产生页面错时，系统能很容易地运行另一线程产生页面错时，系统能很容易地运行另一线程系统调用耗费大系统调用耗费大下一

35、页在内核中实现线程在内核中实现线程本讲稿第三十六页，共八十二页模拟内核线程的功能，使用户空间内实现的线程包调度有更好的性能和有更大的灵活性。模拟内核线程的功能，使用户空间内实现的线程包调度有更好的性能和有更大的灵活性。目目 标：标：内核分配一定数量的虚拟处理机给每个进程，并且让运行期系统将线程分配给处理机内核分配一定数量的虚拟处理机给每个进程，并且让运行期系统将线程分配给处理机 当内核知道一个线程已阻塞时，内核将通过将这个线程的号码和所发生事件的描述作为参数传递到堆当内核知道一个线程已阻塞时，内核将通过将这个线程的号码和所发生事件的描述作为参数传递到堆栈，通知该进程的运行期系统栈，通知该进程的

36、运行期系统 运行期系统一旦被激活，它就能重新调度线程运行期系统一旦被激活，它就能重新调度线程 当一个用户线程在运行产生一个硬件中断时，被中断的当一个用户线程在运行产生一个硬件中断时，被中断的CPUCPU切换进入内核模式处理切换进入内核模式处理实现方法：实现方法：下一页调度者行为调度者行为本讲稿第三十七页，共八十二页在线程上可以运行更轻量级的在线程上可以运行更轻量级的RPCRPC。方法：方法：当服务器线程当服务器线程S S启动时，输出它的接口通知内核启动时，输出它的接口通知内核 需要服务的客户线程需要服务的客户线程C C启动后，从内核中取出启动后，从内核中取出S S的服务接口，并获得该调用的标识

37、的服务接口，并获得该调用的标识 由内核创建专用数据结构来为调用由内核创建专用数据结构来为调用S S做准备。其中包括共享堆栈做准备。其中包括共享堆栈 线程线程C C将参数压入堆栈，然后自陷进入内核将参数压入堆栈，然后自陷进入内核 内核根据参数判断调用是否在本地，如在本地，更改客户内存映像，将客户放入服内核根据参数判断调用是否在本地，如在本地，更改客户内存映像，将客户放入服务器的地址空间，启动客户线程执行服务器过程务器的地址空间，启动客户线程执行服务器过程思想：思想：在线程上进行远程过程调用在线程上进行远程过程调用（RPC）本讲稿第三十八页，共八十二页线线 程程 概概 念念进进 程程：拥有私有地址

38、空间拥有私有地址空间进程之间的互相通信需要借助传递消息进程之间的互相通信需要借助传递消息；也可借助文件系统（但很少）也可借助文件系统（但很少）在并行计算中，用进程进行程序设计被称为：在并行计算中，用进程进行程序设计被称为：基于传递消息的并行程序设计基于传递消息的并行程序设计或被称为：或被称为：非共享存储器并行程序设计非共享存储器并行程序设计进程趋向长期生存，而线程则随着计算的进行动态派生或销毁进程趋向长期生存，而线程则随着计算的进行动态派生或销毁本讲稿第三十九页，共八十二页2.3并行性问题并行性问题及解决方法及解决方法 进程中的同构性进程中的同构性-指并行程序中各分进程的相似性。指并行程序中各

39、分进程的相似性。有有3 3种基本类型：种基本类型：SPMD：在单程序多数据（在单程序多数据（SPMD）程序中的）程序中的分进程是分进程是同构同构的。因为多个进程在不同的数据范畴内的。因为多个进程在不同的数据范畴内执行相同代码执行相同代码。程。程序由数据并行构造，也称序由数据并行构造，也称SPMD为为数据并行程序。数据并行程序。（如（如Fortran 90Fortran 90）MPMD：在多程序多数据（在多程序多数据（MPMD）程序中的）程序中的分进程是分进程是异异构构的。因为多个进程可以的。因为多个进程可以执行不同代码执行不同代码。也称。也称MPMD为为功能功能并行程序、任务并行、控制并行。并

40、行程序、任务并行、控制并行。SPMDSPMD和和MPMDMPMD可以混用。可以混用。本讲稿第四十页，共八十二页并行性问题并行性问题及解决方法及解决方法有有3 3种基本类型：种基本类型：SIMD：SPMDSPMD和和MPMDMPMD程序，两者都是程序，两者都是MIMDMIMD类型的程序类型的程序。因为在同一时间不同指令由不同进程加以执行。因为在同一时间不同指令由不同进程加以执行。而一个而一个SIMD程序比程序比SPMD更加严格，因为多个过程不但必须执更加严格，因为多个过程不但必须执行相同代码，而且它们全体必须在同一时间执行相同的行相同代码，而且它们全体必须在同一时间执行相同的指令。换句话说，指令

41、。换句话说，SIMD程序是程序是 SPMD程序的一个特例。程序的一个特例。本讲稿第四十一页，共八十二页并行性问题并行性问题及解决方法及解决方法 SPMD程序通常用：程序通常用：并行循环构造、数据并行构造或并行循环构造、数据并行构造或单单代码方式加以说明。代码方式加以说明。MPMD程序通常用程序通常用:并行块构造、并行块构造、多代码多代码方式加以说明。方式加以说明。下面分别介绍这几种并行构造方法本讲稿第四十二页，共八十二页2.3并行性问题并行性问题及解决方法及解决方法1 1、并行块、并行块（parallel block)parallel block)表达表达MPMDMPMD程序的一个很自然的方法

42、是使用程序的一个很自然的方法是使用parbeginparbegin和和parendparend构造：构造：Parbegin SParbegin S1 1S S2 2SSn n Parend Parend 它们它们总是成对使用。总是成对使用。这种结构化的构造也称为：这种结构化的构造也称为：cobegin Scobegin S1 1S S2 2SSn n coend coend它被称为是一个它被称为是一个并行块并行块，其中，其中 S S1 1S S2 2SSn n 是分进程，可含有是分进程，可含有不同不同代码。代码。当并行块执行时，它的当并行块执行时，它的n n个分进程个分进程S S1 1S S2

43、 2SSn n就开始同时执行。它们的就开始同时执行。它们的执执行是互相独立的而且以不同速率进行行是互相独立的而且以不同速率进行。当所有当所有n n个分进程终止时，并行块才能终止。个分进程终止时，并行块才能终止。之所以命名为并行块是为了与顺序块相对照，后者在传统的顺序之所以命名为并行块是为了与顺序块相对照，后者在传统的顺序语言中可以找到：语言中可以找到：begin Sbegin S1 1S S2 2SSn n end end。本讲稿第四十三页，共八十二页并行性问题并行性问题2 2、并行循环、并行循环（parallel loop）当当并行块中的所有进程共享相同代码并行块中的所有进程共享相同代码时，

44、我们用一个称为并行时，我们用一个称为并行循环的速记记号来标明如下并行块：循环的速记记号来标明如下并行块：Parbegin Process(1)Process(n)Parend 可被简化成如下的并行循环：可被简化成如下的并行循环：Parfor(i=1;i=n;i+)Process(i)并行循环常用来说明并行循环常用来说明SPMDSPMD并行程序。并行程序。本讲稿第四十四页，共八十二页并行性问题并行性问题 系统程序（如操作系统或网络系统）中的进程通常是异构系统程序（如操作系统或网络系统）中的进程通常是异构的。许多并行计算程序，特别是大规模并行计算机中的并行程的。许多并行计算程序，特别是大规模并行计

45、算机中的并行程序，是高度同构的。序，是高度同构的。要为有要为有1000个处理器的计算机编写一个完全异构的并行程序将是很个处理器的计算机编写一个完全异构的并行程序将是很困难的，因为我们需要为每个处理器写一个不同程序。困难的，因为我们需要为每个处理器写一个不同程序。对于一个分布对于一个分布/并行编程环境而言，希望能同时提供同构并行编程环境而言，希望能同时提供同构和异构进程。但是对于扩展并行机来讲，通常只要支持和异构进程。但是对于扩展并行机来讲，通常只要支持SPMDSPMD就就足够了。在多核时代尤其如此。足够了。在多核时代尤其如此。本讲稿第四十五页，共八十二页并行性问题并行性问题当不同的代码数较小时

46、，我们可以用当不同的代码数较小时，我们可以用SPMD来伪造来伪造MPMD。如：如：MPMD MPMD代码代码:parbegin A；B；C；parend可以等价地表示成一个可以等价地表示成一个SPMDSPMD的并行循环：的并行循环：parfor（i=0;i3；i）If（i=0）A；if（i=1）B；if（i=2）C；本讲稿第四十六页，共八十二页并行性问题并行性问题3、多代码与单代码、多代码与单代码（Multi-Code versus Single Code）在目前的并行计算机，特别是在目前的并行计算机，特别是MPP和和COW上，上，许多编程语言不提供并行块许多编程语言不提供并行块或并行循环构造

47、。或并行循环构造。在这种系统中，在这种系统中，MPMD并行性可用多代码方法加以说并行性可用多代码方法加以说明来解决明来解决。例如，要说明例如，要说明parbeginAparbeginA；B B；C C；parend parend，用户需编写，用户需编写3 3个程序个程序,并将它并将它们编译以生成三个可执行程序们编译以生成三个可执行程序A A、B B和和C C，用，用shellshell脚本脚本将它们装载到将它们装载到3 3个处个处理结点理结点中：中：run A on node 1run B on node 2run C on node 3程序程序A A、B B和和C C仅是顺序程序加上仅是顺序

48、程序加上进行交互的库调用进行交互的库调用。本讲稿第四十七页，共八十二页并行性问题并行性问题SPMDSPMD程序可用单代码方法加以说明程序可用单代码方法加以说明来实现多节点并行来实现多节点并行。例如，要说明并行循环例如，要说明并行循环 parfor（i=0;iN；i+)foo(i),用户只需编写如下的一个程序：用户只需编写如下的一个程序：pidmy_process_id();numproc=number_of_processes();for(i:=pid;iN;i=i+numproc)foo(i);此程序经编译后成为可执行程序此程序经编译后成为可执行程序A A，通过执行命令：，通过执行命令：ru

49、n A numnodes n 可将它装到可将它装到n个结点中。个结点中。应注意的是：对用户来讲，单代码方法更加容易，且它允许应注意的是：对用户来讲，单代码方法更加容易，且它允许相同程序在不同相同程序在不同的结点数上以的结点数上以SPMDSPMD方式重复地加以执行。方式重复地加以执行。在顺序程序的基础上加上在顺序程序的基础上加上进行交互的库调用进行交互的库调用本讲稿第四十八页，共八十二页并行性问题并行性问题4、数据并行构造、数据并行构造在数据并行语言中（如在数据并行语言中（如Fortran 90Fortran 90和和HPFHPF），），SPMD SPMD并行性可用数据并行构并行性可用数据并行构

50、造加以说明。造加以说明。例如，要说明并行循环：例如，要说明并行循环：parforparfor(i:=1;i=N;i+)Ci=Ai+Bi;(i:=1;i=N;i+)Ci=Ai+Bi;用户可用用户可用1 1条赋值语句：条赋值语句：C=A+BC=A+B 或或 用以下循环来表示用以下循环来表示：forall(i=1,N)Ci=Ai+Bi;forall(i=1,N)Ci=Ai+Bi;本讲稿第四十九页，共八十二页静态和动态并行性静态和动态并行性 如果一个程序的结构以及组成进程的个数在运行之前就可确定时，就如果一个程序的结构以及组成进程的个数在运行之前就可确定时，就认为该程序具有认为该程序具有静态并行性静态