Question 1

Indicate TRUE or FALSE for each of the following.  No credit for
letters halfway between T and F!

(a) In a four-way set associative cache, two of the address bits
are used to select which cache block within a set will be chosen.

(b) Programs using arrays will be more likely than
programs using linked lists to benefit from a wide cache design.

(c) Increasing the size of a direct mapped cache decreases
conflict misses.

(d) The choice of write-through or write-back design involves
a tradeoff between miss rate and miss penalty.

(e) The choice of direct mapped or associative design involves
a tradeoff between miss rate and hit cost.


Question 2

Given the physical address 0x0f1653f8, compute its block offset,
set number, and tag for each of the following caches:

size	width	policy		offset	set	tag
(words)	(words)

1024	8	direct-
		mapped
4096	16	4-way set
		associative
4096	4	fully
		associative


Question 3

Running the cache program from homework 13 on the Wazcog Mark IV
computer, you get the following results:

stride->          4       8      16      32      64     128     256

size
----
  64:           109     126     122     121     101     115     116
 128:           120     118     116     121     117     105     112
 256:           119     116     102     117     113     113     110
 512:           466     966     949     949     983     308     311
1024:           458     949     983     966     949     983     307
2048:           449     992     954     966     979     979     979

(Stride and size in bytes, times in nanoseconds.  Yes, this is an
artificially small example, to make the numbers fit easily.)

What is the cache size in bytes?

What is the block size in bytes?

What is the allocation policy?  (Direct mapped, fully associative, or set
associative?  If N-way set associative, what is N?)


Question 4

You have a direct mapped cache with 16K data words (64K bytes),
arranged in blocks
that are four words (16 bytes) wide.  You run the following program:

int array[SIZE], i;
for (i=0; i<SIZE; i += STRIDE) array[i] = 0;	/* initialization */
for (i=0; i<SIZE; i += STRIDE) array[i] = 1;	/* second pass */

During the second pass only, for each of the following sizes and
strides, what cache hit rate would you expect:

(a) SIZE = 64K words, STRIDE = 16K words.

	Nearly 100% hit rate.
	About 50% hit rate.
	Near zero hit rate.

(b) SIZE = 16K words, STRIDE = 2 words.

	Nearly 100% hit rate.
	About 50% hit rate.
	Near zero hit rate.

(c) SIZE = 32K words, STRIDE = 2 words.

	Nearly 100% hit rate.
	About 50% hit rate.
	Near zero hit rate.


Question 5

Given a cache size of 64 bytes (yes, that's small!) with a width of
two words (8 bytes), and four-way set associative access, with the
following contents (all numbers in hexadecimal):

set  tag       word 0    word 1    

0    1232123   12345678  abcd4321  
     0123212   54545454  98701356  
     048c848   9999ffee  05551212  
     0919091   7111248d  fab00123  
1    1232123   12345678  abcd4321  
     0123212   54545454  98701356  
     048c848   9999ffee  05551212  
     0919091   7111248d  fab00123  
}

Circle the byte in the cache corresponding to address 0x12321239,
supposing that this machine is little-endian, so that the lowest-address
byte of a word is the rightmost byte.


Question 6

Consider a machine with 32-bit addresses, byte addressable.  This
machine has a cache with a total capacity of 2^14 words.  Each
cache slot is eight words wide.  The cache is two-way set associative.
How many bits are in the tag field of each cache slot?


Question 7

Consider the following two cache arrangements:

Cache A: size 2 words, direct mapped, width 1 word (therefore two blocks)

Cache B: size 2 words, direct mapped, width 2 words (therefore one block)

Assume that we have an array int a[4]; and that the
address of a[0] is 0x1000.

*   Which of the following program fragments (a, b, or c) will result in a
    better hit rate for cache A than for cache B?

*   Which of the following fragments (a, b, or c) will result in a better hit
    rate for cache B than for cache A?

(a)      a[0]++; a[1]++; a[2]++; a[3]++;
(b)      a[1]++; a[3]++; a[1]++; a[3]++;
(c)      a[1]++; a[2]++; a[1]++; a[2]++;


Question 8

