Parallel Java 5 - Phaser

Barrier in Java

加入barrier會也是需要overhead，例如以下parallel code:

如果要確保所有Hello印出在所有Bye之前，我們插入barrier的位置可以在lookup(i)前或是後，但是這樣一定會讓整個parallel program的span = 200 (記得span就是parallel program中work最大的path)。

node ---> lookup ----> next

如果能夠把lookup和barrier也parallelize 就能降低span到100，類似以下?

node ------------> lookup
         --(join)---> barrier

這事實上是可以的，因為lookup的執行不需要等待barrier的執行，反過來說也是。
Java Phaser class提供這種所謂 split-phase barrier的機制:

Point to Point Synchronization

要壓榨barrier parallelism，必須考慮parallel program的結構，分析哪些statement是dependent on另外statement，不用一致性的等待擋住，以下為例，如果不考慮個別dependency的話，span = 6，因為barrier一刀橫在中間，使得phase 1 work (3) + phase 2 work (3) = 6。

這三個tasks的兩個phases的statements dependency列出來之後發現，可以fine-grained來設定barrier，Java也提供這樣的機制:

Pipeline

想像以下pipeline:

image processing分成好p個步驟，Denoise -> Registration -> Segmentation，這幾個步驟都必須等待前一步驟完成，所以是sequential。

如果有n張image，則同一個時間點可以parallel進行不同image的各個階段，所以n張image經過p個stage pipeline總共的parallel work = n*p （work的定義是所有cost的總和）

computation graph:
D1 --join--> R1 --join--> S1
|fork
D2 --join--> R2 --join--> S2


span (CPL) = n 次Denoise  + 最後一張image 的剩下步驟只能sequentially complete: p - 1 work，所以總共是 n + p - 1

parallelism = work/span = n*p / (n+p-1) ，這邊可以假設 n >> p。所以 parallelism ~= p
也就是大量input的pipeline能獲得平行處理的加速，約等同於pipeline stages的數目。

如果用barrier可以很正確執行上面的semantics: