首页 > 代码库 > 并行计算有向无环图和fork/join 框架

并行计算有向无环图和fork/join 框架

    从多任务OS开始,线程主要用来表示IO异步;而今随着4G和多核等的到来,计算密集型又热门起来了。

硬件价格和性能从低到高:
PC/Laptop multi core, memory shared
PC clusters
SuperComputers
假设一个理想并行计算机:每个处理器计算能力相同,忽略调度,

static thread 是对一个虚拟处理器的软件层面的抽象;
static强调的是线程一直存在,不包含线程的创建和销毁。

dynamic multithreded concurrency platform:
通讯协议,负载平衡调度器
spawn a subroutine
parallel loop


并行计算有向无环图
只有三个关键字: parallel, spawn, sync
并行控制指令:spawn, sync, return(包括函数末尾的隐式return)
不包含并行控制的指令序列表示为一个顶点;
顶点u到v的有向边表示指令序列u必须先于v执行; 这时称u,v是串行的,
否则是并行的。
我们把边(u,v)分为:
continuation: 在同一过程实例中,v是u的直接后继。
spawn: 如果u spawn v。
call:  如果u直接调用了v。
return: u返回到调用它的过程,v是这个过程里面紧接sync的。


性能度量
work 是指仅在一个处理器上总的执行时间。如果把一个顶点的执行时间是1,
则work就是顶点总数。
span 是图中最长的路径执行的时间。如果一个顶点花的时间是1,
则span等于图的关键路径长度+1。


Tp记为用p个处理器所花的的总时间。
P*Tp >= T1
T1 是用1个处理器所需的时间,显然,T1 = work。
Tinf 表示用无穷多个处理所需的时间, 显然,Tinf = span。
T1/Tp 称为加速量(speedup)。如果T1/Tp = P, 则称为perfect linear speedup。
T1/Tinf 称为并行度(parallelism)。
T1/(P*Tinf) 称为slackness。


一个好的调度器追求的目标就是越来越接近perfect linear speedup。
贪心调度器:在每个时间步,把尽可能多的顶点分配给处理器。
定理: 使用贪心调度器, Tp <= T1/P + Tinf。
实践中,
slackness 至少是10,则Tinf < 0.1 T1/P,从而Tp <= 1.1 T1/P,对于工程应用已经足够好了。
这里我们看到并不是并行度越大越好。


例1
FIB(n)
 if(n <= 1)return n;
 else x = spawn FIB(n-1)
      y = FIB(n-2)
      sync
 return x + y;
T1(n) = T(n) = \phi^n;
Tinf(n) = max(Tinf(n-1), Tinf(n-2)) + 1
    = n;
容易看到,n值不用太大,就可以达到perfect linear speedup.


例2
MATVEC(A,x)
 n = A.rows;
 parallel for i = 1 to n
  yi = 0;
 parallel for i = 1 to n
  for j = 1 to n
    yi = yi + aij * xj;
 return y;
把第二个parallel 用spawn来实现:
MATVEC_LOOP(A, x, y, n, 1, 8);
MATVEC_LOOP(A, x, y, n, i1, i2)
  if i1 == i2
    for j = 1 to n
 yi = yi + aij * xj;
  else mid = (i1+i2)/2;
       spawn MATVEC_LOOP(A, x, y, n, i, mid);
  MATVEC_LOOP(A, x, y, n, mid+1, i2);
       sync 
spawn 个数对应为二叉树内部节点个数=叶子树n-1,总共有n个叶子,因此额外开销spawn分摊到每个叶子为常量。 每个叶子的计算量此时不能再看做1,而是n。因此
 span = lgn + n,
 work = n^2,
并行度 = n.
如果对for j 也加上parallel, 则并行度可达到n/lgn。

工程实践:
C/C++ 有 gcc/cilkplus, 因为我下载网上的x64二进制文件, 一直搞不定LD_LIBRARY_PATH,需要从源码编译工具链, 有空的时候练一下。

java 有fork/join framework ,这个框架有什么优点?
当一个fork子问题join等待另一个子问题时,会去偷尚未运行的子问题来执行。
因此每个子问题应该避免使用synchronized,sleep,阻塞IO或过多访问共享变量。

ForkJoinTask类的抽象方法比较多,不适合直接继承,而是继承它的子类RecursiveTask/Action。
子问题执行由ForkJoinPool来调度。

work stealing 如何做到负载平衡?
每个工作线程A都有自己的一个队列。当A划分出一个新任务,把它加入到队列头部(TBD);只有A才可以操作它的队列头部并取出来执行。
当A的队列为空时,它将尝试从另一线程B的队列尾部偷一个任务。
由于这种队列操作特性,是的最大的任务排在队列尾部,从而是的其他线程来偷取实现负载平衡。
一个简短的例子说明多线程的优势:
<script src="https://code.csdn.net/snippets/355523.js" type="text/javascript"></script>

参考:
[0] 算法导论第三版
[1] 两种任务分发方式的比较: http://stackoverflow.com/questions/7926864/how-is-the-fork-join-framework-better-than-a-thread-pool
[2] concurrent collections 的介绍: http://www.ibm.com/developerworks/cn/java/j-tiger06164/
[3] parallel for: http://stackoverflow.com/questions/4010185/parallel-for-for-java