M.Sc Thesis

M.Sc StudentShomar Bishara
SubjectFragmented Line Caches
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROFESSOR EMERITUS Jacob Katzenelson


Cache memory designers tend to enlarge the cache line size in order to exploit the data locality thus decreasing the cache misses. However, We found out that data caches with typical cache line sizes, i.e., 32 bytes or 64 bytes, accesses less than half of the data brought to a cache line before evicting it. Moreover, using longer cache lines, i.e., 128 or 256 bytes, decreases the percentage of the accessed fetched data to less than 30%.

This work presents a new structure of the cache, which is composed out of two types of cache-lines: the “traditional” cache line, we term long line, and a new cache line we term fragmented line. The fragmented line uses as much as half of the long line data area but the same tag size as the long line. Furthermore, the fragmented line stores only fractions of a long line termed sub lines; hopefully these are the fractions that the program needs. The new structures of the cache aim to use long lines for memory regions that exhibit high spatial locality, and fragmented lines for memory regions that exhibit low spatial locality. We introduce three novel cache structures: (1) Fully Fragmented Cache where all the cache lines are fragmented lines. (2) Static Fragmented Combined Cache where each set of the cache has a fixed number of fragmented and long cache lines. (3) Dynamic Fragmented Combined Cache where each set has a number of fragmented line pairs and each pair can dynamically be treated as one long line or two fragmented lines. The later two caches have the ability to change the cache line type according to the program run time behavior. The last scheme was found to be the best among other schemes since it increases the performance by 6% and it reduces the bus traffic by 20%-30% as compared to the unmodified cache.