1University of California, Berkeley College of Engineering Computer Science Division EECS Fall 2000 John KubiatowiczMidterm II December 8, 2000 CS252 Graduate Computer Architecture Your Name: SID Number: Problem Possible Score 1 25 2 30 3 25 4 20 Total 1002 [ This page left for π ] 3.1415926535897932384626433832795028841971693993751058209749443Question #1: Grab Bag 1a) What are the 3 C’s of cache-miss classification? What is the 4th C of multiprocessing? 1b) Name and define two types of locality that caches exploit: 1c) What is a victim cache, what does it help, and why is it a better engineering alternative than other options? 1d) What is the difference between access time and cycle time in DRAM? Why should there be two such numbers?41e) Why is it advantageous to have a prime number of DRAM banks for a vector processor? Assuming that your prime number is of the form (2n-1), what hardware lets you easily map from processor address to a combination of bank number and bank offset while retaining the above advantage? 1f) How can parallelism (such as in a vector processor) be used to reduce to total energy consumed by a computation? Why doesn’t a superscalar processor get this advantage? 1g) What is the cache-coherence problem in a multiprocessor? 1h) What does it mean for a multiprocessor to be sequentially consistent? Why is this a desirable requirement for a multiprocessor?51i) Name the three conditions sufficient for sequential consistency that were presented in class and draw a diagram illustrating these conditions: 1j) How might you use speculation (including the reorder buffer) to implement sequential consistency with almost the same performance as the solutions in (k)?6[This page intentionally left blank]7Problem #2: Checking the bits The error correction coding process can be viewed as a transformation from one space of bits (the unencoded data) to another (the coded data). 2a) For linear block codes, there are two matrices, the Generator (G) and Parity Check (H). What are they, how big are they (in terms parameters n and k), and how are they used? 2b) Define the minimum Hamming distance, dmin, of an error correction code (make sure that this definition makes sense for codes like Reed-Solomon of RAID-5 that have more than one bit per symbol): 2c) Name a constraint on the columns of the parity check matrix (H) which would indicate that a code had minimum distance dmin. 2d) For a code with dmin minimum distance, what is the formula for the maximum number of errors, Edetect, that can be reliably detected? Why might you be able to detect more than the Edetect errors?82e) For a code with dmin minimum distance, what is the formula for the maximum number of random errors, Ecorrect, that can be corrected reliably? Can you prove this? 2f) How does your answer to (2f) change if you have knowledge of which symbols are bad (i.e. which symbols have been erased). How might erased symbols be detected? 2g) Design a distance-4 error correction code to protect 8 bits. How many parity bits are needed? What are the matrices G and H? Prove that your code has distance 4 and list all 8 code words in this error correcting code.9Supposed we arrange our data into a matrix as shown below, within the heavy lines. Assume that we have two block codes, an “inner” code with parameters (N1,K1) and an “outer” code with parameters (N2,K2). We nest them as follows: First, we compute the inner parity bits on all of the rows (placing the parity bits to the right), then compute the “outer” code on the columns (placing the bits on the bottom); we compute an outer code on the parity bits from the “inner” code as well. Finally, assume that we transmit this code row by row after we have encoded it. 2h) If the two codes are both distance-2 parity codes (i.e. the parity is a single bit that is an XOR over all of the data bits), explain how we can (1) we can discover and correct a single bit error and (2) can detect two errors. Can it correct 2 errors? Can it correct 3 errors? 2i) If the inner code is changed to a distance-4 code (like in 2h), what is the maximum “burst error” (number of corrupted bits next to each other in a row) that this code could correct? Ignore bursts that cross rows. A Recursive Error correction code (or matrix code) K2 K1 N1- K1 N2- K2102j) (Extra credit: 5 points): Suppose that a random set of bits gets corrupted in a row. Let rows contain 128 data bits + parity, inner code has distance-4, outer distance-2. What is the probability that we could detect this problem and completely correct it? How many parity bits would you need for the inner code to guarantee that you could correct a complete row failure?11Problem #3: Queuing the network Measurements of a network gateway show that packets arrive at 450 packets per second and that the gateway forwards them in about 2 ms on average. 3a) Why is it reasonable to treat the arrival of packets as a memory-less (exponential) process? 3b) What is the utilization (ξ) of the gateway? 3c) Assuming that the serice time of the gateway is exponentially distributed (M/M/1) queue, what is the mean time that a packet spends inside the gateway? How would this change if the gateway always took exactly 2ms to forward packets (M/D/1 queue)? 3d) Assuming that the service time of the gateway is exponentially distributed (M/M/1 queue), what is the average number of packets in the gateway? What about for the deterministic case (M/D/1 queue)? Hint: Little’s law might be helpful here: L = OT, i.e the number of elements in any system is equal to the arrival rate times the waiting time.123e) As we derived in class, an M/M/1 queue has a probability of ξn of having n or more tasks in the system. What is the chance of an overflow at our gateway if the input queue can hold 10 messages or less? 3f) Suppose that we drop network packets if they arrive and a queue is full. How large do we need to make our M/M/1 queue to ensure that we drop fewer than one packet per million? 3g) Suppose that among other things, a workstation under control of a hacker is feeding “ping” packets into this gateway along a dedicated communication path which takes 200ms from
View Full Document
Unlocking...