/*
 * 01-omp-for-schedule.c  —  Who does which iteration? (schedule clause)
 * Session 10 · 2311CSC501J Parallel Processing · Unit IV — OpenMP in Depth
 *
 * WHAT THIS SHOWS
 *   #pragma omp for splits the iterations of a loop across a team of threads.
 *   But HOW does it decide which thread gets which iterations? That is the job
 *   of the schedule() clause. This program runs the SAME loop three ways —
 *   static, dynamic, and guided — and prints which thread executed each
 *   iteration, so you can literally see the difference.
 *
 *   To make the effect visible we give the LATER iterations more work (a tiny
 *   busy-wait that grows with i). This is an "unbalanced" loop, exactly the
 *   situation where the choice of schedule matters.
 *
 *     static           — iterations split into equal, fixed chunks up front.
 *                        Cheapest (no coordination), best when every iteration
 *                        costs the same. With uneven work, the thread that got
 *                        the heavy tail finishes last while others sit idle.
 *     dynamic[,chunk]  — threads grab the next chunk when they finish the last.
 *                        Great for uneven work (self load-balancing), but the
 *                        grabbing has coordination overhead.
 *     guided[,chunk]   — like dynamic, but chunk sizes start large and shrink.
 *                        A compromise: low overhead early, good balance at the end.
 *
 *   Rule of thumb (ties to Session 09 load balancing):
 *     even work  -> static ;  uneven/unpredictable work -> dynamic or guided.
 *
 * HOW TO COMPILE & RUN
 *       gcc -fopenmp 01-omp-for-schedule.c -o schedule
 *       OMP_NUM_THREADS=4 ./schedule
 *
 *   macOS (Apple clang): clang -Xpreprocessor -fopenmp -lomp 01-omp-for-schedule.c -o schedule
 *   Or paste into OnlineGDB / godbolt.org (add -fopenmp) — no install needed.
 *   Set the team size with OMP_NUM_THREADS=4 (or omp_set_num_threads(4); below).
 */

#include <stdio.h>
#include <omp.h>

#define N 16    /* small so the per-iteration printout is easy to read */

/* A trivial, deliberately-wasteful bit of work whose cost grows with i.
 * Returns a value so the compiler cannot optimize the loop away. */
static long busy_work(int i) {
    long acc = 0;
    /* later iterations (bigger i) spin more -> an unbalanced loop */
    for (long k = 0; k < (long)(i + 1) * 200000L; k++) {
        acc += k % 7;
    }
    return acc;
}

/* Run the loop once with a given schedule and label, printing thread ownership. */
static void run_loop(const char *label) {
    long total = 0;

    /* runtime schedule is chosen by the caller via omp_set_schedule() below,
     * OR you can hard-code e.g. schedule(static) / schedule(dynamic,2). Here we
     * use schedule(runtime) so one function can demonstrate all three. */
    #pragma omp parallel for schedule(runtime) reduction(+:total)
    for (int i = 0; i < N; i++) {
        int tid = omp_get_thread_num();
        printf("  [%-8s] iteration %2d  ->  thread %d\n", label, i, tid);
        total += busy_work(i);
    }

    /* total is only printed so the work is not optimized away. */
    printf("  [%-8s] done (checksum %ld)\n\n", label, total);
}

int main(void) {
    /* Uncomment to force a team size instead of using OMP_NUM_THREADS:
     * omp_set_num_threads(4); */

    printf("Running the SAME 16-iteration unbalanced loop three ways.\n");
    printf("Watch which thread picks up which iteration.\n\n");

    /* schedule(runtime) reads its policy from omp_set_schedule (or the
     * OMP_SCHEDULE environment variable). We set it explicitly per run. */

    printf("STATIC  — equal fixed chunks decided up front:\n");
    omp_set_schedule(omp_sched_static, 0);   /* chunk 0 => default even split */
    run_loop("static");

    printf("DYNAMIC(2) — threads grab 2 iterations at a time as they finish:\n");
    omp_set_schedule(omp_sched_dynamic, 2);
    run_loop("dynamic");

    printf("GUIDED  — big chunks first, shrinking toward the end:\n");
    omp_set_schedule(omp_sched_guided, 0);
    run_loop("guided");

    printf("Notice: with STATIC, the thread that got the high-numbered (heavy)\n");
    printf("iterations finished last. DYNAMIC and GUIDED spread the heavy tail\n");
    printf("more evenly — that is load balancing in action.\n");
    return 0;
}