Cache replacement algorithm using hierarchical allocation scheduling

Cache management has become one of the most popular areas of research in improving the performance of computation. Cache memory is the nearest block of storage between the main memory and the processor. Caches are very fast but have a small memory storage size; therefore only selected instructions or data are to be kept in cache memory. A cache management or also known as a cache replacement policy is a mechanism to manage the process of selecting, keeping, replacing, or evicting the instruction inside cache memory. It is important to determine instructions that need to be kept (or not to be evicted) in order to avoid any disruption for future processes. Therefore, this research is an effort of developing a conceptual model of the cache replacement policy. Predicting a relative important instruction in cache replacement policy can improve the cache performance. The predicted instruction will have the highest priority to be kept in cache memory for future use. Therefore, latency between the processor and memory can be reduced. The existing cache replacement (i.e. least recently used (LRU)) algorithm depends on usage of the data being referenced. Data that are least referenced will be removed during cache replacement if the cache is already full. There is no determination of relative important instruction in this policy. By removing this, based on the least recent, it might cause a potential delay in the future processing if the removed instruction depends on it. To alleviate this limitation, the Hierarchical Allocation Scheduling (HAS) model is proposed in this research. HAS is to schedule the instructions based on the priority of instructions from the aspect of space and time. The core principle is to keep the relatively important instruction in cache memory from being evicted. The development of the HAS model is based on the idea of hierarchical temporal memory (HTM) developed by Numenta Inc. HTM is an approach in which the scheduling is derived on priority and similarity of instruction from the aspect of space and time. The implementation of the HAS model is developed using the OCTAVE software. A simulation of the model is performed to analyse its behaviour in a hypothetical cache management scenario. Specifically, the goal of the experimentation is to study the situation in which the HAS model can accurately predict a single instruction with the highest relative importance. Analyses indicate that it is the most single instruction occurrence when the data range (D) is defined as being between 0 to 9 and the window size (k) is fixed at 10. This only contributes to the simulated behaviour of the model regardless to its actual implementation in the cache replacement policy