Origin:

Why do we need cache in the first place?

Keep in mind: all we care about is speed.

For the CPU to work on some data, that data has to be available to it. And if the data isn’t already in memory, we have to fetch it from secondary storage.

Now, fetching something from a disk is painfully slow compared to what a CPU can do.

A rough idea:

• SSD: ~10–100 μs
• HDD: ~5–20 ms

To put that into perspective, even 50 ns RAM access is 100,000× faster than a 5 ms HDD access.

But wait—we forgot about the CPU.

Suppose we have a 3 GHz processor and, just for simplicity, assume one operation can be completed per clock cycle.

A 3 GHz CPU has:

1 cycle ≈ 0.33 ns

That means the CPU has the potential to execute roughly:

3 × 10⁹ cycles per second

That’s 3 billion cycles every second.

Now imagine the CPU needs data that is sitting in RAM.

Typical DRAM access can be on the order of tens of nanoseconds—say 50–100 ns.

At 3 GHz:

50 ns ≈ 150 CPU cycles

So the CPU could potentially spend hundreds of cycles waiting for a single memory access.

That’s absurd.

The CPU is ready to compute.

The data isn’t.

So we need an even faster way to access frequently used data.

And that’s where cache memory enters the picture.

What makes cache faster?

• Memory technology – uses 4 or 6 transistors(a flip-flop loop) and there is no physical delay, compared to DRAM( capacitor lag)
• Physical distance from CPU – even though speed of signal = speed of light, proximity matters
• Larger memories – require more storage cells, longer wires, larger structures and potentially more complex access circuitry. These increase area, energy and often access latency.
  

How it works?

Now, whenever the CPU wants to compute something, it needs data.

Naturally, we want the best of both worlds:

Huge capacity + blazing-fast access.

Hmm… greedy!

Unfortunately, hardware doesn’t work that way.

The closer a memory is to the CPU and the faster we want it to respond, the more expensive it becomes in terms of area, power, complexity, and design constraints.

So why not just make the register file enormous?

Why not have huge register files?

Registers are the fastest storage available to the CPU. So why not simply put a massive amount of data there?

There are several problems.

First, as the register file grows, the circuitry required to access it becomes larger and more complex.

But there’s an even bigger problem:

Registers need to support multiple operations in the same clock cycle.

Consider:

A + B = C

The processor needs to:

1. Read A
2. Read B
3. Perform the addition
4. Write the result to C

In a naive sequential implementation, these could happen across multiple cycles.

But modern processors want these register accesses to happen in parallel within a clock cycle.

So the register file needs multiple read ports and write ports.

These ports require additional wiring and circuitry throughout the register file.

As the number of registers (N) and the number of ports (P) increase, the hardware complexity and area increase significantly.

Each register cell also needs access circuitry connected through structures such as wordlines and bitlines:

• Wordline: selects which register/storage location is being accessed.
• Bitlines: carry the data being read or written.

So increasing the number of registers doesn’t simply mean adding more storage.

It means adding more circuitry, more wiring, and more physical area.

And that creates another problem.

Power and heat.

A larger, heavily multiported register file consumes more power, and that power eventually becomes heat. At high performance levels, that means more demanding thermal management.

Like registers, cache is designed to be fast—but it is allowed to be larger, because it doesn’t have exactly the same access requirements as a register file.

However, the same fundamental principle still applies:

As the cache gets larger, maintaining extremely low access latency becomes harder.

Larger caches require more storage cells, more wiring, and larger access structures. Eventually, increasing cache capacity starts costing us latency, area, and power.

Numbers time:

command: <exec> n no_of_runs
operation: addition of n*n array elements(used vector<vector<long long>>)

By the way, tiling(block) size is 32

1. Cache locality:
Row-wise traversal is approximately 3.5× faster than column-wise traversal for the vector<vector<long long>> representation.

2. Cache blocking:
Tiling reduces column-wise execution time from approximately 1.35 s to 0.65 s, giving about 2.08× speedup.

3. Tiling overhead:
Applying tiling to the already cache-friendly row-wise traversal increases execution time from approximately 385 ms to 539 ms, showing that blocking is not universally beneficial.

Other points worth considering..

4. Thread-level parallelism:
Increasing threads reduces execution time substantially up to approximately 6 threads.

5. Thread saturation:
The best observed result is 118.5 ms at 6 threads, corresponding to approximately 3.4× speedup over the 1-thread parallel implementation. Increasing to 7–8 threads provides no further benefit.