object PrefixScan {
sealed abstract class Tree[A]
case class Leaf[A](a: A) extends Tree[A]
case class Node[A](l: Tree[A], r: Tree[A]) extends Tree[A]
sealed abstract class TreeRes[A] { val res : A }
case class LeafRes[A](override val res: A) extends TreeRes[A]
case class NodeRes[A](l : TreeRes[A], override val res: A, r: TreeRes[A]) extends TreeRes[A]
def reduceRes[A](t: Tree[A], f:(A,A)=>A): TreeRes[A] = t match {
case Leaf(v) => LeafRes(v)
case Node(l, r) => {
val (tL, tR) = (reduceRes(l, f), reduceRes(r, f))
NodeRes(tL, f(tL.res, tR.res), tR)
}
}
}
I'm concerned about the reduceRes function.
It works ... the result of the computation is great!
However I went and implemented another version, reduceResPar, that uses fork-join at the first few branches, to parallelize the computation. But it gave no speed up.
Then I went back and realized .. the above version, reduceRes, is already using all 12 cores on my machine!! How can it do that? I thought it would just be 1 core!
This code is from the Parallel Programming course on Coursera In the last lecture of week 2, we are learning about parallel prefix scan operations.