convolution.worksheet.sc

import lecture1.parallel

def numContributeTo(input: Array[Int], kernel: Array[Int], output: Array[Int], i: Int): Int =
  if i < 0 || i >= output.length then
    0
  else if (i - kernel.length < 0) then
    i+1
  else if (i >= input.length) then
    output.length - i
  else kernel.length

def sequentialConvolve(
  input: Array[Int],
  kernel: Array[Int],
  output: Array[Int],
  from: Int,
  until: Int
  ): Unit = {
    // Approach A, as described in the clarification announcement for this
    // exercise, where we treat `from` and `until` as indices on `output`
    // instead of `input` as in the given code.
    var iOutput = from
    while iOutput < until do
      var iKernel = math.max(0, iOutput - input.length + 1)
      while iKernel < kernel.length && iKernel <= iOutput do
        // `output` is only ever written to between the indices `from` and
        // `until`, the range of `iOutput`. The indices for `input` and
        // `kernel` are computed accordingly.
        output(iOutput) += input(iOutput - iKernel) * kernel(iKernel)
        iKernel += 1
      iOutput += 1

    // ALTERNATE SOLUTION: Approach B, as described in the clarification
    // announcement for this exercise, which is unchanged from the given
    // code, i.e. we treat `from` and `until` as indices on `input`.
    var iInput = from
    while iInput < until do
      var iKernel = 0
      while iKernel < kernel.length do
        output(iInput + iKernel) += input(iInput) * kernel(iKernel)
        iKernel += 1
      iInput += 1
  }

def parallelConvolve(
    input: Array[Int],
    kernel: Array[Int],
    output: Array[Int],
    from: Int,
    until: Int,
    threshold: Int
): Unit =
  // Approach A, as described in the clarification announcement for this
  // exercise, where we treat `from` and `until` as indices on `output`
  // instead of `input` as in the given code. This does not require us to
  // change anything in this function.  Only receives full credit if used
  // together with Approach A for `sequentialConvolve`.
  if (until - from) <= threshold then
    sequentialConvolve(input, kernel, output, from, until)
  else
    val mid = from + (until - from) / 2
    parallel(
      parallelConvolve(input, kernel, output, from, mid, threshold),
      parallelConvolve(input, kernel, output, mid, until, threshold)
    )

  // ALTERNATE SOLUTION: Approach B, as described in the clarification
  // announcement for this exercise, where we treat `from` and `until` as
  // indices on `input` as in the given code. This requires up to leave a
  // gap in the parallel calls to be filled in sequentially as described
  // below. Only receives full credit if used together with Approach B for
  // `sequentialConvolve`.
  if (until - from) <= threshold then
    sequentialConvolve(input, kernel, output, from, until)
  else
    val mid = from + (until - from) / 2
    val gap = numContributeTo(input, kernel, output, mid)
    // Leave a gap large enough that accesses to `output` from the first
    // parallel call will not overlap with accesses from the second. This
    // gap is of size equal to the number of elements of `input` that will
    // contribute to the computation of the result at the lowest index of
    // `output` in the second parallel call, namely, at index `mid`.
    // However, we are careful not to access indices lower than `from`.
    val gapBeforeMid = Math.max(from, mid - gap + 1)
    parallel(
      parallelConvolve(input, kernel, output, from, gapBeforeMid, threshold),
      parallelConvolve(input, kernel, output, mid, until, threshold)
    )
    // Fill in the gap sequentially.
    sequentialConvolve(input, kernel, output, gapBeforeMid, mid)

object Original_WithOutputRace:

  def sequentialConvolve(
      input: Array[Int],
      kernel: Array[Int],
      output: Array[Int],
      from: Int,
      until: Int): Unit =
    var iInput = from
    while iInput < until do
      var iKernel = 0
      while iKernel < kernel.length do
        output(iInput + iKernel) += input(iInput) * kernel(iKernel)
        iKernel += 1
      iInput += 1

  def parallelConvolve(
      input: Array[Int],
      kernel: Array[Int],
      output: Array[Int],
      from: Int,
      until: Int,
      threshold: Int): Unit =
    if (until - from) <= threshold then
      sequentialConvolve(input, kernel, output, from, until)
    else
      val mid = from + (until - from)/2
      parallel(
        parallelConvolve(input, kernel, output, from, mid, threshold),
        parallelConvolve(input, kernel, output, mid, until, threshold))