Scala Parallel Programming筆記 7 - Prefix sum作業2

Counting change problem in parallel

這個問題的sequential版本在此，又忘記了，哈哈。
這題目還不錯，把n=4和denomination =[1,2]的tree都畫出來，這樣很好理解：

填入countChange的sequential版本，問題是怎麼parallelize?

首先要決定thresholding for agglomeration，agglomeration就是避免parallelism的recursive depth太深，這其實有可能造成很大的synchronization overhead (multithreading是有synchronization overhead)，所以到當input size < threshold （base case)，我們就該停止recursion，然後採用sequential processing。

要寫出parallel版本的countChange不難，就仿照lecture中的簡單範例就可以，但是問題在於threshold怎麼設計？

“Counting change is a canonical example of a task-parallel problem in which the partitioning the workload across processors is solution-driven -- to know how to optimally partition the work, we would first need to solve the problem itself.”

這作業的目的就是要我們知道，即便可以做task parallelization，怎麼分配task load是一個問題，而且需要先解出這個母問題才能解出task load怎麼分配的問題，雞生蛋蛋生雞的問題。這邊難處在於我們不能判斷sequential版本要花費多少時間，不像是array segment那樣容易推理。

作業採用了3種thresholding heuristics，要我們試驗看看哪個比較好？
speedup ~= 3.x倍

Balancing Parentheses in Parallel

這題其實很簡單，但是traverse function的提示誤導了人，多了那兩個int 其實是給recursion用的，如果寫while的話，就完全用不到這兩個ints。

這題目的sequential版本很直接的簡單，但是parallel版本就有點需要思考，首先要知道每次reduce的時候(想像成recursion tree中的non-lead node)，兩個children其實一定是consecutive array segments，所以真正要消除配對的括號要在此階段做，-而不能在sequential traverse中做。

關鍵點在reduction operator其實是找出兩個consecutive segment抵銷matching bracket之後的左右brackets數量。

def parBalance(chars: Array[Char], threshold: Int): Boolean = {

  def traverse(idx: Int, until: Int, arg1: Int, arg2: Int) :(Int,Int)  = { //returns (#left brackets, #right brackets) if not cancelled    var i = idx
    var leftBracketCount = 0    var rightBracketCount = 0
    while (i < until) {
      if (chars(i) == '(') {
        leftBracketCount += 1      }
      else if (chars(i) == ')') {
        if (leftBracketCount != 0)
          leftBracketCount -= 1        else          rightBracketCount += 1      }

      i += 1    }
    (leftBracketCount, rightBracketCount)
  }

  def reduce(from: Int, until: Int) : (Int, Int) = {
    if (until - from <= threshold)
      traverse(from, until, 0, 0)
    else {
      val mid = (from + until)/2      val ( (aLeft:Int,aRight:Int), (bLeft:Int,bRight:Int) ) = parallel(reduce(from, mid), reduce(mid, until))

      val leftCount =
        if (aLeft >= bRight ) aLeft - bRight + bLeft
        else bLeft

      val rightCount =
        if (aLeft >= bRight ) aRight
        else aRight + bRight - aLeft

      (leftCount, rightCount)
    }
  }

  reduce(0, chars.length) == (0,0)
}

Line of sight in Parallel

題意要先搞清楚。一個x軸為水平位置，y軸為高度的terrain:

要計算每個x位置的visibility，但是規定視線只能往上，不能往下，也就是如果tan(x1) > tan(x2)，則visibility(x2) = visibility(x1) = tan(x1)，反之visibility(x2) = tan(x2)，所以sequential 版本的 line of sight很簡單如下:

def max(a: Float, b: Float): Float = if (a > b) a else b

def lineOfSight(input: Array[Float], output: Array[Float]): Unit = {
  var i = 1  output(0) = 0
  while(i < input.length) {
    val tangent = input(i) / i
    output(i) = max(tangent,output(i-1))
    i += 1  }
}

我們要怎麼改成parallel版本?
這是一個prefix sum problem，也就是output(n+1) = f( output(n), input(n+1)，a0 = 0 ，因為一開始在原點沒有位移，所以斜率=0。

我們要先建立reduction tree，透過upsweep 過程。
reduction tree的用意其實就是一個可以parallelize的tree structure，此reduction tree會在每個node都儲存apply f這樣才能進行downsweep。

一個upsweep的reduction tree應該是長這樣:

                              max
                          |            |
                        max       max
                     |          |     |      |
                  [   ]     [   ]  [  ]  [  ]

注意leaf不一定是single value(因為會有threshold來控制parallel depth)，如果是一個array或是collection，則就相當於找出以此為root node的subtree的reduction value，但是在downsweep的時候又要sequential跑一次。

所以基本上這就是模仿課堂中的prefix sum範例就好。
這門課的作業test case給得很少，可以submit時放入log來debug。