A Dependence Removed, and the Honest Baseline

Concept map

One loop, three versions, two builds. Every box is a step you will run.

Step 1 · Set up and build it twice

Every command on this page is meant to be copied and pasted exactly as written. The only thing you ever type yourself is your names, once, in 1c.

1. 1a · Make your repository on GitLab (in the browser)

   New project → Create blank project. Name: CS4170_FA2026_R06_LASTNAME with your last name. Visibility: Private. Uncheck "Initialize repository with a README". Create it, then Settings → Members → add greenr@bgsu.edu as Maintainer.

2. 1b · Log in to Cardinal

   VS Code Remote-SSH to cardinal.osc.edu and open a terminal, or from your own terminal (put your OSC username in place of OSC_USERNAME):

   ssh OSC_USERNAME@cardinal.osc.edu

   copy

3. 1c · Your names, once

   Paste these two lines, then fix them before you press Enter: your GitLab username, and your last name exactly as it is in the project name from 1a.

   GL_USER=your-gitlab-username
   LAST=YOURLASTNAME

   copy

   Check them. This should print your project's address; if it doesn't, run 1c again.

   echo git@gitlab.com:$GL_USER/CS4170_FA2026_R06_$LAST.git

   copy

4. 1d · The lab branch, pushed to your repository

   Your openmp clone is the one from R05. If cd ~/openmp says No such file or directory, run the "No clone yet?" block first.

   cd ~/openmp
   git fetch class
   git checkout -b lab06 class/fa2026-openmp/lab06-solution
   git remote add r06 git@gitlab.com:$GL_USER/CS4170_FA2026_R06_$LAST.git
   git push -u r06 lab06:main
   git config push.default upstream

   copy
   No clone yet?

   git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/openmp.git ~/openmp

   copy

   Then run 1d. If git asks for a password or says Permission denied (publickey), Cardinal has no GitLab key yet: the Permission denied (publickey) row of the troubleshooting table in README.md on the branch (view it on GitLab), or the MPI setup you did in September.

   What you should see

   Switched to a new branch 'lab06', then a push ending branch 'lab06' set up to track 'r06/main'. Check with:

   git status
   ls

   copy

   On branch lab06, and README.md Default ex6 harness jobScript.slurm predictions src among the files.

5. 1e · Cores of your own

   One allocation for steps 1 to 5: 48 cores for 30 minutes. Wait for Granted job allocation before you paste anything else. If you run out of time, run this line again; nothing is lost.

   salloc -N 1 -n 1 -c 48 -t 00:30:00 -A PCS0313

   copy
   salloc or srun fails? (for example Protocol authentication error)

   Skip the allocation. From the login node, paste this once; every srun on this page then queues its own short job with the right account and cores, and the commands work unchanged. Paste it again after any new login.

   srun() { command srun -A PCS0313 -N 1 -n 1 -c 48 -t 00:10:00 "$@"; }

   copy

   Each command now waits in the queue before it runs, usually seconds, sometimes a few minutes.

6. 1f · Both builds, on the compute node

   cd ~/openmp
   module load gcc/12.3.0
   srun -c 48 make -C Default OSC O3

   copy
   What you should see

   Two built ... with: lines, one ending g++ -O2 and one ending g++ -O3 -march=native. Then:

   ls -l Default/OMP Default/OMP_O3

   copy

   Two executables. No such file for either one means the build failed: scroll up to the first error:.

   Paste → nothing. Step 1 has no block in the README; the job in step 6 rebuilds both binaries anyway.

Step 2 · The original loop

A leaky running total: each element is most of the previous total plus a new value. Five lines, and one of them is the whole problem.

// KEEP = 0.99999999: each step keeps almost all of the total so far
double s = 0.0;

for (long i = 0; i < n; i++) {
    s = KEEP * s + x[i];
    y[i] = s;
}

Run it

Still inside your allocation from 1e. tee shows the output and keeps a copy in ex6/steps/, so nothing depends on your scrollback.

cd ~/openmp
module load gcc/12.3.0
mkdir -p ex6/steps
OMP_NUM_THREADS=1 srun -c 48 Default/OMP leaky_serial 1e8 | tee ex6/steps/step2.txt

The two lines for block 2, and nothing else:

grep -E '^(CHECK|ELAPSED)' ex6/steps/step2.txt

HOST <a compute node>
THREADS 1
N 100000000  KEEP 0.99999999
CHECK leaky_serial ok  max rel err 0 (tolerance 1e-09)
ELAPSED …

Step 3 · The wrong fix

The obvious move: put parallel for on the loop and hope. The program has this version on purpose. It is called leaky_racy.

y[0] = x[0];

#pragma omp parallel for schedule(static)
for (long i = 1; i < n; i++) {
    y[i] = KEEP * y[i - 1] + x[i];     // y[i-1] may not be written yet
}

Run it, at two sizes

cd ~/openmp
module load gcc/12.3.0
mkdir -p ex6/steps
OMP_NUM_THREADS=48 srun -c 48 Default/OMP leaky_racy 1e8 --repeat 100 | tee ex6/steps/step3_1e8.txt
OMP_NUM_THREADS=48 srun -c 48 Default/OMP leaky_racy 1e4 --repeat 100 | tee ex6/steps/step3_1e4.txt

