m6.md

Use the following commands to make a fresh clone of your repository:

git clone -b m6 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git m6

Useful links

• A guide to the Scala parallel collections
• The API documentation of the Scala parallel collections
• The API documentation of the Scala standard library
• The API documentation of the Java standard library

If you have issues with the IDE, try reimporting the build, if you still have problems, use compile in sbt instead.

Exercise

In this exercise, you will implement an array Combiner using internally a doubly linked list of arrays. Your goal is to complete the implementation of the (simplified) Combiner interface, by implementing the result method to compute the result array from this array combiner.

Here you can see the declaration of the DLLCombiner class and the related Node class definition. Look at the Lib trait in the lib.scala file to find all definitions of relevant functions and classes.

  class Node(val size: Int) {
    var value: Array[Int] = new Array(size)
    var next: Node = null
    var previous: Node = null
    var cnt = 0

    def add(v: Int) = {
      value(cnt) = v
      cnt += 1
    }
  }

  // Simplified Combiner interface
  // Implements methods += and combine
  // Abstract methods should be implemented in subclasses
  abstract class DLLCombiner(val chunk_size: Int)

DLLCombiner class contains the implementation of methods += and combine. You should look at them to better understand the structure of this array Combiner, before moving on to solving this exercise.

Your task in the exercise will be to implement the result method of the DLLCombinerImplementation class. This method should compute the result array from this array combiner. This method should work in parallel according to the Combiner contract. Implement this method efficiently using 4 parallel tasks, by copying the doubly linked list to the array from both ends at the same time. Two threads should start from the start of the list and two from the end. In each case, one thread would be responsible for odd list indexes and the other for even ones.

  class DLLCombinerImplementation(chunk_size: Int = 3) extends DLLCombiner(chunk_size) {

    // Computes every other Integer element of data array, starting from the first (index 0), up to the middle
    def task1(data: Array[Int]) = task {
      ???
    }

    // Computes every other Integer element of data array, starting from the second, up to the middle
    def task2(data: Array[Int]) = task {
      ???
    }

    // Computes every other Integer element of data array, starting from the second to last, up to the middle
    def task3(data: Array[Int]) = task {
      ???
    }

    // Computes every other Integer element of data array, starting from the last, up to the middle
    // This is executed on the current thread.
    def task4(data: Array[Int]) = {
      ???
    }

    def result(): Array[Int] = {
      val data = new Array[Int](cnt)

      ???

      data
    }

  }

Following the description above, your task in the exercise is to:

• Implement the four tasks to copy parts of the array. Each task is responsible for computing one quarter of the array, as indicated in comments:
  • Task 1: Computes every other Integer element of data array, starting from the first (index 0), up to the middle
  • Task 2: Computes every other Integer element of data array, starting from the second, up to the middle
  • Task 3: Computes every other Integer element of data array, starting from the second to last, up to the middle
  • Task 4: Computes every other Integer element of data array, starting from the last, up to the middle
• Implement the method result to compute the result array in parallel using those four tasks.

Hints:

• Note that this doubly linked list implementation uses null pointers to represent the absence of nodes. Be careful when working with null pointers in your solution, to avoid causing a NullPointerException.

• DLLCombinerImplementation comes with a private copyForward method that you can use in your solution:

  private def copyForward(data: Array[Int], curr: Node, from: Int, to: Int, limit: Int)

This method copies certain elements from a doubly linked list to an array, in a way that might be useful for this exercise.

Examples

Here is one example of the result method with intermediate results:

    val combiner1 = DLLCombinerImplementation(4)
    combiner1 += 7 // (7)
    combiner1 += 2 // (7, 2)
    combiner1 += 4 // (7, 2, 4)
    combiner1 += 3 // (7, 2, 4, 3)
    combiner1 += 9 // (7, 2, 4, 3) <-> (9)
    combiner1 += 5 // (7, 2, 4, 3) <-> (9, 5)
    combiner1 += 1 // (7, 2, 4, 3) <-> (9, 5, 1)

    val res1 = combiner1.result() // (7, 2, 4, 3, 9, 5, 1)

In this example, task1 was responsible for computing elements at indexes 0 and 2, task2 for computing the element at index 1, task3 for computing elements at indexes 5 and 3, and task4 for computing elements at indexes 6 and 4.

Here is another example with combining:

    val c1 = DLLCombinerImplementation(4)
    c1 += 7 // (7)
    c1 += 2 // (7, 2)
    c1 += 4 // (7, 2, 4)
    c1 += 3 // (7, 2, 4, 3)
    c1 += 9 // (7, 2, 4, 3) <-> (9)
    c1 += 5 // (7, 2, 4, 3) <-> (9, 5)
    c1 += 1 // (7, 2, 4, 3) <-> (9, 5, 1)

    val c2 = DLLCombinerImplementation(4)
    c2 += 6 // (6)
    c2 += 8 // (6, 8)
    c2 += 5 // (6, 8, 5)
    c2 += 1 // (6, 8, 5, 1)

    val c3 = DLLCombinerImplementation(4)
    c3 += 1 // (1)

    c1.combine(c2).combine(c3) // (7, 2, 4, 3) <-> (9, 5, 1) <-> (6, 8, 5, 1) <-> (1)
    val res = c1.result() // (7, 2, 4, 3, 9, 5, 1, 6, 8, 5, 1, 1)

You can look at the public tests to find more examples.

In your solution you should only make changes to the DLLCombinerImplementation class. You are not allowed to change the file lib.scala. You can get partial points for solving parts of this exercise.