Name
Abstract | ||
|---|---|---|
On-chip cache is often shared between processes that run concurrently on different cores of the same processor. Resource contention of this type causes performance degradation to the co-running processes. Contention-aware co-scheduling refers to the class of scheduling techniques to reduce the performance degradation. Most existing contention-aware co-schedulers only consider serial jobs. However, there often exist both parallel and serial jobs in computing systems. In this paper, the problem of co-scheduling a mix of serial and parallel jobs is modelled as an Integer Programming (IP) problem. Then the existing IP solver can be used to find the optimal co-scheduling solution that minimizes the performance degradation. However, we find that the IP-based method incurs high time overhead and can only be used to solve small-scale problems. Therefore, a graph-based method is also proposed in this paper to tackle this problem. We construct a co-scheduling graph to represent the co-scheduling problem and model the problem of finding the optimal co-scheduling solution as the problem of finding the shortest valid path in the co-scheduling graph. A heuristic A*-search algorithm (HA*) is then developed to find the near-optimal solutions efficiently. The extensive experiments have been conducted to verify the effectiveness and efficiency of the proposed methods. The experimental results show that compared with the IP-based method, HA* is able to find the near-optimal solutions with much less time. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/ICPP.2015.31 | ICPP |
Keywords | Field | DocType |
HA* search method,heuristic A*-search algorithm,graph-based method,small-scale problems,small-scale method,IP-based method,optimal coscheduling solution,integer programming problem,computing systems,contention-aware coscheduling,performance degradation,resource contention,on-chip cache,multicore processors | Heuristic,Co scheduling,Cache,Scheduling (computing),Computer science,Parallel computing,Integer programming,Linear programming,Solver,Multi-core processor,Distributed computing | Conference |
ISSN | Citations | PageRank |
0190-3918 | 1 | 0.35 |
References | Authors | |
19 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Huanzhou Zhu | 1 | 11 | 2.19 |
| Ligang He | 2 | 542 | 56.73 |
| Bo Gao | 3 | 36 | 5.68 |
| Kenli Li | 4 | 1389 | 124.28 |
| Jianhua Sun | 5 | 192 | 25.27 |
| Hao Chen 0002 | 6 | 4 | 0.73 |
| Keqin Li | 7 | 2778 | 242.13 |