Mathematical optimization of multi-level cache allocation using calculus and Python — derives minimum memory access time through symbolic differentiation, numerical solving, and visualization. Cache Optimization — Minimizing Memory Access Time in a Multi-Level Cache System
This project applies calculus and Python to solve a real computer architecture problem: how to allocate cache capacity across L1 and L2 to minimize total memory access time. The solution combines symbolic mathematical derivation with numerical Python verification and graphical analysis.
The Problem
Modern processors use a memory hierarchy where L1 cache is fastest and smallest, L2 is larger but slower, and main memory is the slowest of all. Deciding how much capacity to give each level directly affects how fast a processor can access data. This project models that decision mathematically and finds the optimal allocation.
The Mathematical Model
The total memory access time is modeled as:
T(S1, S2) = h1 * t1 + (1 - h1) * h2 * t2 + (1 - h1) * (1 - h2) * t_mem
where hit rates are exponential functions of cache size:
h1(S1) = 1 - e^(-k1 * S1) h2(S2) = 1 - e^(-k2 * S2)
Using the constraint S1 + S2 = S_total, the two-variable problem reduces to a single-variable function T(S1), which is then differentiated and solved for its minimum.
What the Code Does
The Python implementation uses SymPy for symbolic definition and simplification of the full access time expression. It computes the derivative dT/dS1 symbolically and solves for critical points. A numerical optimizer then finds the S1 value that minimizes T(S1) for a given set of parameters. The code also plots T(S1) versus S1 and the hit rate curves h1 and h2 to visually confirm where the minimum occurs.
Parameters used for numerical analysis: t1 = 1 ns, t2 = 5 ns, t_mem = 100 ns, k1 = 0.05, k2 = 0.01, S_total = 64 KB.
Key Finding
The derivative analysis shows the function is monotonically decreasing across the feasible range, meaning the minimum access time occurs at the boundary S1 = S_total = 64 KB. The numerical verification confirms this: T(20) is approximately 24.98 ns while T(64) is approximately 5.04 ns. Manual derivation and Python computation produced consistent results.
Stack
Python, SymPy, NumPy, Matplotlib, SciPy
Stack: Python
.gitignore
2b.py
3b.py
4a.py
5a.py
6a.py
7a.py
Calculus Project.pdf
Project Report.docx
README.md