Locality-information-based scheduling in shared-memory multiprocessors

Abstract

Lightweight threads have become a common abstraction in the field of programming languages and operating systems. This paper examines the performance implications of locality information usage in thread scheduling algorithms for scalable shared-memory multiprocessors. The elements of a distributed scheduler using all available locality information as well as experimental measurements are presented.

Most shared-memory multiprocessors use multiple stages of caches to hide latency. Data structures and policies of a scheduling architecture have to reflect the various levels of the memory hierarchy in order to achieve high data locality. Per-processor data structures avoid lock contention and help to reduce memory traffic. While CPU utilization of processes still determines scheduling decisions of contemporary schedulers, we propose novel scheduling policies based on cache miss rates and information about synchronization. All data gathered at runtime are transformed into affinity values inside a metric space, so that threads migrate near to their (sub)optimal operation points defined by location and timing of execution. The distribution of data structures and the usage of locality information characterizes the proposed memory-conscious scheduling architecture. A prototype implementation shows that a locality-conscious scheduler outperforms centralized and distributed approaches ignoring locality information.