Scala Parallel Programming筆記 11 - Splitter and Combiners

Iterator 

首現我們知道Java有iterator:

Splitter (iterator parallel counterpart)

每一個parallel collection都依定會implement Splitter trait。
一但呼叫了split，就分成幾個disjoint splitter set:

原來的splitter instance會變成undefined state。
remaining是"estimate"目前splitter中有幾個element。

來看怎麼用splitter trait implement fold?

首先迴響 for .. yield會產生一個collection，所以children是一個collection for task[Splitter]，每個task會recursively呼叫fold，由於每次children都是remaining > threshold時 split出child Splitters而來，所以remaining會越來越少，直到抵達base case去做sequential foldLeft。最後一行還是要記得去呼叫foldLeft在這個children collection上，才能真正去merge。

Builder

result被呼叫的話，就會return collection，而此builder就undefined。

所以builder其實是把一個collection的“增加member"這件事抽象化的trait，

Combiner (parallel Builder)

combiner要efficient需要經過一番努力，所謂的efficient是要在O(logn + logm)時間內完成，當然落，要不然不等於linearly跑過一次，那哪叫什麼efficient combiner。簡單以四核心cpu為例：

一個reduction tree的leaves會分配給4 core cpus，假設剛好分成四份，每份1/4 N，但是在往root combine的過程中，其實總共累積了（粗略計算） 7/4 N > N的工作量，這比單一cpu sequentially map的時間還久！！！

combine對Map/Set來說，是union。
對sequence來說 (List/Vector/Array) combine是concatenation。

可惜的是，對常見的data  structure來說，combine的動作不可能達到efficient (O(logm + logn)。

兩階段parallel construction

但是實際上幾乎所有的scala collection都能轉換成parallel collection，為何？
因為採取了兩階段的collection construction，使用暫時的data structure來儲存state，例如Array 可能採用其他的intermediate data structure來表現，使得efficient combiner可以實現。

這個intermediate data structure有以下的性質：

第三點就是builder/combiner為什麼會有result method的原因，因為要捨棄這個intermediate data structure，convert到真正的data structure，需要再O(n/P) time內，n = size of the data structure, P = # processors。這個convert必須也要能parallellizable。

phase 1：每個processor先呼叫 += 來build intermediate data structures，然後每個ids被combine直到reduction tree root。

phase 2: parallelly build final data structure from ids。

總共約N/2 for 4 processors。

Array Combiners

intermediate data structure主要就是nested array:

先來看怎麼implement += :

這是O(1)。如果裏層array滿了，就new一個新的更大的。注意上圖中其他的第一層array element都是空的。

combine就很簡單了，因為第一層array是一堆Array pointer，所以只要指向另一個被combine的nested array就可：

這邊 ++= 倒是第一次看到的operator! 這是constant time operation 。

再來是conversion result:

後來的筆記都消失了....因為chrome給我當機 @@
火大ㄟ