Exercise 5¶

What this exercise is about¶

Pick one question from Q1 and Q2 and solve it.

General Instructions¶

All submitted work must be stored in your GitLab repository. Below it will be explained how to do that. For the repository it is important that:

one exercise = one GitLab repository → each exercise gets its own GitLab repository
your repository must be private
your repository must be named exactly as specified (in the setup below); do not change the name or the upper-case/lower-case letters
create commits frequently, at least one commit per question
push your work frequently (this also is your backup if your laptop breaks)
your repository must be up-to-date before the deadline
you must double-check your repository in the web browser to make sure all your work is uploaded to the code.vt.edu server
you must provide screenshots as proof when they are requested; screenshots are also committed to the repository

⚠️ You must run your code yourself! Not following this is an Honor Code violation.

⚠️ You must create complete log files of all AI conversations! Not following this is an Honor Code violation.

0. Setup: Git and GitLab¶

Create a new repository on GitLab at code.vt.edu:
- in the top-left corner, click the "+" icon
- in the new menu that pops up, click "New project/repository"; a new page loads
- in the new page, click the "Create black project" button; a new page loads:
  - enter the "Project name":
```
cmda3634-ex5
```
  - in the drop-down field "Pick a group or namespace", select your username
  - the "Project slug" field should populate automatically after entering a project name; do not change the slug
  - for the "Visibility level", select "private" (very important!)
  - for the "Project configuration", select only "Initialize repository with README"
Add the instructor and TA to your repository as a member with Developer access. In the web browser with your new repository open:
- in the left sidebar, hover the mouse cursor over "Manage"
- in the menu that pops up, click "Members"; a new page loads
- on the new page, click button "Invite members"
  - enter the jrudi
  - select maximum role: "Developer"
  - click the button "Invite"
- repeat to invite a new member:
  - enter the jraind
  - select maximum role: "Developer"
  - click the button "Invite"

1. Parallel Reduction Patterns¶

This question explores different approaches to reduction operations in parallel programs, a fundamental pattern in data science and scientific computing.

Problem¶

Compute the sum of a large array. Compare different parallel reduction strategies.

A reduction takes many values and combines them into a single value using an associative operation (like +, *, min, max).

Part A: Sequential Implementation¶

Implement a sequential sum function:
```
func sumArray(data []float64) float64
```
Test with known values to verify correctness.
Generate a large array (e.g., 10,000,000 elements) and measure execution time.

Part B: Parallel Reduction with Shared Accumulator (Mutex)¶

Implement a parallel version where multiple goroutines share a single accumulator:

type SharedAccumulator struct {
    sum float64
    mu  sync.Mutex
}

func (sa *SharedAccumulator) Add(value float64)

Each goroutine processes a chunk of the array and adds its local sum to the shared accumulator.
Use sync.WaitGroup to synchronize goroutines.
Run with -race to check if any race conditions are detected (note that false negatives are possible).
Measure execution time with varying numbers of goroutines.

Part C: Lock-Free Reduction (Local + Combine)¶

Implement a parallel version where each goroutine computes a local sum first, then combine at the end:

func sumArrayParallel(data []float64, numGoroutines int) float64 {
    chunkSize := len(data) / numGoroutines
    var wg sync.WaitGroup
    localSums := make([]float64, numGoroutines)

    // Each goroutine computes local sum
    // Combine local sums after WaitGroup

    return total
}

This approach avoids the mutex contention during the main computation.
Verify correctness by comparing with the sequential version.
Run with -race to detect possible races.
Measure execution time.

Part D: Performance Comparison¶

Compare the performance of:
- Sequential version
- Mutex-based parallel version
- Lock-free (local + combine) parallel version
Test with varying:
- Array sizes (small, medium, large)
- Make sure that the code can handle data that is not divisible by the number of workers
- Number of goroutines (2, 4, 8)
Create a log-file and graph of your results. Present the graph in the README.md.
Use the Graph in 3 and answer the following questions:

a) Which approach is fastest? Why?\ b) Under what conditions might the mutex version be acceptable?\ c) What happens to mutex contention as you increase goroutines?\ d) Does the lock-free version always scale linearly with goroutines? Why or why not?

Part E: Other Reduction Operations¶

Implement parallel versions for:

Finding the maximum value
Finding the minimum value (Optional)
Computing the product (Optional)

Learning goals¶

Understanding reduction as a fundamental parallel pattern
Comparing mutex-based vs. lock-free reduction
Understanding mutex contention and its performance impact
Performance analysis and scaling
When to use each approach in real applications
Reduction operations in data science (aggregations, statistics)

2. Parallel Reduction with Channels (Fan-in Pattern)¶

This question explores using channels for reduction operations, implementing the fan-in pattern where multiple goroutines send results to a single goroutine that combines them.

Problem¶

Compute the sum of a large array using channel-based reduction. This is a common pattern in data science where workers process data chunks and send results to a collector.

Part A: Sequential Implementation¶

Implement a sequential sum function:
```
func sumArray(data []float64) float64
```
Test with known values to verify correctness.

Part B: Fan-in Reduction with Channels¶

Implement a parallel version using the fan-in pattern:
- Create a work channel to distribute chunks to workers (in many real applications we already have distributed data we have to do a reduction on)
- Launch multiple worker goroutines
- Each worker:
- Receives a chunk from the work channel
- Computes the partial sum
- Sends the partial sum to a result channel
- A collector goroutine receives all partial sums and combines them
```
func sumArrayChannelReduction(data []float64, numWorkers int) float64 {
    workCh := make(chan []float64)
    resultCh := make(chan float64, SomeBufferValueIfNeeded)

    // Launch workers
    // Each worker receives chunks, computes sum, sends to resultCh

    // Send work to workCh

    // Collect results from resultCh

    return total
}
```
Use proper channel directions.
Ensure all workers complete before collecting final results.
Verify correctness by comparing with sequential version.

Part C: Multiple Result Channels for Fan-in¶

Extend the implementation to handle multiple result channels using select or similar:
- Each worker has its own result channel
```
resultChs := make([]chan float64)
for i := range resultChs {
    resultChs[i] = make(chan float64)
}
```
- Use select to receive from any worker as results arrive
Compare the performance with the single result channel approach.

Part D: Timing and Analysis¶

Test with large arrays (e.g., 10,000,000 elements). Make sure that the code can handle data that is not divisible by the number of workers
Compare execution times:
- Sequential version
- Channel-based fan-in with 2 workers
- Channel-based fan-in with 4 workers
- Channel-based fan-in with 8 workers
Does adding more workers always improve performance? Explain.

Part E: Other Reduction Operations (Optional)¶

Implement channel-based reduction for:
- Finding maximum value
- Finding minimum value
How does the fan-in pattern compare to the mutex approach for these operations?

Learning goals¶

Fan-in pattern with channels
Channel-based work distribution
Using select for multiplexing
Comparing channel-based vs mutex-based reduction
Performance analysis of channel communication overhead

Final README and reflection¶

Update the README.md file in your submission repository. (If no file named README.md exists in your repository, then create one.)

Add complete log files of ALL your AI conversations – just like you did in the previous exercises. Store them in the files named ai_log.md.

Create folders named after the questions that you completed (one of q1, q2).

Write "Reflection" and "AI use" statements into the README.

Submission¶

Submit this exercise, as done with all previous exercises, via Canvas and GitLab.

Do not forget to submit the link in Canvas on time and do not edit the GitLab after the link has been submitted to Canvas.

Congrats! You're done! 🍪