On-Chip Democracy: A Study on the Use of Voting Systems for Computer Cache Memory Management

In computer architecture, memory management is required to optimize data accesses by the processor(s). Therefore, cache replacement policies, such as LRU, FIFO, etc., have been developed. These standalone policies optimize for a single access attribute, limiting their impact for applications with non-uniform behaviors. In this work, we propose a preliminary study on the use of voting systems for computer memory management, with a Hybrid Voting-based Eviction policy (HyVE). HyVE combines existing policies by taking their individual ranking of the eviction candidates and uses a voting system to select the evicted data. The Borda count and the Condorcet method are applied, and we analyze how their properties regarding Arrow’s axioms of democracy affect the results. Simulations show that HyVE/Borda consistently performs better than its constituent standalone policies, improving cache performance by 3% compared to LRU on average. Compared to the Borda count, we observe that the Condorcet method performance falls short in this computer memory context, although respecting the Condorcet criterion. This can be explained by the small number of voters involved, which seems to be compensated by Borda’s point system.