1

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?

7
  • Although the overhead will not be as low as an array, Vector does have O(1) random access. For high performance matrix operations, you probably don't want an array of arrays, but rather a single array with N * M elements where you computer the linear position based on the matrix dimensions. That also gives you the ability to have either row- or column-major organization (relevant for access locality). Since you're using a primitive type (Double), there's a very large advantage in space overhead with array over any other collection that will have to box the primitive values. Commented Mar 10, 2014 at 13:02
  • Yeah, I know one can go to great lengths to make cache efficient, platform aware implementations, but the idea here is to simply show simple parallelization strategies while comparing to a naïve imperative (triple nested whileloop) version. All this aside, the question is: why do the types not pan out? Commented Mar 10, 2014 at 13:09
  • Sorry, just to make clear: This is for educational purpose, the course is not on high-performance computing, I just need to give the students a sense of how parallelization can be done in a shared memory setting, while still giving them the sense that much more needs to be done for real high performance computing. Commented Mar 10, 2014 at 13:12
  • To help get an actual answer to your question, you should show the code that doesn't compile. It's clear from the compiler output that we're not seeing the whole program. Commented Mar 10, 2014 at 13:57
  • @RandallSchulz That's because of the little scrollbar widget thingy. /smiley Commented Mar 10, 2014 at 16:34

1 Answer 1

3

The context bound makes the difference:

scala> val as = Array.tabulate(10,10)((x,y)=>y)
as: Array[Array[Int]] = Array(Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9))

scala> as map (x => x.sum)
res0: Array[Int] = Array(45, 45, 45, 45, 45, 45, 45, 45, 45, 45)

scala> def f[A: Numeric](as: Array[Array[A]]) = as map (x => x.sum)
f: [A](as: Array[Array[A]])(implicit evidence$1: Numeric[A])scala.collection.mutable.ArraySeq[A]

scala> def f[A](as: Array[Array[A]]) = as map (x => 42)
f: [A](as: Array[Array[A]])Array[Int]

Presumably it uses the fallback CanBuildFrom that yields a Seq.

Edit: to fix it, supply a reflect.ClassTag[T] so that it can create the Array[T] you want.

You'll need it on:

def matMul[T:Numeric](A:Matrix[T],B:Matrix[T])(implicit ev1: ClassTag[T])

and

implicit class MatrixOps[T:Numeric](m:Matrix[T])(implicit ev1: ClassTag[T])
Sign up to request clarification or add additional context in comments.

2 Comments

Hmm that is horrible. I guess I could scrap the numeric typeclass for this example, but I thought it was a nice touch.
The question only asks why does it do that, but I added the more helpful fix, to enable you to upvote and accept. Do they ever call you El Fix? It might make more sense to have trait LinearAlgebra[A: Numeric] etc.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.