并行处理及分布式系统期末复习_分布式并行计算期末划重点

 1、任务并行

1.1什么是任务并行

一个程序是通过将任务划分给各个进程或者线程来实现并行的   。

划分的各个任务之间相互独立，不存在依赖或者存在依赖但是可以解决

任务并行的粒度比较大且通常通信很少或者没有，是线程级并行的理想选择                        

1.2任务并行的应用

任务并行不适合于向量化处理，（任务并行粒度比向量化需要的力度大）

如果同时存在任务并行和数据并行且每个任务内部存在数据并行，那么单个任务则更适合向量化并行处理。

网络服务器利用多线程并行处理多个访问请求是一种任务并行和多线程结合的应用场景

任务并行通常适用于在集群内运行，将不同的任务分配给集群中不同的计算节点，由于任务并行的通信通常比较少，故用于集群通常只需要增加任务分发机制，非常易于实现。由于通信少，能够获得近似线性的扩展，任务并行在分布式应用较多

1.3任务并行常见的问题

1.3.1负载均衡问题

负载均衡指的是在进行任务分配的时候使得每个进程/线程获得大致相等的工作量需要在进程/线程之间平均分配任务从而满足负载均衡条件。通常使用任务队列来解决负载均衡问题

1.3.2数据共享问题

由于任务并行是从任务的层次来获取并行性，这导致数据冲突的可能性很大，常见的解决办法是对数据加锁，必须要软件开发人员参与数据加锁。

2、数据并行

2.1什么是数据并行

通过将多个数据分配给多个处理器，然后通过让各个处理器使用相同的指令来操作数据子集实现并行化

对于串行的满足数据并行特点的代码进行并行化，通常可以采用两个类型：以输入数据为主和以输出数据为主。

2.2数据并行的应用

数据并行应用最广泛的是图形学算法

数据并行还可以应用于数据统计学要分析大量数据的时候

一些模拟计算，如分子动力学、天体物理、计算流体力学算法也具有数据并行的特点。

深度学习研究和应用也表现出数据并行的特点，如矩阵乘法和卷积

绝大对数满足数据并行特征的应有都可以向量化

数据并行也适合线程化，每个线程处理一批数据，不同线程处理不同批数据

在开发环境上，基于进程的、基于线程的环境，甚至指令级并行环境都可以很好地应用在数据并行上

2.3数据并行的类别

2.3.1向量化并行

是一种细粒度的并行计算，通常是一个指令作用于一个数组/向量，向量化并行是数据并行的一个细粒度子集，在某些情况下可以认为向量化并行是指令级的数据并行。

向量化并行适合处理图形图像、音频视频、游戏等应用程序，科学计算和模拟中也大量使用向量并行化，如分子动力学、计算金融、石油勘测等

2.3.2循环并行化

串行循环：如果某次循环必须等待其前面的循环执行完成才能够执行，这成为串行循环

并行训环：如果每次循环之间不存在依赖可以并行执行，称之为并行循环。 

一般情况下串行循环不能并行化，但是某些串行循环可变换成并行循环，而某些看起来不能并行的串行循环已经有很好的并行算法了。有一些循环看起来是串行循环，但是经过循环拆分可以变成并行循环。

3、冯诺依曼体系

3.1什么是冯诺依曼体系结构

经典的冯诺依曼结构包括：主存、中央处理单元（CPU）处理器或核，以及主存和CPU之间的互连结构。

主存中有许多个区域，每个区域都可以存储指令和数据。每个区域都有一个地址，可以通过这个地址来访问相应的区域以及区域内存储的数据和指令。

中央处理器分为控制单元和算术逻辑单元（ALU）。控制单元负责决定应该执行程序中的那些指令，而ALU负责执行指令。

CPU中的数据和程序执行时的状态信息存储在特殊的快速存储介质即寄存器中。控制单元有一个特殊的寄存器，叫做程序计数器，用来存放下一条指令的地址。

指令和数据通过CPU和主存之间的互连结构进行传输。这种互连结构通常是总线，总线中包括一组并行的线以及控制这些线的硬件。

冯诺依曼机器一次执行一条指令，每条指令对一个数据进行操作。

当数据或指令从主存传送到CPU时称为数据或指令从内存中取出或者读出。当数据或者指令从CPU传送到主存时称为数据或指令写入或者存入内存中。

3.2冯诺依曼体系结构的瓶颈

主存和CPU之间的分离称为冯诺依曼瓶颈。这是因为互连结构限定了指令和数据访问的速率。程序运行所需要的大部分数据和指令被有效的以CPU隔离开。

3.3冯诺依曼体系结构瓶颈的改进

3.3.1加入Cache

加入缓存，不再是一次传输一条指令或者一个数据，而是将互连通路加宽，使得一次内存访问能够传送更多的数据或者更多的指令。

