Scala Parallel Programming筆記 2 - Parallel Computation

Basic parallel construct

最簡單的construct就是同時執行兩個expressions:

舉例來說，我們要計算p-norm，所謂p-norm就是p維度vector的length (稱為norm)，定義如下：

首先看一個比較簡單的問題，怎麼計算一個vector中其中幾個elements的sum of elements raised to the power p:

Scala sequential版本的implementation如下：

有了以上的function，可以簡單建構出p-norm:

Parallel computation of P-Norm

最簡單就是把array a拆成兩份，同時處理sumSegment:

然後直接call sumSegment兩次，最後再求和與開p方根：

不過以上還是sequential的執行，還沒用到parallelism。

直覺當然可以把他丟給兩個threads來執行，不過我們這邊要講更上位的parallel construct，所以就改用第一段說到的basic parallel construct:

所以執行上會是平行的（一開始會有一點overhead):

要改成4個同時進行的運算：

Recursion + Parallelism

recursion是parallelism的好朋友，上面的code可以簡單用recursion版本寫出：

所以basic parallel construct可以是以下的function prototype:

注意taskA和taskB是call by name，也就是不會先evaluate傳進來的task，這當然如此，否則怎麼確保他的parallelism? 因為call by value會先evaluate taskA，然後才evaluate taskB，變成保證是sequential execution。

瓶頸

可能原因來自:
1. resource bottleneck，即便我們能夠把code parallelize分配給cpu執行，但是access memory可能遠比cpu運算慢，得不到真正平行運算的加速
2. 所需要的時間瓶頸卡在平行處理中最長運算單元

More flexible construct: Task

parallel(e1,e2)可以寫成更彈性的construct:

用t.join就可以block main thread，然後等待value被task function回傳回來。

Task最少需要以下的interface定義：

注意computation c是call by name，回傳task of type A，而task of type A至少有join method，回傳A。

有這個task construct，我們可以用來implement之前所說的parallel construct:

我們把cB丟給另一個thread去做，所以initiate task tB，而我們自己的這個thread則執行cA，記住cA是call by name，所以val tA:A = cA 這行已經evaluate cA了。最後我們block自己的thread，直到tB做完，透過tB.join來達成。

記住不能寫成以下：

因為這樣變成main thread要block自己去等tB結束才evaluate tA，這樣變成sequential code!