# Memory Organization

## Memory Hierarchy

We say that Registers have the highest speed, followed by cache, main memory then secondary storage. However, they are inversely proportional to the capacity they can hold.


## Main Memory


Here we will be focusing on non-volatile ROM:

| | PROM | EPROM | EFPROM |
| - | - | - | - |
| Characteristics | ROM that can be **modified only once** by user | programmable ROM that can be **erased and reused** | user-modifiable ROM that can be **erased and reprogrammed repeatedly** through a normal electrical voltage |
| Full Name| **Programmable Read Only Memory** | **Erasable Programmble Read Only Memory** | **Electrically Erasable Read Only Memory** |
| Developer | Wen Tsing Chow, 1956 | Dov Frohman, 1971 | George Perlegos, 1978 |
| Reprogrammability | reprogrammable only once | can be reprogrammed **using UV light** | can be reprogrammed **using electrical charge** |

## Auxiliary Memory

Auxiliary memory can also be referred to as secondary memory. It has the following characteristics:

- non-volatile
- low cost
- highest capacity
- slowest access storage

| Solid State Drive (SSD) | Hard Disk Drive (HDD) |
| - | - |
| **speed up computer performance signifcantly** (more than CPU or RAM) | **slower** |
| **more expensive and less storage** | **cheaper and offers more storage** |

## Associative Memory

Associative memory is a type of computer memory which items may be retrieved by matching some part of their content, rather than by specifying their address, also called Content-Addressible Memory (CAM).

It is **much slower than RAM, rarely encountered in maintstream computer designs.**

- used in multilevel memory systems
- in cache that may hold copies of large blocks of a larger memory for rapid access
- retrieving word needs a search key that represents particular values of all or some of the bits in the word
- compared in parallel with corresponding lock or tag bits of all stored words
- all matching words the key are signaled to be available
- expensive to implement as integrated circuitry
- can be used in certain very high speed searching applications
- can search data (tag) for access by content of data rather than address

## Cache Memory

We say that a single cache has the following organization:


wheresas a three-level cache organization:


### Cache Organization

**Direct-Mapped Cache**

- **all cache blocks have diff colors**
- memory blocks in each page **cycle through the same colors in order**
- a memory block can be placed **only in a cache block of matching color**


- restrict possible placements of a memory block in the cache
- a block in main memory can be placed in exactly one location in the cache
- a cache line can be target only of a subset of possible memory blocks
- Many - 1 relation from memory blocks of cache lines
- useful to think of memory divided into pages of contiguous blocks
- size of a page is the size of the Direct Mapped Cache
- k-th block in any page can be mapped only to the k-th cache line

From a given memory block address we can know exactly where to search for it in the cache:




We say that each memory block has a unique location it can be present in the cache:

- Main memory cache: $N = 2^n$ blocks, block addresses: $0, 1, ..., 2^n - 1$
- Cache size: $M = 2^M$ blocks, block addresses: $0, 1, ..., 2^m - 1$


**Fully Associative Cache**

The memory block can be placed in any cache block:
- When data is fetched from memory, it can be placed in any unused block of the cache
- no conflicts will happen between multiple memory addresses which map to a single cache block

## Exercises

### Question 1

Assuming the "Tag bits, Index bits, Offset bits" with the T:I:O of the direct mapped cache is `16:10:6`, find:

- main memory size
- cache size
- block (line) size
- number of memory blocks
- number of cache blocks

### Answers

Main memory size can be calculated by the sum of T, I and O:

$$T + I + O = 16 + 10 + 6 = 32 \text{ bits}$$

$$\text{Main Memory Size} = 2^{32} = 4 \text{ GB}$$

Finding the cache size requires obtaining the product of the number of cache blocks and block size:

$$\text{Cache Size } = \text{Number of Cache Blocks} \times \text{Block Size}$$

For number of cache blocks:

$$\text{Number of Cache Blocks} = 2^{\text{Index bits}}$$

