ASSIGNEMNT 4
University of New Brunswick Computer Science
Computer Architecture and Organization
Scott R. Young, scott.young@unb.ca
Due Date: August 3, 2020 – 10:00 am
Problem 1. Using the following psudo-code and a assuming a 4 stage pipeline (Instruction fetch, instruction decode, execute, write back) show how instruction reordering, loop unrolling and branch delay slots could be used to fix data and control hazards. The ; character denote the start of a comment.
; increment all the values in an array by 1.
0x00000100: mov r1, 0xffffffff ; load -1 into r1.
0x00000104: mov r2, 0x0000fff8 ; load start of array.
0x00000108: mov r3, 0x00000200 ; load size of array, 1024 items.
0x0000010c: mov r4, 0x00000001 ; load constant to increment values by.
0x00000110: add r5, r2, r3
0x00000114: mov r6, [r2]
0x00000118: add r6, r6, r4
0x0000011c: add r2, r2, r4
0x00000120: cmp r7, r5, r2
0x00000124: jp [0x00000114], r7 ; if we have more to do, jump to start of loop.
0x00000128: hlt ; we have finished updating the array.
; save the max index.
; start of loop. load array value to be worked on.
; perform the increment.
; update the array pointer.
; have we hit the max index? 1 means no.
Intructions are:
• mov DST, SRC: Moves the value held in the SRC register to the DST register.
• mov DST, 0xImm: Stores the value of Imm in the DST register. Imm is a 4 byte value.
• mov DST, [SRC]: Moves the value held in memory at the location pointed to by the SRC register to the DST register.
• mov DST, [0xImm]: Moves the value held in memory at the location pointed to by the value Imm in the DST register. Imm is a 4 byte value.
• mov [0xImm], SRC: Moves the value held in the SRC register to the memory location pointed to by the value Imm.
• mov [DST], SRC: Moves the value held in the SRC register to the memory location pointed to by the DST register.
• add DST, SRC, TRG: Stores the result of SRC + TRG in DST.
• neg DST: Negates the result of DST and stores it in DST.
• cmp DST, SRC, TRG: Stores a 1 in DST if, and only if, SRC – TRG is a positive number, greater than 0.
• jp [Addr], SRC: If the register SRC contains a positive number, load the instruction pointer to by Addr instruction buffer and update the instruction pointer to Addr + 1.
Assignemnt 4 1 Summer 2020
• hlt: Stops the processor.
Assume that the jump instruction modifies the instruction pointer in the execute
stage.
Assignemnt 4 2 Summer 2020
Problem 2. Consider the following psudo-code:
max = v[0];
for(i = 1; i < 10000; i++) {
if ( v[i] > max )
max = v[i];
}
Assuming the following are true about the cache:
• It is empty before executing the first line of code.
• max is an integer and v is an array of integers.
• 128 byte cache line size.
• An 8K cache.
• 4 byte intructions.
• 4 byte integers.
• A split L1 cache.
• i and max are stored in a registers (no memory access)
• no pre-fetching (only 1 cache line swapped per miss).
(a) Estimate the cache hit ratio for the L1D cache with direct mapping. Show your work.
(b) Estimate the cache hit ratio for the L1D cache with full associativity. Show your work.
(c) Estimate the cache hit ratio for the L1D cache with 4-way set associativity. Show your work.
Assignemnt 4 3 Summer 2020