m1.md

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

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

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

Given the following sequential implementation of a function that computes the sequence of rolling averages, your task will be to complete and optimize a parallel version of this code.

/** Compute the rolling average of array.
 *
 *  For an array `arr = Arr(x1, x2, x3, ..., xn)` the result is
 *  `Arr(x1 / 1, (x1 + x2) / 2, (x1 + x2 + x3) / 3, ..., (x1 + x2 + x3 + ... + xn) / n)`
 */
def rollingAveragesSequential(arr: Array[Int]): Array[Double] =
  // Transform all numbers to fractions with denominator 1
  val arr1 = arr.map(x => Frac(x, 1))
  // Compute the rolling average keeping the sum of all elements in the numerator and the count of elements in the denominator.
  val arr2 = arr1.scan(Frac(0, 0))((acc, x) => Frac(acc.numerator + x.numerator, acc.denominator + x.denominator))
  // Transform fractions to Doubles
  arr2.map(frac => frac.toDouble)
  // Drop the extra initial element that was added by the scan
  arr3.tail

This implementation has some issues:

• It does not use parallelism
• Creates two intermediate arrays by calling map
• Creates an extra intermediate arrays by calling tail
• Scan returns an extra element we do not need

We want to parallelize and avoid the creation of the extra arrays. As we are calling a scan the natural operations we need are upsweep and downsweep. It is possible specialize those operations for our problem by letting those operations do the mapping. It is also possible to change those operations to not generate the first element.

We give you a version of rollingAveragesSequential that partially implements the parallelization using upsweep and downsweep.

Your tasks in the exercise will be to:

• TASK 1: Implement the parallelization of upsweep and downsweep
• TASK 2: Remove the calls to the map
• TASK 3: Remove the call to tail

You can get partial points for solving part of the tasks. The order of the tasks is a suggestion, you may do them in any order if that is simpler for you.

Look at the Lib trait to find the definitions of functions and classes you can use (or already used). In this question we use a Arr array class instead of the normal Array. You may assume that this class has the same performance characteristics as the normal array. Arr provides only a limited set of operations.