A.  Consider the following cache geometry:

	Data size: 4096 bytes
	Width: 16 bytes
        Type: Direct-mapped

    The address 0x7f55a356 will be mapped to which of the following?

    a. Set number: 0xa35, tag:   0x7f55
    b. Set number:  0x35, tag:  0x7f55a
    c. Set number: 0x356, tag:  0x7f55a
    d. Set number:  0x56, tag: 0x7f55a3

B.  What is the number of sets in an 80 Kbyte, 5-way set associative cache
with a block size of 32 bytes?  (1 Kbyte = 1024 bytes.)

C. Suppose that a page contains 4 Kbytes.  A virtual address and a physical
address are both 32 bits wide.  Here is the TLB:

                    Virtual page #    Physical page #
                  -------------------------------------
                0 |     0x00678     |      0x27       |
                1 |     0x01234     |      0x543      |
                2 |     0x12345     |      0x200      |
                3 |     0x45678     |      0x5        |
                  -------------------------------------

Convert the virtual address 0x12345678 into a physical address.

D.  An operating system could allow any of the following to be paged out 
    *except*:

  a. page tables
  b. disk I/O handler
  c. system call handler
  d. user programs


Question 9

Choose one of the following to fill the blank.  The main reason that
the design of a virtual memory system is different from the design of
a cache is that the _____ is so much greater.

(a) hit rate
(b) hit penalty
(c) miss penalty


Question 10

Consider the following configuration:

Virtual address: 32 bits
Physical memory size: 16 Mbytes ($2^{24}$ bytes)
Page size: 4 Kbytes
Cache size: 512 bytes (128 words)
Cache width: 32 bytes (8 words)
Cache storage policy: 2-way set associative
Write policy: write-through
TLB size: 8 entries
TLB storage policy: fully associative

The current data stored in this computer is as follows (Note: all numbers
are in hexadecimal and all leading zeros have been omitted from the data
stored in the cache):

TLB:        Virtual Page #    Physical Page #
	  -------------------------------------
	0 |      207b1      |       112       |
	1 |      040fa      |       067       |
	2 |      103e8      |       b5a       |
	3 |      081f4      |       a1c       |
	4 |      81f44      |       855       |
	5 |      03e89      |       22b       |
	6 |      40fa2      |       076       |
	7 |      07012      |       624       |
	  -------------------------------------
}

Cache:                                      Word #
 Set# Block#  Tag    V     0      4      8      c     10     14     18     1c
            --------------------------------------------------------------------
  0     0   | 0673 | 1 |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |
        1   |      | 0 |      |      |      |      |      |      |      |      |
  1     2   | 22b1 | 1 |   9  |   a  |   b  |   c  |   d  |   e  |   f  |  10  |
        3   |      | 0 |      |      |      |      |      |      |      |      |
  2     4   | b5a8 | 1 |  11  |  12  |  13  |  14  |  15  |  16  |  17  |  18  |
        5   |      | 0 |      |      |      |      |      |      |      |      |
  3     6   | 0672 | 1 |  19  |  1a  |  1b  |  1c  |  1d  |  1e  |  1f  |  20  |
        7   |      | 0 |      |      |      |      |      |      |      |      |
  4     8   | 6245 | 1 |  21  |  22  |  23  |  24  |  25  |  26  |  27  |  28  |
        9   | 076d | 1 |  29  |  2a  |  2b  |  2c  |  2d  |  2e  |  2f  |  30  |
  5     a   | 1125 | 1 |  31  |  32  |  33  |  34  |  35  |  36  |  37  |  38  |
        b   |      | 0 |      |      |      |      |      |      |      |      |
  6     c   | a1c5 | 1 |  39  |  3a  |  3b  |  3c  |  3d  |  3e  |  3f  |  40  |
        d   | 0765 | 1 |  41  |  42  |  43  |  44  |  45  |  46  |  47  |  48  |
  7     e   | 8556 | 1 |  49  |  4a  |  4b  |  4c  |  4d  |  4e  |  4f  |  50  |
        f   |      | 0 |      |      |      |      |      |      |      |      |
	    --------------------------------------------------------------------

