Memory Hierarchy Design and Performance Modeling

Coherence

As data is copied across multiple levels, the system must ensure that all copies remain consistent. This is addressed through two types of coherence:

• Vertical Coherence: Ensures that updates made in a fast, upper level are eventually propagated to the slower, lower levels.
• Horizontal Coherence: In systems with multiple processors or multiple caches at the same level, horizontal coherence ensures that if one cache updates a piece of data, all other caches sharing that level are alerted to the change to prevent them from using stale data.

Exam Tip: When discussing coherence, remember that Vertical refers to the relationship between levels (e.g., L1 to Main Memory), while Horizontal refers to the relationship between peer components (e.g., Core 1's L1 to Core 2's L1).

Performance Modeling: Two-Level Systems

To evaluate a hierarchy, designers use mathematical models to predict how much time the processor will spend waiting for data. For a simple two-level system, the average system access time ($T_s$) is calculated based on the access time of the upper level ($T_1$), the access time of the lower level ($T_2$), and the hit ratio ($H$).

The hit ratio $H$ represents the fraction of memory references found in the first level ($M_1$). The formula is:

$$\begin{aligned} T_s &= T_1 + (1 - H) \times T_2 \end{aligned}$$

Access Efficiency

A critical metric for designers is access efficiency, which is the ratio of the upper-level access time to the total average access time:

$$\begin{aligned} \text{Efficiency} &= \frac{T_1}{T_s} \end{aligned}$$

If the latency gap between $T_1$ and $T_2$ is large, maintaining a very high hit ratio is essential to prevent the system performance from collapsing toward the speed of the slower memory.

Cost Modeling

Designers must also balance performance with cost. The average cost per bit ($C_s$) for a two-level system is a weighted average of the costs of the two levels ($C_1$ and $C_2$) and their respective sizes ($S_1$ and $S_2$):

$$\begin{aligned} C_s &= \frac{C_1 S_1 + C_2 S_2}{S_1 + S_2} \end{aligned}$$

An effective design ensures that $C_s \approx C_2$ by keeping the expensive, high-speed memory ($S_1$) significantly smaller than the cheap, high-capacity memory ($S_2$).

Multilevel Hierarchies

Modern architectures are far more complex than two-level systems. For example, the IBM z13 utilizes a sophisticated hierarchy including multiple cache levels (L1, L2, L3, and L4), main storage (DRAM), and secondary memory (disks).

In an $n$-level system, performance is modeled using conditional probabilities. Let $h_i$ be the probability that data is found in level $M_i$, given that it was not found in the previous level $M_{i-1}$. The total access time $T_s$ is minimized when the hit ratios at each level are maximized.

The hierarchy typically follows this progression:

1. Caches (L1, L2, L3, L4): Extremely fast, semiconductor-based memory located near or on the processor.
2. Main Storage (DRAM): Larger, slower semiconductor memory that holds the active working set of the operating system and applications.
3. Secondary Memory: Massive, non-volatile storage such as hard disks or SSDs used for long-term data retention.

By layering these technologies, designers can create systems that satisfy the competing requirements of high speed, massive capacity, and low cost.