Time-Based Least Memory Intensive Scheduling

In the modern chip-multiprocessor system, main memory is a shared resource among multiple concurrently executing threads/applications. The memory scheduling algorithms are developed to resolve memory contention by arbitrating memory access in such a way that competing threads progress at a relatively fast and even pace, resulting in high system throughput and fairness. This paper presents a new memory scheduling algorithm called Time-Based Least Memory Intensive scheduling (TB-LMI) that addresses system throughput and fairness with the goal of achieving a better throughput and limiting the unfairness. The main idea is to prioritize threads according to their memory contentions every pre-defined period of cycles to improve system throughput and to guarantee fairness. We evaluate TB-LMI on a variety of multi-programmed workloads with different queue sizes of memory controllers and compare its performance to four previously proposed scheduling algorithms. TB-LMI achieves the best system throughput and fairness. On 8-core system, TB-LMI improves system throughput and fairness on average by 4.22% and 11.7% respectively compared to Thread Cluster Memory scheduling (TCM) (previous work providing the best system throughput and fairness). Our newly proposed technique adds negligible area and logic overhead to the Memory Controller compared to the benefits on the system performance.