Clustered affinity scheduling on large-scale NUMA multiprocessors

Abstract

Modern shared-memory multiprocessors have high and non-uniform memory access (NUMA) costs. The communication cost gradually dominates the source of parallel applications' execution. Algorithms based on affinity, like affinity scheduling algorithm (AFS), perform better than dynamic algorithms, such as guided self-scheduling (GSS) and trapezoid self-scheduling (TSS). However, as the number of processors increases, AFS suffers heavy overheads for migrating workload. The overheads include remote reads to the queues for the indices information, synchronous writes to the queues for migrating iterations, and the time in loading data into cache. In this paper, we propose a new loop scheduling algorithm, clustered affinity scheduling (CAFS), to improve affinity scheduling algorithm. We distribute the processors into several clusters, and cluster-based migrations are carried on when imbalance occurs. We confirm our idea by running many applications under a realistic hierarchy memory simulator. Our results show that CAFS reduces at least 1/3 of both remote reads and synchronous writes to the queues under most applications. CAFS also improves the cache hit ratios, and balances the workload. Therefore, we conclude that under large NUMA multiprocessor, CAFS is a better choice among loop scheduling algorithms. (C) 1997 Elsevier Science Inc.