I am making a small example of a linear algebra with sequential and parallel implementations. Below is the current code:
import util.Random
import System.currentTimeMillis
import actors.Futures._
import Numeric.Implicits._
object Parallel extends App{
val rnd = new Random(1337)//Seeded RNG
//Create 2 matrices with dimension NxN
val N = 550
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 } )
}
}
//Interface, knows nothing about implementation
trait LinearAlgebra{
type Vector[T] = Array[T]
type Matrix[T] = Vector[Vector[T]]
implicit class VectorOps[T:Numeric](v:Vector[T]){
def dot(that:Vector[T]):T = innerProd(v,that)
}
implicit class MatrixOps[T:Numeric](m:Matrix[T]){
def *(that:Matrix[T]):Matrix[T] = matMul(m,that)
}
//Functionality is deferred to implementing traits
def innerProd[T:Numeric](a:Vector[T],b:Vector[T]):T
def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]):Matrix[T]
}
//Implements LinearAlgebra interface in a sequential fashion
trait SequentialLinearAlgebra extends LinearAlgebra {
def innerProd[T:Numeric](a:Vector[T],b:Vector[T]) =
((a,b).zipped map (_*_)).sum
def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]) = {
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[T:Numeric](a:Vector[T],b:Vector[T]) =
((a,b).zipped map (_*_)).sum
def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]) = {
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[T:Numeric](a:Vector[T],b:Vector[T]) =
((a,b).zipped map (_*_)).sum
def matMul[T:Numeric](A:Matrix[T],B:Matrix[T]) = {
val Bt = B.transpose
val res = A map ( row => future {Bt map (col => row dot col)})
res.map(_.apply)
}
}
The code seems correct to me, but I get the following errors:
fsc Parallel.scala
/home/felix/Documents/teaching/2014/dm509/scala/Parallel.scala:61: error: type mismatch;
found : Array[scala.collection.mutable.ArraySeq[T]]
required: SequentialLinearAlgebra.this.Matrix[T]
(which expands to) Array[Array[T]]
A.map(row => Bt.map(col => row dot col))
^
/home/felix/Documents/teaching/2014/dm509/scala/Parallel.scala:71: error: type mismatch;
found : Array[scala.collection.mutable.ArraySeq[T]]
required: ParColLinearAlgebra.this.Matrix[T]
(which expands to) Array[Array[T]]
(A.par map (row => Bt map (col => row dot col))).toArray
^
/home/felix/Documents/teaching/2014/dm509/scala/Parallel.scala:82: error: type mismatch;
found : Array[scala.collection.mutable.ArraySeq[T]]
required: FutureLinearAlgebra.this.Matrix[T]
(which expands to) Array[Array[T]]
res.map(_.apply)
^
three errors found
The problem seems to be that Array.map sometimes returns ArraySeq as oppposed to the expected Array. If I do a search-replace with Array and List, the program works as expected. The reason for moving to Array is that I wish to compare the efficiency to an imperative implementation, i.e., I need efficient random access.
Can someone explain this behaviour?
