Scribd Logo
Upload

Welcome to Scribd!

  • 506 views

    Lab One: Cache Simulator Steve Shen

    Uploaded by

    Steve Shen
    This document discusses cache replacement techniques and types of cache misses. It analyzes miss rates for different cache configurations using sample input sequences. The key points are: 1) RAND replacement had the lowest miss rate overall, followed by LRU for the given 120-element input sequence. The 64 block 4-way RAND configuration performed best. 2) The three types of cache misses are compulsory, capacity, and conflict misses. Compulsory misses occur on the first reference to a block, capacity misses are due to limited cache size, and conflict misses are due to multiple blocks mapping to the same set. 3) A fully associative cache would minimize conflict misses but is impractical due to high hardware cost

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Lab One: Cache Simulator Steve Shen

    Uploaded by

    Steve Shen
    506 views2 pages
    This document discusses cache replacement techniques and types of cache misses. It analyzes miss rates for different cache configurations using sample input sequences. The key points are: 1) RAND replacement had the lowest miss rate overall, followed by LRU for the given 120-element input sequence. The 64 block 4-way RAND configuration performed best. 2) The three types of cache misses are compulsory, capacity, and conflict misses. Compulsory misses occur on the first reference to a block, capacity misses are due to limited cache size, and conflict misses are due to multiple blocks mapping to the same set. 3) A fully associative cache would minimize conflict misses but is impractical due to high hardware cost

    Original Description:

    Results of a cache simulation

    Original Title

    Cache Simulation

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses cache replacement techniques and types of cache misses. It analyzes miss rates for different cache configurations using sample input sequences. The key points are: 1) RAND replacement had the lowest miss rate overall, followed by LRU for the given 120-element input sequence. The 64 block 4-way RAND configuration performed best. 2) The three types of cache misses are compulsory, capacity, and conflict misses. Compulsory misses occur on the first reference to a block, capacity misses are due to limited cache size, and conflict misses are due to multiple blocks mapping to the same set. 3) A fully associative cache would minimize conflict misses but is impractical due to high hardware cost

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    506 views2 pages

    Lab One: Cache Simulator Steve Shen

    Uploaded by

    Steve Shen
    This document discusses cache replacement techniques and types of cache misses. It analyzes miss rates for different cache configurations using sample input sequences. The key points are: 1) RAND replacement had the lowest miss rate overall, followed by LRU for the given 120-element input sequence. The 64 block 4-way RAND configuration performed best. 2) The three types of cache misses are compulsory, capacity, and conflict misses. Compulsory misses occur on the first reference to a block, capacity misses are due to limited cache size, and conflict misses are due to multiple blocks mapping to the same set. 3) A fully associative cache would minimize conflict misses but is impractical due to high hardware cost

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 2

    COSC6340

    Lab1

    Lab One: Cache Simulator Steve Shen


    1) Consider the input sequence of length 120 given below. (a) Analyze the effectiveness of different block replacement techniques by listing down the miss rate in each case. 2-way LRU 97.58 % 90.17 % 82.42 % 67.75 % FIFO 97.58 % 91.67 % 82.42 % 70.33 % RAND 96% 90.92 % 80.25 % 39.25 % 4-way LRU 96.75 % 91.92 % 82.42 % 66% FIFO 96.75 % 91.92 % 82.42 % 70.17 % RAND 96.25 % 91.92 % 80% 37.58 % 8-way LRU 96.75 % 91.83 % 80.83 % 61.67 % FIFO 96.75 % 91.83 % 81.58 % 65.33 % RAND 96.75 % 91.08 % 79.5% 44.67 %

    8 block s 16 block s 32 block s 64 block s

    In general, higher blocks had a smaller miss rate. The RAND technique overall had the lowest miss rate using the given input sequence and the Least recently used (LRU) came in second. For the given input sequence, the 64 block 4-way RAND had the best performance. (b) What other block replacement technique can be used and is proved to be the ideal? Explain. Optimal page replacement (OPT) swaps out a page whose next use will occur furthers in the future whenever a page needs to be swapped in; however, it is difficult to figure out how long it will be before a page is going to be used so it is impractical except when the software that runs on the system will work with static analysis of its memory reference patterns. 2) In an N-way set-associative cache, blocks are mapped to different sets when N changes. Also, for a particular sequence, the number of compulsory and conflict misses change with the cache type. Consider the following sequence 4 0 9 7 8 11 7 5 2 1 12 6 8.

    COSC6340

    Lab1

    (a) List the compulsory and conflict misses for techniques for the caches below. MISSES LRU FIFO Comp Conflict Comp 4 blocks 2 sets 4 8 4 8 blocks 2 sets 8 3 8 16 blocks 2 sets 11 0 11

    different replacement Conflict 8 3 0 RANDOM Comp 4 8 11 Conflict 9 4 0

    (b) Define compulsory, capacity and conflict misses. Explain the difference between them. Compulsory misses are those misses caused by the first reference to a location in memory. Capacity misses are ones that happen due to the limited size of the cache and conflict misses are misses that happen when several blocks are mapped to the same set or block frame. (c) What is the best way to reduce conflict misses? Can it be used? A fully associative cache would reduce miss rates the most; however, the perfection of one is impossible because the future cannot be read so currently you have to deal with a trade-off where you can get lower miss rates but suffer from a high miss penalty. (d) List which set in the given cache will the following blocks be mapped BLOCK 0 9 11 4 2 9 10 4 7 1 12 3 CACHE 8 blocks, 2 sets #SET 0 1 1 0 2 1 2 0 1 1 0 1

    8 blocks, 4 sets

    16 blocks, 2 sets

    You might also like