《并行程序设计导论》

并行程序设计导论

一、为什么需要并行计算

基本术语

多核处理器：单个芯片上多个相对简单的处理器

单核系统：只有一个CPU的处理器

核：中央处理器、CPU

通信：一个或多个核将自己的部分和结果发送给其他的核。

负载平衡：简单来说，每个核分配大致相同数目的数据来计算。

同步：比如使用Synchronize_cores()，每个核都会再在此处等待，直到所有的核都进入该函数——特别的，必须要等到master核进入该函数。

共享内存系统：每个核能够共享访问计算机的内存，能够读、写内存的所有区域

分布式内存系统：每个核都有自己的私有内存，核之间的通信是显式的，必须使用类似在网络中发送消息的机制。

并发：指两个或多个事件在同一时间间隔内发生。

并行：指两个或多个事件在同一时刻发生。（紧耦合）

分布式：更多是指通过网络连接多台客户端与服务端进行数据处理。是把海量数据分布在不同的计算机或软件中分别处理的一种软件结构。（与并行类似，松耦合）

并行程序设计的两个基本方法：

任务并行
数据并行

举例子：100个学生的试卷（总共5道题目），5个助教。批改方案有两种：

每个助教负责给一个问题打分（任务并行）“执行不同的指令”
试卷分为5叠，每个助教负责一叠试卷（数据并行）“对相似的数据进行评分”

二、并行硬件和并行软件

冯·诺依曼结构：主存、中央处理器（算术逻辑单元ALU+控制单元）、主存和CPU之间的互连结构（总线）

主存和CPU之间的分离，称为冯·诺依曼瓶颈。因为互连结构限定了指令和数据访问的速率。（CPU执行指令的速度远远大于从主存中取指令的速度！！！）

进程：运行着的程序的一个实例。包括以下实体：

可执行的机器语言程序
一块内存空间，包括代码、栈、堆、其他内存区域
资源描述符
安全信息
进程状态信息（进程控制块PCB）

大多数现代操作系统都是多任务的。即操作系统提供对同时运行多个程序的支持。这对单核系统也是可行的，使用时间片轮转的技术即可。

线程：线程间的切换比进程间的切换更快，是“轻量级”的。线程包含在进程中，所以线程可以使用相同的可执行代码，共享相同的内存和相同的I/O设备。两个线程之间最大的差别是，他们各自需要一个私有的程序计数器和函数调用栈，使他们能够独立运行。

如果进程是执行的“主线程”，其他线程由主线程启动和停止。开始时，子线程从进程中派生（fork）出来；一个进程结束后，它会合并（join）到进程中。

对冯诺依曼模型的改进有三种措施：

缓存（caching）
虚拟存储器
低层次并行

1.Cache基础知识

高速缓冲存储器（cache）：访问时间比其它存储区域的访问时间短。本书谈到缓存，一般指CPU缓存（CPU Cache）

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

运用局部性原理，系统使用更宽的互连结构（总线）来访问数据和指令。也就是：一次内存访问能存取一整块代码和数据，而不是单条指令和单条数据。这些块称为高速缓冲块或高速缓存行。

Cache本身也分为三层：第一层（L1）最小但最快、更高层Cache（L2、L3）更大但相对较慢。当CPU访问指令或数据时，它会沿着Cache的层次结构向下查询：首先是L1，接着L2。。。最后是主存。

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

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

写回：数据不是立即更新到主存中，而是将发生数据更新的高速缓存行标记成 脏（dirty）

全相联映射：

直接映射：

n路组相联：

2.性能

线性加速比：\(T_{并行} = \frac{1}{p}T_{串行}，假设并行为p核系统上进行的\)

加速比：\(S=\frac{T_{串行}}{T_{并行}}\)

效率：\(E=\frac{S}{p}=\frac{T_{串行}}{p*T_{并行}}\)

并行开销：\(T_{并行} = \frac{1}{p}T_{串行} + T_{开销}\)

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

可扩展性：如果增加程序的进程数/线程数，在输入规模也以相应增长率增加的情况下，该程序的效率一直是E。

强可扩展：进程线程数增加，不增加问题规模，却可以维持固定的效率。（线程++，问题—，E—）

弱可扩展：进程线程数增加，需要增加问题规模，才可以维持固定的效率。（线程++，问题++，E—）

3.计时

我们需要记录的是什么时间呢？

对程序从开始到结束的时间不感兴趣，而对程序的某个部分感兴趣
对所谓的“CPU时间”不感兴趣。CPU时间代表的是程序执行代码的总时间，但是它不包括程序空闲状态的时间！！！
我们通常使用的是墙上时钟时间，即某段代码从开始到结束总耗费的时间。

不同的API使用的获取时间函数是不一样的

问题一：分辨率resolution：是指计时器的时间测量单位问题，即最短的非零时间跨度。

问题二：线程的同步问题

double start, finish;
start = Get_current_time();
/*执行的代码*/
finish = Get_current_time();
elapsed = finish - start;

这样的代码可能会输出多个时间，可以使用barrier函数来进行同步，并且取出运行时间的最大值。

shared double global_elapsed;
private double my_start, my_finish, my_elapsed;

Barrier();    //路障，用于使所有进程同时开始
my_start = Get_current_time();
/*执行的代码*/
my_finish = Get_current_time();
my_elapsed = my_finish - my_start;

global_elapsed = Global_max(myelapsed);    //取出所有进程运行时间的最大值
if(my_rank == 0)    //主进程负责输出时间
    cout<<global_elapsed<<endl;