What is the hexadecimal integer number contained in virtual address
0x40fa25d4?
Show your work: Indicate which TLB entry and/or cache set number and block
number you use.


Question 11

The page size of a computer is 4K bytes; the cache width is 32 words.
The cache is 8K bytes large, and is 4-way set associative. Both the virtual and
physical addresses are 32 bits long, and the machine is byte-addressable.
Calculate the sizes (number of bits) of the following fields:

    a. block offset		d. page offset
    b. set index		e. virtual page number
    c. tag			f. physical page number


Question 12

The cache and the virtual memory system are very similar ideas.  Each
uses a smaller, faster kind of memory to hold recently used items, and
a larger, slower kind of memory to hold older items.  Explain briefly
why the cache is entirely controlled in hardware, but the virtual memory
system is largely managed by software.  (Two sentences should be enough
for a precise answer.)


Question 13

What is the use of the dirty bit in a page table entry or a TLB entry?


Question 14

For each of the following tasks, indicate whether it is always done by
hardware, always done by the operating system, or could be either way:

a.  Reading a page table entry from main memory.
b.  Reading a TLB entry.
c.  Setting the write enable bit for a page.


Question 15

Under what circumstances might a valid page table entry have its Modified
bit on, but its Referenced bit off?


Question 16

True or false:  Because the penalty for a page fault is so great,
the replacement policy for TLB slots must be LRU rather than Random.
Explain your answer in one sentence.


Question 17

Is each of the following true or false?

    If a desired page isn't found in the process's physical memory, the system
    looks for it in the process's virtual memory.

    Considering virtual memory as a kind of caching, what corresponds to
    the cache width is the size of a page.

    Considering virtual memory as a kind of caching, what corresponds
    to the cache size is the size of the virtual address space.

    If the TLB design doesn't include a Writeable bit, the software can
    simulate it using the Dirty bit.


Question 18

(a) What hardware feature supports the use of the LRU algorithm in page
replacement?

(b) How can an operating system support LRU if this hardware feature
is missing?


Question 19

A.  The PDP-10 had a Block Transfer instruction (blt) for copying
a consecutive chunk of memory (such as an array) from one place to another.
Its operands were the beginning source address, the beginning destination
address, and the length of the transfer.  This instruction allows a high
level language to have assignments from one array variable to another,
instead of a loop to copy the array element by element.  Why wouldn't this
instruction make sense in the MIPS architecture?  (One or two sentences
should be enough.)

B.  The PDP-10 had four different procedure-calling instructions!  (One of
them, called jsp for Jump and Save PC, was much like the jal
instruction on the MIPS machines.)  We'd like you to comment on another
of them, the jsr (Jump to SubRoutine).  It was designed to
allow procedure calling without a stack.  Its operand was a memory
address.  The instruction stored the PC at that address, then started
executing instructions at the following word.  So a subroutine would start
this way:

subr:   .word  0            ; reserve space for PC
        addi   ...          ; first instruction of subroutine

The subroutine would return with a jump-indirect instruction whose operand
was the address subr, i.e., the address containing the return address.
Give two reasons (no more than two sentences each) why this procedure
calling mechanism wouldn't be a good idea in the MIPS architecture.


Question 20

The MIPS hardware treats general register 0 specially: it always
contains a zero value.

(a) Indicate at least two programming situations in which this hardware
feature is useful.

(b) Suppose this hardware feature were not provided.  Could it be
simulated by software?  If so, say how.  If not, why not?

(c) Someone suggests that two more general registers should be reserved
to contain the values 1 and -1 because these are often useful to
increment pointers and other variables.  How would you decide whether
or not this is a good idea?  (Note, the question is not ``is it a good
idea,'' but rather, what steps would you take to decide?)


Question 21