不再是将所有的数据和指令存储在主存中，可以将部分数据块或者代码块存储在一个靠近CPU寄存器的特殊存储器里。

CPU Cache位于与CPU同一块的芯片或者位于其他芯片上，但比普通的内存芯片能更快的访问。

3.3.2使用虚拟存储器

虚拟存储器大小=不超过主存+部分外存

利用虚拟存储器（或虚拟内存）使得主存可以作为辅存的缓存。它通过将程序以分页或分段的方式切分，将当前运行的程序所需要用到的部分存放在内存中，来利用时间和空间局部性。那些暂时用不到的部分存储在辅存的块中，称为交换空间。

与CPUCache类似，虚拟存储器也是对数据块和指令块进行操作，这些块通常称为页，页的大小是固定的，从4-16kb不等。

3.3.3采用指令级并行（ILP）

指令级并行通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。

3.3.3.1流水线

流水线是指将功能单元分阶段安排。通过将功能分成多个单独的硬件或者功能单元，并把它们按顺序串接来提高性能。

k个阶段的流水线不可能达到k倍的性能提高。如果各种功能单元的运行时间不同，则每个阶段的有效运行时间取决于最慢的单元，此外有些延迟（例如等待操作数）也会造成流水线的阻塞。

3.3.3.2多发射

多发射是指让多条指令同时启动。通过复制功能单元来同时执行程序中的不同指令。

静态多发射：功能单元是在编译时调度的。

动态多发射：功能单元是在运行时间调度的。

超标量：一个支持动态多发射的处理器称为超标量。

为了能够利用多发射，系统必须找出能够同时执行的指令，最重要的技术是预测，在预测技术中，编译器或者处理器对一条指令进行预测，然后在猜测的基础上执行代码。

3.4局部性

局部性：程序访问完一个存储区域往往会访问接下来的区域，这个原理称为局部性。

在访问完一个内存区域（指令或者数据），程序会在不久的将来（时间局部性）访问邻近的区域（空间局部性）

4、Flynn分类法

4.1Flynn分类法涉及的几种模型

SIMD：单指令多数据流

SISD：单指令单一数据流

MISD：多指令单数据流

MIMD：多指令多数据流

4.2Flynn分类法涉及模型的特点

4.2.1SIMD

SIMD系统是并行系统。通过对多个数据执行相同的指令从而实现在多个数据流上的操作。（一个控制单元和多个ALU）一条指令从控制单元广播到多个ALU，每个ALU或者在当前数据上执行指令或者处于空闲状态。

在经典的SIMD系统中，ALU必须同步操作，即在下一条指令开始执行之前，每个ALU必须等待广播，ALU没有指令存储器，所以ALU不能通过存储指令来延迟执行指令。

SIMD系统适合于对处理大型数组的简单循环实行并行化。SIMD并行性在大型数据并行问题上非常有用，但是在处理其他并行问题时并不优秀。

4.2.1.1向量处理器

能够对数组或者数据向量进行操作，传统的CPU是对单独的数据元素或者标量进行操作。

向量寄存器：能够存储由多个操作数组成的向量，并且能够同时对其内容进行操作的寄存器，向量的长度由系统决定，从4到128个64位元素不等。

向量化和流水化的功能单元：对向量中的每个元素需要做同样的操作，或者某些类似于加法的操作，这些操作需要应用到两个向量中相应的元素对上，因此向量操作是SIMD。

向量指令：在向量上操作而不是在标量上操作的指令。如简单的向量加法，只需要一次加载、一次加法和一次存储操作就完成了对一个某长度的数据块的操作，而传统的系统系统需要对数据块中的每个元素单独进行加载、加法和存储操作。

交叉存储器：内存系统由多个内存体组成，每个内存体能够独立访问。如果向量中的各个元素分布在不同的内存体中，那么在装入/存储连续数据是能够几乎无延迟的访问。

步长式存储器访问和硬件散射/聚集：在步长式存储器访问中，程序能够访问向量中固定间隔的元素。散射/聚集是对无规律间隔数据进行读聚集和写散射。

4.2.2MIMD

MIMD系统通常包括一组完全独立的处理单元或者核，每个处理单元或者核都有自己的控制单元和ALU。，MIMD系统通常是异步的，即每个处理器能够按照自己的节奏运行。

主要有共享内存系统和分布式内存系统两种类型。

4.2.2.1共享内存系统

一组自治的处理器通过互联网络与内存系统相互连接，每个处理器能够访问每个内存区域。在共享内存系统中，处理器通过访问共享的数据结构来隐式的通信。

最广泛使用的共享内存系统使用一个或者多个多核处理器。一个多核处理器在一块芯片上有多个CPU或者核。通常每个核都拥有私有的L! Cache，而其他的Cache可以在核之间共享，也可以不共享。

通过处理器中内置的特殊硬件使得各个处理器可以访问内存中的其他块。

一致内存访问：芯片之间没有连接，访问其他内存时间相同，易于编程。

非一致内存访问：芯片之间存在直接连接，访问其他内存时间不定，失去易于编程的优点，有更大容量。

4.2.2.2分布式内存系统

最广泛使用的使用的分布式内存系统称为集群，由一组商品化系统组成（如PC），通过商品化网络连接（如以太网）。

这些系统中的节点（通过通信网络相互连接的独立计算单元）通常都是有一个或者多个多核处理器的共享内存系统。现在通常认为一个集群有多个共享内存节点。

5、关于Cache

5.1Cache的特点

容量一般在几千字节到几兆字节之间，速度一般比主存快五到十倍，其内容是主存局部域的副本，对程序员来说是透明的。

Cache分为不同的层，第一层（L1）最小但最快，跟高层Cache（L2、L3......）更大但相对较慢。

Cache通常用来存储速度较慢的存储器中信息的副本，可以认为低层Cache（更快、更小）是高层Cache的Cache。

5.1.1Cache访问特点

当CPU需要访问指令或者数据时，它会沿着Cache的层次结构向下查询：首先查询L1Cache，接着是L2Cache，以此类推，最后如果Cache中没有需要的信息，就会访问主存。

5.2Cache缺失

当向Cache中查询信息时，如果信息不存在，则称为Cache缺失或者缺失

5.3Cache命中

当向Cache中查询信息时，如果Cache中有信息，则称为Cache命中或者命中。

命中和缺失是相对Cache层而言的。

5.4Cache中的值与内存中的值不一致的解决办法

写直达：当CPU向Cache写数据时，高速缓存行会立即写入主存

写回：数据不是立即更新到主存中，而是将发生数据更新的高速缓存行标记成脏，当发生高速缓存行替换时，标记为脏的高速缓存行被写入主存中。

高速缓存行是Cache读写的处理单位。

5.5Cache映射

全相联：每个高速缓存行能够放置在Cache中的任意位置。

直接映射：每个高速缓存行在Cache中有唯一的位置。

n路组相联：每个高速缓存行都能放置到Cache中n个不同区域位置中的一个。

5.6Cache一致性及解决办法

5.6.1Cache一致性问题

在多核系统中，各个核的Cache存储相同变量的副本，当一个处理器更新Cache中该变量的副本时，其他处理器应该知道该变量已更新，即其他处理器中Cache的副本也应该更新，这称为Cache一致性问题。

5.6.2解决方法一——监听Cache一致性协议

当多个核共享总线时，总线上传递的信号都能被连接到总线的所有核看到。当某个核更新自己Cache中的某变量信息时，会在总线上广播告诉其他核该值所在的整个Cache行已经更新，其他核的Cache中若有该变量，会将自己核中的含有该值的Cache行标记为非法。

互连网络不一定必须是总线，只要能够支持从每个处理器广播到其他处理器就可以。

监听协议能够在写直达和写回Cache上都能工作。写直达不需要额外的互连网络，写回Cache需要额外的通信。

5.6.3解决方法二——基于目录的Cache一致性协议

在大型网络上，广播是非常昂贵的，监听Cache一致性协议每更新一个变量时就需要广播一次，所以监听Cache一致性协议是不可扩展的，因为对于大型系统，它会导致性能的下降。

基于目录的Cache一致性协议通过使用一个叫目录的数据结构来解决上面的问题。目录存储每个内存行的状态。这个目录标识局部内存对应高速缓存行的状态。

当一个高速缓存行被读入时，如核0的Cache，与这个高速缓存行相对应的目录项就会更新，表示核0有这个行的副本。当一个变量需要更新时，就会查询目录，并将所有包含该变量的高速缓存行置为非法。

5.7伪共享

CPU Cache是由硬件来实现的，硬件是对高速缓存行进行操作的而不是对单独的变量进行操作。

伪共享是满足cache一致性后引发的问题，线程并不共享任何东西(除了一个cache line),但线程对内存访问的行为好像它们正在共享一个变量,把这种现象命名为伪共享。

伪共享不会引起错误结果，但它会引起过多不必要的访存，降低程序的性能。

6、关于效率

6.1加速比

线性加速比：T并行=T串行/p    T并行：并行运行时间   T串行：串行运行时间    p：核数

不可能获得线性加速比。

并行程序的加速比S=T并行/T串行    线性加速比为S=p，

效率可以表示为：E=S/p=（T串行/T并行）/p=T串行/（p*T并行）

T并行、S、E依赖于p，即依赖于进程或线程的数目。T并行、S、E和T串行还依赖于问题的规模。

加速比S<P，效率E<1，固定问题规模，当P增加时，E通常会减小；固定进程/线程数量，增加问题规模时，S和E都会增加。

T并行=T串行/p+T开销

当问题规模不变时,随着处理器数量增大,效率降低的性质对所有并行算法成立，当处理器数量和问题规模同时增大,部分并行算法能保持效率恒定。

6.3阿姆达尔定律

阿达姆尔定律：除非一个串行程序的执行几乎全部都并行化，否则，不论有多少可以利用的核，通过并行化所产生的加速比都会是受限的。

如果使用p个核，假设程序可并行化部分的加速比就是p，该程序串行版本的运行时间是T串行，并行部分占总程序的比例为q，则可并行部分的运行时间是q*T串行/p，不可并行部分的运行时间为（1-q）*T串行，该程序的全部运行时间为：

T串行=（q*T串行）/p+（1-q）*T串行

加速比为

S=T串行/（（q*T串行）/p+（1-q）*T串行）

随着p的增加，程序并行部分的运行时间q*T串行/p会越来越趋向于0，但是程序并行版本的总运行时间不可能小于（1-q）*T串行，因此，加速比S≤T串行/（（1-q）*T串行）

总的说来，如果串行程序中有比例为r的部分不可并行化，则根据阿姆达尔定律可知，该程序能达到的最好加速比趋近于1/r，即趋近于不可并行化部分的倒数。

7、关于线程

7.1静态线程

主线程在完成必须的设置后，派生出所有的线程，在工作结束前所有的线程都在运行。当所有的线程都合并到主线程后，主线程需要做一些清理工作（如释放内存），然后自己也终止。在资源利用方面静态线程不是很高效，但是在考虑线程派生和合并操作耗时的情况下，静态线程很有优势。

7.2动态线程

有一个主线程，在任何时刻都有一组工作线程（可能为空），主线程通常等待工作请求（例如通过网络），当一个请求到达时它派生出一个线程来执行请求，当工作线程完成任务，就会终止执行再合并到主线程中。这种模式充分利用了系统资源，线程需要的资源只在线程实际运行时使用。

7.3非确定性

非确定性：给定的输入能产生不同的输出，这种计算称为非确定性。如果多个线程独立执行任务，每次运行时他们完成语句的速度各不相同，那么程序的结果也不同。

语句执行的顺序是不能预测的。

竞争条件：当线程或者进程尝试同时访问一个资源时，这种访问会引发错误，我们经常说这样的程序有竞争条件，因为线程或者进程处于竞争状态下。

临界区：一次只能被一个线程执行的代码块称为临界区，通常是由程序员负责来保证互斥的访问临界区。

保证互斥执行的最常用机制是互斥锁、互斥量、锁。互斥量是由硬件支持的一个特殊类型的对象。使用互斥量增强了临界区的串行性，因为在临界区中，一次只有一个线程能执行代码。

7.4伸缩性/可扩展性

增加程序所用的进程/线程数，如果在输入规模也以相应增长率增加的情况下，该程序的效率值一直是不变的，那么我们就称该程序是可扩展的。

强可扩展性：在增加进程/线程的个数时，可以维持固定的效率，却不增加问题的规模，那么程序称为强可扩展的。

弱可扩展性：如果在增加进程/线程个数的同时，只有以相同的倍率增加问题的规模才能使效率保持不变，那么程序称为弱可扩展的。

7.5数据依赖的识别

数据依赖：如果两个内存访问可能引用相同的内存位置并且其中一个引用是写操作，则它们涉及数据依赖

有依赖关系的语句，其中至少一条语句会有序地写或更新变量。因此为了检测循环依赖，我们只需要重点观察被循环体更新的变量，即我们应该寻找在一个迭代中被读或被写，而在另一个迭代中被写的变量。

数据依赖是对必须保留以保持正确性的一对内存操作的排序
数据依赖可以在两个不同的程序语句之间，也可以在同一程序语句的两个不同的动态执行之间

7.6任务划分方式

7.6.1静态任务分配

每个子任务分别实现一个子功能，子任务的数量有限。一个处理器/执行内核负责一个子任务。

子任务之间有两种形式关系：形式1：互相独立，各自处理不同的数据集合。形式2：构成一个流水线，依次对一组数据集合进行处理，数据集合的数量很大。

各个子任务的数据处理功能相同，各自处理不同的数据集合。

一个处理器/执行内核在开始数据处理之前，需要先确定处理的子任务有哪些。

7.6.2动态任务分配

处理器/执行内核完成一个子任务后，再分配一个新的子任务。

各个处理器/执行内核运行的算法要相同，都能实现子任务需要的数据处理功能。

子任务要相互独立，分别处理不同的数据集合

实现方式一：对等协同的动态任务分配：全部处理器/执行核扮演的角色都是相同的，采用“锁”机制实现“子任务池”的操作。

