a.)

Show all the data, anti and output dependence. Note: dependent instructions may not be next to each other.

Data (RAW)

An instruction needs to read a value that a previous instruction writes. This is a “true” dependency because the actual data is being passed between instructions.

i1 → i2: i1 writes f0, i2 reads f0
i2 → i4: i2 writes f4, i4 reads f4
i3 → i4: i3 writes f6, i4 reads f6
i4 → i5: i4 writes f6, i5 reads f6
i6 → i8: i6 writes x1, i8 reads x1
i8 → i9: i8 writes x4, i9 reads x4

i6 → i1 (next iteration): i6 writes x1, i1 reads x1
i7 → i3 (next iteration): i7 writes x2, i3 reads x2
i7 → i5 (next iteration): i7 writes x2, i5 reads x2

Anti (WAR)

An instruction wants to write to a register or memory location that a previous instruction is still scheduled to read

i1 → i6: i1 reads x1, i6 writes x1
i3 → i7: i3 reads x2, i7 writes x2
i5 → i7: i5 reads x2, i7 writes x2

i2 → i1 (next iteration): i2 reads f0, i1 writes f0
i4 → i2 (next iteration): i4 reads f4, i2 writes f4
i5 → i4 (next iteration): i5 reads f6, i4 writes f6

Output (WAW)

Two instructions write to the same register or memory location. Within a Single Loop Iteration:

i3 → i4: i3 writes to f6, i4 writes to f6

b.)

Assume a single-issue pipeline. Show how the loop would look both unscheduled by the compiler and after compiler scheduling, including any stalls or idle clock cycles. What is the execution time (in cycles) per element of the result vector Y, unscheduled and scheduled?

Unscheduled

• The total execution time for one element of the vector Y is 22 clock cycles.

Scheduled

• The total execution time for one element of the vector Y is 19 clock cycles.

c.)

Assume a single-issue pipeline. Unroll the loop by a factor of 4 to schedule it without any stalls, collapsing the loop overhead instructions. Show the unrolled and scheduled instruction sequence. What is the execution time per element of the result? You can assume that the number of iterations is always a multiple of the unrolled loop body.

• The unrolled and scheduled loop processes 4 elements in a total of 24 cycles

Execution time per element = Total Cycles / Number of Elements = 24 / 4 = 6 cycles

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

// Define the size of the arrays
#define N 200000

// Function to get the current time in seconds
double get_time() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec / 1000000.0;
}


int main() {
    // Using static to avoid stack overflow for large arrays
    static double x[N], y[N], y_unrolled[N];
    double a;

    // Initialize arrays with random numbers
    for (int i = 0; i < N; i++) {
        x[i] = (double)rand() / RAND_MAX;
        y[i] = (double)rand() / RAND_MAX;

        y_unrolled[i] = y[i];
    }
    a = (double)rand() / RAND_MAX;

    printf("Starting DAXPY benchmark with N = %d\n", N);

    double start_time = get_time();

    for (int i = 0; i < N; i++) { 
        y[i] = a * x[i] + y[i];   
    }

    double end_time = get_time();
    double standard_loop_time = end_time - start_time;
    printf("Standard loop execution time:   %f seconds\n", standard_loop_time);

    start_time = get_time();

    // Loop unrolled by a factor of 4 
    for (int i = 0; i < N; i += 4) {
        y_unrolled[i]   = a * x[i]   + y_unrolled[i];
        y_unrolled[i+1] = a * x[i+1] + y_unrolled[i+1];
        y_unrolled[i+2] = a * x[i+2] + y_unrolled[i+2];
        y_unrolled[i+3] = a * x[i+3] + y_unrolled[i+3];
    }

    end_time = get_time();
    double unrolled_loop_time = end_time - start_time;
    printf("Unrolled loop execution time:   %f seconds\n", unrolled_loop_time);

    printf("\nComparison:\n");
    printf("The unrolled loop was %.2f times faster.\n", standard_loop_time / unrolled_loop_time);

    return 0;
}

Starting DAXPY benchmark with N = 200000
Standard loop execution time:   0.000348 seconds
Unrolled loop execution time:   0.000257 seconds

Comparison:
The unrolled loop was 1.35 times faster.