[2021] COMP1411 Introduction to Computer Systems - Q6 Program Execution Procedure
Question 6. [25 marks]
Given the program written in the Y86-64 assembly language.
irmovq $1, %rsi
irmovq $4, %rdi
irmovq $0, %rax
addq %rsi, %rax
L0:
rrmovq %rax, %rbp
andq %rsi, %rbp
nop
nop
nop
je .L1
addq %rbx, %rcx
addq %rsi, %rcx
addq %rdi, %rcx
nop jmp .L2
L1:
irmovq $5, %rcx
andq %rdi, %rcx
addq %rsi, %rbx
subq %rbx, %rcx
L2:
addq %rsi, %rax
rrmovq %rax, %rbp
subq %rdi, %rbp
jle .L0
ret
Assume that all the instructions are stored in continuous addresses of the main memory, and the main memory is partitioned into blocks with each block has size of 16 bytes. Assume that the first instruction is exactly at the beginning of block 1 (blocks are numbered 1, 2, 3, 4, …, according to increasing addresses).
The system has a cache that can hold 3 blocks. When the CPU loads an instruction from the main memory, it first checks if the block containing the required instruction is in the cache or not. If the block is in the cache, we say there is a cache hit; if otherwise the block is not in the cache, we say there is a cache miss, and the CPU will fetch the block(s) containing the required instruction from the main memory and put the block in the cache. At the beginning of the program execution, the cache is empty.
If the cache is full, i.e, the cache is holding 3 blocks and a new block will be loaded into the cache, one of the 3 existing blocks will be replaced out of the cache. Assume that Least Recently Used (LRU) is applied when replacing blocks. By LRU, the block with the oldest access time (among the 3 blocks) will be evicted out of the cache.
6(a) Show the partition of blocks, and list the sequence of block numbers that are accessed during the execution of the program.
Main behavior of the program should be provided to support your given block access sequence.
Note that if multiple instructions belonging to the same block are consecutively executed, we treat the execution of these instructions as a single access to the corresponding block.
[14 marks]
6(b) Draw the history of cache states during the program execution. [11 marks]
An example with 2 block accesses is given below: the vertical boxes represents a cache state with some blocks in the cache; an arrow represents the behavior of accessing a block, changing the cache state from the left one to the right one.
Write the accessed block number above the arrow, and write out whether the access to the block is a cache hit (H) or miss (M) below the arrow.
1
1
2
1
→
→
2
(M)
(M)
Question 6. [25 marks]
Given the program written in the Y86-64 assembly language.
irmovq $1, %rsi
irmovq $4, %rdi
irmovq $0, %rax
addq %rsi, %rax
L0:
rrmovq %rax, %rbp
andq %rsi, %rbp
nop
nop
nop
je .L1
addq %rbx, %rcx
addq %rsi, %rcx
addq %rdi, %rcx
nop jmp .L2
L1:
irmovq $5, %rcx
andq %rdi, %rcx
addq %rsi, %rbx
subq %rbx, %rcx
L2:
addq %rsi, %rax
rrmovq %rax, %rbp
subq %rdi, %rbp
jle .L0
ret
Assume that all the instructions are stored in continuous addresses of the main memory, and the main memory is partitioned into blocks with each block has size of 16 bytes. Assume that the first instruction is exactly at the beginning of block 1 (blocks are numbered 1, 2, 3, 4, …, according to increasing addresses).
The system has a cache that can hold 3 blocks. When the CPU loads an instruction from the main memory, it first checks if the block containing the required instruction is in the cache or not. If the block is in the cache, we say there is a cache hit; if otherwise the block is not in the cache, we say there is a cache miss, and the CPU will fetch the block(s) containing the required instruction from the main memory and put the block in the cache. At the beginning of the program execution, the cache is empty.
If the cache is full, i.e, the cache is holding 3 blocks and a new block will be loaded into the cache, one of the 3 existing blocks will be replaced out of the cache. Assume that Least Recently Used (LRU) is applied when replacing blocks. By LRU, the block with the oldest access time (among the 3 blocks) will be evicted out of the cache.
6(a) Show the partition of blocks, and list the sequence of block numbers that are accessed during the execution of the program.
Main behavior of the program should be provided to support your given block access sequence.
Note that if multiple instructions belonging to the same block are consecutively executed, we treat the execution of these instructions as a single access to the corresponding block.
[14 marks]
6(b) Draw the history of cache states during the program execution. [11 marks]
An example with 2 block accesses is given below: the vertical boxes represents a cache state with some blocks in the cache; an arrow represents the behavior of accessing a block, changing the cache state from the left one to the right one.
Write the accessed block number above the arrow, and write out whether the access to the block is a cache hit (H) or miss (M) below the arrow.
1 | 1 | 2 | 1 | |
→ | → | 2 | ||
(M) | (M) |
Get the Solution to This Question
WeChat (微信)
WhatsApp
