Practice exam 2¶

Question 1¶

part a)¶

Define the term "race condition"?

part b)¶

What is the main purpose of a sync.Mutex?

Question 2¶

part a)¶

What does it mean that Go channels are typed?

part b)¶

Consider:

ch := make(chan int)

What characterizes an unbuffered channel?

Question 3¶

part a)¶

Derive the fundamental limit of speedup according to Amdahl's law.

part b)¶

Explain the key idea behind Gustafson's law, and give the formula describing that law. (You don't need to derive the final formula of Gustafson's law.)

Question 4¶

Consider the following Go program that computes a convolution in 1 dimension:

package main

import (
    "fmt"
)

func main() {
    x := []float64{1, 2, 3, 4}
    h := []float64{1, 1}

    y := make([]float64, len(x)+len(h)-1)

    for n := 0; n < len(y); n++ {
        go func(n int) {
            var sum float64
            for k := 0; k < len(h); k++ {
                if n-k >= 0 && n-k < len(x) {
                    sum += x[n-k] * h[k]
                }
            }
            y[n] = sum
        }(n)
    }

    fmt.Println(y)
}

part a)¶

What is the expected correct result of this computation for the given x and h?

part b)¶

Will this program reliably print the correct result? Briefly explain why or why not.

part c)¶

Identify one concurrency issue in this program and describe how to fix it (no need to write full code).

Hint: Which goroutine will run the Println statement?

Question 5¶

Recall the definition of discrete convolution:

\[ (x \ast h)_n = \sum_{k=0}^{M-1} x_{n-k} h_k, \]

where the subscript denotes the index of a vector, for example: \(h_k\) is the \(k\)-th element of the vector \(h\).

You are given:

Signal x of length N
Kernel h of length M
Number of workers k

part a)¶

Write a sequential Go function:

func Conv1D(x, h []float64) []float64

that computes the convolution using reflective padding: \(x_{n−k} = x_{\text{reflect}(n-k,N)}\) where the reflection function is

\[ \text{reflect}(i, N) = \begin{cases} i, \quad &\text{if } 0 \le i \le N−1 \\ −i, \quad &\text{if } i < 0 \\ 2(N−1) − i, \quad &\text{if } i \ge N \end{cases} \]

part b)¶

Now describe (in words or pseudocode) how to partition the work among k goroutines so that each computes a subset of output indices.

part c)¶

Write a Go function:

func ParallelConv1D(x, h []float64, k int) []float64

that:

Spawns k goroutines
Assigns each a contiguous chunk of output indices
Uses a sync.WaitGroup
Writes results into a shared preallocated slice

(You may omit minor syntax details.)

part d)¶

Briefly explain if this problem needs channels or mutexes. If it does not, explain why not.

Question 6¶

Consider the following Go code:

package main

import (
    "sync"
)

func worker(x, h, y []float64, start, end int, wg *sync.WaitGroup) {
    defer wg.Done()

    for n := start; n < end; n++ {
        sum := 0.0
        for k := 0; k < len(h); k++ {
            idx := n - k
            if idx >= 0 && idx < len(x) {
                sum += x[idx] * h[k]
            }
        }
        y[n] = sum
    }
}

func ParallelCompute(x, h []float64, k int) []float64 {
    N := len(x)
    M := len(h)
    y := make([]float64, N+M-1)

    var wg sync.WaitGroup
    chunk := len(y) / k

    for i := 0; i < k; i++ {
        start := i * chunk
        end := start + chunk
        if i == k-1 {
            end = len(y)
        }

        wg.Add(1)
        go worker(x, h, y, start, end, &wg)
    }

    wg.Wait()
    return y
}

part a)¶

What is the purpose of the worker function? Be specific about its inputs and outputs.

part b)¶

Explain how the output indices are divided among goroutines.

part c)¶

Why is it safe for multiple goroutines to write to the slice y without additional synchronization?

part d)¶

Modify or describe how you would modify the code so that:

Instead of contiguous chunks, each goroutine processes interleaved indices (e.g., goroutine i processes i, i+k, i+2k, ...).

Provide pseudocode or a short code snippet.