Caches and Digital Logic CSCI-UA.0201 Spring 2022
Logisim代写 | C代写 | Digital Logic代写 – 该题目是值得借鉴的Logisim代写的题目
homework 2
Caches and Digital Logic
CSCI-UA.0201 Spring 202 2
The questions below involve writing answers (using Word or whatever) in an answer file as well as generating circuit files using Logisim Evolution (below). When you are finished, upload the answer file (in PDF form) as well as the Logisim circuit files that youve created. It will take a while to build the circuits, so get started on these as soon as possible (once theyve been covered in lectures).
Caches
- Define the terms compulsory miss, capacity miss, and conflict miss.
- Which of the above types of cache misses are reduced by having a set-associative cache instead of a direct-mapped cache?
- Consider the following statement: For n-way set-associative caches, as n gets larger (assuming the total number of data bytes stored in the cache remains constant), the number of capacity misses will increase because there are fewer sets in the cache.
a. Is the statement true or false?
b. Explain your answer.
c. If your answer was true, why dont CPU manufacturers just use n=1? If your
answer was false, why dont CPU manufacturers set n to the largest possible
value (i.e. set n to the number of cache lines that can be stored in the cache).
- In your own words, describe what temporal locality means and give an example in a tiny C program.
- Describe what aspect of a cache exploits temporal locality.
- In your own words, describe what spatial locality means and give an example in a tiny C program.
- Describe what aspect of a cache exploits spatial locality.
- Suppose a machine has two caches, an L1 cache and an L2 cache. Assume the following characteristics of cache performance:
- The processor is able to execute an instruction every cycle, assuming there is no delay fetching the instruction or fetching the data used by the instruction.
- An L1 cache hit provides the requested instruction or data immediately to the processor (i.e. there is no delay).
- An L2 cache hit incurs a penalty (delay) of 10 cycles.
- Fetching the requested instruction or data from memory which happens when there is an L2 miss incurs a penalty of 100 cycles. That is, the total delay is 100 cycles on an L2 miss, dont add the 10-cycle delay above.
- The L1 miss rate for both instructions and data is 3%. That is, 97% of instruction and data fetches result in an L1 cache it.
- The L2 miss rate for instructions is 1% and for data is 2%. That is, of those instruction fetches that result in an L1 cache miss, 99% of them will result in an L cache hit. Similarly, of those data fetches that result in an L1 cache miss, 98% of them will result in an L2 cache hit.
- 30% of instructions require data to be fetched (the other 70% dont). a. Given a program that executes I instructions, how many cycles would the program take to execute, under the above assumptions? Be sure to show your work. b. Suppose you are manufacturer of the above machine and, in the next release, you have the option of increasing the size of the L1 cache so that the L1 miss rate is reduced by 50% for both data and instructions or increasing the size of the L cache so that the L2 miss rate is reduced by 50% for both data and instructions. If your only goal was to make the above program faster, which option would you choose? Show your work.
- Assuming a word size of 32 bits, so that both addresses and integers are represented as 32 bits, how would the bits of an address be used to support caching on a machine with a 16 MB 8 – way set-associative cache and a 16 – word cache line? That is, specify which bits of the address would be used for the byte offset, the word offset, etc. The 16MB refers to the total amount of data that can be stored in the cache, and does not include the storage required for the tags, valid bit, etc.
Digital Logic (using Logisim Evolution)
To do this homework, you will need to install Logisim Evolution, the digital logic simulator that I used in class. It should only take you a couple of minutes to install, its easy to use, and frankly, its fun.
Instructions for installing and running Logisim Evolution are found under the Resources tab on Brightspace.
Once youve started Logisim, its very easy to create a circuit. To learn how, just click on Help and then Tutorial to run the tutorial. It takes only a few minutes to get through the tutorial. As practice, be sure to build the XOR device described in the tutorial.
- Build a 4-bit adder from AND, OR, and NOT gates as follows.
a. Write out the truth table for a 1-bit adder, which has three 1-bit inputs: a, b, and
carry_in, and two 1-bit outputs: result and carry_out.
b. Implement, in Logisim, the circuit for the 1-bit adder corresponding to the above
truth table.
c. In Logisim, create the four-bit adder by making three more copies of the above 1-
bit adder, and then connecting them together. The resulting four-bit adder should
have the following inputs: a0, a1, a2, a3, b0, b1, b2, b3 and carry_in. It should
have the following outputs: result0, result1, result2, result3, and carry_out. (Note:
To copy and paste the 1-bit adder, select the entire 1-bit adder by dragging the
mouse over the adder, copy by typing either control-C or command-C, and then
paste by typing control-V or command-V. Youll need to drag each new copy
into the right position).
d. Be sure to test the adder to make sure it is getting the right outputs. Once you
have it working, you should:
i. Give the circuit a name by clicking on main under the untitled folder
in the upper left-hand window and then, in the bottom left where it says
main next to circuit name, typing in the name you want to give the
circuit. In this case one_bit_adder is a good name, but its up to you.
ii. Save the circuit (by clicking File and Save) to a file named
adder.circ.
- In Logisim, create a 2-input, 1-select line multiplexor (mux) from AND, OR, and NOT gates. Give the circuit a name and save the file as 2_input_mux.circ. (Note: To create a new circuit, click File and New).
- In Logisim, create a 4-input, 2-select line (mux) from AND, OR, and NOT gates. Give the circuit a name and save the file as 4_input_mux.circ.
- In Logisim, using your adder, the muxs you built (as many copies of these as you need), and AND, OR, and NOT gates, create a 4-bit ALU that performs AND, OR, + and -. It should have the following inputs: a0, a1, a2, a3, b0, b1, b2, b3, control0, and control1. It should have following outputs: res0, res1, res2, res3, and carry_out. The two control lines should determine the operation to be performed as follows:
control1 control
0 0 AND
0 1 OR
1 0 +
1 1 -
Note that this ALU will be slightly different from the ALU in the class notes, since there
is no separate Binvert line. Note: To incorporate previously-built circuits in a circuit, click
project > Load Library > Logisim-evolution Library... and then choose the file you
had saved. On the left hand side, a new folder will appear with the name of the file.
Double-click on the folder and you should see a circuit with the name you gave it. It will
be represented as a rectangle with inputs (small dots) on the left and outputs (also small
dots) on the right. Select and use the circuit just as you would any other device (e.g. AND
gate). Be sure to add text to label the devices.
- In Logisim, build a falling-edge triggered D flip-flop out of AND, OR, and NOT gates. To do this, build a simple unclocked-latch, then use the unclocked latch to build a clocked D latch, then use the D latch to build flip-flop. Dont use any of the devices that Logisim may provide other than AND, OR, and NOT gates (that is, it provides you with a whole bunch of different devices, including flip-flops, but dont use them).
- In Logisim, build a 4-bit register from your flip-flops of the previous step. The inputs to your register should be: data0, data1, data2, data3, clock, and write_enable. The values on data0 through data3 should be stored in the register (upon the falling edge of the clock, of course), but only if write_enable is asserted. The outputs should be output0, ouput1, output2, and output3.
- Finally, in Logisim, build a circuit containing:
- Three of your 4-bit registers.
- Your ALU. The outputs of two of the above registers should be wired to the inputs to the ALU and the outputs of the ALU should be wired to the inputs of the third register.
- A clock. If you look in the Wiring folder in the left hand side of the Logisim screen, youll see a clock device to click on. Your circuit should have a single clock input that is wired to all three registers. You can change the value of the clock (from 0 to 1 and 1 to 0) by using the poke tool ( ) and clicking on the clock. You can also make the clock cycle in a regular pattern by clicking on the Simulate menu, choosing a Auto-Tick Frequency, and clicking Auto-Tick Enabled.
- The inputs to the first two registers should be from pins, using the usual input tool ( ). The control inputs to the CPU should also be from pins.
This way, you are able to write specific 4-bit values to the first two registers and compute
the value of the third register by choosing an operation (AND, OR, +, -) on the ALU.
Digital Logic (not using Logisim – write the answers in your answer file)
- Consider the drawing of the register file in my lecture notes.
a. Describe precisely what the function of the decoder is in the operation of the
register file.
b. What is the function of the two multiplexers?
- Consider the drawing of the DRAM cell in my lecture notes.
a. Why is this memory called Dynamic RAM?
b. When does a DRAM cell have to be refreshed and why? How is a DRAM cell
refreshed?
c. If the word line is de-asserted, can the DRAM cell be read or written? Explain.
- Consider the drawing of the portion of the datapath that fetches instructions in the simple processor in my lecture notes.
a. Why is 8 being added to the program counter register (e.g. %rip)?
b. Why dont we have to worry about 8 being added to the program counter register
while the instruction address is still being sent to the instruction memory?
- Consider the drawing of the portion of the datapath that performs simple operations on registers (only) in the lecture notes.
a. Why is the second operand sent to both the second read-select line and the write-
select line?
b. Since the register indicated by the second read-select line and the register
indicated by the write-select line are the same, why doesnt the writing of data to
that register interfere with the reading of that register while the operation is being
performed? Explain.
- Consider the drawing of the portion of the datapath that implements move operations involving memory.
a. Could this datapath be used to move data from one location in memory to another
location in memory in a single cycle? Explain your answer.
b. What would be different, in terms of the values carried by the various lines
(wires) shown in the diagram, between movq %rax,8(%rcx) and
movq 8(%rcx),%rax.
- Consider the drawing of the portion of the datapath that implements conditional branch instructions.
a. What is the role of the multiplexer in the top right portion of the drawing?
b. Under what circumstances would that multiplexer send its first input to its output
and under what circumstances would it send its second input to its output?
c. Why does the output of the multiplexer get sent to the program counter register
rather than to the register file shown in the drawing?