CS 351 Homework 5/6

Links: [Course Home] [Schedule] [Resources] [Study Guide] [Moodle]

Due Friday, December 8 at 5:00 PM. No late submissions accepted. Solutions will be posted to Moodle by Saturday at 2 PM. This assignment is worth 200 points.


Complete the following problems. In order to receive credit, you must show enough work to make it clear how you arrived at your answer. If applicable, you may write programs to solve these problems; in that case, include your source code and program output in your writeup.

You should submit your assignment as a single PDF via Moodle. It is OK to submit a PDF consisting of photos of handwritten pages, as long as your work is clearly legible and the lighting is reasonable. An app like Genius Scan can help with this. Corrupted or unreadable files will not receive any credit, and submissions in formats other than PDF may lose points.

You may work in groups of up to three students. Please refer to the course collaboration policy.

Submitting the assignment: Please have just one group member submit the assignment, and put all group members' names in the submitted document. Because Moodle has no idea who your group members are, the assignment will show up as missing/unsubmitted for the other group members until it's graded. This is annoying but harmless.

Problem 1: Average Memory Access Time (38 points)

Do Problem 5.10.1 through 5.10.4 in your textbook (pp. 501-502). Points breakdown:


Problem 2: Cache Tracing (72 points)

For each problem below, assume that memory addresses are 8 bits and that each byte of memory has its own address. The cache stores 16B of data.

For each cache design option below, trace through the following sequence of references. Show how each address is split up, and show the state of the cache after the access to address 13 and the final access to address 11. When you show the state of the cache, you should show all metadata for each block, and provide the addresses of the data stored in that block.

Sequence: Address 2, address 3, address 11, address 21, address 16, address 13, address 64, address 50, address 19, address 11, address 22, address 4, address 27, address 6, address 11

  1. Direct-mapped cache with 1B blocks
  2. 2-way set-associative cache with 1B blocks
  3. Direct-mapped cache with 4B blocks

Problem 3: Redundancy (30 points)

You have the following 4 bytes of data:

11010100, 10011100, 10001110, 10000000

  1. If you're enforcing even parity, what's the parity byte for this data?
  2. If the disk holding 11010100 fails, how does its value get reconstructed?
  3. If the disk containing 10011100 fails before we get around to reconstructing the first failed disk, what can we deduce about the two lost bits?

Problem 4: RAID (60 points)

You have four 2-TB disks of original data whose individual latency is 6 ms and transfer time is 20 ms for a 4 MB access. You're willing to buy however many additional disks you need for a particular RAID scheme.

Answer all questions for RAID 0, 1, and 5. Assume that the RAID stripe sizes are 128 KB where applicable.

  1. How many total disks do you need?
  2. How long would a 4 MB read take?
  3. How long would a 4 MB write take?
  4. If you lost one disk, how would you reconstruct its contents, and how long would that take?