Homework 4: Pipelining, I/O, the memory hierarchy, and
caches
CSE 410, Autumn 1999
Due in class, October 25th
Reading
H+P Chapter 7, sections 1, 2, 3, and 5.
To do on your own
Review for the midterm. A review guide will be available on Friday.
To be turned in
1. Pipelining. H+P 6.1, 6.4
2. At RightaWay Sandwich Shop, workers (also known as
"artists") make your sandwich in a pipeline with the following stages:
- Order Fetch. Worker 1 asks you what kind of sandwich you
would like and prepares the bread. (20 seconds)
- Meat. Worker 2 adds the meat to your sandwich. (15
seconds)
- Veggies. Worker 3 adds the veggies to your sandwich.
(15 seconds)
- Payment. Worker 4 wraps up your sandwich and takes your
money. (30 seconds)
a. What is the latency of sandwich preparation?
b. What speedup does RSS get by using 4 workers rather than 1?
c. What is the throughput of RSS when 4 workers are working? (Write
your answer in sandwiches per minute.)
d. If the lengths and operations of each stage are fixed, what can
RSS do to cut costs while maintaining throughput? Reducing the meat
per sandwich is not the answer I'm looking for. :-)
3. I/O. H+P 8.1, 8.3
4. Data locality. H+P 7.1, 7.2, 7.3
5. Direct mapped caches. H+P 7.7, 7.8
6. Associative caches. H+P 7.20, 7.21, 7.22, 7.24. In 7.24,
you do not need to show the number of bits needed to implement the
cache.