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