The following are proposed extensions to the MIPS hardware instruction
set.  For each proposed instruction, the question is this:  Can this
instruction be implemented in a way that is consistent with the
existing five-stage MIPS pipeline?  (You are not allowed to add extra
components to the processor.  For example, you can't throw in another
ALU or another memory port.)  The register numbers and offsets in
the descriptions below are just examples; the instructions should
accept any register or offset values!  Check the ones that are
consistent with the pipeline:

    PUSH $8, 0($29) stores the value
    from $8 into the specified memory address, and then
    subtracts 4 from the register that was used in specifying
    the address---$29 in this example.  (In effect, it allocates and fills
    a one-word stack frame.)

    LWR $10, $8($9) is the Load Word Register instruction.
    It adds the values in $8 and $9, and
    uses the result as an address, loading the word from that memory address
    into $10.  (This is something 61C students often do by mistake in the
    LW instruction!)

    INCSW $10, 200($8) is the Increment and Store Word instruction.
    It adds 1 to the value in $10, putting the result both back into
    $10 and into the specified memory address.

    ADDM $10, 200($8) is the Add Memory instruction.  It
    adds the value in $10 to the value in
    the selected memory address, putting the result back into $10.

    EXCH $10, 200($8) is the Exchange instruction.  It puts the old
    value from $10 into the selected memory address, and puts the old value
    from the selected memory address into $10.

    LWZ $10, 200($8) is the Load Word if Zero instruction.
    If the old value in $10 is zero, it loads the value from
    the selected memory address into $10.  If the old value
    in $10 is nonzero, that value is unchanged.


Question 22

The PDP-10 had an Exchange exch) instruction, which
exchanged the contents of a memory location and a register, like a MIPS
LW and SW done in parallel.  What is the main reason why
this instruction wouldn't make sense in the MIPS architecture?  (One or two
sentences should be enough.)


Question 23

Explain why the MIPS designers used pipelining to improve performance
of instruction processing rather than other possible forms of parallelism.


Question 24

For each of the following TAL operation types, indicate whether an operand
of an operation of that type always requires relocation by the loader,
sometimes requires relocation depending on the operation and the
operands used, or never requires relocation by the loader:

R-type _____

I-type _____

J-type _____


Question 25

Suppose that the following code were assembled into the file skip.o,
which is intended to be loaded along with another .o file that contains
the GETCHAR subroutine.

        .TEXT
__START:
        JAL     SKIPBLANKS
        DONE
	
SKIPBLANKS:
        ADDI    $SP,-4
        SW      $31,0($SP)
LOOP:
        JAL     GETCHAR       # returns a char in $2, or -1 if no more
        BLTZ    $2,SKIPPED
        LI      $8,' '        # a blank
        BNE     $2,$8,SKIPPED # check for nonblank
        J       LOOP          # blank, so get more
SKIPPED:
	LW      $31,0($SP)
	ADDI    $SP,4
	JR      $31

(a) In the table below, list the relocation entries that skip.o
would contain.

In the r_type column, indicate one of R_JMPADDR, R_REFHI,
or R_REFLO.  For r_extern, indicate 0 for false or 1
for true.

r_vaddr          r_type     r_extern          text or data reference?

(b) Suppose that the program is loaded so that SKIPBLANKS
represents address 0x124 and GETCHAR represents address 0x800.
Translate the five instructions starting at LOOP into machine code.
Your instructions should be specified as five eight-digit base 16 values.


Question 26

The reason the linker must do relocation is that the program may
occupy different memory addresses from the ones expected by the assembler.
If relocation concerns the use of memory,
why doesn't the MIPS linker have to relocate LW and SW instructions?
Those are the ones that access memory.  Explain in no more than two sentences.


Question 27

The MIPS program fragments on the left, below, include translations of the
C program fragments on the right, but not necessarily in the same order.
Next to each C program fragment, indicate the letter (a)--(e) of the
corresponding MIPS instructions.

(a)     lb    $16, 0($4)                        ch = *cp++;   ____
        addi  $4, $4, 1
                                                ch = (*cp)++; ____
(b)     addi  $8, $4, 1
	lb    $16, 0($8)                        ch = (*cp)+1; ____

(c)     lb    $16, 0($4)                        ch = *(cp+1); ____
        addi  $16, $16, 1
                                                ch = *++cp;   ____
(d)     lb    $16, 0($4)
	addi  $16, $16, 1
	sb    $16, 0($4)

(e)     addi  $4, $4, 1
	lb    $16, 0($4)

(f)     lb    $16, 0($4)
	addi  $8, $16, 1
	sb    $8, 0($4)