并行程序设计难的原因

Ø  技术先行,缺乏理论指导

Ø  程序的语法/语义复杂, 需要用户自已处理

任务/数据的划分/分配

数据交换

同步和互斥

性能平衡

Ø  并行语言缺乏代可扩展和异构可扩展, 程序移植困难, 重写代码难度太大

Ø  环境和工具缺乏较长的生长期,缺乏代可扩展和异构可扩展

并行语言的构造方法

3种并行程序设计方法比较：

并行性问题

进程的同构性

SIMD: 所有进程在同一时间执行相同的指令

MIMD:各个进程在同一时间可以执行不同的指令

SPMD: 各个进程是同构的，多个进程对不同的数据执行相同的代码(一般是数据并行的同义语)，常对应并行循环，数据并行结构，单代码

MPMD:各个进程是异构的， 多个进程执行不同的代码（一般是任务并行，或功能并行，或控制并行的同义语），常对应并行块，多代码

静态并行性和动态并行性：

静态并行性: 程序的结构以及进程的个数在运行之前(如编译时, 连接时或加载时)就可确定, 就认为该程序具有静态并行性.  

动态并行性: 否则就认为该程序具有动态并行性. 即意味着进程要在运行时创建和终止

进程编组

目的:支持进程间的交互,常把需要交互的进程调度在同一组中

一个进程组成员由：组标识符+ 成员序号唯一确定.

划分与分配

原则: 使系统大部分时间忙于计算, 而不是闲置或忙于交互; 同时不牺牲并行性(度).

划分: 切割数据和工作负载

分配：将划分好的数据和工作负载映射到计算结点(处理器)上

分配方式：

显式分配: 由用户指定数据和负载如何加载

隐式分配：由编译器和运行时支持系统决定

就近分配原则：进程所需的数据靠近使用它的进程代码

并行度(Degree of Parallelism, DOP):同时执行的分进程数.

并行粒度(Granularity): 两次并行或交互操作之间所执行的计算负载.

Ø  指令级并行

Ø  块级并行

Ø  进程级并行

Ø  任务级并行

并行度与并行粒度大小常互为倒数: 增大粒度会减小并行度.

增加并行度会增加系统(同步)开销

交互/通信问题

交互的类型

Ø  通信：两个或多个进程间传送数的操作

    通信方式：

共享变量

父进程传给子进程(参数传递方式)

消息传递

Ø  同步：导致进程间相互等待或继续执行的操作

 同步方式:

原子同步

控制同步(路障,临界区)

数据同步(锁,条件临界区,监控程序,事件)

Ø  聚集(aggregation)：用一串超步将各分进程计算所得的部分结果合并为一个完整的结果, 每个超步包含一个短的计算和一个简单的通信或/和同步.

聚集方式:

归约

扫描

交互的方式

同步的交互: 所有参与者同时到达并执行交互代码C

异步的交互: 进程到达C后, 不必等待其它进程到达即可执行C

交互的模式

按交互模式是否能在编译时确定分为:

Ø  静态的

Ø  动态的

按有多少发送者和接收者参与通信分为

Ø  一对一:点到点(point topoint)

Ø  一对多:广播(broadcast),播撒(scatter)

Ø  多对一:收集(gather), 归约(reduce)

Ø  多对多:全交换(TatalExchange), 扫描(scan) , 置换/移位(permutation/shift)

五种并行编程风范

Ø  相并行（PhaseParallel）

一组超级步（相）

步内各自计算

步间通信、同步

BSP

方便差错和性能分析

计算和通信不能重叠

Ø  分治并行（Divideand Conquer Parallel）

父进程把负载分割并指派给子进程

递归

重点在于归并

分治设计技术（6.2）

难以负载平衡

Ø  流水线并行（PipelineParallel）

一组进程

流水线作业

流水线设计技术

Ø  主从并行（Master-SlaveParallel）

主进程：串行、协调任务

子进程：计算子任务

划分设计技术

与相并行结合

主进程易成为瓶颈

Ø  工作池并行（WorkPool Parallel）

初始状态：一件工作

进程从池中取任务执行

可产生新任务放回池中

直至任务池为空

易与负载平衡

临界区问题（尤其消息传递）

并行程序设计模式

隐式并行模型

Ø  概况：

程序员用熟悉的串行语言编程

编译器或运行支持系统自动转化为并行代码

Ø  特点：

语义简单

可移植性好

单线程，易于调试和验证正确性

效率很低

数据并行模型

Ø  概况：

SIMD的自然模型

局部计算和数据选路操作

Ø  特点：

单线程

并行操作于聚合数据结构（数组）

松散同步

单一地址空间

隐式交互作用

显式数据分布

消息传递模型

Ø  概况：

MPP, COW的自然模型

Ø  特点：

多线程

异步

多地址空间

显式同步

显式数据映射和负载分配

显式通信

共享变量模型

Ø  概况：

PVP, SMP, DSM的自然模型

Ø  特点：

多线程：SPMD,MPMD

异步

单一地址空间

显式同步

隐式数据分布

隐式通信