Home | About | Projects | Academic | DVB-T | Contact

Learning Cache Replacement Policies using Register Automata

ESP: Aprendizaje de políticas de remplazo de la cache usando automatas con registro


Processors are a basic unit of the computer which accomplish the mission of processing data stored in the memory. Large memories are required to process a big amount of data. Not all data is required at the same time, few data is required faster than other. For this reason, the memory is structured in a hierarchy, from smaller and faster to bigger and slower. The cache memory is one of the fastest elements and closest to the processor in the memory hierarchy.

The processor design companies hides its characteristics, usually under a confidential documentation that can not be accessed by the software developers. One of the most important characteristics kept in secret in this documentation is the replacement policy. The most famous replacement policies are known but the hardware designers can apply modifications for performance, cost or design reasons.

The obfuscation of a part of the processor implies many developers to avoid problems with, for example, the runtime. If a task must be executed always in a certain time, the developer will take always the case requiring more time to execute (also called "Worst Case Execution Time") implying an underutilisation of the processor.

This project will be focused on a new method to represent and infer the replacement policy: modelling the replacement policies with automaton and using a learning process framework called LearnLib to guess them. This is not the first project trying to match the cache memory characteristics, actually a previous project is the basis to find a more general model to define the replacement policies.

The results of LearnLib are modelled as an automaton. In order to test the effectiveness of this framework, different replacement policies will be simulated and verified. To provide a interface with a real cache memories is developed a program called hwquery. This program will interface a real cache request for using it in Learnlib.

Uppsala University Library DiVA:
IT 13 089

Mid-Term Presentation:
PDF (104 KB)
PDF (159 KB)

Defence (157 KB)

Mid-Term Presentation:
PDF (104 KB)
PDF (159 KB)

Code of SimCache (JAVA)
Code of SimCache (Python)
Code of HwQuery (C)

List of LearnLib's logs:

FIFO2-Unf5 FIFO2-Unf7
FIFO3-Unf5 FIFO3-Unf7
FIFO4-Unf5 FIFO4-Unf7
FIFO5-Unf5 FIFO5-Unf7
LRU2-Unf5 LRU2-Unf7
LRU3-Unf5 LRU3-Unf7
LRU4-Unf5 LRU4-Unf7
LRU5-Unf5 LRU5-Unf7
PLRU2-Unf5 PLRU2-Unf7
PLRU4-Unf5 PLRU4-Unf7
MRU2-Unf5 MRU2-Unf7
MRU3-Unf5 MRU3-Unf7
MRU4-Unf5 MRU4-Unf7
MRU5-Unf5 MRU5-Unf7

Valid HTML 4.01 Strict

Licencia Creative Commons