并行計算有向無環圖和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;

  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的隊列尾部偷一個任務。

由于這種隊列操作特性，是的最大的任務排在隊列尾部，進而是的其他線程來偷取實作負載平衡。

一個簡短的例子說明多線程的優勢：

參考：

[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