Practice exam 11¶

Question 1¶

part a)¶

Go supports two major concurrency approaches. Please list what they are?

part b)¶

Why is the following operation unsafe in concurrent programs?

balance = balance + amount

(Assume that this operation is run by more than one goroutine.)

Question 2¶

part a)¶

Consider:

ch := make(chan int)

ch <- 42
fmt.Println(<-ch)

What will happen when this program runs?

part b)¶

In the bank account example that uses channels, the balance variable is accessed only by the teller() goroutine. Why is this design useful in the context of concurrency?

Question 3¶

part a)¶

Explain a general experimental setup with the goal to measures runtimes and, in turn, compute weak scalability. Use the notation n for problem size and p for processes.

part b)¶

Explain how the experimental setup would differ when one wants to determine strong scalability.

Question 4¶

Consider the following self-contained Go program.

package main

import (
    "fmt"
    "sync"
)

func distribute(n, k int) [][2]int {
    chunk := n / k
    segments := make([][2]int, k)
    for i := 0; i < k; i++ {
        start := i * chunk
        end := start + chunk
        if i == k-1 {
            end = n
        }
        segments[i] = [2]int{start, end}
    }
    return segments
}

func main() {
    vals := []float64{1, 2, 3, 4, 5, 6, 7, 8}
    out  := make([]float64, len(vals))
    k    := 3

    segs := distribute(len(vals), k)
    fmt.Println(segs)

    var wg sync.WaitGroup
    for _, seg := range segs {
        wg.Add(1)
        s, e := seg[0], seg[1]
        go func() {
            defer wg.Done()
            for i := s; i < e; i++ {
                out[i] = vals[i] * 2
            }
        }()
    }
    wg.Wait()
    fmt.Println(out)
}

part a)¶

What does distribute(8, 3) return? Write the exact value printed by the first fmt.Println.

part b)¶

What does the second fmt.Println print? Justify your answer in one sentence.

part c)¶

The goroutine closure captures s and e as local copies rather than using seg[0] and seg[1] directly inside the loop. Why is this important? What incorrect output could occur if the code were instead written as:

go func() {
    defer wg.Done()
    for i := seg[0]; i < seg[1]; i++ { ... }
}()

part d)¶

The goroutines write to non-overlapping ranges of out. Is a mutex needed to protect these writes? Briefly justify your answer.

Question 5 (advanced)¶

The prefix sum (also called scan) of a sequence \(x[0], x[1], \ldots, x[N-1]\) is the sequence \(s[0], s[1], \ldots, s[N-1]\) defined by:

A parallel strategy partitions the array into \(k\) contiguous blocks of roughly equal size. Each goroutine independently computes the sum of its own block. The block sums are then used to compute an offset for each block: the offset for block \(i\) is the sum of all block sums for blocks \(0, 1, \ldots, i-1\) (the offset for block 0 is equal to 0). Finally, each goroutine adds its block's offset to every element of its partial prefix sum to produce the correct global prefix sum.

part a)¶

Implement the function signature below. Use exactly k goroutines for the first parallel phase (computing partial sums within each block). Use a sync.WaitGroup to synchronise.

func ParallelPrefixSum(x []float64, k int) []float64

part b)¶

After the first parallel phase, the main goroutine computes the block offsets sequentially. Explain why this sequential step is necessary (i.e., why cannot the offsets be computed in parallel with the first phase)?

part c)¶

Launch a second parallel phase (again k goroutines, again using a WaitGroup) in which each goroutine adds its block's offset to every entry of the partial prefix sum it computed in phase 1. Write this second phase. What is the overall time complexity of your parallel algorithm, assuming unlimited processors and ignoring the sequential offset step?

Hint: for full credit your implementation should use two separate sync.WaitGroup synchronisation barriers — one after phase 1, one after phase 2.

Question 6 (advanced)¶

The function below uses a worker-pool pattern (rather than index partitioning) to apply a sliding-window moving average to a signal. Read it carefully, then answer the questions.

package main

import "sync"

type job struct {
    idx int
    x   []float64
    w   int
}

func workerMA(jobs <-chan job, out []float64, wg *sync.WaitGroup) {
    defer wg.Done()
    for j := range jobs {
        n := len(j.x)
        sum := 0.0
        lo := j.idx - j.w/2
        hi := j.idx + j.w/2
        for t := lo; t <= hi; t++ {
            if t >= 0 && t < n {
                sum += j.x[t]
            }
        }
        count := 0
        for t := lo; t <= hi; t++ {
            if t >= 0 && t < n {
                count++
            }
        }
        out[j.idx] = sum / float64(count)
    }
}

func ParallelMovingAverage(x []float64, w, k int) []float64 {
    n   := len(x)
    out := make([]float64, n)
    jobs := make(chan job, n)

    var wg sync.WaitGroup
    for i := 0; i < k; i++ {
        wg.Add(1)
        go workerMA(jobs, out, &wg)
    }

    for i := 0; i < n; i++ {
        jobs <- job{idx: i, x: x, w: w}
    }
    close(jobs)

    wg.Wait()
    return out
}

part a)¶

Explain what workerMA computes for a given job. In particular: what role does w play, why is count computed separately from sum, and what boundary condition does the if t >= 0 && t < n guard handle?

part b)¶

Why is the channel jobs created with a buffer of size n rather than 0 (unbuffered)? What deadlock risk would arise if the buffer were 0 and k == 1? (Assume n > 1.)

part c)¶

The current implementation loops over [lo, hi] twice: once to accumulate sum and once to count valid indices. Rewrite workerMA to use a single loop, computing both sum and count simultaneously. Your rewrite must produce identical output and must not change the function signature.