Parallel Java 1 - Task Parallelism

Async and Finish primitives

這是用high level眼光來看parallelism。

SUM = SUM1 + SUM2

我們說SUM1 和 SUM2 run asynchronizely ，也就是獨立運作，可能in parallel (在不同的CPU core) or not都有可能。

當SUM1 和 SUM2都完成computation，我們說finish，所以finish是定義所有async tasks的scope，而SUM需要等finish才能得到正確答案。

在Java中，async可以用fork()來實現。
finish可以用join()來實現。

例如以下：

或是可以把用parallelize的objects都放入invoke():

這樣會自動fork / join。

Modelling Parallelism

我們可以用graph來model parallelism，假設我們有以下的async/finish execution:

我們可以用以下的graph來model:

directed path意味著sequential dependency，所以沒有被path連接的node tasks，就是可以run in parallel，以上圖來說就是S2 S3。

Work and Span

要衡量computation graph的瓶頸，我們可以引入work / span衡量。
work: 所有node task的cost總和
span: 某條最長path的work

以上圖來說，work = 1 + 10 + 10 + 1 = 22
其中有兩條path的work 都是最大的，是12，所以span = 12

span可以說是瓶頸。
所以如果把 graph work / span稱為"ideal parallelism"，我們可以得出一個"多少parallelism"的metric，因為如果能夠parallelized tasks越多，則span越少，那parallelism越大。

ideal parallelism是這個computation graph的parallelism upper bound。

Execution time estimation on multi-core processors

假設有一個parallel computation graph如下：

如果在2-cord processor上面，依照OS的scheduler的演算法，有可能造成不同的分配給CPU的結果。定義Tn = 在n-core上需要執行的cost：

注意T1 = work，因為單一cpu壹定要完成所有的task。
T_inf  = span = 最大的path work，因為其他的tasks都可以跟最大path tasks run in parallel，這使得span成為瓶頸。

所以   T_inf <= Tp <= T1
我們定義 speedup = T1/Tp ，這很好理解。

speedup一定 <= p，因為speedup = p是最理想狀態，發生在work被平均分配給p個processor的graph，則speedup = T1/ (T1/p) = p。不過實際上通常會有一個longest path的出現。

另外speedup <= ideal parallelism，因為之前說過ideal parallelism是一個computation graph parallelism upper bound。

Amdahl's law

這定律很好證明，如果知道一個parallel program中sequential part佔了q %，則speedup <=  1/q。例如假設q = 50%，則直覺來想如果你的program平行化之後，只有50%能run in parallel，那當然最多只能獲得比現在執行時間少一半的效能，也就是 1/0.5 = 2。

這個定律在我們不知道computation graph時來預估speedup有用，證明如下：

1. span >= q * work，這容易理解，因為span就是最大的 path cost，當然 >= 那q percentage的不能被parallelize的部分的work (?? 這解釋有點疑問)

2. 又我們知道 speedup <= work/span這個upper bound，把1. 中的span帶入:
speedup <= 1/q

得證。