Dynamic cache partitioning and adaptive cache replacement schemes for chip multiprocessors.

Abstract

One of the dominant approaches towards implementing fast and high performance computer architectures is the Chip Multi Processor (CMP), in which the design of the memory hierarchy has a critical effect on performance. Performance can be improved by the use of a shared cache on the chip, but it is a matter of ongoing research as to how each processor can gain the greatest advantage from the cache without affecting the performance of other processors. Moreover, power is a critical issue in CMP design. Cache replacement policies and cache partitioning schemes have been investigated and proven able to enhance shared cache management. However, it is still desirable to have an optimal replacement policy that can retain useful data as long as possible to minimise miss rate and not degrade performance in a partitioned shared cache. Many of the metrics that have led to innovations in various partitioning schemes have increased the complexity of the partitioning strategies and the hardware overhead. There is scope for more work in achieving the right balance between power consumption and performance improvement in the CMP. This thesis investigates the effects of the cache replacement policy in a partitioned shared cache. The goal is to quantify whether a better power/performance trade-off can be achieved by using less complex replacement strategies. A Middle Insertion 2 Positions Promotion (MI2PP) policy is proposed to eliminate cache misses that could adversely affect the access patterns and the throughput of the processors in the system. The insertion, promotion and eviction strategies of the replacement policy are investigated and modified to improve shared cache utilisation by the competing processors. The MI2PP policy employs a static predefined insertion point, near distance promotion and the concept of ownership in the eviction policy to avoid resource stealing among the processors. With these strategies, the performance of the shared cache and the overall system were enhanced and the miss rate showed significant improvement over the Least Recently Used (LRU) policy. While existing cache partitioning schemes use a variety of performance metrics to allocate the cache for each competing processor, most of the schemes focus only on one metric in their partitioning algorithm. An Adaptive Cycles per Instruction (CPI)-based Cache Partitioning (ACCP) scheme is introduced to investigate the efficiency of using two metrics to optimise partitioning decisions and to study the trade-offs between the complexity of using more performance metrics in partition decision-making and additional hardware cost. The analysis performed on ACCP showed that the performance of the processors was improved compared to the existing CPI-based partitioning scheme introduced by Muralidhara et al. [2010], which uses only one of the performance metrics employed in ACCP. Evaluation on a more complex scheme, namely the Utility Cache Partitioning (UCP) scheme demonstrated that the ACCP on average achieved similar performance although the ACCP is simpler to implement. The low hardware overhead incurred by ACCP showed that it is superior to UCP. ACCP demonstrates that the complexity of the partitioning mechanism and hardware cost could be reduced without degrading the overall system performance.