实现方式二：集中调度的动态任务分配：各个处理器扮演不同的角色，一个处理器/执行核专门负责“子任务池”的维护，其他处理器/执行核负责子任务的数据处理。采用“消息交换”机制实现子任务的分配。

7.7并行化步骤

1、划分：将要执行的指令和数据按照计算部分拆分成多个小任务。这一步的关键在于识别出可以并行执行的任务。

2、通信：确定上一步所识别出来的任务之间需要执行哪些通信。

3、凝聚或聚合：将第一步所确定出来的任务与通信结合成更大的任务。

4、分配：将上一步聚合好的任务分配到进程/线程中。这一步还要使通信量最小化，使各个进程/线程所得到的工作量大致均衡。

8、链表操作及分析

8.1链表并行存在的问题

对于链表函数来说，多线程同时执行Member操作，即读链表操作是没有问题的，但是当多个线程同时访问链表且至少有一个线程长在执行Insert或Delete操作，即写链表结点时，是不安全的。

8.2链表并行问题的解决方案

8.2.1 对链表加锁解决不安全问题

在调用链表的三个函数之前用互斥量来保护链表。

存在的问题：必须串行访问链表。对于大量进行Member操作的链表来说，并行效率会很低，失去了开发并行的机会。

优点：对于大量进行Insert或者Delete的链表来说这是最好的解决方案，这两个操作的大部分都需要串行执行，而且这个解决方案很容易实现。

8.2.2对链表上的结点上锁解决不安全问题

对链表上的单个结点上锁，而不是对整个链表上锁。每次访问一个结点时必须先对该节点加锁。每次访问一个结点时，必须先对该结点加锁。要求有一个与head_p相关联的互斥量。

存在的问题：实现比原来的方案更加复杂；由于每次访问一个结点时都必须对结点加锁和解锁，每一次的结点访问都至少要增加两次函数调用，所以它比原来的实现要慢；如果线程需要等待锁会增加延迟；由于每个结点都增加了一个互斥量域，这会导致整个链表存储量需求增加。

优点：细粒度锁是一个更接近需求的方案，只对当前感兴趣的结点加锁，所以多个线程能同时访问链表不同的部分，且与他们执行的操作无关。

8.2.3读写锁解决不安全问题

除了提供的锁函数是两个外，读写锁基本上与互斥量差不多。这两个锁函数一个为读操作对读写锁上锁，一个为写操作对读写锁上锁。多个线程能通过调用读锁函数而同时获得锁，但只有一个线程能通过写锁函数获得锁。如果任何线程拥有了读锁，则任何请求写锁的线程将阻塞在写锁函数的调用上。任何线程拥有了读锁，则任何想获取读或写锁的线程将阻塞在他们对应的锁函数上。

8.3不同实现方案性能对比

当线程数为1时，读写锁与单互斥量实现的执行时间是一样的，因为没有对读写锁和互斥量的竞争，这些操作是串行执行的，这两种实现的开销都包含对链表进行操作时两次额外的函数调用的开销。使用每个结点一个锁的实现比较慢，因为每次单个结点被访问，将会有两个操作（一次加锁、一次解锁）。开销会比较大。

在多线程的情况下，每个结点一个互斥量的实现效率仍然是最低的。每个结点一次加锁一次解锁开销很大。

在多线程情况下，如果Insert和Delete十分少，读写锁性能优于单互斥量访问，这是因为单互斥量的实现需要串行化所有的操作。如果有相对多Insert和Delete（大约每个10%）时，读写锁和单互斥量实现的性能几乎没有差别。

如果使用一个互斥量或者每个结点一个互斥量，程序在多线程下运行总是比只运行一个线程时更快或者一样快。当Insert和Delete的数量相对较大时，读写锁的多线程程序也比单线程快。对于读写锁实现，当有大量写锁操作时，会出现太多的锁竞争，综合性能下降很快。

//链表结构体
struct list_node_s{
    int data;
    struct list_node_s* next;
}
//Member函数
int Member(int value,struct list_node_s* head_p){
    struct list_node_s* curr_p = head_p;
    while(curr_p != NULL && curr_p->data<value)
        curr_p = curr_p->next;
    if(curr_p == NULL || curr_p->data >value)
        return 0;
    else
        return 1; 
}
//Insert函数
int Insert(int value, struct list_node_s** head_p){
    struct list_node_s* curr_p = *head_p;
    struct list_node_s* pred_p = NULL;
    struct list_node_s* temp_p;
    while(curr_p != NULL && curr_p->data < value){
        pred_p = curr_p;
        curr_p = curr_p->next;
    }
    if(curr_p == NULL || curr_p->data > value){
        temp_p = malloc(sizeof(struct list_node_s));
        temp_p->data = value;
        temp_p->next = curr_p;
        if(pred_p == NULL)    /*New first node*/
            *head_p = temp_p;
        else
            pred_p->next = temp_p;
        return 1;
    }else{    /*Value already in list*/
        return 0;
    }
}
 
