# (PART) 并行处理结构 {-}
本部分介绍并行处理结构。要深入了解并行处理结构，必须要从系统设计（即软硬件协同设计）的角度入手。本部分重点介绍并行程序的编程基础，以及广泛应用的并行处理结构——多核处理器。
# 并行编程基础
## 程序的并行行为
人们对应用程序性能的追求是无止境的，例如天气预报、药物设计、核武器模拟等应用。并行处理系统可以协同多个处理单元来解决同一个问题，从而大幅度提升性能。评价一个并行处理系统，主要看其执行程序的性能（即程序在其上的执行时间）。可以通过一些公认的并行测试程序集（如SPLASH、NAS）来进行评测。因此，在讨论并行处理结构之前，先来看一下程序的并行行为。程序的并行行为主要包括指令级并行性、数据级并行、任务级并行性。
### 指令级并行性
指令级并行性（Instruction Level Parallelism，简称ILP）主要指指令之间的并行性，当指令之间不存在相关时，这些指令可以在处理器流水线上重叠起来并行执行。在程序运行中，如果必须等前一条指令执行完成后，才能执行后一条指令，那么这两条指令是相关的。指令相关主要包括数据相关、控制相关和结构相关。数据相关包括写后读（Read After Write，简称RAW）相关、读后写（Write AfterRead，简称WAR）相关和写后写（WriteAfter Write，简称WAW）相关。其中RAW相关是真正的数据相关，因为存在真正的数据传递关系；WAR相关和WAW相关又称为假相关或者名字相关，指令之间实际不存在数据传递。控制相关主要是由于存在分支指令，一条指令的执行取决于该分支指令的执行结果，则这两条指令之间存在控制相关。结构相关是指两条指令同时需要流水线中的同一个功能部件。在这些相关中，RAW数据相关和控制相关是真正制约指令级并行执行的相关。指令相关容易造成处理器流水线上的冲突，引起流水线阻塞，从而降低流水线效率。
现代处理器采用多种微结构设计技术挖掘指令级并行性，包括指令流水线、多发射、动态调度、寄存器重命名、转移猜测等技术。指令流水线重叠执行多条不相关的指令；多发射技术允许一个时钟周期执行多条指令，类似于“多车道”；动态调度允许后续指令越过前面被阻塞的指令继续被调度执行，相当于允许“超车”；寄存器重命名主要解决RAW和WAW的假相关问题；转移猜测技术可以猜测分支指令的方向和目标，在分支指令还未执行完之前获取更多可执行指令，以减少控制相关造成的指令流水线阻塞。这方面的技术已经比较成熟。
### 数据级并行性
数据级并行性（Data Level Parallelism，简称DLP）是指对集合或者数组中的元素同时执行相同的操作。这种并行性通常来源于程序中的循环语句。下列代码块所示的代码就是一个数据并行的例子。对于数组local中的元素local[i],执行相同的操作(i+0.5)*w。可以采用将不同的数据分布到不同的处理单元的方式来实现数据级并行。
```c
for(i=0;i
#include
int main(){
int i;
int num_steps=1000000;
double x,pi,step,sum=0.0;
step = 1.0/(double) num_steps;
for(i=0;i
#include
#include
#define NUM_THREADS 4 //假设线程数目为4
int num_steps = 1000000;
double step = 0.0, sum = 0.0;
pthread_mutex_t mutex;
void *countPI(void *id) {
int index = (int ) id;
int start = index*(num_steps/NUM_THREADS);
int end;
double x = 0.0, y = 0.0;
if (index == NUM_THREADS-1)
end = num_steps;
else
end = start+(num_steps/NUM_THREADS);
for (int i=start; i
#include
#include
#define NUM_THREADS 4 //假设线程数目为4
#define n 1000
double *A,*B,*C;
void *matrixMult(void *id) {//计算矩阵乘
int my_id = (int)id;
int i,j,k,start,end;
//计算进程负责的部分
start = my_id*(n/NUM_THREADS);
if(my_id == NUM_THREADS-1)
end = n;
else
end = start+(n/NUM_THREADS);
for(i=start;i
main(){
int var1,var2,var3;
…
#pragma omp parallel private(var1,var2) shared(var3)
{
…
}
…
}
```
2.编译制导语句
下面介绍编译制导语句的格式。参看前面的OpenMP程序并行结构的例子，在并行开始部分需要语句“#pragma omp parallel private(var1,var2) shared(var3)”。下表是编译制导语句的格式及解释。
```{r Compiler-guidance-language, echo=FALSE, fig.align='center', fig.cap="编译制导语言", out.width='100%'}
knitr::include_graphics("images/chapter10/编译制导语言-01.png")
```
3.并行域结构
一个并行域就是一个能被多个线程执行的程序块，它是最基本的OpenMP并行结构。并行域的具体格式为：
```C++
#pragma omp parallel [if(scalar_expression)| num_threads(integer-
expression）|default(shared|none)|private(list)|firstprivate(list)|shared
(list)| copyin(list)|reduction(operator:list)|
proc_bind(master|close|spread)]
newline
```
当一个线程执行到parallel这个指令时，线程就会生成一列线程，线程号依次从0到n-1，而它自己会成为主线程（线程号为0）。当并行域开始时，程序代码就会被复制，每个线程都会执行该代码。这就意味着，到了并行域结束就会有一个栅障,且只有主线程能够通过这个栅障。
4.共享任务结构
共享任务结构将其内封闭的代码段划分给线程队列中的各线程执行。它不产生新的线程，在进入共享任务结构时不存在栅障，但是在共享任务结构结束时存在一个隐含的栅障。图\@ref(fig:shared-task)显示了3种典型的共享任务结构。其中：do/for将循环分布到线程列中执行，可看作是一种表达数据并行s的类型； sections把任务分割成多个各个部分（section），每个线程执行一个section，可很好地表达任务并行；single由线程队列中的一个线程串行执行。
```{r shared-task, echo=FALSE, fig.align='center', fig.cap='共享任务类型', out.width='100%'}
knitr::include_graphics("images/chapter10/shared_task.png")
```
下面具体来看一下。
1）for编译制导语句。for语句（即C/C++中的for语句），表明若并行域已经初始化了，后面的循环就在线程队列中并行执行，否则就会顺序执行。语句格式如下：
```c
#pragma omp for [private(list)|firstprivate(list)|lastprivate(list)|
reduction(reduction-identifier:list)|schedule(kind[,chunk_size])|colla
pse(n)|ordered| nowait]
newline
```
其中，schedule子句描述如何在线程队列中划分循环。kind为static时，将循环划分为chunk_size大小的循环块，静态分配给线程执行，若chunk_size没有声明，则尽量将循环在线程队列中平分；kind为dynamic时，线程会动态请求循环块来执行，执行完一个循环块后就申请下一个循环块，直到所有循环都执行完，循环块的大小为chunk_size，若chunk_size没有声明，则默认的块长度为1；kind为guide时，线程会动态请求循环块来执行，循环块的大小为未调度的循环数除以线程数，但循环块大小不能小于chunk_size（除了最后一块），若chunk_size没有声明，则默认为1。
2）sections编译制导语句。该语句是非循环的共享任务结构，它表明内部的代码是被线程队列分割的。语句格式如下：
```c
#pragma omp sections [private(list)|firstprivate(list)|lastprivate(list)|
reduction(reduction-identifier:list)|nowait]
newline
{
[#pragma omp section newline]
Structured_block
[#pragma omp section newline
Structured_block]
}
```
值得注意的是，在没有nowait子句时，sections后面有栅障。
3）single编译制导语句。该语句表明内部的代码只由一个线程执行。语句格式如下：
```c
#pragma omp single [private(list)|firstprivate(list)|
copyprivate(list)|nowait] newline
Structured_block
```
若没有nowait子句，线程列中没有执行single语句的线程，会一直等到代码栅障同步才会继续往下执行。
5.组合的并行共享任务结构
下面介绍两种将并行域制导和共享任务制导组合在一起的编译制导语句。
1）parallel for编译制导语句。该语句表明一个并行域包含一个单独的for语句。语句格式如下：
```c
#pragma omp parallel for [if(scalar_expression)|num_threads(integer-
expression|default(shared|none)|private(list)|firstprivate(list)|lastpriv
ate(list)|shared(list)|copyin(list)|reduction(Structured_block:list)|proc
_bind(master|close|spread)|schedule(kind[,chunk_size])|collapse(n)|ordere
d]
newline
For_loop
```
该语句的子句可以是parallel和for语句的任意子句组合，除了nowait子句。
2）parallel sections编译制导语句。该语句表明一个并行域包含单独的一个sections语句。语句格式如下：
```c
#pragma omp parallel sections [if(scalar_expression)|num_threads(integer-
expression)|default(shared|none)|private(list)|firstprivate(list)|lastpri
vate(list)|shared(list)|copyin(list)|reduction(Structured_block:list)|pro
c_bind(master|close|spread)]
{
[#progma omp section newline]
Structured_block
[#progma omp section newline
Structured_block]
…
}
```
同样，该语句的子句可以是parallel和for语句的任意子句组合，除了nowait子句。
6.同步结构
OpenMP提供了多种同步结构来控制与其他线程相关的线程的执行。下面列出几种常用的同步编译制导语句。
1）master编译制导语句。该语句表明一个只能被主线程执行的域。线程队列中所有其他线程必须跳过这部分代码的执行，语句中没有栅障。语句格式如下：
```c
#pragma omp master newline
```
2）critical编译制导语句。该语句表明域中的代码一次只能由一个线程执行。语句格式如下：
```c
#pragma omp critical[name] newline
```
3）barrier编译指导语句。该语句同步线程队列中的所有线程。当有一个barrier语句时，线程必须要等到所有的其他线程也到达这个栅障时才能继续执行。然后所有线程并行执行栅障之后的代码。语句格式如下：
```c
#pragma omp barrier newline
```
4）atomic编译制导语句。该语句表明一个特别的存储单元只能原子地更新，而不允许让多个线程同时去写。语句格式如下：
```c
#pragma omp atomic newline
```
另外，还有flush、order等语句。
7.数据环境
OpenMP中提供了用来控制并行域在多线程队列中执行时的数据环境的制导语句和子句。下面选择主要的进行简介。
1）threadprivate编译制导语句。该语句表明变量是复制的，每个线程都有自己私有的备份。这条语句必须出现在变量序列定义之后。每个线程都复制这个变量块，所以一个线程的写数据对其他线程是不可见的。语句格式如下：
```c
#pragma omp threadprivate(list)
```
2）数据域属性子句。OpenMP的数据域属性子句用来定义变量的范围，它包括private、firstprivate、lastprivate、shared、default、reduction和copyin等。数据域变量与编译制导语句parallel、for、sections等配合使用，可控制变量的范围。它们在并行结构执行过程中控制数据环境。例如：哪些串行部分的数据变量被传到程序的并行部分以及如何传送；哪些变量对所有的并行部分是可见的；哪些变量是线程私有的；等等。具体说明如下。
- private子句：表示它列出的变量对于每个线程是局部的，即线程私有的。其格式为：
```c
private(list)
```
- shared子句：表示它列出的变量被线程队列中的所有线程共享，程序员可以使多线程对其进行读写（例如通过critical语句）。其格式为：
```c
shared（list）
```
- default子句：该子句让用户可以规定在并行域的词法范围内所有变量的一个默认属性（如可以是private、shared、none）。其格式为：
```c
default(shared|none)
```
- firstprivate子句：该子句包含private子句的操作，并将其列出的变量的值初始化为并行域外同名变量的值。其格式为：
```c
firstprivate(list)
```
- lastprivate子句：该子句包含private子句的操作，并将值复制给并行域外的同名变量。其格式为：
```c
lastprivate(list)
```
- copyin子句：该子句赋予线程中变量与主线程中threadprivate同名变量的值。其格式为：
```c
copyin(list)
```
- reduction子句：该子句用来归约其列表中出现的变量。归约操作可以是加、减、乘、与(and)、或(or)、相等(eqv)、不相等(neqv)、最大（max）、最小（min）等。其格式为：
```c
reduction(reduction-identifier:list)
```
利用梯形规则计算π的OpenMP并行化的C语言代码示例
```c
#include
#include
int main(){
int i;
int num_steps=1000000;
double x,pi,step,sum=0.0;
step = 1.0/(double) num_steps;
# pragma omp parallel for private(i, x), reduction(+:sum)
for(i=0;i
#include
#define n 1000
double A[n][n],B[n][n],C[n][n];
int main()
{
int i,j,k;
//初始化矩阵A和矩阵B
for(i=0;i
#include "mpi.h"
int main(int argc, char **argv){
int num_steps=1000000;
double x,pi,step,sum,sumallprocs;
int i,start, end,temp;
//进程编号及组中的进程数量, 进程编号的范围为0到num_procs-1
int ID,num_procs;
MPI_Status status;
//初始化MPI环境
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&ID);
MPI_Comm_size(MPI_COMM_WORLD,&num_procs);
//任务划分并计算
step = 1.0/num_steps;
start = ID *(num_steps/num_procs) ;
if (ID == num_procs-1)
end = num_steps;
else
end = start + num_steps/num_procs;
for(i=start; i
#include "mpi.h"
#define n 1000
int main(int argc, char **argv)
{
double*A,*B,*C;
int i,j,k;
int ID,num_procs,line;
MPI_Status status;
MPI_Init(&argc,&argv); //Initialize the MPI environment
MPI_Comm_rank(MPI_COMM_WORLD,&ID);//获取当前进程号
MPI_Comm_size(MPI_COMM_WORLD,&num_procs);//获取进程数目
//分配数据空间
A = (double *)malloc(sizeof(double)*n*n);
B = (double *)malloc(sizeof(double)*n*n);
C = (double *)malloc(sizeof(double)*n*n);
line = n/num_procs;//按进程数来划分数据
if(ID==0) { //节点0，主进程
//初始化数组
for(i=0;i
马建仓 AI 助手
