hw0sol

CS 252 - Homework #0 Solution

Homework 0 is due on Thursday 1/25/02. 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.

List the following 5 stages of the MIPS processor in order from beginning to end. Then briefly describe the function performed in each stage.

            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

Write after write (WAW), write after read (WAR), read after write (RAW) are three types of potential data hazards. Give example for each in MIPS assembly code.

    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.

Processor A has 3 types of instructions, memory access, integer operation, and floating point operation. Memory access takes 2 cycles each. Integer operation takes 1 cycle each. Floating point takes 3 cycles each. Program X compile for processor A has 30% memory access instructions, 50% integer operation instructions, and 20% floating point operation instructions. What is the cycle per instruction (CPI) for processor A running program X.

    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.

Describe the following types of misses in cache. Describe how the block size, associativity, and overall size of the cache affect each type of miss.

            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

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