EECS Publication
Analytical Modeling for Affinity-Based Thread Scheduling on Multicore Platforms
Fengguang Song, Shirley Moore, and Jack Dongarra
This paper proposes an analytical model to estimate the cost of running an affinity-based thread schedule on multi-core shared-memory systems. This model considers a memory architecture as a generic tree structure and allows for a portable, architecture-aware optimization framework to find an optimized schedule for multi-threaded programs. It consists of three submodels in order to measure the cost of executing a thread schedule: affinity graph model, memory hierarchy model, and a cost model that characterize machines, programs, and costs respectively. With the aid of the model, we formalize the problem of finding the best thread schedule as an optimization problem. Due to the NP-hardness of the problem, we designed a hierarchical graph partitioning algorithm to compute an approximate solution. We then extended the algorithm to support threads with data dependencies (i.e., DAGs). The algorithm has been implemented in a feedback-directed optimization framework and applied to two real-world scientific applications: a Computational Fluid Dynamics (CFD) kernel and Cholesky factorization. We conducted our experiments on both SMP and DSM machines. The results show that our analytical model is accurate enough, and using the optimized thread schedule improves the program performance by 25% to 4 times, demonstrating that our method is efficient and practical.
Published 2008-08-12 04:00:00 as ut-cs-08-626 (ID:101)