面向多核处理器系统的Cache感知调度算法

A Cache-aware Scheduling Algorithm on Multicore Systems

Cache空间的不公平使用和争用直接影响系统的整体性能,现有Linux操作系统的默认调度算法不能感知程序的行为,包括访问cache的失效次数,不了解线程之间访存模式和频度上可能存在的差异,因而无法做出更加合理的调度.本文提出并在Linux环境下实现了一种Cache感知的调度算法CAS,通过监测每个任务每千条指令的共享cache失效次数,把cache失效次数相近的任务聚合到同一个核上,使得cache失效次数差异较大的任务运行在不同的核上,避免了cache失效次数都很大的任务在不同的核上同时运行,从而减小了cache空间的不公平使用和争用.实验表明,CAS算法在大多数情况下,减少了整个负载的共享cache失效次数,提高系统的平均吞吐量约5%左右.

The unfair utilization and contention on cache space impose a significant influence on system performance. Current default Linux operating system scheduling algorithm lacks the awareness of program behavior including cache miss rate, instructions retired etc. Therefore it can not learn about the differences of memory access pattern and frequency between different tasks. This paper pro- poses and implements a cache-aware scheduling algorithm called CAS. CAS analyzes the cache miss rate of different tasks and desig- nated tasks with similar cache miss rate to the same core. Tasks with different cache miss rate will run on different cores and hence it is impossible to run simultaneously for two tasks with same cache miss rate, thereby reducing cache space unfair utilization and cont- ention. Experimental results show the algorithm CAS can reduce total cache miss of the whole workload and improve system through- put up to 5 % on the average in most cases.