페이지

2015년 6월 3일 수요일

Computer Architecture. chap4 Cache Memory

Cache memory

Overview

I will describe most of the concept of cache by the figure below and just post about L1 cache.
Where is cache?

Example. How to works cache



Assume
 - IR: 16 bit
 - AC: 16 bit = 2bytes = 1word
Steps
  1. PC = 300  IR = 1940 Read operation
    Cache state: miss (hit/miss)
  2. PC = 301 AC = 003 Read operation
    Cache state: miss
  3. PC = 301 IR = 5941 Read operation
    Cache state: hit
  4. PC = 302 AC = 0002 → 0005 Read operation
    Cache: hit
  5. PC = 302 AC = 0005 → M (941) Write operation

Memory Hierarchy - Diagram

Ref: Computer Organization and Architecture 5th edition,
William Stallings, P.139
  This hierarchy goes down the following occur
  1. Decreasing cost per bit
  2. Increasing capacity
  3. Increasing access time
  4. Decreasing frequency of access of the memory by the processor

    The basis for the validity of condition '4.' is  a principle known as locality of reference (that's why created cache). During the course of execution of a program, memory references by the processor, for both instructions and data, tend to cluster. In short, references to a small set of instructions.

Cache/ Main Memory Structure & Cache Mapping

Ref: Computer Organization and Architecture 5th edition,
William Stallings, P.143
  This is an example with some assume. Then, I will add some description about it.

Mapping function  

  1. Direct: Have only 1-way. According to the above example, Tag is 6 bits
            →The whole line number appears at address bit. Remainder part is Tag
  2. Associative: Have 2^r way. According to the above example, Tag is 14 bits
            →The line number does not appear at address bit. 
  3. Set associative: Have k way {k | 1 ~ k ~2^R}.
            →Some of line number appears at address bit.  Remainder part is Tag
Variables summary 
(If you don't have text book(Computer Organization and Architecture 5th edition, William Stallings), ignore it)
  • n: address bits
  • s: block bits
  • r: line bits
  • ra: line bits included in the address bits
  • w: word bits
  • t: Tag bits = s - ra = direct (14 - 8 - = 6) | associative (14 - 0 = 14) 
  • k: way

Cache structure = Tag + block

  If a block can be stored in only one line, that means 'one way'  
                                                                               Direct mapping function

CAM (Content Addressable Memory)

  • Compare input with Tags return an address (Line number)
  • It has parallel structure, so it returns value immediately.
NOTE
Normally, a memory address is made up by 'byte-addressable' method.
If do something with 'word-addressable' method at same memory, 

LRU(Least Recently Used) replacement

I will just show some figure of LRU.
The components of cache include LRU bit

Details of LRU bit

Locality

  • Spatial Locality: refers to the tendency of execution to involve a number of memory locations that are clustered.
  • Temporal Locality: refers to the tendency for a processor to access memory locations that have been used recently.

Write Policy

Compare two different styles when memory is shared