<commit_before>---
layout: post
tags: [systems, theory]
published: True
---

When we write programs for computers, we often abstract away memory as a large, fast contiguous byte-addressable array. 
But we have a problem when we try to implement this abstraction in hardware - it turns out that it's impossible to satisfy all these conditions. 

It's possible to make a small amount of fast memory, and it's also possible to make a large amount of slow memory. 

By building the memory heirarchy, namely a series of caches, we can give the appearance that our memory is both fast and large. 

## Caching
Caching exploits **temporal locality** as well as **spatial locality**. Basically, the distribution of memory accesses is not uniform - if we access a specific block of memory, it's very likely that we will repeatedly access that block. It's also very likely that we will access the memory spots right next to that spot.

A memory address that is entered into the cahce is split into the tag, the index, and the block offset.
When we lookup in the cache, we take our address and use the tag to query the cache. 

### Virtual Memory

Programs assume that they have access to all the memory available to the system. To them, memory looks like an infinitely large contiguous byte-addressable array. 

The OS is responsible for providing every program running on the computer with this abstraction. To do so it uses a page table to turn virtual addresses into physical ones. 

The MMU is responsible for taking in virtual addresses and outputing physical addresses. It maintains a cache called the TLB, or translation lookaside buffer. 

Basically every virtual address and translation is stored inside a page table. In early virtual memory systems, the TLB didn't exist and thus each translation required an access to the page table held in main memory - this is problematic because it breaks down the memory heirarchy that we set up earlier - the page table is too big to fit in the cache and thus resides in main memory, and since every access to memory has to go through this page table, we're bottlenecked by out translation speed. 

The TLB is a cache of common memory translations. 

In the worst case, when the page table may not be in memory. In this case, we must pull the page table from the disk, invoking an even larger time penalty.

### Caching and Virtual Memory
Here we have a problem - we can either cache on the **virtual address** or on the **physical address**. Each of these have different benefits

1. Physically indexed, physically tagged (PIPT)
    - In this kind of cache, the physical address is used for both the index and the tag. This is great, because we have no problems with coherency or aliasing. 
    - On the other hand, this now means we need to do a TLB lookup **every** time we access memory. Furthermore, we may pay an even greater penalty if our memory translation is not in the TLB - we must then access main memory, which takes even more time

2. Virtually indexed, virtually tagged (VIVT)<commit_msg>added associativity<commit_after>---
layout: post
tags: [systems, theory]
published: True
---

When we write programs for computers, we often abstract away memory as a large, fast contiguous byte-addressable array. 
But we have a problem when we try to implement this abstraction in hardware - it turns out that it's impossible to satisfy all these conditions. 

Creating memory that is both fast and large is extremely expensive - however it's possible to cheaply make a small amount of fast memory, and it's also possible to make a large amount of slow memory.

To provide the illusion of a large amount of fast memory, we can construct the memory hierarchy, namely a series of caches.

![mem_heiarchy](https://qph.fs.quoracdn.net/main-qimg-9fed1764126687d17348ac6b4a39a0de-c)

Caching exploits **temporal locality** as well as **spatial locality**. Basically, the distribution of memory accesses is not uniform - if we access a specific block of memory, it's very likely that we will repeatedly access that block. It's also very likely that we will access the memory spots right next to that spot. By putting items that we recently accessed into the cache, we can speed up memory access.

## Caching
A memory address that is entered into the cache is split into the tag, the index, and the block offset.

We usually cache blocks of memory - 

### Types of Cache Misses


### Associativity
We pick a replacement policy such as LRU in order to pick where a block of memory will go. If a cache block can go into any place inside the cache, the cache is said to be **fully associative**. More generally, if a block of memory can be put in any one of $$N$$ places, we refer to thjat cache as **n-way** associative. 

A fully associative cache may experience fewer cache misses (specifically conflict misses), but lookups in the cache will take longer - we will have to look at every item in the cache in order to determine if we have a cache hit or miss. 

## Address Translation

### Virtual Memory

Programs assume that they have access to all the memory available to the system. To them, memory looks like an infinitely large contiguous byte-addressable array. 

The OS is responsible for providing every program running on the computer with this abstraction. To do so it uses a page table to turn virtual addresses into physical ones. 

The MMU is responsible for taking in virtual addresses and outputing physical addresses. It maintains a cache called the TLB, or translation lookaside buffer. 

Basically every virtual address and translation is stored inside a page table. In early virtual memory systems, the TLB didn't exist and thus each translation required an access to the page table held in main memory - this is problematic because it breaks down the memory heirarchy that we set up earlier - the page table is too big to fit in the cache and thus resides in main memory, and since every access to memory has to go through this page table, we're bottlenecked by out translation speed. 

The TLB is a cache of common memory translations. 

In the worst case, when the page table may not be in memory. In this case, we must pull the page table from the disk, invoking an even larger time penalty.

### Caching and Virtual Memory
Here we have a problem - we can either cache on the **virtual address** or on the **physical address**. Each of these have different benefits

1. Physically indexed, physically tagged (PIPT)
    - In this kind of cache, the physical address is used for both the index and the tag. This is great, because we have no problems with coherency or aliasing. 
    - On the other hand, this now means we need to do a TLB lookup **every** time we access memory. Furthermore, we may pay an even greater penalty if our memory translation is not in the TLB - we must then access main memory, which takes even more time

2. Virtually indexed, virtually tagged (VIVT)
{'fraction_non_alphanumeric': 0.040219114891163324, 'fraction_numerical': 0.00360386334150209, 'mean_word_length': 4.108983799705449, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2856943', 'n_tokens_mistral': 1710, 'n_tokens_neox': 1584, 'n_words': 1152}