《第2章并行编程基础优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章并行编程基础优秀课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章 并行编程基础第1页，本讲稿共82页第第2章章 并行编程基础并行编程基础2.1 2.1 并行编程综述并行编程综述2.2 2.2 进程、任务和线程进程、任务和线程2.3 2.3 并行性问题并行性问题2.4 2.4 交互交互/通信问题通信问题2.5 2.5 并行程序中的语义问题并行程序中的语义问题第2页，本讲稿共82页并行编程基础并行编程基础并行编程综述并行编程综述并行编程缘何艰难并行编程缘何艰难1、并行软件一直落后的主要原因是并行编程比起顺序编程来是一个更复杂的智并行软件一直落后的主要原因是并行编程比起顺序编程来是一个更复杂的智力活动。它包含了顺序编程中的所有问题，还要加上在智力上更具挑战
2、性的力活动。它包含了顺序编程中的所有问题，还要加上在智力上更具挑战性的许多其他问题。许多其他问题。2、顺序编程只有一个基本模型（冯诺依曼模型），而、顺序编程只有一个基本模型（冯诺依曼模型），而并行编程中却有许多不同并行编程中却有许多不同的模型。的模型。3、开发顺序程序的软件环境工具，如编译器、调试程序、以及特征分析器，要、开发顺序程序的软件环境工具，如编译器、调试程序、以及特征分析器，要比并行程序的先进得多。比并行程序的先进得多。4、比起并行编程来，有更多的人一直在从事顺序编程而且已有长得多的时间。、比起并行编程来，有更多的人一直在从事顺序编程而且已有长得多的时间。对顺序编程由于已积累了大量知
3、识，包括过去所发现的错误以及所得到的教对顺序编程由于已积累了大量知识，包括过去所发现的错误以及所得到的教训，因此更为成熟。训，因此更为成熟。第3页，本讲稿共82页2.1 并行编程综述并行编程进展并行编程进展面向超级计算机的编程模型正集中趋向于两种模型：面向超级计算机的编程模型正集中趋向于两种模型：1 1）适用于）适用于PVPPVP、SMPSMP、DSMDSM的单地址空间的的单地址空间的共享变量共享变量模型模型；2 2）适用于）适用于MPPMPP和机群的多地址空间的和机群的多地址空间的消息传递模型消息传递模型。SIMD模型原已从主流超级计算机中淡出，但对于如同语言、图象和多媒体模型原已从主流超级
4、计算机中淡出，但对于如同语言、图象和多媒体处理的专用嵌入式那些应用仍非常有用。处理的专用嵌入式那些应用仍非常有用。-尤其是多核芯片的问世，以尤其是多核芯片的问世，以SIMD模型模型为基础，未来的通用计算机为基础，未来的通用计算机编程将带来很大的改进编程将带来很大的改进。第4页，本讲稿共82页并行编程综述并行编程进展并行编程进展 高层并行编程模型正集中趋向于高层并行编程模型正集中趋向于4种标准模型：种标准模型：1 1）数据并行数据并行（如（如HPFHPF）2 2）消息传递消息传递（如（如PVMPVM和和MPIMPI）3 3）共享变量共享变量（如（如ANSI X3H5ANSI X3H5）4 4）蕴
5、式并行模型蕴式并行模型，用户只需编写顺序程序，其中的蕴式并行性由并行化，用户只需编写顺序程序，其中的蕴式并行性由并行化编译器（如编译器（如KapKap）进行析取。）进行析取。图图1吞吐率处理吞吐率处理 减少单个并行应用的响应时间减少单个并行应用的响应时间 增加多个独立顺序作业的系统吞吐率增加多个独立顺序作业的系统吞吐率第5页，本讲稿共82页并行编程基础并行编程基础并行编程环境并行编程环境 并行处理系统的组成部分并行处理系统的组成部分 图图2并行编程环境工具：并行编程环境工具：作业管理工具作业管理工具调试工具调试工具性能工具性能工具第6页，本讲稿共82页并行编程基础并行编程基础 并行编程方法并行
6、编程方法 目前在实际的并行计算中广泛使用的并行编程模型有目前在实际的并行计算中广泛使用的并行编程模型有4种：种：蕴蕴式并行模型、数据并行、式并行模型、数据并行、消息传递、共享变量消息传递、共享变量 这些并行编程模型均已在实际的并行编程系统中得到实现，绝大部这些并行编程模型均已在实际的并行编程系统中得到实现，绝大部分为扩展的分为扩展的Fortran或扩展或扩展C。对于顺序编程有三种扩展并行性的方法：对于顺序编程有三种扩展并行性的方法：库子程序、新语言构造库子程序、新语言构造、编译器命令编译器命令。第7页，本讲稿共82页并行编程基础并行编程基础 库子程序：库子程序：除了在顺序语言中可用的标准库外，
7、除了在顺序语言中可用的标准库外，加入一组新的库函数，加入一组新的库函数，以支持并行化和交互操作。以支持并行化和交互操作。这种库的实例包括这种库的实例包括:消息传递消息传递(MPI)和和 多线程库多线程库(POSIX Pthreads)。新构造：新构造：扩展程序设计语言扩展程序设计语言使其具有某些新构造，以支持并行化和交互。使其具有某些新构造，以支持并行化和交互。例如例如Fortran 90中密集数报操作。中密集数报操作。编译器命令：编译器命令：程序设计语言不变，但程序设计语言不变，但加入称为编译器命令加入称为编译器命令（或（或pragmas）的格式化注解的格式化注解。第8页，本讲稿共82页三种
8、并行化方式举例三种并行化方式举例:for(i=0;iN;i+)Ai=bi*bi+1;for(i=0;iN;i+)ci=Ai+Ai+1;(a)(a)串行代码段串行代码段三种并行化方式举例第9页，本讲稿共82页并行编程基础并行编程基础所有所有3 3个程序均执行相同的如图个程序均执行相同的如图a a所示的串行所示的串行C C代码的计算。代码的计算。（1）图图b说明了说明了库方法库方法 其中两个循环被分配到其中两个循环被分配到P个过程并行执行个过程并行执行。由两个库函数：。由两个库函数：my_process_id()和和number_of_processes()开发并行性。开发并行性。路障路障barr
9、ier()函数保证在第函数保证在第1个循环后，所有进程同步，个循环后，所有进程同步，这样第这样第2个循环将使用在第一个循环中已更新的数组个循环将使用在第一个循环中已更新的数组A的正确值。的正确值。第10页，本讲稿共82页 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)使用使用库例程库例程的等效并行代码的等效并行代码三种并行化方式第11页，本讲稿共82页并行编程基础并行编程基础（2）若使用新的语言构造）若使用新
10、的语言构造 使用新的语言构造使用新的语言构造,上述的这些并行操作就可变得相当简单，上述的这些并行操作就可变得相当简单，如图如图c所示。所示。Fortran 90的的数组赋值构造数组赋值构造A(0:N-1)=b(0:N-1)*b(1:N)可在可在1条数组赋值语句中完成条数组赋值语句中完成N个元素乘法和赋值个元素乘法和赋值。在两个数组赋值之间，。在两个数组赋值之间，不需要显式同步，因为不需要显式同步，因为Fortran 90语句是语句是松散同步松散同步：在下一语句开始：在下一语句开始执行前，前一语句中的操作必须都已完成。执行前，前一语句中的操作必须都已完成。第12页，本讲稿共82页my_proce
11、ss_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 中使用中使用数组操作数组操作的等效代码的等效代码三种并行化方式第13页，本讲稿共82页并行编程基础并行编程基础（3）图图d编译器命令方法编译器命令方法 由并行由并行pragma指明下一语句（以块形式出现）应并行执行。指明下一语句（以块形式出现）应并行执行。由共享由共享(shared)pragma说明说明3个数组变量为并行进程共享，而局部个数组变量为并行进程共享，而局部pra
12、gma则用来指明每个进程有一个局部的变量。则用来指明每个进程有一个局部的变量。SGI的的pfor pravgma命令系统命令系统以并行方式执行下一循环。而由同步以并行方式执行下一循环。而由同步pragma产生一个路障同步。产生一个路障同步。第14页，本讲稿共82页#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#pragma pfor iterate(i=0;N;1)for(i=0;iN;i+
13、)ci=Ai+Ai+1;(d)SGI power C(d)SGI power C中使用中使用pragmapragma的等效代码的等效代码三种并行化方式第15页，本讲稿共82页并行编程基础并行编程基础 下表中总结了下表中总结了3 3种方法的优缺点。由于容易实现，种方法的优缺点。由于容易实现，库例程是目前使库例程是目前使用最广泛的方法用最广泛的方法所有并行化和交互功能由附加到顺序所有并行化和交互功能由附加到顺序C C或或FortranFortran的一组的一组程序实现。因此就无需实现新的编译器。然而由于没有编译器支持，用户就程序实现。因此就无需实现新的编译器。然而由于没有编译器支持，用户就丧失了编
14、译时间分析、错误检查和优化的机会。丧失了编译时间分析、错误检查和优化的机会。方法实例优点缺点库例程MPI,PVM,Cray Craft易于实现，不需要新编译器无编译器检查、分析和优化新构造Fortran90,Cray Craft允许编译器检查、分析和优化实现困难，需要新编译器命令HPF,Cray Craft介于库例程和新构造方法之间，在串行平台上不起作用第16页，本讲稿共82页2.2 进程、任务和线程进程、任务和线程抽象进程的定义抽象进程的定义定义定义2.1 一个进程一个进程P是一个是一个4元组元组P=（p,C,D,S）其中其中p是程序（或代码），是程序（或代码），C是控制状态，是控制状态，D
15、为数据状态，为数据状态，S为进程为进程P的状态。的状态。进程是动态的，其中它不单是指代码和数据是动态的，而且还包含正在执进程是动态的，其中它不单是指代码和数据是动态的，而且还包含正在执行的思想。行的思想。第17页，本讲稿共82页进程、任务和线程进程、任务和线程 任何进程与一个程序相关，作为一个例子，考虑如下的任何进程与一个程序相关，作为一个例子，考虑如下的C代码：代码：main（）（）int i=0;fork();fork();printf(“Hello！n”);我们可如下编译此程序（假设它在文件我们可如下编译此程序（假设它在文件hello.c中）中）:cc-o Hi hello.c，并可用简
16、单命令：并可用简单命令：Hi 执行它。执行它。第18页，本讲稿共82页进程、任务和线程进程、任务和线程 操作系统将操作系统将创建一个输出创建一个输出hellohello的进程的进程。除了由用户提供的显。除了由用户提供的显式代码外，进程还使用运行时间支持、库例程以及系统函数。上述进程称式代码外，进程还使用运行时间支持、库例程以及系统函数。上述进程称为为Printf（），它是（），它是C语言标准语言标准I/O库中的例程，以及库中的例程，以及fork(),它是它是Unix系统系统的一个调用。的一个调用。控制和数据状态控制和数据状态 大多数程序基于大多数程序基于命令式机器模型命令式机器模型，其中新概念
17、是，其中新概念是状状态更新态更新。一个命令式程序可看成是一个状态机（或一个自动机），它将程序从初一个命令式程序可看成是一个状态机（或一个自动机），它将程序从初始状态映射到一个或多个最后状态。始状态映射到一个或多个最后状态。第19页，本讲稿共82页进程、任务和线程进程、任务和线程 定义定义2.22.2 一个程序使用两个变量集：一个程序使用两个变量集：数据变量数据变量由程序员声明用来保存数据值的变量；由程序员声明用来保存数据值的变量；控控制变量制变量是保存控制信息的变量，它们不需要显式说明。是保存控制信息的变量，它们不需要显式说明。换言之，控制变量保存的是有关下一步应执行什么操换言之，控制变量保存
18、的是有关下一步应执行什么操作的信息。作的信息。数据变量集和控制变量集两者的合集形成了程序变量集。数据变量集和控制变量集两者的合集形成了程序变量集。第20页，本讲稿共82页进程、任务和线程进程、任务和线程 定义定义2.32.3 在任何时候，一个程序的每个数据或控制变量需与一个值在任何时候，一个程序的每个数据或控制变量需与一个值配为一对，该值可能是一个未定义的特殊值。在时间配为一对，该值可能是一个未定义的特殊值。在时间t t时所有（数据时所有（数据变量、数据值）的配对集定义了变量、数据值）的配对集定义了时间时间t t的程序数据状态的程序数据状态。类似地，。类似地，时间时间t t的所有（控制变量，控
19、制值）配对集定义了时间的所有（控制变量，控制值）配对集定义了时间t t的程的程序控制状态。因此，序控制状态。因此，时间时间t t的程序状态是的程序状态是t t时间的数据状态和时间的数据状态和控制状态的和。控制状态的和。或者我们可以说或者我们可以说t t时的程序状态是所有（程序时的程序状态是所有（程序变量、值）的配对集。变量、值）的配对集。第21页，本讲稿共82页进程、任务和线程进程、任务和线程 定义定义2.42.4 程序从初始状态启动。程序从初始状态启动。当执行了程序的一个原子操作后，程序就从当执行了程序的一个原子操作后，程序就从当前状态转为下一状态当前状态转为下一状态。程序不断执行原子操作并
20、不断更新其状态，直至终。程序不断执行原子操作并不断更新其状态，直至终止。此时程序处在最后状态。止。此时程序处在最后状态。这样一个命令式程序可视为是这样一个命令式程序可视为是产生一个或多个序列的原子操产生一个或多个序列的原子操作作，它们将状态机从初始状态转换到最后状态。，它们将状态机从初始状态转换到最后状态。当一个程序进入一个被确认不会终结的状态时，则说该程序当一个程序进入一个被确认不会终结的状态时，则说该程序进入了进入了发散状态。发散状态。第22页，本讲稿共82页进程、任务和线程进程、任务和线程 我们可把控制变量当作程序计数器。对具有单控制线程的进程来讲，我们可把控制变量当作程序计数器。对具有
21、单控制线程的进程来讲，它只有一个控制变量：程序计数器；它只有一个控制变量：程序计数器；而对有多控制线程的进程而言，而对有多控制线程的进程而言，它它有多个控制变量有多个控制变量，每个线程有一个每个线程有一个，它含有该线程的程序计数器值；，它含有该线程的程序计数器值；对于多子进程情况，整个进程可有若干个控制变量，对于多子进程情况，整个进程可有若干个控制变量，每个子进程有每个子进程有一个。一个。在用户程序中，在用户程序中，数据变量可用蕴式或显式方式说明。数据变量可用蕴式或显式方式说明。例例如，如，UnixUnix进程的数据变量含有隐藏的文件指针进程的数据变量含有隐藏的文件指针stdinstdin、s
22、tdoutstdout以及以及stderrstderr各自用作标准输入、标准输出和标准错误，它们可显式地各自用作标准输入、标准输出和标准错误，它们可显式地加以说明。加以说明。第23页，本讲稿共82页进程状态进程状态在任何时间，进程具有某个状态：在任何时间，进程具有某个状态：图图4 开始时，进程不存在（为开始时，进程不存在（为不存在状态不存在状态）。当它的创建者，父进程执行）。当它的创建者，父进程执行进程创建操作后，它才出现。一个新创建的子进程准备执行，但仅在被调进程创建操作后，它才出现。一个新创建的子进程准备执行，但仅在被调度后，它方可开始度后，它方可开始运行运行（执行其代码）。在进程运行中可
23、能发生以下（执行其代码）。在进程运行中可能发生以下几种情况：几种情况：由于页面失挂或其他情况，它无法继续执行时，就被挂起，从而由于页面失挂或其他情况，它无法继续执行时，就被挂起，从而进入进入挂起状态挂起状态。第24页，本讲稿共82页进程状态进程状态在任何时间，进程具有某个状态：在任何时间，进程具有某个状态：一个正在运行进程可能被具有更高优先级的另一进程抢占，或一个正在运行进程可能被具有更高优先级的另一进程抢占，或者它可能已用完分配给它的者它可能已用完分配给它的CPUCPU时间片（到时）。不论是哪种情况，时间片（到时）。不论是哪种情况，进程本身能（准备）继续执行，但它被强制放弃进程本身能（准备）
24、继续执行，但它被强制放弃CPUCPU资源并转换其资源并转换其状态成为状态成为就绪就绪。最后，一个正在运行的进程能终止本身，或是正常地在它完成代码执行后，最后，一个正在运行的进程能终止本身，或是正常地在它完成代码执行后，或是异常地（夭折）终止，并停止存在。或是异常地（夭折）终止，并停止存在。另一个经常使用的操作是另一个经常使用的操作是进程切换进程切换，它是指将一个正常运行的进程，它是指将一个正常运行的进程转换成或是转换成或是挂起挂起或是或是就绪就绪状态，并调度下一个就绪的进程运行。状态，并调度下一个就绪的进程运行。第25页，本讲稿共82页进程状态进程状态 在实际的操作系统和并行编程环境中，由于还
25、有附在实际的操作系统和并行编程环境中，由于还有附加的其他状态，因而情况更为复杂。加的其他状态，因而情况更为复杂。以上提及的进程概念很适合于需要使用并行语言的用户。以上提及的进程概念很适合于需要使用并行语言的用户。对于那些要实现进程并行概念者，就需要更为详细的进程观。对于那些要实现进程并行概念者，就需要更为详细的进程观。在实现进程并行运行时，还必须考虑以下各方面：在实现进程并行运行时，还必须考虑以下各方面：执行方执行方式、地址空间、现场进程描述符和进程控制。式、地址空间、现场进程描述符和进程控制。第26页，本讲稿共82页进程状态进程状态寻找工作状态：寻找工作状态：一个进程根据其是否已完成执行，可
26、以进入一个进程根据其是否已完成执行，可以进入寻找工作状寻找工作状态态，若向这个未被雇佣的进程分配某个新工作时，它就被，若向这个未被雇佣的进程分配某个新工作时，它就被激活了。激活了。可减少由于一个进程结束后接着再被创建去从事一项可减少由于一个进程结束后接着再被创建去从事一项新工作时所需的开销。新工作时所需的开销。适用于共享存储器模型的并行编程。适用于共享存储器模型的并行编程。第27页，本讲稿共82页线线 程程 概概 念念线线 程程：指控制线程：指控制线程逻辑组成由：程序代码、逻辑组成由：程序代码、一个程序计数器、一个程序计数器、一个调用堆栈、适量的专一个调用堆栈、适量的专用数据（包括通用寄存器）
27、。用数据（包括通用寄存器）。线线 程共享对存储器的访问，所以线程之间能够通过读或写对它们都程共享对存储器的访问，所以线程之间能够通过读或写对它们都可见的存储器互相通信。可见的存储器互相通信。线线 程也可共享对文件系统的访问。程也可共享对文件系统的访问。用线程进行程序设计被称为：用线程进行程序设计被称为：基于线程的并行程序设计基于线程的并行程序设计；或被称为：或被称为：共享存储器共享存储器并行程序设计并行程序设计 第28页，本讲稿共82页线程线程由进程创建的一种轻型进程，线程相对于进程，犹如进程相对于机器。同一进程的所有线程共享地址空间同一进程的所有线程共享地址空间有程序计数器和堆栈有程序计数器
28、和堆栈像进程一样共享处理机像进程一样共享处理机线程可以创建子线程线程可以创建子线程当一个线程被阻塞时，可调度运行同一进程中的另一线程当一个线程被阻塞时，可调度运行同一进程中的另一线程每个线程能读写，甚至清除另一线程的堆栈，线程之间没有保护每个线程能读写，甚至清除另一线程的堆栈，线程之间没有保护线程的状态：运行、阻塞、就绪、结束线程的状态：运行、阻塞、就绪、结束下一页第29页，本讲稿共82页每个进程的项目地址空间全局变量打开的文件子进程计时器标志信号量计算信息每个线程的项目程序计数器堆栈寄存器组子线程状态第30页，本讲稿共82页引入线程是为了将并行性引入顺序执行的系统。下图是线程与进程的三种组织
29、派遣者/工作者模型团队模型管道线模型文件服务器进程工作者线程共享块cache工作请求到达邮箱派遣者线程内核 线程的用途线程的用途下一页用线程构造服务器进程的三种方法第31页，本讲稿共82页模 式特性线程并行，阻塞系统调用单线程进程不并行，阻塞系统调用有限状态机并行，非阻塞系统调用第32页，本讲稿共82页与线程相关的用户可得的原语集（即库调用）与线程相关的用户可得的原语集（即库调用）线 程 包：线程管理：静态设计，程序编写或编译时就确定线程个数。每个线程分配一个固定静态设计，程序编写或编译时就确定线程个数。每个线程分配一个固定堆栈。堆栈。动态设计，允许线程在运行过程中动态的创建和回收动态设计，允
30、许线程在运行过程中动态的创建和回收线程结束：自己退出自己退出 被外界中止被外界中止共享数据：互斥变量，使用锁解决临界区数据共享问题互斥变量，使用锁解决临界区数据共享问题 条件变量，解决同步问题，避免死锁条件变量，解决同步问题，避免死锁全局变量：分配一块内存给全局变量，并将它作为一个参数传递给线程中的每一个过分配一块内存给全局变量，并将它作为一个参数传递给线程中的每一个过程程引入新的库过程来创建、设置和读取这些线程全局变量引入新的库过程来创建、设置和读取这些线程全局变量线程调度：优先级法优先级法 轮转法轮转法线程包的设计问题线程包的设计问题第33页，本讲稿共82页有两种方法：在用户空间实现和在操
31、作系统内核实现线程包的实现线程包的实现用户空间内核空间运行期系统内核内核内核空间用户空间线程0线程1线程2线程3线程4线程0线程1线程2线程3线程4(a)用户级线程包(b)由内核管理的线程包下一页第34页，本讲稿共82页在用户空间中实现线程在用户空间中实现线程在用户空间中实现线程：在用户空间中实现线程：将线程包完全放到用户空间中去，内核对此一无所知将线程包完全放到用户空间中去，内核对此一无所知线程运行在运行期系统的上层，运行期系统是一些管理线程的过程集线程运行在运行期系统的上层，运行期系统是一些管理线程的过程集线程执行系统调用时进入休眠，由运行期系统接管控制权，它负责线程的切换线程执行系统调用
32、时进入休眠，由运行期系统接管控制权，它负责线程的切换优点优点：能够在不支持线程的操作系统中实现能够在不支持线程的操作系统中实现系统开销小，线程切换可用有限的几条指令完成系统开销小，线程切换可用有限的几条指令完成允许每一个进程有自己定制的调度算法允许每一个进程有自己定制的调度算法难以实现阻塞系统调用难以实现阻塞系统调用线程调度是非抢先式调度，如果线程一直运行，运行期系统就得不到控制权线程调度是非抢先式调度，如果线程一直运行，运行期系统就得不到控制权缺点缺点：第35页，本讲稿共82页内核知道并管理线程。当一个线程想去创建一个新线程或撤销已存在的线程时，它内核知道并管理线程。当一个线程想去创建一个新
33、线程或撤销已存在的线程时，它发出一个内核的调用，由它完成创建和回收工作发出一个内核的调用，由它完成创建和回收工作在内核中每个进程都有一张表，每个线程在表中有一个入口，每个入口保存着线程在内核中每个进程都有一张表，每个线程在表中有一个入口，每个入口保存着线程的寄存器、状态、优先权和其他信息的寄存器、状态、优先权和其他信息当一线程阻塞时，内核可以调用同一进程中的其它线程，也可以调用另一个进程的当一线程阻塞时，内核可以调用同一进程中的其它线程，也可以调用另一个进程的线程线程按系统调用来实现线程的阻塞调用，但开销较大按系统调用来实现线程的阻塞调用，但开销较大在内核中实现线程：在内核中实现线程：优点：优
34、点：缺点缺点：不需要任何新的非阻塞系统调用不需要任何新的非阻塞系统调用 不易产生死锁不易产生死锁产生页面错时，系统能很容易地运行另一线程产生页面错时，系统能很容易地运行另一线程系统调用耗费大系统调用耗费大下一页在内核中实现线程在内核中实现线程第36页，本讲稿共82页模拟内核线程的功能，使用户空间内实现的线程包调度有更好的性能和有模拟内核线程的功能，使用户空间内实现的线程包调度有更好的性能和有更大的灵活性。更大的灵活性。目目 标：标：内核分配一定数量的虚拟处理机给每个进程，并且让运行期系统将线程分配给处内核分配一定数量的虚拟处理机给每个进程，并且让运行期系统将线程分配给处理机理机 当内核知道一个
35、线程已阻塞时，内核将通过将这个线程的号码和所发生事件的当内核知道一个线程已阻塞时，内核将通过将这个线程的号码和所发生事件的描述作为参数传递到堆栈，通知该进程的运行期系统描述作为参数传递到堆栈，通知该进程的运行期系统 运行期系统一旦被激活，它就能重新调度线程运行期系统一旦被激活，它就能重新调度线程 当一个用户线程在运行产生一个硬件中断时，被中断的当一个用户线程在运行产生一个硬件中断时，被中断的CPUCPU切换进入内核模式处切换进入内核模式处理理实现方法：实现方法：下一页调度者行为第37页，本讲稿共82页在线程上可以运行更轻量级的在线程上可以运行更轻量级的RPCRPC。方法：方法：当服务器线程当服
36、务器线程S S启动时，输出它的接口通知内核启动时，输出它的接口通知内核 需要服务的客户线程需要服务的客户线程C C启动后，从内核中取出启动后，从内核中取出S S的服务接口，并获得该调用的标的服务接口，并获得该调用的标识识 由内核创建专用数据结构来为调用由内核创建专用数据结构来为调用S S做准备。其中包括共享堆栈做准备。其中包括共享堆栈 线程线程C C将参数压入堆栈，然后自陷进入内核将参数压入堆栈，然后自陷进入内核 内核根据参数判断调用是否在本地，如在本地，更改客户内存映像，将客户放内核根据参数判断调用是否在本地，如在本地，更改客户内存映像，将客户放入服务器的地址空间，启动客户线程执行服务器过程
37、入服务器的地址空间，启动客户线程执行服务器过程思想：思想：在线程上进行远程过程调用（RPC）第38页，本讲稿共82页线线 程程 概概 念念进进 程程：拥有私有地址空间拥有私有地址空间进程之间的互相通信需要借助传递消息进程之间的互相通信需要借助传递消息；也可借助文件系统（但很少）也可借助文件系统（但很少）在并行计算中，用进程进行程序设计被称为：在并行计算中，用进程进行程序设计被称为：基于传递消息的并行程序设计基于传递消息的并行程序设计或被称为：或被称为：非共享存储器并行程序设计非共享存储器并行程序设计进程趋向长期生存，而线程则随着计算的进行动态派生或销毁进程趋向长期生存，而线程则随着计算的进行动
38、态派生或销毁第39页，本讲稿共82页2.3并行性问题并行性问题及解决方法及解决方法 进程中的同构性进程中的同构性-指并行程序中各分进程的相似性。指并行程序中各分进程的相似性。有有3 3种基本类型：种基本类型：SPMD：在单程序多数据（在单程序多数据（SPMD）程序中的）程序中的分进程是分进程是同构同构的。因为多个进程在不同的数据范畴内的。因为多个进程在不同的数据范畴内执行相同代码执行相同代码。程序。程序由数据并行构造，也称由数据并行构造，也称SPMD为为数据并行程序。数据并行程序。（如（如Fortran Fortran 9090）MPMD：在多程序多数据（在多程序多数据（MPMD）程序中的）程
39、序中的分进程是分进程是异构异构的。因为多个进程可以的。因为多个进程可以执行不同代码执行不同代码。也称。也称MPMD为为功功能并行程序、任务并行、控制并行。能并行程序、任务并行、控制并行。SPMDSPMD和和MPMDMPMD可以混用。可以混用。第40页，本讲稿共82页并行性问题并行性问题及解决方法及解决方法有有3 3种基本类型：种基本类型：SIMD：SPMDSPMD和和MPMDMPMD程序，两者都是程序，两者都是MIMDMIMD类型的程类型的程序序。因为在同一时间不同指令由不同进程加以执行。因为在同一时间不同指令由不同进程加以执行。而一个而一个SIMD程序比程序比SPMD更加严格，因为多个过程不
40、但必须执行相同更加严格，因为多个过程不但必须执行相同代码，而且它们全体必须在同一时间执行相同的指令。换句话代码，而且它们全体必须在同一时间执行相同的指令。换句话说，说，SIMD程序是程序是 SPMD程序的一个特例。程序的一个特例。第41页，本讲稿共82页并行性问题并行性问题及解决方法及解决方法 SPMD程序通常用：程序通常用：并行循环构造、数据并行构造或并行循环构造、数据并行构造或单单代码方式加以说明。代码方式加以说明。MPMD程序通常用程序通常用:并行块构造、并行块构造、多代码多代码方式加以说明。方式加以说明。下面分别介绍这几种并行构造方法第42页，本讲稿共82页2.3并行性问题并行性问题及
41、解决方法及解决方法1 1、并行块、并行块（parallel block)parallel block)表达表达MPMDMPMD程序的一个很自然的方法是使用程序的一个很自然的方法是使用parbeginparbegin和和parendparend构造：构造：Parbegin SParbegin S1 1S S2 2SSn n Parend Parend 它们它们总是成对使用。总是成对使用。这种结构化的构造也称为：这种结构化的构造也称为：cobegin Scobegin S1 1S S2 2SSn n coend coend它被称为是一个它被称为是一个并行块并行块，其中，其中 S S1 1S S2
42、2SSn n 是分进程，可含有是分进程，可含有不同不同代代码。码。当并行块执行时，它的当并行块执行时，它的n n个分进程个分进程S S1 1S S2 2SSn n就开始同时执行。它们的就开始同时执行。它们的执行是互相独立的而且以不同速率进行执行是互相独立的而且以不同速率进行。当所有当所有n n个分进程终止时，并行块才能终止。个分进程终止时，并行块才能终止。之所以命名为并行块是为了与顺序块相对照，后者在传统的顺序语言中之所以命名为并行块是为了与顺序块相对照，后者在传统的顺序语言中可以找到：可以找到：begin Sbegin S1 1S S2 2SSn n end end。第43页，本讲稿共82页
43、并行性问题并行性问题2 2、并行循环、并行循环（parallel loop）当当并行块中的所有进程共享相同代码并行块中的所有进程共享相同代码时，我们用一个称时，我们用一个称为并行循环的速记记号来标明如下并行块：为并行循环的速记记号来标明如下并行块：Parbegin Process(1)Process(n)Parend 可被简化成如下的并行循环：可被简化成如下的并行循环：Parfor(i=1;i=n;i+)Process(i)并行循环常用来说明并行循环常用来说明SPMDSPMD并行程序。并行程序。第44页，本讲稿共82页并行性问题并行性问题 系统程序（如操作系统或网络系统）中的进程通常是异系统程
44、序（如操作系统或网络系统）中的进程通常是异构的。许多并行计算程序，特别是大规模并行计算机中的并构的。许多并行计算程序，特别是大规模并行计算机中的并行程序，是高度同构的。行程序，是高度同构的。要为有要为有1000个处理器的计算机编写一个完全异构的并行程序将是很困难的，个处理器的计算机编写一个完全异构的并行程序将是很困难的，因为我们需要为每个处理器写一个不同程序。因为我们需要为每个处理器写一个不同程序。对于一个分布对于一个分布/并行编程环境而言，希望能同时提供同并行编程环境而言，希望能同时提供同构和异构进程。但是对于扩展并行机来讲，通常只要支持构和异构进程。但是对于扩展并行机来讲，通常只要支持SP
45、MDSPMD就足够了。在多核时代尤其如此。就足够了。在多核时代尤其如此。第45页，本讲稿共82页并行性问题并行性问题当不同的代码数较小时，我们可以用当不同的代码数较小时，我们可以用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；第46页，本讲稿共82页并行性问题并行性问题3、多代码与单代码、多代码与单代码（Multi-Code versus Single Code）在目前
46、的并行计算机，特别是在目前的并行计算机，特别是MPP和和COW上，上，许多编程语言不提许多编程语言不提供并行块或并行循环构造。供并行块或并行循环构造。在这种系统中，在这种系统中，MPMD并行性可用多代并行性可用多代码方法加以说明来解决码方法加以说明来解决。例如，要说明例如，要说明parbeginAparbeginA；B B；C C；parend parend，用户需编写，用户需编写3 3个程序个程序,并将并将它们编译以生成三个可执行程序它们编译以生成三个可执行程序A A、B B和和C C，用，用shellshell脚本脚本将它们装载将它们装载到到3 3个处理结点个处理结点中：中：run A o
47、n node 1run B on node 2run C on node 3程序程序A A、B B和和C C仅是顺序程序加上仅是顺序程序加上进行交互的库调用进行交互的库调用。第47页，本讲稿共82页并行性问题并行性问题SPMDSPMD程序可用单代码方法加以说明程序可用单代码方法加以说明来实现多节点并行来实现多节点并行。例如，要说明并行循环例如，要说明并行循环 parfor（i=0;iN；i+)foo(i),用户只需编写如下的一个程序：用户只需编写如下的一个程序：pidmy_process_id();numproc=number_of_processes();for(i:=pid;iN;i=i+
48、numproc)foo(i);此程序经编译后成为可执行程序此程序经编译后成为可执行程序A A，通过执行命令：，通过执行命令：run A numnodes n 可将它装到可将它装到n个结点中。个结点中。应注意的是：对用户来讲，单代码方法更加容易，且它允许应注意的是：对用户来讲，单代码方法更加容易，且它允许相同程序在不同相同程序在不同的结点数上以的结点数上以SPMDSPMD方式重复地加以执行。方式重复地加以执行。在顺序程序的基础上加上在顺序程序的基础上加上进行交互的库调用进行交互的库调用第48页，本讲稿共82页并行性问题并行性问题4、数据并行构造、数据并行构造在数据并行语言中（如在数据并行语言中（
49、如Fortran 90Fortran 90和和HPFHPF），），SPMD SPMD并行性可用数据并行并行性可用数据并行构造加以说明。构造加以说明。例如，要说明并行循环：例如，要说明并行循环：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;第49页，本讲稿共82页静态和动态并行性静态和动态并行性 如果一个程序的结构以及组成进程的个数在运行
50、之前就可确定时，就认为如果一个程序的结构以及组成进程的个数在运行之前就可确定时，就认为该程序具有该程序具有静态并行性静态并行性。（如在编译时间，连接时间或装载时间）否否则就说它具有则就说它具有动态并行性动态并行性，这就蕴含着哪些进程要在运行时间内，这就蕴含着哪些进程要在运行时间内创建和终止。创建和终止。静态并行程序显得需要较少的运行时间开销，因此比动态静态并行程序显得需要较少的运行时间开销，因此比动态并行程序有更高的效率。这是因为静态并行程序可免去许多并行程序有更高的效率。这是因为静态并行程序可免去许多初始化操作（如存储器分配、堆栈分配、系统表初始化等）。初始化操作（如存储器分配、堆栈分配、系