CS 252 - Homework #0 Solution

Homework 0 is due on Thursday 1/23/03.  This is not counted toward your final grade.  It is a review on prerequisite topics.  You should still turn in the homework to familiarize yourself with the homework turn in procedure.
 

            memory access
            decode
            execute
            write back
            fetch
    solution:
            stage name            stage function
            ---------------------------------------------------
            fetch                    : fetch instruction
            decode                : decode instruction, access register file, determine next program counter
            execute                : execute the instructions involving alu
            memory access    : access memory for memory access function
            write back           : write result back to register file

    solution:
            data hazards type        example                                        explanation
            --------------------------------------------------------------------------------------------------------------------
            WAW                 add r1, r2, r3    #1: r2 + r3 -> r1        The WAW data hazard is between instruction 1 and 3.
                                       add r4, r1, r5    #2: r1 + r5 -> r4        Both instructions write to register 1.
                                       add r1, r3, r5    #3: r3 + r5 -> r1

            WAR                  add r4, r1, r5    #1: r1 + r5 -> r4        The WAR data hazard is between instruction 1 and 2.
                                       add r1, r3, r5    #2: r3 + r5 -> r1        The second instruction writes to register 1 after the first
                                                                                                 instruction reads it.

            RAW                  add r1, r2, r3    #1: r2 + r3 -> r1        The RAW data hazard is between instruction 1 and 2.
                                       add r4, r1, r5    #2: r1 + r5 -> r4        The second instruction reads register 1 after the first
                                                                                                 instruction writes to it.

    solution:
            instruction type                        percentage of total instruction        cycle count            CPI contribution
          ---------------------------------------------------------------------------------------------------------
           memory access                    :                            30%                *        2                        0.6
           integer operations                 :                            50%                *        1                        0.5
           floating point operations        :                            20%                *        3                        0.6
                                                                                                                                --------------------------
                                                                                                                                =>     1.7 CPI for processor A running program X.


            Compulsory
            Capacity
            Conflict

    solution:
            The table describes how increasing block size, associativity, and overall size affects each type of misses in cache.
 

Cache miss type

Description

Block size

Associativity

Overall Size

Compulsory

misses occurred when the starting cache is empty

decrease
This increases the amount of prefetch, therefore decreases initial misses needed to fill up the cache with relevant entries.

no affect

no affect

Capacity

misses occurred when the cache is too small to contain the working set of memory access

no affect

no affect

decrease 

Conflict

misses occurred when multiple memory entries are mapped to the same cache entry due to cache mapping algorithm. 

increase
The cache will contain less blocks.  This increases mapping conflicts for far away memory entries.

decrease
this increases the number of cache entries available to the same memory entry, therefore give rise to less misses due to mapping conflict 

no affect