Principle of locality (temporal - spatial): Foundations

5.4.1 · D1 · Hardware › Memory Hierarchy & Caches › Principle of locality (temporal - spatial)

Yeh page assume karta hai ki tumne pahle almost kuch nahi dekha. Isse pahle ki tum parent note locality ke baare mein padh sako, humein uske har word ko earn karna hoga: address, memory location, access, reference, cache, block, hit/miss, reuse distance, stride, aur woh arithmetic notation ke bits ( $A_{i}$ , $∣ \cdot ∣$ , $⌈ \cdot ⌉$ , $\sum$ , $P (\cdot)$ ) jis par woh rely karta hai. Hum inhe bilkul usi order mein build karenge jis order mein yeh ek dusre par depend karte hain.

1. Memory ek lambi street ki tarah hai numbered boxes ke saath

Sab kuch yahan se shuru hota hai. Circuits bhool jao — ek bahut lambi street imagine karo jisme identical boxes ek row mein hain. Har box ek chhota number hold karta hai. Har box par ek permanent house-number paint kiya hua hai.

Figure — Principle of locality (temporal - spatial)

Figure mein drawn ek subtle lekin vital point: consecutive addresses physically side by side hote hain. Address $0 x 1004$ bilkul $0 x 1000$ ke daayein wala box hai. "Number mein close" ka matlab hai space mein close. Yeh yaad rakho — yeh spatial locality ka poora engine hai.

Recall

Ek memory location vs. ek address ::: Location woh box hai (physical slot); address uس par paint kiya hua number hai.

2. Ek box ko Access aur Reference karna

Parent ek program ki baat karta hai jo accesses ki ek sequence karta hai. Ek stream of tickets imagine karo, ek per access, har ek par us address ka stamp jise touch kiya gaya:

$A_{1}, A_{2}, A_{3}, \dots$

3. List ke baare mein do sawaal — aur woh symbols jo jawab dete hain

Parent note locality ke har flavour ko ek tiny formula mein squeeze karta hai. Har formula list $A_{1}, A_{2}, \dots$ ke baare mein ek sawaal hai. Pehle arithmetic earn karte hain.

3a. Do numbers ke beech distance: absolute value $∣ \cdot ∣$

Topic ko yeh kyun chahiye? Do consecutive addresses ke beech ki doori measure karne ke liye:

$Stride = ∣ A_{i + 1} - A_{i} ∣$

Yahan $A_{i + 1} - A_{i}$ hai "agla box number minus yeh box number." Agar program aage step kiya to difference positive hai; agar woh peeche jump kiya to negative hai. Hum sirf jump kitna bada tha care karte hain, uski direction nahi — isliye hum ise $∣ \cdot ∣$ mein wrap karte hain.

Recall

Stride formula mein absolute value kyun ::: Ek backward step ( $A_{i + 1} < A_{i}$ ) ek negative difference deta hai, lekin hum sirf distance care karte hain jump ki, isliye hum sign strip karte hain.

3b. Distinct visitors count karna: reuse distance

Topic is counting job ko ek naam se likhta hai; "do markers ke beech unique items count karo" ki machinery wahi hai jo parent ke formula ka matlab hai. Koi naya symbol nahi — bas word "count."

4. Word-vs-byte ka trap, aur blocks kyun exist karte hain

5. Kuch aur notation gadgets jo parent use karta hai

6. Yeh sab topic ko kaise feed karta hai

Jab yeh foundations in place ho jaayein to tum Cache organization fundamentals aur Cache mapping strategies (shelf kaise arrange hai) ke liye ready ho, Working set model (use mein chhote portion ko formalise karna), aur Loop blocking and tiling (bad-stride matrix case fix karna). Baad mein, Virtual memory locality ko ek coarser page grain par reuse karta hai.

Equipment checklist

Self-test: kya tum aage badhne se pahle har ek ka jawab de sakte ho?

Ek memory location aur uske address mein kya fark hai?

Location woh physical box hai; address usse label karne wala number hai.

A_{i}

ka kya matlab hai, aur iska kya matlab nahi hai?

i

-th access dwara touch kiya gaya address; yeh

A

times

i

NAHI hai.

Stride formula mein absolute value

∣ A_{i + 1} - A_{i} ∣

kyun use hota hai?

Hum jump ka size chahte hain, uski direction nahi, isliye hum sign discard karte hain.

Reuse distance ko ek sentence mein define karo.

Same address ke do touches ke beech access kiye gaye distinct addresses ki count.

Array stride 4 bytes kyun hai jab hum ek element at a time step karte hain?

Ek int word 4 bytes ka hota hai, isliye agla element 4 addresses aage hota hai.

Ek cache block kya karta hai jo spatial locality ko useful banata hai?

Yeh ek fetch mein padosi boxes ki ek contiguous run scoop karta hai, isliye nearby baad ke accesses free hits hote hain.

Ek hit aur ek miss mein kya fark hai?

Ek hit box ko fast shelf par already paata hai; ek miss ko slow memory se uska poora block fetch karna padta hai.

⌈ 1000/16 ⌉ = 63

kyun hai aur

62

nahi?

8 baaki bache accesses ko bhi ek aur fetch chahiye; tum round up karte ho kyunki partial miss nahi ho sakta.

P (hit) = 0.9

tumhe kya batata hai?

Har 10 accesses mein se 9 cache se serve hote hain.