Cache coloring problem

In multi core systems, the last level of cache (LLC) is a source of  unpredictability for real time systems. In figure 1  a task T1 running on core C1 and a task T2 running on core 2. If both the tasks access memory regions M1, M2 and M3, M4 respectively such that these memory regions map to the same cache set, then they will keep conflicting with each other and evicting each other repeatedly, assuming the cache implements a LRU/ PLRU replacement policy.

Caches can be managed predictability by using a coloring technique in which the physical pages are colored such that no two pages with the same color map to the same cache set. In other words, two differently colored physical pages will never map to the same cache set.

TLB coloring problem

Translation look aside buffer ( TLB) is another source of unpredictability for real time systems. Figure 2 shows a 2 way set associative TLB with 4 sets. If two tasks T1 and T2 running on the same core request memory from malloc, malloc could return virtual addresses such that they map to the same TLB set, causing the tasks to replace each other's page mappings in the TLB.

TLB coloring can be used to allocate the TLB in a predictable manner.  In this method, virtual pages are colored such that no two differently colored virtual pages map to the same TLB set.

Combined problem of TLB and cache coloring

In this project, our focus is on solving both the TLB conflicts and cache conflicts as a whole. Cache coloring has been developed by the group at University of North Carolina at Chapel Hill (UNC) while the TLB coloring has been developed by North Carolina State University( NCSU). The focus of this work is to port the cache coloring onto ARM architecture, port the tlb coloring on ARM architecture and then combine the two to get a solution which solves both the problems.