任务调度、负载平衡技术和停机准则.ppt

任务调度、负载平衡技术与停机准则
两种主要并行开销:
进程交互
进程空闲:负载不平衡、任务依赖
优良调度必须尽量达到两个目标:
减少不同进程上任务之间的依赖
减少由于负载不平衡引起的进程空闲
两个目标通常相互冲突,任务调度并不简单
2018/9/5
1
任务调度、负载平衡技术与停机准则(续)
负载平衡是减少进程空闲的必要条件,但并非充分条件
1
2
3
4
5
6
7
8
9
10
11
12
P0
P1
P2
P3
开始同步结束
t=0 t=2 t=3
2018/9/5
2
任务调度、负载平衡技术与停机准则(续)
负载平衡是减少进程空闲的必要条件,但并非充分条件
1
4
7
10
2
5
8
11
3
6
9
12
P0
P1
P2
P3
开始同步结束
t=0 t=3 t=6
2018/9/5
3
任务调度、负载平衡技术与停机准则(续)
静态调度
在算法执行之前事先进行任务分配
对静态生成的任务,可用静态调度,也可用动态调度
采用静态调度时,并行算法的设计与编程比较容易
动态调度
程序执行过程中在进程间分配任务
不知道任务的计算量,静态调度有可能引起严重的负载不平衡,或者任务是动态生成的
采用动态调度时,并行算法的设计与编程比较复杂
2018/9/5
4
静态调度策略
基于数据划分的静态调度
基于任务分解的静态调度
混合调度
2018/9/5
5
基于数据划分的静态调度
数组分布方法
块分布:将数组中连续的部分数据分布到进程上
循环块分布与循环分布
随机块分布
图划分方法
2018/9/5
6
块分布
一个d维数组通过沿某几个具体的维,将一个数据块分布到进程上
当交互具有局部性时,块分布十分有效
可以分为一维块分布与多维块分布两类
2018/9/5
7
块分布(续)
一维块分布示例
按行块分布
P0
P2
P3
P1
按列块分布
P0
P1
P2
P3
2018/9/5
8
块分布(续)
二维块分布示例
4  4块分布
P0
P8
P12
P4
P1
P9
P13
P5
P2
P10
P14
P6
P3
P11
P15
P7
24块分布
P0
P1
P2
P3
P4
P5
P6
P7
2018/9/5
9
块分布(续)
一般高维分布下可以利用更多的进程来并行计算
矩阵乘法就是典型例子
对许多问题,高维分布除了提供更高的并发度外,也有助于减少进程交互
矩阵乘法的例子
2018/9/5
10