Software Systems
Spring 2005

For today, you should have:

1) finished Homework 1

2) prepared for a quiz

2) looked at the Disk Drive Handouts


Outline:

1) quiz

2) finish the reading exercise from last time

3) the holy grail of system design

4) caches!


For next time:

1) read the Magnetic Disk handout from Hennessey and Patterson

2) read 'The Memory Hierarchy' from Stallings

3) start Homework 2


Software System Design
----------------------

1) what is the software interface?

   We got this from the SCSI manual.

2) what are the relevant performance characteristics?

   We can get this from the manufacturer, although we might
   want to run some of our own tests.

3) is there a model for this component that is sufficient
   for our purposes as users/designers of software systems?

   Does the reading from Hennessey and Patterson do this?

   platter, cylinder, track, sector, block
   read/write head

   time = overhead + seek + rotational latency + transfer

4) can we build an abstract interface for this device that will
   make it easy to use without sacrificing control and performance?

   Well, that's pretty much what a file system is.



Summary of the introduction:

1) we discussed the Holy Grail of System Design, an abstract interface
   that makes the system easy to use without sacrificing control and
   performance.

2) we looked at disk drives as an example

3) we will apply this framework to other devices as we go along.




The storage hierarchy
---------------------

registers
cache
memory
disk
tape

fast = expensive = small
big = slow

Fundamental theorem of caching:

small and fast + big and slow ~= big and fast

IF (and this is a mighty big IF)

the access pattern has locality

1) temporal locality: the tendency to use values that were
   read or written recently

2) spatial locality: the tendency to use values NEAR others
   that were read or written recently.

Example:

1) a loop in a program tends to access the same instructions
   over and over

2) programs that work with arrays and files often access data
   sequentially.


Vocabulary confusion:

THE cache is the small fast memory between registers and main memory

A cache is anyplace in the hierarchy where a small storage device is
used to store values from a big storage device temporarily.


How does this help?

1) if you access a value 10 times, you might pay full price
   once, and then find it in cache 9 times.

   Hit rate = 90%

2) if you access the first element of an array, the cache
   might load the first 256 elements in the hope that you
   will use some of them.

   Hit rate > 99%


Average access time = hit rate  x cache latency + 
                      miss rate x backing store latency


Cache parameters:

1) size and latency (obviously)

2) transfer (block) size

3) replacement policy  (mapping function, associativity)

4) write policy



Homework Two
------------

What we want to know:

1) how big are the L1 and L2 caches?

2) what is the block size for transferring things from
   memory to L2, L2 to L1?

3) what is the associativity of the caches (maybe)?


Here are some suggestions for approaching problems like this:

1) Start with a simple experiment and figure out what
   behavior you expect in theory.

2) Look at the real data and compare it with your
   theoretical expectations.

3) Gradually make the experiment more complicated.


Simple experiment
-----------------

Create a big array and traverse it many times, reading
and writing each word (4 bytes) once per traversal.

Calculate the average time per read/write

	  (How to measure something small.
	  Repeat many times and divide
	  by the number of repetitions.)

	  (How to handle loop overhead)

What performance do you expect when the array is smaller
than the L1 cache?

What about when it is bigger than the L2 cache?

What about in between?

How would you plot the data in order to test this theory?


Next experiment
---------------

What happens when 

1) the size of the array is bigger than the L1 cache,
   but the stride is two words?  four words?

What happens when the stride is the same as the block size?


And the process repeats from there.  Add something to the
experiment, look at results, check for anomalies and see
if you can explain them, repeat.



Homework teams
--------------

For some of the assignments, I will assign you to work in groups
of two or three, at random.  Here are the assignments for Homework 2

 nicole.hori	    jonathan.pollack
 sharon.talbot	    aleksander.lorenc
 sarah.leavitt	    grant.hutchins
 leighton.ige	    kathleen.king
 nicholas.zola	    brendan.doms
 douglas.ellwanger  kathryn.rivard
 matthew.colyer	    steven.shannon
 christopher.stone  kevin.tostado
 alexander.davis    jesus.fernandez
 william.clayton    jonathan.tse

Who's not on my list yet?