//多线程链表
//Delete函数
int Delete(int value, struct list_node_s** head_p){
    struct list_node_s* curr_p == *head_p;
    struct list_node_s* pred_p == NULL;
    
    while(curr_p != NULL && curr_p->data < value){
        pred_p = curr_p;
        curr_p =curr_p->next;
    }
    if(curr_p != NULL && curr_p->data == value){
        if(pred_p == NULL){    /*Deleting first node in list*/
            *head_p = curr_p->next;
            free(curr_p);
        }else{
            pred_p->next = curr_p->next;
            free(curr_p);
        }
        return 1;
    }else{    /*Value isn't in list*/
        return 0;
    }
}
//用每个链表结点拥有一个互斥量的方式来实现Member函数
//在链表结点中添加互斥量
struct list_node_s{
    int data;
    struct list_node_s* next;
    pthread_mutex_t mutex; 
}
 
int Member(int value){
    struct list_node_s* temp_p;
    pthread_mutex_lock(&head_p_mutex);
    temp_p = head_p;
    while(temp_p != NULL && temp_p->data < value){
        if(temp_p->next != NULL)
            pthread_mutex_lock(&(temp_p->next->mutex));
        if(temp_p == head_p)
            pthread_mutex_unlock(&head_p->mutex);
        pthread_mutex_unlock(&(temp_p->mutex));
        temp_p = temp_p->next;
    }
    if(temp_p == NULL || temp_p->data > value){
        if(temp_p == head_p)
            pthread_mutex_unlock(&head_p_mutex);
        if(temp_p != NULL)
            pthread_mutex_unlock(&(temp_p->mutex));
        return 0;
    }else{
        if(temp_p == head_p)
            pthread_mutex_unlock(&head_p_mutex);
        pthread_mutex_unlock(&(temp_p->mutex));
        return 1;
    }
}

9、MPI常用的API及分析

9.2MPI常用的API

//MPI初始化函数
int MPI_Init(int* argc_p,char*** argv_p);
//argc_p是指向argc的指针
//argv_p是指向argv的指针
//当程序不使用这些参数时，一般传递NULL
//一般的用法为
int MPI_Init(NULL,NULL);
//函数返回值是一个整数，传递初始化成功与否的信息，一般忽略
//该函数一般用于MPI程序段之前，再次之前不应该存在任何MPI有关的函数或代码段

