Effects of topology-aware allocation policies on scheduling performance

Abstract. This paper studies the influence that job placement may have on scheduling performance, in the context of massively parallel comput-ing systems. A simulation-based performance study is carried out, using workloads extracted from real systems logs. The starting point is a par-allel system built around a k-ary n-tree network and using well-known scheduling algorithms (FCFS and backfilling). We incorporate an alloca-tion policy that tries to assign to each job a contiguous network partition, in order to improve communication performance. This policy results in severe scheduling inefficiency due to increased system fragmentation. A relaxed version of it, which we call quasi-contiguous allocation, reduces this adverse effect. Experiments show that, in those cases where the ex-ploitation of communication locality results in an effective reduction of application execution time, the achieved gains more than compensates the scheduling inefficiency, therefore resulting in better overall perfor-mance.