Computer Architecture and Organization.

This question has two part. Please answer them both.

A typical code sequence in many applications includes a loop, but the loop body executes different instructions for different iterations. The following C code shows an example:

Here is the Assembly version of the same example as on the previous slide for N=5:

Part 1. Find all data dependencies, output dependencies, anti-dependencies in the code segment. Note: please execute the loop only once (i.e. you do not have to track loop dependencies across the different iterations).

Part 2. Use a 1-bit predictor to predict the outcome of the Branch b1. Complete the following table. Assume that the initial state of the branch predictor is 0.

Part 3. Use a 2-bit predictor to predict the outcome of the Branch b1. Complete the following table. Assume that the initial state of the branch predictor is 01.

if ( i== 2) { a[i] all a[1-1]; = else t all ali The following Register assignments are being used: x10 is used to store N , is initialized to 5 x1 is used to store i ( the loop variable), is initialized to 1 X2 is used to store the value 2 (used in the if statement). .x6 contains the starting address of the array a [ .X8 is used to store a [i] x4 is used to store a [i-1] Each element of a[ takes 8 bytes. 1 2 3. LOOP: LDURXA, [x6, #0] ADDI x6, x6, #8 MOV X8, X4 BEQ X1, X2, JMARK ; load a[0] ;increment memory address ; Branch bl ; if X1X2 goto JMARK X8, X8, (X6, #1 ADD! STUR X8, ADDI X1, X1, #1 ADDI x6, x6, #8 MOV X4, X8 BNEQ Xl, X10, Loop 6.1 JMARK : #0] ; store a[i] ;increment loop counter ;increment memory address 10 ; Branch b2 ; if x1 != x10 goto Loop Value of i or X1 Branch predictor for (Taken/Not outcome of (Yes/No) Branch b1 taken) Prediction Actual Misprediction? branch b1 0) 4 Value of i or X1 Branch predictor for (Taken/Not outcome of (Yes/No) Prediction Actual Misprediction? ranch b1 taken) branch b1 01 2. 4