Memory and Cash

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 30 · page 30.3
Memory and Cash
How the OSI works, what's a pointer like arrays in memory, and why the cache of the processor makes the code 100 times faster.
The processor doesn't work directly with the OSI, between them.
3 levels of cache
To understand that means to understand why
for i for j
and
for j for i
may differ in speed by five times.
GEF
PIF
He's got a little bit of depth.
01
OSI: Addresses and Cells
Operational memory (RAM)
It's a huge array of numbered cells. Each cell stores 1 byte (8 bits) and has a unique set of cells.
Address
- a whole number.
The processor reads memory by team
LOAD адрес → регистр
and record by team.
STORE регистр → адрес
Everything in the computer -- variables, arrays, objects -- is just a range of memory cells.
🔬
RAM cell simulator
Press the cell to change its value (0–255).
Index
Massive
Data
What's stored in the box?
- depends on the type of variable:
char c = 'A'
♪ 1 byte ♪ ASCII code 65 =
0100 0001
int n = 300
♪ 4 bytes ♪ is recorded in the 1 byte code
double x = 3.14
♪ 8 bytes ♪ IEEE 754 duble
int* p
♪ 4 or 8 byte ♪
Address
other memory cell
02
Indexes
Index (pointer)
- a variable that keeps
Address
another variable in memory.
int x = 42;
- variable in a cell, e.g. address
0x1000
int* p = &x;
- Index
p
Saves Value
0x1000
*p
— Fashioning: Read the value to the address stored in p received
42
👉
Index chain simulator
Press "The Next Step" to go through the chain of defecations.
What's with the signposts?
Transfer by reference
The function changes the variable of the trigger code without copying the whole large object.
Dynamic memory
malloc
/
new
Returns the index to the selected block. The size is only known in the rebound.
Data structures
Contact lists, trees, graphs — knots keep signposts on neighbors.
Arrays
The C/C++ array name is an index to its first element.
03
Massives in memory
Massive is
continuous memory
All elements are in a row, close to each other.
For array
int arr[5]
(each)
int
= 4 bytes) with an initial address
0x2000
:
arr[0]
→ 0x2000,
arr[1]
→ 0x2004,
arr[2]
→ 0x2008, …
Address of element i:
base + i × sizeof(type)
📦
Massive memory: address visualiser
Type of element
Mass Size
Basic address (hex)
Two-dimensional array:
is stored as a single-dimensional, line by line (row-major orderer in C).
a[i][j]
→
base + (i*cols + j) * sizeof(тип)
That's why the rows are faster than the columns — the neighbouring elements of the same line are close to the memory (and together they enter the cache).
04
Ierarchy of memory and cache of processor
The processor is operating on a tactical frequency of ~3–5 GHz.
60-100 ns
In order not to wait, there are several levels of rapidity between the processor and the OZM.
Cache memory (SRAM)
:
L1 cache
32 - 64 KB · 1 - 4 cycles (~0.5 ns) in each kernel
↕
L2 cache
256 KB - 1 MB 10 - 20 cycles (~5 ns) in each kernel
↕
L3 cache
8 - 32 MB 30 - 50 cycles (~15 ns) common to kernels
↕
OZU (DRAM)
4 - 64 GB 200 - 300 cycles (~80 ns) slowly!
The analogy:
The processor is a cook, L1 is what's right in front of him on the cutting board (imminent access), L2 is on the kitchen table, L3 is in the refrigerator next door, OZU is in a closet behind the door. If you don't have the right one on the board, you go on, you waste your time.
Working principle:
1. The processor requests data to the address
A
.
2. Check L1: Found?
cache hit
~0.5 ns.
3. Not in L1? Checks L2. No? L3. No?
cache miss
Let's go to the OZU.
4. Data are downloaded from OZN to L3 ~ L2 ~L1
Cacheline
(64 bytes at once)
5. The next access to neighbouring addresses is already cache hit!
05
Cache Simulator (direct display)
Direct-mapped cache:
The line is defined by the formula:
строка = адрес mod N
where N is the number of rows of caches.
⚡
Simulator: direct-capped cache (8 lines)
The processor turns to the addresses. See: hit (green) or misse (red).
Cache status (8 rows):
Address sequence:
Press Start to start simulation.
Returns
0
Hit
0
Miss
0
Hit rate
—
Self-checking Job:
Change sequence to
0,8,0,8,0,8
And start. Why hit rate = 0%?
cache thrashing
.
06
Mini test
🧠
Mini-test: 5 questions