Developing Graph-Based Co-Scheduling Algorithms on Multicore Computers

Ligang He*, Huanzhou Zhu, Stephen A. Jarvis

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


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 languageEnglish
Article number7194818
Pages (from-to)1617-1632
Number of pages16
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number6
Publication statusPublished - 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.


  • graph
  • Multicore
  • parallel computing
  • scheduling

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Developing Graph-Based Co-Scheduling Algorithms on Multicore Computers'. Together they form a unique fingerprint.

Cite this