Scala Parallel Programming筆記 9 - Data Parallel Operations

fold construct

scala collection多數能直接轉成parallel collection，透過.par method:

所以filter / count 都可以execute in parallel。例如我們可以寫一個collection sum:

def sum(xs:Array[Int]):Int = {
  xs.par.foldLeft(0)((x,y) => x+y)
}

可惜foldLeft不能直接parallelize，先看其signature:

所以foldLeft accumulator type B，collection element type A，透過f(B,A) => B來把每一個element fold成一個單一值。但是每次進入f的B其實是前一次f的output，也就是foldLeft只能sequential computation。

fold/reduce/scan 都是只能sequential operation。

如果fold是以下的signature的話，就可以用parallelization (reduction tree):

事實上scala有fold function，是專門給parallel computation用的。當然要用parallel fold還是得要遵守operator必須是associative的前提，舉例來說，以下的operator (play剪刀石頭布)只有communtative，但是不associative，所以不同的execution order會有不同的結果：

所以初始值(z)和binary operator f必須滿足以下性質（稱為monoid關係）：

所以z丟進去f其實就是a的identity function。

可是fold很明顯不夠用，因為所有參數都只能是same type，這只能用在受限的application context。

Aggregation construct

解決fold不夠expressive的問題，另一個parallel operation稱為aggregation:

比較特別的是，他接受兩個operators f and g，f是sequential operator, g是parallel operator，為什麼要這樣？

注意f是跟foldLeft的operator f一樣的signature，而g的signature是跟fold的operator一樣的signature，所以aggregation事實上是combine foldLeft 和 fold:

所以把array 先分成不同parts，然後每個parts用sequential foldLeft，最後用fold combine，不過問題是，為什麼這樣可以？

舉以下的例子：

的確這是可行的，因為sequential的f不依賴任何其他parts results，而parallel的g符合monoid structure ( 0 + count = count 且 + operator是associative )。