Abstract
It is common that multiple cores reside on the same chip and share the on-chip cache. As a result, resource sharing can cause performance degradation of co-running jobs. Job co-scheduling is a technique that can effectively alleviate this contention and many co-schedulers have been reported in related literature. Most solutions however do not aim to find the optimal co-scheduling solution. Being able to determine the optimal solution is critical for evaluating co-scheduling systems. Moreover, most co-schedulers only consider serial jobs, and there often exist both parallel and serial jobs in real-world systems. In this paper a graph-based method is developed to find the optimal co-scheduling solution for serial jobs; the method is then extended to incorporate parallel jobs, including multi-process, and multi-threaded parallel jobs. A number of optimization measures are also developed to accelerate the solving process. Moreover, a flexible approximation technique is proposed to strike a balance between the solving speed and the solution quality. Extensive experiments are conducted to evaluate the effectiveness of the proposed co-scheduling algorithms. The results show that the proposed algorithms can find the optimal co-scheduling solution for both serial and parallel jobs. The proposed approximation technique is also shown to be flexible in the sense that we can control the solving speed by setting the requirement for the solution quality.
Original language | English |
---|---|
Article number | 7194818 |
Pages (from-to) | 1617-1632 |
Number of pages | 16 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Volume | 27 |
Issue number | 6 |
DOIs | |
Publication status | Published - 1 Jun 2016 |
Bibliographical note
Funding Information:The authors acknowledge a number of different funding sources that support this work: The Royal Society Industry Fellowship Scheme (IF090020/AM); Bull Information Systems and the Bull/Warwick Premier Partnership and the PhD funding that this provides; EPSRC and Intel Corporation Industrial CASE Account (awards 38405-2013 and 15220082-2015).
Publisher Copyright:
© 2015 IEEE.
Keywords
- graph
- Multicore
- parallel computing
- scheduling
ASJC Scopus subject areas
- Signal Processing
- Hardware and Architecture
- Computational Theory and Mathematics