//MPI释放函数
int MPI_Finalize(void;
//该函数只有一个作用：告诉系统MPI相关的函数段已经全部执行完毕，可以释放MPI占用的资源了
//在该函数之后不应该再有任何关于MPI的程序段或函数

//MPI程序基本框架
...
#include<mpi.h>
...
int main(int argc,char* argv[]){
    ...
    /*no MPI calls before this*/
    MPI_Init(&argc,&argv);
    ...
    MPI_Finalize();
   /*no MPI calls after this*/
    ...
    return 0;
}
//我们并不一定需要向MPI_Init函数传递参数，也不是一定要在main函数中调用MPI_Init和MPI_Finalize

//获取当前通信域中的进程数
int MPI_Comm_size(MPI_Comm comm,int* comm_sz_p);
//comm是通信子，是函数的输入，类型是MPI为通信子定义的特殊类型
//comm_sz_p是函数的返回值，是一个整数，代表了进程的个数

//获取正在运行的进程在通信子中的进程号
int MPI_Comm_rank(MPI_Comm comm,int* my_rank_p);
//comm是函数的输入
//my_rank_p是函数的返回值，是一个整型变量，其值是进程号
//在MPI_COMM_WORLD中经常用参数comm_sz表示进程的数量，用参数my_rank表示进程号

//进程发送消息的函数
int MPI_Send(void* msg_buf_p,int msg_size,MPI_Datatype msg_type,int dest,
                int tag,MPI_Comm communicator);
//msg_buf_p：是函数的输入，是一个指向消息内容内存块的指针
//msg_size：是函数的输入，表示消息字符串字符数量+1，+1指的是加了一个字符数量的字符结束符'\0'
//msg_type：势函数的输入，表示发送的消息的数据类型
//dest：是函数的输入，是一个整型量，表示接受消息的进程的进程号
//tag：是函数的输入，是一个非负整型量，用于区分看上去完全一样的消息
//communicator：是函数的输入，是一个通信子类型，所有涉及到通信的函数都会加上，用来指定通信的范围，防止一个通信子中的进程发送的消息被另一个通信子中的进程接收

//进程接收消息的函数
int MPI_Recv(void* msg_buf_p,int buf_size,MPI_Datatype buf_type,int source,int tag,
                MPI_Comm communicator,MPI_Status* status_p);
//msg_buf_p：是函数的输出，是一个指向消息所在内存块的指针
//buf_size：是函数的输入，表示内存块中要存储的对象的数量
//buf_type：是函数的输入，表示接受的对象的类型
//source：是函数的输入，表示接受的消息来自哪个进程
//tag：是函数的输入，用来区分看上去完全一样的消息，与发消息的进程的tag对应
//status_p：是函数的输入，一般不使用这个参数，一般在使用时直接赋值为MPI_STATUS_IGNORE

//找回接收到的数据量
int MPI_Get_Count(MPI_Status* status_p,MPI_Datatype type,int* count_p);
//status_p：是函数的输入
//type：是函数的输入，表示消息对象的类型
//count_p：是函数的输出，表示接受到的元素的数量

//规约函数
int MPI_Reduce(void* input_data_p,void* output_data_p,int count,MPI_Datatype datatype,
                MPI_Op operator,int dest_process,MPI_Comm comm);
//input_data_p：是函数的输入，每个进程的待处理数据存放在
//output_data_p：是函数的输出，存放最终结果的目标进程的地址
//count：是函数的输入，缓冲区中的数据个数
//datatype：是函数的输入，数据项的类型
//operator：是函数的输入，操作符，例如加法
//dest_process：是函数的输入，目标进程的编号，指明由哪个进程调用该函数

//所有进程都获取规约结果
int MPI_Allreduce(void* input_data_p,void* output_data_p,int count,
                    MPI_Datatype datatype,MPI_op operator,MPI_Comm comm);
//input_data_p：是函数的输入，每个进程的待处理数据都放在input_data_p中
//output_data_p：是函数的输出，存放最终结果的目标进程的地址
//count：是函数的输入，缓冲区中的数据的个数
//datatype：是函数的输入，数据项的类型
//operator：是函数的输入，操作子，例如加减

//广播函数
int MPI_Bcast(void* data_p,int count,MPI_Datatype datatype,int source_proc,MPI_Comm comm);
//data_p：是函数的输入/输出，缓冲区的起始地址
//count：是函数的输入，缓冲区中的数据个数
//datatype：是函数的输入，缓冲区中的数据类型
//source_proc：是函数的输入，发送信息的进程id

//散射函数
int MPI_Scatter(void* send_buf_p,int send_count,MPI_Datatype send_type,void* recv_buf_p,
                    int recv_count,MPI_Datatype recv_type,int src_proc,MPI_Comm comm);
//如果通信子comm包含comm_sz个进程，那么该函数会将send_buf_p所引用的数据分成comm_sz份，并将第i份分给第i-1号进程
//send_buf_p：是函数的输入，发送缓冲区的起始地址
//send_count：是函数的输入，发送的数据的个数
//send_type：是函数的输入，发送缓冲区中的数据类型
//recv_buf_p：是函数的输出，接受缓冲区的起始地址
//recv_count：是函数的输入，待接收的元素个数
//recv_type：是函数的输入，接受的数据类型
//src_proc：是函数的输入，发送消息的进程id

//聚集函数：将其他进程的结果收集到某个进程上
int MPI_Gather(void* send_buf_p,int send_count,MPI_Datatype send_type,void* recv_buf_p,
                int recv_count,MPI_Datatype recv_type,int dest_proc,MPI_Comm comm);
//send_buf_p：是函数的输入，发送缓冲区的起始地址
//send_count：是函数的输入，发送缓冲区的数据个数
//send_type：是函数的输入，发送缓冲区中的数据类型
//recv_buf_p：是函数的输出，接收缓冲区的起始地址
//recv_count：是函数的输入，待接收的元素个数
//recv_type：是函数的输入，接收的数据类型
//dest_proc：是函数的输入，接受进程的id

//全局聚集函数：将每个进程的send_buf_p内容串连起来，存储到每个进程的recv_buf_p参数中
int MPI_Allgather(void* send_buf_p,int send_count,MPI_Datatype send_type,void* recv_buf_p,
                    int recv_count,MPI_Datatype recv_type,MPI_Comm comm);
//与MPI_Gather相比少了一个指定聚类目的地址的dest_proc参数，其他参数使用同上

//创建由不同基本数据类型的元素所组成的派生数据类型
int MPI_Type_create_struct(int count,int array_of_blocklengths[],
                        MPI_Aint array_of_displacements[],
                        MPI_Datatype array_of_type[],MPI_Datatype* new_type_p);
//count：是函数的输入，指的是数据类型中元素的个数，每个数组参数都有count个元素
//array_of_blocklengths[]：

//寻找内存单元地址的函数
int MPI_Get_address(void* location_p,MPI_Aint* address_p);
//location_p：是函数的输入，指向要寻找地址的单元
//address_p：是函数的输出，是一个整数型，它的长度足以表示系统地址

//指定新数据类型的函数
int MPI_Type_commit(MPI_Datatype* new_mpi_p);
//在使用MPI_Type_create_struct：函数的第五个参数之前我们要先调用此函数去指定它

//释放新数据类型额外的存储空间
int MPI_Type_free(MPI_Datatype* old_mpi_t_p);

//计时函数：返回从过去某一时刻开始所经过的秒数
double MPI_Wtime(void);

//确保进程同时返回函数：确保同一个通信子中的所有进程都完成调用该函数之前，没有进程能够提前返回
int MPI_Barrier(MPI_Comm comm);

//同步发送函数：可以用这个函数来代替MPI_Send来检查程序是否安全
int MPI_Ssend(void* msg_buf_p,int msg_size,MPI_Datatype msg_type,int dest,int tag,
                MPI_Comm communicator);
//msg_buf_p：是函数的输入，是一个指向包含内容的内存块的指针
//msg_size：是函数的输入，表示消息字符串字符数量+1（+1是需要加一个'\0'（字符结束符））
//msg_type：是函数的输入，发送的数据类型
//dest：是函数的输入，指定了要接受消息的进程号
//tag：是函数的输入，是一个非负int型变量，用于区分看上去完全一样的消息

//自己调度通信函数
int MPI_sendrecv(void* send_buf_p,int send_buf_size,MPI_Datatype send_buf_type,int dest,
                int send_tag,void* recv_buf_p,int recv_buf_size,MPI_Datatype recv_buf_type,
                int source,int recv_tag,MPI_Comm communicator,MPI_Status* status_p);
//调用一次这个函数会分别执行一次阻塞式消息和一次消息接受
//dest和source参数可以相同也可以不同
int MPI_Sendrecv_replace(void* buf_p  /*in/out*/,int buf_size  /*in*/,
                          MPI_Datatype buf_type  /*in*/,int dest  /*in*/,
                          int send_tag  /*in*/,int source  /*in*/,
                          int recv_tag  /*in*/,MPI_comm communicator  /*in*/,
                          MPI_Status* status_p  /*in*/);
//如果发送和接收使用的是同一个缓冲区，可以使用该函数，作用和上述函数相同

10、Pthreads

10.1Pthreads常用的API及其应用

//将字符串转换成long int（长整型）
long strtol(const* char number_p,char** end_p,int base);
//number_p：是函数的输入，表示待转换的字符串
//end_p：是函数的输出，如果该值不是NULL，它就指向number_p字符串中第一个无效字符（非数值字符）
//base：是函数的输入，表示这个整数值所用的基
 

//生成线程的函数
int pthread_create(pthread_t* thread_p,const pthread_attr_t* attr_p,
                        void* (*start_routine)(void*),void* arg_p);
//thread_p：是函数的输出，是一个指针，指向对应的pthread_t对象，它不是由pthread_create函数分配的，必须在调用pthread_create函数前将pthread_t对象分配到内存空间。
//attr_p：是函数的输入，一般不使用，只是在函数调用时把NULL传递给参数
//(*start_routine)(void*)：是函数的输入，表示该线程将要运行的函数
//arg_p：是函数的输入，是一个指针，指向传递给start_routine的参数
//返回值一般用于表示线程调用过程中是否有错误

//停止线程
int pthread_join(pthread_t pthread,void** ret_val_p);
//thread：是函数的输入，指向对应的pthread_p对象
//ret_val_p：是函数的输出，可以接收任意有pthread_t对象所关联的那个线程产生的返回值

//互斥量函数
//互斥量初始化函数
int pthread_mutex_init(pthread_mutex_t* mutex_p,const pthread_mutexattr* attr_p);
//互斥量销毁函数
int pthread_mutex_destroy(pthread_mutex_t* mutex_p);
//上锁函数
int pthread_mutex_lock(pthread_mutex_t* mutex_p);
//解锁函数
int pthread_mutex_unlock(pthread_mutex_t* mutex_p);

//信号量函数
//信号量函数的语法：信号量不是Pthreads线程库的一部分，所以需要在使用信号量的程序开头加头文件#include<semaphore.h>
//初始化函数
int sem_init(sem_t* semaphore_p,int shared,unsigned initial_val);
//销毁函数
int sem_destory(sem_t* semaphore_p);
//解锁函数
int sem_post(sem_t* semaphore_p);
//上锁函数
int sem_wait(sem_t* semaphore_p);

//条件变量的一般使用方法
lock mutex;
if condition has occurred

10.2互斥锁的实现及应用

10.3忙等待的实现及应用

11、OpenMP常用的编译指令及其子句应用

12、课本典型案例

12.1矩阵向量乘法

12.2曲边梯形面积计算

12.3通过数学求和公式计算π

12.4蒙特卡洛方法计算π

12.5奇偶交换排序