Exercise 4¶

What this exercise is about¶

Pick one question from Q1 and Q2 and solve it. (Only one them will be graded.)
Pick one question from Q3 and Q4 and solve it. (Only one them will be graded.)

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-ex4
```
  - 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 Leibniz Formula for \(\pi\) (45 points)¶

The Leibniz series for \(\pi\) is:

\[ \pi = 4 \sum_{n=0}^{N} \frac{(-1)^n}{2n+1} \]

Implement a sequential version:
```
func piLeibniz(N int) float64
```
Verify that your implementation approximates \(\pi\). Argue why.
Implement a second parallel version where:
- The iteration space is split into chunks
- Each goroutine computes a partial sum
- Partial sums are combined after wg.Wait()
Important: Do not use channels or mutual exclusion (because we did not cover this).
Measure execution time for large N and compare sequential vs parallel.
Increase N and record the effect of N on execution time. Explain your observations.

Learning goals¶

Dividing loop iterations among workers
Chunk-based decomposition
Reduction pattern (partial sums → final result)

2. Parallel Monte Carlo \(\pi\) (45 points)¶

Use random sampling to approximate \(\pi\):

Generate random points in the unit square.
Count how many fall inside the unit circle.

\[ \pi \approx 4 \cdot \frac{\text{points inside}}{\text{total points}} \]

Implement a sequential version:
```
func piMC(N int) float64
```
N is the number of random samples. Verify that your implementation approximates \(\pi\). Argue why.
Implement a second parallel version:
- Divide the total number of samples among multiple goroutines.
- Each goroutine:
- Generates random points
- Counts local hits
- Combine counts after join.
Important: Do not use channels or mutual exclusion (because we did not cover this).
Measure execution time for large N and compare sequential vs parallel.
Increase N and record the effect of N on execution time. Explain your observations.

Learning goals¶

Work partitioning
Local counters to avoid contention
Aggregation step

3. Parallel Numerical Integration (45 points)¶

Approximate:

\[ \int_a^b f(x),dx \]

using the midpoint rule:

\[ \sum_{i=0}^{N-1} f(x_i)\Delta x \]

Implement:
```
func integrate(f func(float64) float64, a, b float64, N int) float64
```
Verify that your implementation approximates the integral of a given function. Argue why.
Write a parallel version:
- Divide the interval into equal subranges
- One goroutine per subrange
- Combine results using fork–join
Important: Do not use channels or mutual exclusion (because we did not cover this).
Measure execution time for large N and compare sequential vs parallel.
Increase N and record the effect of N on execution time. Explain your observations.

Test case¶

Use:

\[ f(x) = x^2 \]

over \([0,1]\) (exact result = ⅓).

Learning goals¶

Parallelizing numerical loops
Parameter passing to goroutines
Reduction of partial results

4. Parallel Matrix-Matrix Multiplication (45 points)¶

Given:

\[ C = A B \]

where:

\(A\) is an \(m \times r\) matrix
\(B\) is an \(r \times n\) matrix
\(C\) is the resulting \(m \times n\) matrix

Each entry of \(C\) is defined as:

\[ C_{ij} = \sum_{k=0}^{r-1} A_{ik} B_{kj} \]

Observe that each row of \(C\) can be computed independently; and that each entry \(C_{ij}\) can be computed independently.

Sequential Implementation:

func MatMat(A, B [][]float64) [][]float64

Parallel Implementation
- Use one goroutine per row of \(C\)
- Use sync.WaitGroup
- Each goroutine computes all columns of its assigned row
- Store results directly in the correct indices of the output matrix C
Measure execution while varying rows and columns of the matrices \(A,B\); and compare sequential vs parallel time.
Increase the number of rows and columns simultaneously and record the effect on execution time. Explain your observations.

Final README and reflection (10 points)¶

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 Exercise 2. Store then in the files named ai_log.md.

Create folders that contain your solutions named after the questions that you completed (two from the choices q1, q2, q3, q4).

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! 🍪