\documentstyle[class,11pt]{article}
\def\ClassName{Computer~Organization}
\def\ClassNumber{CS~333}
\handedout{(11/17/95) Handout \#15}
\vspace{0.5in}

\begin{document}
\begin{center}
{\large \bf Homework \#7} \\
{\bf Due before 12 noon, November 29, 1995 \\
Turn in at TA's office L423 DCL (Basement)} \\
(Slide in under door if locked.)
\end{center}

{\bf NOTE the NOON due date.}

{\it As with all class assignments, you are expected to work the problems
on your own.  Discussions with other students should be limited to
understanding the problem and discussing general issues, NOT solving
the problems.  Electronic mail or posting to the course news group
(uiuc.class.cs333) is probably the fastest way to get clarification of
any problems, but you are welcome to contact any of the teaching staff
directly.  Check the WWW (URL: http://www-courses.cs.uiuc.edu/{$\sim$}cs333) 
for course information such as office hours.}

{\bf Introduction:} This assignment focuses on virtual memory, cache
coherence, and input/output.  Before starting the homework, you should
have read Chapter 6 and Sections 8.3, 8.4 and 8.6 in the textbook.

{\bf Problems:}
If you feel that a problem is specified insufficiently, state clearly
and justify the assumptions you are making.  Please write your
solutions neatly, making sure to SHOW CLEARLY how you arrived at your
answers.  Illegible or insufficiently clear solutions may be graded 
as incorrect.

\begin{problems}
\problem \Points{30}
{\bf Virtual Memory Translation}

a. Virtual memory systems use page tables to translate from virtual
addresses to physical addresses.  Consider a machine such as the DEC
Alpha 21064 which has 64 bit registers and manipulates 64-bit
addresses.  If the page size is 8KB, how many bits of virtual page
number are there?  If the page table used for translation from virtual
to physical addresses were 8 bytes per entry, how much memory is
required for the page table and is this amount of memory feasible?

b. The actual DEC 21064 processor only implements 43 bits of virtual
address space and 34 bits of physical address.  Explain how this could
be done when programs manipulate 64-bit addresses.  Does this cause
programmers that use less than $2^{43}$ bytes of address space any
difficulty?

c. Consider the TLB design for the 21064.  Reducing the virtual
address size and physical address size simplifies the TLB
significantly.  If a TLB with 64-bit addresses (both virtual and
physical) with 16 entries could be implemented, how much larger a TLB
could be implemented if the storage is the limiting implementation
constraint? 

d. Consider a simultaneous translation scheme which uses the lower 13
bits of address to index and select from the L1 caches in the DEC
Alpha 21064.  If L1 cache misses take 30 cycles to service and TLB
misses take 50 cycles to service, for L1 cache miss rates of 1,2,4,
and 8\% (for both the instruction and data caches), calculate the TLB
miss rate which would result in an equal amount of execution time
spent servicing TLB and L1 cache misses.  Make sure to account for
both instruction and data references, and assume the Load/store
fraction is 30\%.

\problem \Points{10}
{\bf Cache Coherence I} -- H\&P Exercise 8.3

\problem \Points{30}
{\bf Cache Coherence II} -- H\&P Exercise 8.8

\problem \Points{30}
{\bf Input/Output (Disk Arrays)} 

Disk arrays: Consider a disk array built from Seagate ST31401N Elite-2
Drives (see Figure 6.2 in the text).  The array has five disks, with
parity interleaved across the disks in 512 byte sectors, using a
RAID-5 organization.

a. Assuming a seek time of exactly 10
milliseconds and synchronized disks, how long would it take to do a
32 kilobyte and 16 megabyte read respectively?

b. If the disks in the array are not synchronized how would this
affect the average time to do a 16 megabyte read?  Calculate this
as a function of the largest seek time of the 5 disks.

c. Discuss how would the numbers for part 2 change if the disk array had 9
disks?  17 disks?  (Don't have to calculate the answer precisely.)

d. Finally, the worst case performance for RAID-5's is small writes.
Assuming we're writing 512-byte blocks, what is the average latency
for 512-byte writes?  What is the average throughput for the 5-disk
array for such writes, assuming first-come-first-serve disk head
scheduling?
\end{problems}

\end{document}