Parallel Java 4 - Loops

Forall Construct (Java沒有 @@）

forall是for loop的parallel版本，可以看到semantics如下：

範例：
forall (i : [0:n-1]) a[i] = b[i] + c[i]

如果只對一個collection做事的話，也可以用stream。

forall (n) 會spawn n tasks，所以使用forall來設計parallel program的話，要盡量減少tasks數目，不能隨便使用。

Matrix Multiplication Example

用數學定義來做matrix multiplication的話：

會是一個triple loop:
對C中每個row I來說
對row I中每個column J說
對C[I][J]要loop相對應的A[I][all K] 以及 B[all K][J]

可以把計算每個C[i][J]的task parallelize，所以，所以計算C[0][0] 和 C[0][1]是independent的，那有辦法把裡面的K-loop parallelize嗎？

K-loop是對某特定C[I][J]做累加，如果不做任何synchronization的話，會產生data race。不過這不是concurrent programming，所以當然不會做synchronization，要不然就失去parallelism。

所以K-loop需要sequential execution。

Phase Barrier Construct in Forall

barrier是一個forall中使用的construct，可以把forall中的code分成好幾個phase，所有parallel execution都會被擋在barrier前，不能往下執行，直到所有的parallel execution都完成phase 1的code。

癌舉例來說，以下的兩種寫法都能得到一樣的Jacobi algorithm答案：

第一個方法顯而易見產生更多的tasks。
第二種方法把forall變成outer loop，但是由於有swap array pointer的需要，我們必須確保在swap pointer之前，所有的tasks都完成computation。此時需要barrier的協助，注意barrier是放入在inner sequential loop中。

雖然這邊會instantiate 和第一個方法#tasks 一樣多的barriers，但是barriers的overhead遠比task coordination少得多，所以這也就是能夠比第一種方法加速的原因。

避免產生太多tasks!

由上面那一段可以知道，由於實體的cpu core數目相對於data數目總是太少（例如16 cores vs 1 billion elements)，如果把每個element 都parallel去處理，反而會拖慢速度，因為overhead >> 加速性。

所以類似之前做法，要把1 billion elements拆成幾個 n parts，那些n parts就可以在inner sequential loop處理掉，而outer loop就可以用forall parallelize，這樣tasks的數目就減少到n個。

n 的數目要實驗，因為會依據環境而定。

至於怎麼拆法，那就不一定，看選擇。