Changelog:

  • 2 Nov 2023: correct URL to point to tool for this semester; adjust due date slightly later
  • 14 Nov 2023: more text re: how branch prediction works

1 Your Task

Fill in a pipeline diagram for a small function’s full execution.

Place you answer in the online tool https://kytos02.cs.virginia.edu/cs3130-fall2023/pld.php.

2 Guidelines

Consider the following code:

long count_odd(long *arr, long len) {
    long ans = 0;
    for(long i=0; i<len; i+=1)
        ans += arr[i]&1;
    return ans;
}

which has been compiled to (numbers inserted for ease of reference)

    count_odd:
0.      xorl    %eax, %eax
1.      testq   %rsi, %rsi
2.      jle .LBB0_2
    .LBB0_1:
3.      movq    (%rdi), %rcx
4.      andl    $1, %ecx
5.      addq    %rcx, %rax
6.      addq    $8, %rdi
7.      decq    %rsi
8.      jne .LBB0_1
    .LBB0_2:
9.      retq

Assume that this is run on a five-stage pipeline, where

You’re asked to expand this assuming

  1. you start with the first instruction after count_odd is called
  2. the first instruction of count_odd does not need to stall
  3. arr pointing to the array {1, 2}
  4. len stores the value 2
  5. the retq is the last instruction you need to handle