A “Least Recently Used Updater” circuit (LRU), which is used in page replacement of memory management. Done in SystemC
Page replacement is a widely used approach in memory management. The idea is simple: the main memory cannot hold all the referred pages in memory. So whenever a new page is referenced, an existing page is replaced by the page that was newly called. The goal of any page replacement mechanism is to minimize the number of page faults.
We have sixteen pages with tags from 0 to 15 (0 is the most recently used and 15 is the least recently used). The tag of each page is defined using a 4-bit binary number that are kept in a Memory. As shown in figure 1, the Memory needs a 4-bit address bus and two 4-bit data buses. NewPageBus input provides the ID of the current page that has just been accessed. A pulse on the completed input shows that the page access has been completed and the LRU memory needs to be updated. All pages with lower tag than the tag of the recently accessed page must increment theirtag by one.
To do this, this module examines all entries of the memory one by one and increments tags
that are lower than that of the current page. The entry that corresponds to the current page will
be set to zero indicating this page is the most recently used. Other entries that have higher tag
values will be kept intact. After updating the Memory, the output free signal becomes one. (as
an example see figure 2)
The DataPath and Controller of this circuit are as follows:
They are Implimented and tested using SystemC, which can be seen in the LRU_RTLSystemC directory as LRU_DP ans LRU_CP the modules used in them, like the incrementer and subtractor are also Implimented and have their own respective .h files in the LRU_RTLSystemC directory.
this circuit was tested in the main.cpp file using a SystemC test bench which is found in the main Directory as LRU_TB
the VCD output waveform for 7 put on the NewPageBus is as follows:
**There's also a difrent design and Implimentation of this LRU, in which updating is completed in one clock cycle. It uses shift registers with enable input and comparators. Each register stores the page number and has a fixed tag which is from 0 to 15 (0 is MRU and 15 is LRU). This circuit has two inputs named NewPageBus and completed and no output.
The functional SystemC description of this LRU Updater is written and can be found in LRU_BusFunctionalSystemC directory. The result of it's simulation is as follows:
