Veljko Milutinovic
CAC:
Understanding the Essence
Caching and Cache Hierarchy
…the problem is not technology, but economics.
Figure CACU1:
On-chip cache (source: [Tanenbaum90])Legend:
CAC—Cache and cache hierarchy.
|
Address |
|
Block # |
Valid |
Block # |
Value |
|
|
0 |
|
0 |
1 |
0 |
137 |
|
|
|
137 |
|
1 |
600 |
2131 |
½ |
|
|
|
|
1 |
2 |
1410 |
½ |
|
4 |
|
1 |
0 |
|
|
½ |
|
|
52 |
|
1 |
160248 |
290380 |
1K lines |
|
|
|
|
0 |
|
|
½ |
|
8 |
|
2 |
|
|
|
½ |
|
|
1410 |
|
M |
M |
M |
½ |
|
|
|
|
|
|
|
¯ |
|
12 |
|
3 |
¬ 1 bit® |
¬ ¾ 22 bits¾ ® |
¬ ¾ 32 bits¾ ® |
|
|
|
635 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
4 |
|
|
|
|
|
|
M |
|
|
|
|
|
|
224 |
|
|
|
|
|
|
Figure CACU2:
An associative cache with 1024 lines and 4-byte blocksLegend: Self-explanatory.
|
|
Entry 0 6 4 4 7 4 4 8 |
Entry 1 6 4 4 7 4 4 8 |
L |
Entry (n - 1)6 4 4 7 4 4 8 |
||||||
|
Line |
|
|
|
Valid |
Tag |
Value |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
M |
M |
M |
M |
M |
M |
M |
M |
M |
M |
|
|
|
|
|
|
|
|
|
|
|
|
Figure CACU3:
A set-associative cache with n entries per line (source: [Tanenbaum90])Legend: Self-explanatory.
|
Line |
Valid |
Tag |
Value |
Addresses that use this line: |
|
0 |
1 |
2 |
12130 |
0, 4096, 8192, 12288, … |
|
1 |
1 |
1 |
170 |
4, 4100, 8196, 12292, … |
|
2 |
1 |
3 |
2142 |
8, 4104, 8200, 12296, … |
|
3 |
0 |
|
|
12, 4108, 8204, 12300, … |
|
4 |
0 |
|
|
16, 4112, 8208, 12304, … |
|
5 |
0 |
|
|
20, 4116, 8212, 12308, … |
|
M |
M |
M |
M |
|
|
1023 |
1 |
|
|
4092, 8188, 12284, … |
|
|
12 |
10 |
2 |
|
Address bits |
Tag |
Line |
00 |
Figure CACU4:
A direct-mapped cache with 1024 4-byte lines and a 24-bit addressLegend: Self-explanatory.
Reference:
[Tanenbaum90] Tanenbaum, A. S.,
Structured Computer Organization,
Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1990.
Veljko Milutinovic
CAC:
State of the Art
Using Pointers to Page Numbers
…to minimize tag size of on-chip caches.
|
AddressTag |
V |
Data |
Figure CACS1:
Structure of a cache line (source: [Seznec96])Legend:
V—Valid bit.
Figure CACS2:
Indirect-tagged VV cache; TLB serves as a PN-cache (source: [Seznec96])Legend:
VV—Virtually indexed, virtually tagged;
PN—Page number.
Figure CACS3:
Indirect-tagged VP cache with physical page numbers stored in the PN-cacheLegend:
VP—Virtually indexed, physically tagged;
PN—Page number.
Figure CACS4:
Indirect-tagged PP-cache (source: [Seznec96])Legend:
PP—Physically indexed, physically tagged;
PN—Page number.
Reference:
[Seznec96] Seznec, A., “Don’t use the page number, but a pointer to it,”
Proceedings of the ISCA-96, Philadelphia, Pennsylvania, USA, June 1996.
Veljko Milutinovic
CAC:
IFACT
A Spatial/Temporal Split Data Cache
Essence:
References:
[Milutinovic95] Milutinovic, V.,
“A New Cache Architecture Concept:
The Split Temporal/Spatial Cache Memory,”
UBG-ETF-TR-95-035,
Belgrade, Serbia, Yugoslavia, January 1995.
[Milutinovic96a] Milutinovic, V., Markovic, B., Tomasevic, M., Tremblay, M.,
“The Split Temporal/Spatial Cache Memory:
Initial Performance Analysis,”
Proceedings of the IEEE SCIzzL-5,
Santa Clara, California, USA, March 1996, pp. 63–69.
[Milutinovic96b] Milutinovic, V., Markovic, B., Tomasevic, M., Tremblay, M.,
“The Split Temporal/Spatial Cache Memory:
Initial Complexity Analysis,”
Proceedings of the IEEE SCIzzL-6,
Santa Clara, California, USA, September 1996, pp. 89–96.