Total: 60 points (worth 30% of overall class grade)
For each question, if you know the value, write the value, for example “6”. Otherwise, describe the value, for example, “Content of Register 3”.
1. Assume you have a pipelined datapath as shown on Lecture 14 Slide 9 (reproduced in Supplementary Handout Slide 6).
Instructions and opcodes are from Lecture 10 Slide 8 (reproduced in Supplementary Handout Slide 4). Instruction format is from Lecture 10 Slide 7 (reproduced in Supplementary Handout Slide 2). Instruction decoder is from Lecture 10 Slide 10 (reproduced in Supplementary Handout Slide 5).
Copyright By PowCoder代写 加微信 powcoder
Ignore the Branch Control. Assume the following delay at each component:
• Register Propagation Delay: 1 ns
• Register Set-up time: 2 ns
• Instruction Memory Read: 6 ns
• Instruction Decoder: 3 ns
• Extend: 1 ns
• Zero Fill: 1 ns
• 8-to-1 or 4-to-1 MUX (in register file): 1 ns
• 2-to-1 MUX: 1 ns
• ALU: 5 ns
• Shifter: 4 ns
• Data Memory Read: 9 ns
• Data Memory Write: 5 ns
• 2-to-4 (or 3-to-8) Decoder: 1 ns
• AND Gate: 1 ns
(a) [2] What is the time required for the IF stage?
(b) [2] What is the time required for the DOF stage?
(c) [2] What is the time required for the EX stage?
(d) [2] What is the time required for the WB stage?
(e) [2] What is the minimum clock cycle time possible for this pipelined computer so that we can run all instructions without error?
2. Suppose we’re executing the following instructions:
In the DOF stage: ADD R1 R4 R2 (Address of this instruction is 00000101.) In the EX stage: AND R2 R1 R3 (Address of this instruction is 00000100.)
Suppose we’re using the Data Stall hardware on Lecture 15 Slide 16 (reproduced in Supplementary Handout Slide 6).
Use the RISC Instruction format from Lecture 15 Slide 4 (reproduced in Supplementary Handout Slide 3). .
(a) [2] What are the values of AA and BA in the DOF stage?
(b) [2] What are the values of HA and HB?
(c) [1] What is the input to the RW register in the EX/WB boundary? (d) [1] What is the input to the RW register in the DOF/EX boundary?
3. Single-cycle computer
We are using the instruction set (Supplementary Slide 4) and single-cycle circuit (Supplementary Slide 9) given in class. Instruction decoder and formats are all the same as in class and in Supplementary Handout. Suppose we add the following instruction to our instruction set.
Instruction Opcode Mnemonic Format Action
Multiply 1000000 MUL RD, RA, RB R[DR] ← R[SA] x R[SB]
Furthermore, assume that you have a new “Multiplication” component that accepts two inputs A and B, and outputs F, the product of A and B.
[6] How would you change the circuit to run this new instruction, as well as all existing instructions.
4. Pipeline parallelism
In a particular ISA, there are four stages in the pipeline: IR, DOF, EX and WB. Suppose that:
DIV operation takes 5 cycles in the EX stage
MUL operation takes 3 cycles in the EX stage, and
SUB operation takes 1 cycle in the EX stage.
All instructions take 1 cycle each in the IR, DOF and WB stages. There are three EX units.
[4] How many clock cycles does it take to complete the following sequence of instructions?
Make sure your scheduling handles any hazards. Assume that there is data forwarding hardware to forward the data from the EX stage to the DOF stage.
MUL R1 R3 R4 (This means R1 ← R3 x R4. In other words R1 is the destination register.) SUB R2 R1 R4
MUL R1 R5 R4
Suppose that we have a two-way set-associative cache with four-word lines. Suppose that this cache uses write back. Suppose the cache has the current state shown below:
1010…1111….0000…0000
1110…0111…1011…1000
1010…1100…1010…1100
1011…0000…0001…1011
0000…0001…1111…0000
1010…1111…1110…1100
0001…1100…1000…0101
1000…0101…1100…0001
0011…1111…0110…0101
0111…1011…1110…0000
0000…1111…1000…0101
1100…1000…0101…0111
1000…0101…1100…0000
1000…0001…0110…0001
1111…0000…0000…1111
1011…1110…0000…0001
Assume that the memory is byte-addressed, as usual. Only the most significant 4 bits of each word are shown. Assume the rest of the bits are 0. The left-most word of the line is assumed to be the most significant word (word with the largest address) of the line.
Assume write-back cache with write-allocate.
(a) Suppose that the CPU requests a memory WRITE to a word at address location 00110011000. Suppose that data the CPU wants to write is 1110… (once again, most significant 4 bits of the word.).
If the line is not in the cache, then assume that the line at the memory location is: 0000…1011…1100…1111 (most significant word is left-most, most significant 4 bits of each word shown.).
The cache uses a random cache replacement policy. The next random number to be generated is 0 (which would indicate that the left-hand-side set would be replaced if no empty cache positions can be found).
(i)[3] Draw the contents of the new cache. (You can cross out and write the new numbers in the diagram above. If no change, write “No change.”)
(ii)[3] Does anything get written to memory? If yes, say what is written into memory, and at what location.
(b) Suppose that after what happens in part (a), the CPU then requests a memory WRITE at address location 11010110100.
Suppose that data the CPU wants to write is 0000… (once again, most significant 4 bits of the word.). If the line is not in the cache, then assume that the line at the memory location is: 0100…1110…1101…1000 (most significant word is left-most, most significant 4 bits of each word shown.).
The cache uses a random cache replacement policy. The next random number to be generated is 0 (which would indicate that the left-hand-side set would be replaced if no empty cache positions can be found).
(i) [3] Draw the contents of the new cache. (You can cross out and write the new numbers in the diagram above. If no change, write “No change.”)
(ii)[3] Does anything get written to memory? If yes, say what is written into memory, and at what location.
(c) Suppose that after what happens in parts (a) and (b), the CPU then requests a memory READ of the word at address location 11011111100.
(i) [2] Is the data found in the cache? If yes, what is the data returned to the CPU.
If the word is not found in the cache, assume that the line at the memory location is: 0100…1110…1101…1000 (most significant word is left-most, most significant 4 bits of each word shown.).
The cache uses a random cache replacement policy. The next random number to be generated is 0 (which would indicate that the left-hand-side set would be replaced if no empty cache positions can be found).
(ii) [3] Draw the contents of the new cache. (You can cross out and write the new numbers in the diagram above. If no change, write “No change.”)
(iii)[3] Does anything get written to memory? If yes, say what is written into memory, and at what location.
(d) Suppose that after what happens in part (a), (b), and (c), the CPU then requests a memory WRITE at word at address location 11011110100.
Suppose that data the CPU wants to write is 0100… (once again, most significant 4 bits of the word.). (If the line is not in the cache, then assume that the line at the memory location is: 0101…1111…1000…1001 (most significant word is left-most, most significant 4 bits of each word shown.). )
The cache uses a random cache replacement policy. The next random number to be generated is 0 (which would indicate that the left-hand-side set would be replaced if no empty cache positions can be found).
(i) [3] Draw the contents of the new cache. (You can cross out and write the new numbers in the diagram above. If no change, write “No change.”)
(ii)[3] Does anything get written to memory? If yes, say what is written into memory, and at what location.
6. Virtual Memory
Suppose we have the following parameters:
Virtual address space: 32 bits Page size: 211 bytes each Main memory of size 216 bytes Page table size: 211 bytes each
Suppose that each page table entry is 4 bytes long. Suppose that each directory page entry is also 4 bytes long. Suppose that memory is byte-addressed, as usual.
(a) [1] How many entries can one page table contain?
(b) [1] How many entries does the directory page contain?
(c) [1] How many page tables are there?
(d) How much memory does the directory page consume?
Suppose that the virtual address accessed by the CPU is 00001111011001100001101101100000. (e) [1] What is the index used to find the page table number in the directory page?
(f) [1] Once the page table is located, what is the index used to find the physical page number in the page table?
(g) [1] Once the physical page is found, what is the index used to find the requested byte within the physical page?
(h) [1] How many bits long is a physical page number?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com