parallel sh!t

\begin{lstlisting}
import util.Random
import System.currentTimeMillis
import actors.Futures._

object Parallel2 extends App{

  val rnd = new Random(1337)//Seeded RNG

  //Create 2 matrices with dimension NxN
  val N = 500
  val A:Array[Array[Double]] = Array.fill(N,N){ rnd.nextDouble }
  val B:Array[Array[Double]] = Array.fill(N,N){ rnd.nextDouble }

  //Time a call-by-name block and return milli-seconds
  def time(b: => Unit):Long = {
    val start = currentTimeMillis
    b
    currentTimeMillis-start
  }

  val sequentialProgram = new LinearAlgebra with SequentialLinearAlgebra {
    println("Sequential time: "+time { A * B } )
  }

  val parColProgram = new LinearAlgebra with ParColLinearAlgebra {
    println("ParCol time: "+time { A * B } )
  }

  val futureProgram = new LinearAlgebra with FutureLinearAlgebra {
    println("Future time: "+time { A * B } )
  }

  val imperativeProgram = new LinearAlgebra with ImperateiveLinearAlgebra {
    println("Imperative time: "+time { A * B } )
  }

}

//Interface, knows nothing about implementation
trait LinearAlgebra{

  type Vector = Array[Double]
  type Matrix = Array[Array[Double]]

  implicit class VectorOps(v:Vector){
    def dot(that:Vector):Double = innerProd(v,that)
  }
  implicit class MatrixOps(m:Matrix){
    def *(that:Matrix):Matrix = matMul(m,that)
  }

  //Functionality will is deferred to implementing traits
  def innerProd(a:Vector,b:Vector):Double
  def matMul(A:Matrix,B:Matrix):Matrix
}

//Implements LinearAlgebra interface in a sequential fashion
trait SequentialLinearAlgebra extends LinearAlgebra {

  def innerProd(a:Vector,b:Vector) =
    ((a,b).zipped map (_*_)).sum

  def matMul(A:Matrix,B:Matrix) = {
      val Bt = B.transpose
      A.map(row => Bt.map(col => row dot col))
    }

}

//Implements LinearAlgebra interface using parallel collections
trait ParColLinearAlgebra extends LinearAlgebra {

  def innerProd(a:Vector,b:Vector) =
    ((a,b).zipped map (_*_)).sum

  def matMul(A:Matrix,B:Matrix) = {
    val Bt = B.transpose
    (A.par map (row => Bt map (col => row dot col))).toArray
  }

}

//Implements LinearAlgebra interface using futures, i.e. explicit workload distribution
trait FutureLinearAlgebra extends LinearAlgebra {

  def innerProd(a:Vector,b:Vector) =
    ((a,b).zipped map (_*_)).sum

  //One thread per row in A
  def matMul(A:Matrix,B:Matrix) = {
      val Bt = B.transpose
      val res = A map ( row => future {Bt map (col => row dot col)})
      res.map(_.apply)
    }

}

//Implements LinearAlgebra interface in imperative algorithms
trait ImperateiveLinearAlgebra extends LinearAlgebra {

  //Actually, we don't need this for this benchmark
  def innerProd(a:Vector,b:Vector) = {
    var accum = 0d
    var i = 0
    while(i<a.length) {
      accum += a(i)*b(i) //State mutation!
      i += 1  //State mutation!
    }
    accum
  }

  def matMul(A:Matrix,B:Matrix) = {
    val res = Array.ofDim[Double](A.length,B(0).length)
    var i=0
    while(i<A.length){
      var j=0
      while(j<B(0).length){
        var k=0
        while(k<A(0).length){
          res(i)(j) += A(i)(k)*B(k)(j)  //State mutation!
          k+=1                          //State mutation!
        }
        j+=1                            //State mutation!
      }
      i+=1                              //State mutation!
    }
    res
  }

}


\end{lstlisting}