The four lines for block 3, in order (10⁸ first):

grep -hE '^(CORRECT|IDENTICAL)' ex6/steps/step3_1e8.txt ex6/steps/step3_1e4.txt

run 1 of 100:  CHECK leaky_racy WRONG  97916665 of 100000000 elements … first at i = 2083335 (block 1 of 48) …
CHECK leaky_racy WRONG  0 of 100 runs correct
CORRECT 0/100
IDENTICAL 100/100  (bitwise, against run 1)      ← n = 10⁸: the same wrong answer every run
…
CORRECT 0/100
IDENTICAL 1/100  (bitwise, against run 1)        ← n = 10⁴: a different wrong answer almost every run

Step 4 · The right fix

Remove the dependence instead of ignoring it: a two-pass blocked scan. Each thread scans its own block from zero, one thread works out what each block should have started from, and each thread adds that back in.

y[lo + j]  =  s_(lo + j)  +  KEEP^(j + 1) * c          // j = 0, 1, 2, ... inside the block

The three parts, animated

// pass 1: scan my block from zero
double s = 0.0;
for (long i = lo; i < hi; i++) {
    s = KEEP * s + x[i];
    y[i] = s;
}
blockLast[tid] = s;

// the carries: every thread must finish pass 1 first
#pragma omp barrier

#pragma omp single
{
    for (int k = 1; k < p; k++) {
        long len = blockLo(n, k, p) - blockLo(n, k - 1, p);
        carryIn[k] = std::pow(KEEP, (double) len) * carryIn[k - 1] + blockLast[k - 1];
    }
}   // implicit barrier: every carryIn[] is set

// pass 2: add my decayed carry back in -- a running factor, not pow per element
double c = carryIn[tid];
for (long i = lo; i < hi; i++) {
    c *= KEEP;
    y[i] += c;
}

Run it

cd ~/openmp
module load gcc/12.3.0
mkdir -p ex6/steps
OMP_NUM_THREADS=48 srun -c 48 Default/OMP leaky 1e8 --repeat 20 | tee ex6/steps/step4.txt

The two lines for block 4:

grep -E '^(CORRECT|IDENTICAL)' ex6/steps/step4.txt

THREADS 48
N 100000000  KEEP 0.99999999
CHECK leaky ok  20 of 20 runs correct
CORRECT 20/20
IDENTICAL 20/20  (bitwise, against run 1)
ELAPSED …

Step 5 · What the fix costs

The scan gives the same answer as the loop, in parallel. It is not free. On one thread it does strictly more work than the loop it replaced, and that extra work is paid at every thread count, divided among the threads.

Open the file and fill in every field: in VS Code, open predictions/ex6.yaml from the explorer; in a plain terminal, use the line below (type your answers, then Ctrl+O, Enter, Ctrl+X to save and quit).

cd ~/openmp
nano predictions/ex6.yaml

Commit and push it. The last line prints the commit hash for README §1.

cd ~/openmp
git add predictions/ex6.yaml
git commit -m "R06 prediction, before step 5 and the job"
git push
git log -1 --format=%h

Run it: the first look

cd ~/openmp
module load gcc/12.3.0
mkdir -p ex6/steps
OMP_NUM_THREADS=1 srun -c 48 Default/OMP leaky 1e8 | tee ex6/steps/step5_scan.txt
OMP_NUM_THREADS=1 srun -c 48 Default/OMP leaky_serial 1e8 | tee ex6/steps/step5_serial.txt

The two ELAPSED lines for block 5, scan first. The ratio (first ÷ second) is yours to work out and write on a third line.

grep -h '^ELAPSED' ex6/steps/step5_scan.txt ex6/steps/step5_serial.txt

Done with the allocation. Give the cores back; step 6 is submitted from the login node. (Used the srun() line from 1e instead of salloc? Skip this: there is no allocation, and exit would log you out.)

exit

Step 6 · The honest baseline

Speedup = serial time ÷ parallel time. Step 1 built two serial times for the same loop. This step measures both, and the scan at 1 to 48 threads, and makes you choose.

Run the job

From the login node (after the exit in step 5), in the repository root. Commit your prediction first; it was step 5.

cd ~/openmp
sbatch jobScript.slurm

It prints Submitted batch job and a number. Check on it; rerun this line every minute or two until your job is no longer listed (it runs under ten minutes once it starts, and you also get an email when it ends):

squeue -u $USER

When it is gone from the list, check that everything came back:

cd ~/openmp
ls ex6/results
cat ex6/results/check.txt

Then print block 6 exactly as the README lays it out, each table under its file name:

cd ~/openmp
for f in serial_O2 serial_O3 scan1_O2 scan_O3; do
    echo "ex6/results/$f.csv"
    python3 harness/reduce.py ex6/results/$f.csv
    echo
done

cd ~/openmp
tail -n 30 $(ls -t slurm-*.out | head -1)

Two speedups from one run

What you hand in

The URL of your CS4170_FA2026_R06_LASTNAME project, in Canvas, by Sunday, November 15, 11:59 PM. Three sections in README.md and a time line.

git add -A
git commit -m "R06 record and judgment"
git push