ELE00067M Digital Design Coursework Assessment 2021/22
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Department of Electronic Engineering
ELE00067M Digital Design Coursework Assessment 2021/22
ELE00067M Digital Design - Homework Set
Try to answer all questions. This is an INDIVIDUAL effort. Access any material you deem useful (lecture notes, books, internet). You are allowed to discuss general approaches (for example, using the lecture slides as support) but not specific solutions, as this would be considered collusion.
IMPORTANT: This assessment should be submitted as a single PDF file through the VLE. Answer each question on a separate page. Write your exam number on every page. Failure to do so might result in your homework not being marked.
Question 1 12 marks
The diagram below, taken from the slides of lecture 8, illustrates the algorithm that controls the operation of pagination. Draw a similar algorithm for paged segmentation, assuming the presence of separate translation lookaside buffers (TLBs) for pages and segments. [12 marks]
Hint 1: Paging and segmentation do not work sequentially, but are nested.
Hint 2: Only pages are retrieved from HD – segments are only data structures.
Hint 3: Always keep in mind the ultimate objective: to retrieve the physical address ofthe data!
Question 2 12 marks
Consider a processor with a 16KB cache organized in blocks of 64 32-bit words (256 bytes). Assume that addresses are coded in 32 bits and that there are 4GB ofRAM without virtual memory (i.e., the 32 bit addresses in a program code directly the physical address in main memory, without any Memory Management Unit). All memories are byte-addressable. A complete block is retrieved from memory on a cache miss.
A program reads three one-dimensional arrays A, B, and C of256 words each, one word at a time (that is, it reads in sequence A[0], B[0], C[0], A[1], B[1], C[1], A[2] … C[254], A[255], B[255], C[255]). Array A is stored in consecutive memory locations starting at hexadecimal address A1A10600, array B is stored in consecutive memory locations starting at hexadecimal address A1A20600, and array C is stored in consecutive memory locations starting at hexadecimal address BCADA600.
For a direct-mapped cache, compute:
- The number of bits required for the tag and for the index [1 mark].
- The number of cache hits and misses as the program completely reads the three arrays [2 marks].
For a fully-associative cache, assuming a least-recently-used replacement policy, compute:
- The number of bits required for the tag (or address) [1 mark].
- The number of cache hits and misses as the program completely reads the three arrays [2 marks].
For a set-associative cache with 2 blocks per set, assuming a not-last-used replacement policy, compute:
- The number of bits required for the tag and for the index [1 mark].
- The number of cache hits and misses as the program completely reads the three arrays [2 marks].
For a set-associative cache with 8 blocks per set, assuming a least-recently-used replacement policy, compute:
- The number of bits required for the tag and for the index [1 mark].
- The number of cache hits and misses as the program completely reads the three arrays [2 marks].
For all answers, show all the steps of the calculation and explain in a few words how you reached the results.
Question 3 26 marks
Consider the following piece of code, which implements a multiplication algorithm:
Identify all the data (RAW only) and control hazards in this code for the 5-stage pipeline ofArchitecture D (see lecture 7), described in the lectures and copied below for reference [4 marks].
To begin with, ignore the presence of any forwarding path (i.e., assume that there are no such paths) and assume that control hazards will be handled by the processor using pipeline stalls (i.e. no need to explicitly insert NOP instructions). Re-order the instructions to eliminate as many of the data hazards you have identified (without changing the function realized by the code, of course!). Then, insert the minimal number ofNOP (no operation) instructions necessary to eliminate all remaining data dependencies. For your answer, rewrite the entire instructions and not just the line numbers. [7 marks].
Go back to the original code (without reordering and NOPs). Let F1 be the forwarding path from the Memory Access stage to the Execute stage, F2 the path from the Register Write stage to the Execute stage, and F3 the path between the Register Write stage and the Register Read stage (see figure below as a reminder). Identify which (if any) of the bypass paths can be used to eliminate each data hazard you have identified [3 marks].
The code above has two conditional branch instructions: B1 at position 09 and B2 at position 14. For a multiplication of 16 bit data, each ofthose branches is evaluated 16 times. B1 is taken or not depending on the value ofthe single bits ofthe multiplier, and hence it can be assumed that it will be taken, on average, 50% of the time. B2 is used to select which bit ofthe multiplier is evaluated, and hence will be always taken the first 15 times, not taken the last (16th) time.
For Architecture D and ignoring data hazards (i.e., assuming that forwarding will solve any issues related to data hazards), compute how many clock cycles would be necessary to execute the above piece of code:
Without any form of speculative execution [3 marks];
With speculative execution using static prediction – predict not taken [3 marks];
With speculative execution using static prediction – predict taken [3 marks];
With speculative execution using static prediction – direction-based prediction [3 marks].
For all cases, show all the steps of the calculation and explain in a few words how you reached the results.
2022-01-12