CLUSTERED AFFINITY SCHEDULING ON LARGE-SCALE NUMA MULTIPROCESSORS

Modern shared-memory multiprocessors have high and non-uniform memory access (NUMA) costs. The communication cost gradually dominates the so urce of parallel applications' execution. Algorithms based on affinity , like affinity scheduling algorithm (AFS), perform better than dynami c 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 wr ites to the queues for migrating iterations, and the time in loading d ata into cache. In this paper, we propose a new loop scheduling algori thm, clustered affinity scheduling (CAFS), to improve affinity schedul ing algorithm. We distribute the processors into several clusters, and cluster-based migrations are carried on when imbalance occurs. We con firm 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 appl ications. CAFS also improves the cache hit ratios, and balances the wo rkload. Therefore, we conclude that under large NUMA multiprocessor, C AFS is a better choice among loop scheduling algorithms. (C) 1997 Else vier Science Inc.