$$= 2^{10} = 1024 \text{ blocks}$$

For block (line) size:

$$\text{Block Size} = 2^{\text{Offset Bits}}$$

$$= 2^6 = 64 \text{ bytes}$$

For cache size:

$$\text{Cache Size} = 2^{16} \text{ bytes}$$

We calculate the number of memory blocks by dividing main memory size by block size:

$$\text{Number of Memory Blocks} = \frac{\text{Main Memory Size}}{\text{Block Size}}$$

$$= \frac{2^{32}}{2^6} = 2^{26}$$


### Question 2

In the Fig.1 to Fig.3, **each blank box in the CPU Cache represents 8 bits (1 byte) of data.** Our memory is byte-addressed, meaning that there is **one address for each byte.** Assuming that the main memory address is 32-bit, find:

- **the T:I:O(the “Tag bits, Index bits, Offset bits” )**
- **type of cache**
- **cache size**

*Hint: Index bits=log2 (Number of index rows), Offset bits=log2 (Number of offsets columns))*

Fig 1:

Fig 2:

Fig 3:

### Answers

**Figure 1**

There's no index rows, so index bits = 0. We can find the offset bits:

$$\text{Offset Bits} = \log_2 \text{Number of Offset Columns}$$

$$= \log_2 4 = 2$$

Since the main memory address is 32 bits, we can obtain tag bits through subtracting it with index and offset bits:

$$\text{Tag Bits} = 32 - \text{Index Bits} - \text{Offset Bits}$$

$$= 32 - 0 - 2 = 30$$

No index rows where each block from main memory is mapped to the offset, this is a **Fully-Associative Cache.**

**Figure 2**

We can see that there's 2 sets of cache, this implies it's a **2-Way Set Associative Cache.** From Fig 2, the cache consists of 2 sets, **shown by 2 separate rows for each way in the cache, each set is uniquely identified as an index:**

$$\text{Index Bits} = \log_2 \text{Number of Index Rows}$$

$$= \log_2 2 = 1$$

We can find the offset bits:

$$\text{Offset Bits} = \log_2 \text{Number of Offset Columns}$$

$$= \log_2 4 = 2$$

Since the main memory address is 32 bits, we can obtain tag bits through subtracting it with index and offset bits:

$$\text{Tag Bits} = 32 - \text{Index Bits} - \text{Offset Bits}$$

$$= 32 - 1 - 2 = 29$$

**Figure 3**

From the hint and Fig 3, we can find the index bits:

$$\text{Index Bits} = \log_2 \text{Number of Index Rows}$$

$$= \log_2 4 = 2$$

Similarly, we can find the offset bits:

$$\text{Offset Bits} = \log_2 \text{Number of Offset Columns}$$

$$= \log_2 4 = 2$$

Since the main memory address is 32 bits, we can obtain tag bits through subtracting it with index and offset bits:

$$\text{Tag Bits} = 32 - \text{Index Bits} - \text{Offset Bits}$$

$$= 32 - 2 - 2 = 28$$

**Figure 3 has both index rows with offset columns. This is a Direct Mapped Cache** All cache sizes are 16 bytes.

### Question 3

Draw a figure for a **fully associative cache,** assuming the **main memory address is 32-bit, each block has 8 Bytes,** and the **cache size is 256 Bytes.**

### Answers

- fully associative cache: no index

Each block is 8 bytes, total cache size is 256 bytes:

$$\text{Number of Cache Blocks} = \frac{\text{Cache Size}}{\text{Block Size}}$$

$$= \frac{256}{8} = 32 \text{ blocks}$$

We then determine the number of offset bits (O):

$$\text{Offset Bits} = \log_2 \text{Block Size}$$

$$= \log_2 8 = 3$$

We can determine tag bits by:

$$\text{Tag Bits} = 32 - 0 - 3 = 29$$

Hence, T:I:O = 29:0:3

We continue to determine the cache rows by performing the following calculations:

