COMP 2421 Computer Organization Homework 2
Deadline: 11:59 pm, Apr. 18 (Monday), 2022.
PROBLEM 1 [15 PTS]
Suppose in a computer storage system, the basic addressable unit is one Byte (i.e., 1 word = 1 Byte). The size of themainmemoryis1MB(1MB=210 KB;1KB=210 Bytes)andeachblockinmainmemoryhasasizeof16 Bytes. The size of the Cache is 64 KB.
Copyright By PowCoder代写 加微信 powcoder
Answer the following questions:
(1) <3 pts> Assume direct mapping. Given a memory address A004B in hexadecimal format, write the values of its tag, line, word fields in binary format, respectively. Explain your answer.
(2) <2 pts> Assume direct mapping. Give any two memory addresses with different tag values that would be mapped to the same Cache line. Note, write the addresses in hexadecimal format.
(3) <3 pts> Assume direct mapping. Suppose for a specific line in the cache, we found that this line current stores a byte with address 0100 0001 0011 1110 0000. What are the addresses of the other bytes that are currently stored in this line along with that byte?
(4) <2 pts> Assume associative mapping. Given a memory address A004B in hexadecimal format, write the values of its tag and word fields in binary format, respectively.
(5) <5 pts>Suppose that the processor needs to access a byte with address F001A and assume that this byte is currently stored in the Cache. Explain the processes of locating this byte in Cache using direct mapping and associative mapping, respectively. What’s the major difference?
(1) The length of the address is 20 bits.
Since the size of a block is 16 = 24 Bytes, the word field contains 4 bits.
Since the size of Cache is 64 KB = 216 B and each line has 24 B, there are 212 lines in the Cache. So, the line field contains 12 bits.
Then, the tag field contains 20 − 4 − 12 = 4 bits.
In summary, the address is divided into: tag (4 bits), line (12 bits), and word (4 bits).
For this question, the values of the tag, line and word fields in binary format are: 1010, 0000 0000 0100,
1011, respectively.
(2) For any two given addresses, the line field should be the same, the tag field should be different, and there’s
no requirement for the word field.
Example: A004B, B004B.
(3) This line should store the bytes within the same block. Thus, only the last 4 bits (word field) will be different.
Thus, this line will store 16 bytes, with addresses 0100 0001 0011 1110 0000 to 0100 0001 0011 1110 1111.
(4) For associative mapping, the tag field contains the first 16 bits, and the word filed contains the last 4 bits.
Given address A004B, the values of tag and word fields are 1010 0000 0000 0100, 1011, respectively.
(5) For directly mapping, the processor knows the line field 001 (in hexadecimal), with which it can locate the
line in Cache that is currently storing this block. It can then use the word field A to locate the byte.
For associative mapping, the processor knows the tag field F001, and it will compare this F001 with the tag of each line in Cache to find the line that is currently storing the block. Then it will use word field A
to locate the byte.
The main difference is that, in direct mapping, the processor can directly use the line field in the address to locate the line in Cache; while in associative mapping, the processor needs to compare the tag field in the address with the tag of each line in Cache to locate the line.
PROBLEM 2 [10 PTS]
(1) Consider a general error correction code which can correct 1 error (we assume that at most one error could occur). This error correction code contains M data bits and K parity bits. The redundancy of this code is calculated as MK . Recall the relation between M and K and find the minimum value of K for these three cases:(1)M =4;(2)M =20;(3)M =32.<3pts>
Consider the above three cases, what’s the trend of redundancy as we increase M? What’s the risk of
increasing M? <2 pts>
(2) Consider an error correction code with M = 2 and K = 3. The encoding scheme is as follows:
Data bits (M = 2 bits) 00
Codeword (M + K = 5 bits) 00000
What’s the minimum hamming distance dmin between every two codewords?<1 pts>
Can this code correct one error? Explain your answer (if not, give a counter example). <4 pts>
(1) Therelationis2K ≥M+K+1. When M = 4, we have K ≥ 3. When M = 20, we have K ≥ 5. When M = 32, we have K ≥ 6.
The redundancy will decrease as we increase M. But we cannot keep increasing M. Because an assumption is that at most one error could occur. Increasing M will increase the possibility of errors, thus violating this assumption.
(2) The minimum hamming distance is dmin = 1.
No. Suppose a codeword 00001 is received. There are two possible cases: (1) it is a codeword with no error, then the data bits are 01. (2) the original codeword is 00000 and one error occurred, resulting in this codeword 00001. Then the data bits are 00.
Since we can not differentiate these two cases, this code cannot correct 1 error.
(Other correct explanations are also acceptable.)
PROBLEM 3 [5 PTS]
Consider a processor with two configurations of cache. In the first configuration, the processor uses a cache of 32KB, obtaining a 95% hit rate, 2 ns hit time and an 18 ns miss penalty. In the second configuration, the cache has a size of 64KB, resulting in a hit rate of 97%, a hit time of 3 ns and the same miss penalty as in the previous case. Explain why a larger cache can increase the hit rate? <1 pts>
Compute the average access time for both configurations. <4 pts>
(1) For a larger cache, more data from memory can be copied into cache, resulting in a higher hit rate.
(2) First: average access time = 2 ns + (1 – 0.95)* 18 ns = 2.9 ns. Second: average access time = 3 ns + (1 – 0.97)* 18 ns = 3.54 ns.
PROBLEM 4 [20 PTS]
Answer the following short questions:
(1) <2 pts> Why is main memory not suitable for permanent program storage or backup purposes?
(2) <3 pts> What are three basic components in a computer system taught in this course?
(3) <2 pts> Why are I/O modules are needed in a computer system? Given two reasons.
(4) <3 pts> What’s the main difference between programmed I/O and interrupt-driven I/O?
(5) <3 pts> What’s the main difference between Memory-mapped I/O and Isolated I/O?
(6) <3 pts> In Constant Angular Velocity magnetic disk, what is done to ensure constant data rate for writ-
ing/reading?
(7) <2 pts> Explain the seek time and rotational delay for magnetic disk.
(8) <2 pts> Why can RAID increase the reliability of storage?
(1) Main memory is volatile. The data stored will be lost if no power is provided.
(2) CPU (processor), Memory, I/O
(3) There are many reasons. For example: cope with the different data transfer rate between CPU and external
devices; serve as data buffers; control the communication, etc.
(4) In programmed I/O, CPU will check the status of I/O periodically. In interrupt-driven I/O, the I/O will cause
an interrupt to CPU when it’s ready.
(5) In Memory-mapped I/O, I/O (more specifically, external devices) and memory will share the same address
space; Isolated I/O will not.
(6) In constant angular velocity, the outer tracks have relatively higher rotational speed, so the density of the
spots (bits) is relatively lower. As a result, the data rate will remain the same for outer and inner tracks.
(7) Seek time: the Head moves to the right track.
Rotational delay: the desired sector rotates to the Head.
(8) Redundant data (for example, using error correction code) are stored such that data can be recovered if
failure happens.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com