HD-CPS: Hardware-assisted Drift-aware Concurrent Priority Scheduler for Shared Memory Multicores
Mohsin Shan, Omer Khan · 2022
Efficiently exploiting parallelism remains a challenging problem in multicore processors. For many algorithms, executing tasks in some priority order results in a work-efficient execution. However, searching high-priority tasks requires communication that hampers performance. A concurrent priority scheduler (CPS) selects high-priority tasks and schedules them on different cores. Modern CPS designs offer various strategies to select high-priority tasks at low communication cost for improved performance. However, they do not explicitly track the priority of tasks and cannot adjust task distribution if the cores are processing low-priority tasks. Moreover, they cannot estimate the right amount of communication required to select high-priority tasks. This paper critically observes that the cores’ priority drift can be quantified and used for better performance. A novel CPS design, HD-CPS is proposed to use priority as a signal to optimize drift and communication at runtime. Furthermore, compute-intensive task transfer and processing aspects of the CPS are offloaded to per-core local hardware at a low cost to enhance performance. HD-CPS is shown to consistently improve performance over several state-of-the-art software-based and hardware-assisted CPS designs. With hardware-assist, it approaches near-linear performance scaling as a function of core counts for large shared-memory multicores.