$$256 = 2^{m + b}$$

$$m + b = 8$$

$$m = 8 - b = 5$$

### Question 4

Draw a figure for a **direct mapped cache,** assuming the **main memory address is 32-bit, each block has 8 Bytes,** and the **cache size is 256 Bytes.**

### Answers

- direct mapped cache: index and offset bits

We can determine the offset bits:

$$\text{Offset Bits} = \log_2 \text{Block Size} = 3$$

We can calculate the index bits through number of cache blocks:

$$\text{Number of Cache Blocks} = \frac{\text{Cache Size}}{\text{Block Size}}$$

$$= \frac{256}{8} = 32 \text{ blocks}$$

$$\text{Index Bits} = \log_2 \text{Number of Cache Blocks}$$

$$= \log_2 32 = 5$$

For the calculation of tag bits:

$$\text{Tag Bits} = 32 - 5 - 3 = 24$$

Hence, we get that T:I:O = 24:5:3

We continue to determine the cache rows by performing the following calculations:

$$256 = 2^{m + b}$$

$$m + b = 8$$

$$m = 8 - b = 5$$

### Question 5

Draw a figure for a **8-way set associative cache,** assuming the **main memory address is 32-bit, each block has 8 Bytes,** and the **cache size is 256 Bytes.**

## Conclusion with Examples

| **Step** | **Description** | **Formula/Explanation** |
|----------|----------------------------------------------------------|---------------------------------------------------------------------------------------------------------|
| **1** | **Determine Offset Bits (O)** | Offset bits = $\log_2(\text{Block size})$. This identifies the byte within each block. |
| **2** | **Determine Index Bits (I)** | $I = \log_2(\text{Number of Sets})$. For fully associative cache, $I = 0$. |
| **3** | **Determine Tag Bits (T)** | $T = \text{Total Address Bits} - I - O$. |
| **4** | **Verify Cache Size** | $\text{Cache Size} = 2^{m + b}$, where $m$ = Index bits + Number of rows, $b$ = Offset bits. |
| **5** | **For Associativity Problems** | $\text{Number of Sets} = \frac{\text{Total Cache Blocks}}{\text{Associativity}}$. |
| **6** | **For Fully Associative Cache** | $I = 0$. All blocks can map to any cache line. |
| **7** | **For Direct-Mapped Cache** | $\text{Index bits} \neq 0$. Blocks map to specific cache lines based on their index bits. |
| **8** | **For Set-Associative Cache** | Combine steps 2 and 5 to calculate the number of sets and index bits. |

| **Scenario** | **Given Details** | **Solution** |
|--------------------------------|----------------------------------------------------------|---------------------------------------------------------------------------------------------------------|
| **Fully Associative Cache** | Cache size = 256 bytes, Block size = 8 bytes | $O = 3$, $I = 0$, $T = 32 - 3 - 0 = 29$. Cache size $256 = 2^{m+b}$, $m + b = 8$. |
| **Direct-Mapped Cache** | Cache size = 256 bytes, Block size = 8 bytes | $O = 3$, $I = 5$, $T = 32 - 5 - 3 = 24$. Cache has $32$ blocks. |
| **8-Way Set-Associative Cache** | Cache size = 256 bytes, Block size = 8 bytes, 8-way | $O = 3$, $I = 2$, $T = 32 - 2 - 3 = 27$. Cache has $4$ sets. |

**Offset Bits (O):**

- Determined solely by the block size.
- $\text{Block size} = 2^b \implies O = \log_2(\text{Block size})$.

**Index Bits (I):**

- Depends on the cache structure:
- $I = \log_2(\text{Number of sets})$ for set-associative or direct-mapped cache.
- $I = 0$ for fully associative cache.

**Tag Bits (T):**

- The remainder of the memory address bits after accounting for $I$ and $O$.

**Cache Size Verification:**

- $\text{Cache size} = 2^{m+b}$, where $m$ and $b$ come from Index + Offset bits.