Name
Title | ||
|---|---|---|
Analytical modeling and optimization for affinity based thread scheduling on multicore systems |
Abstract | ||
|---|---|---|
This paper proposes an analytical model to estimate the cost of running an affinity-based thread schedule on multicore systems. The model consists of three submodels to evaluate the cost of executing a thread schedule: an affinity-graph submodel, a memory hierarchy submodel, and a cost submodel that characterize programs, machines, and costs respectively. We applied the analytical model to both synthetic and real-world applications. The estimated cost accurately predicts which schedule will provide better performance. Due to the NP-hardness of the scheduling problem, we designed an approximation algorithm to compute near-optimal solutions. We have extended the algorithm to support threads with data dependences. We conducted experiments with a computational fluid dynamics (CFD) kernel and Cholesky factorization on both UMA SMP and NUMA DSM machines. The results show that using the optimized thread schedule can improve the program performance by 25% to 400%, demonstrating that our method for determining an optimized thread schedule for multicore systems is efficient and practical. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/CLUSTR.2009.5289173 | CLUSTER |
Keywords | Field | DocType |
numa dsm machines,optimisation,computational fluid dynamics kernel,processor scheduling,microprocessor chips,approximation theory,np-hardness,multicore systems,affinity based thread scheduling,memory hierarchy submodel,affinity-graph submodel,approximation algorithm,cholesky factorization,cost submodel,analytical modeling,graph theory,uma smp machine,scheduling problem | Kernel (linear algebra),Graph theory,Memory hierarchy,Job shop scheduling,Computer science,Parallel computing,Approximation theory,Real-time computing,Thread (computing),Computational fluid dynamics,Cholesky decomposition | Conference |
ISSN | ISBN | Citations |
1552-5244 E-ISBN : 978-1-4244-5012-1 | 978-1-4244-5012-1 | 10 |
PageRank | References | Authors |
0.66 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fengguang Song | 1 | 232 | 19.88 |
| Shirley Moore | 2 | 342 | 33.61 |
| Jack J. Dongarra | 3 | 17625 | 2615.79 |