Scala Parallel Programming筆記 8 - Data Parallelism

Task parallelism vs Data parallelism

之前講的都是task parallelism，也就是怎麼把一個program，分成好幾個平行處理的tasks。現在要講的是，怎麼把data變成可以丟給不同processor平行處理的data? 因為data進來的狀況不見得適合平行處理。

一個可能的data parallelization是parallel for:

上面這個function把v寫到xs所有elements中。
把(0 until xs.length)這range呼叫par方法，就能把壹些range分散給不同processor，但是這個方法是把v寫入xs，這是side effect，not pure functional (not input -> output)，因為使用到了side effect，這有賴於parallel range不會重疊，否則就有race condition的問題。

Mandelbrot set example

假設c為複數平面任一點，定義mandelbrot set如下，這個值如果絕對值 < 2，就屬於mandelbrot set:

如果把複數平面畫成一個image，如果把不收斂（many iterations之後，和的絕對值 >= 2，也就是)的iteration數目mapping到顏色的話，長這樣：

所以收斂的pixel我們不填值，是黑色的，不是黑色的pixel都是發散的pixel。以下是sequential mapping 發散pixel顏色的方法：

如果要data parallelization的話：

如果用task parallelization (reduction tree)，速度是最慢的。如果用data parallelization (scala parallel collection)，速度比task parallelization約快25%。如果用data parallelization + workload balancing scheduler，速度會達到task parallelization的兩倍！

由於mandelbrot set中的pixel值的workload是跟他的iteration數目成正比，而不是const cost，所以藉由workload balancing機智，能夠比task parallelization快上兩倍。