A Graph based approach for Co-scheduling jobs on Multi-core computers

Huanzhou Zhu, Ligang HeICCSW 2013 · OpenReview

TL;DR

This paper introduces a novel graph-based approach to model and find optimal co-scheduling solutions for jobs on multi-core processors, specifically addressing the challenge of parallel jobs. By considering parallel job execution, their method achieves a significant 31% average performance improvement compared to approaches that only handle serial jobs.

What Problem Does This Paper Address?

Modern multi-core processors, while powerful, suffer from resource contention when multiple applications run concurrently. This contention, particularly for shared resources like the last-level cache (LLC), can lead to performance degradation. While "co-scheduling" aims to mitigate this by intelligently assigning jobs to cores, most existing solutions focus on serial jobs (those running on a single core) and don't aim for optimal performance. This leaves a gap: how to find the best possible co-scheduling for a mix of serial and parallel jobs, and how much performance improvement is truly achievable. Understanding this optimal point is crucial for designing better schedulers and hardware.

Methods

The authors propose a two-pronged approach:

  1. Graph Modeling: They introduce a "co-scheduling graph" to represent the problem. In this graph, nodes represent possible co-scheduling configurations (sets of jobs assigned to cores), and edges connect these configurations. The "weight" of a node is the performance degradation associated with that job set. This graph is structured into levels, with a start and end node.
  2. Optimal Parallel-aware Shortest Path Algorithm (OP-SCG): Finding the optimal co-scheduling solution is framed as finding the shortest valid path from the start to the end node in this graph. OP-SCG is an adaptation of Dijkstra's algorithm. Key modifications include:
  3. Edges are dynamically established as the algorithm progresses.
  4. Invalid paths (containing duplicate jobs) are disregarded.
  5. Crucially, it incorporates a mechanism to compute the degradation of parallel jobs. For parallel jobs, the degradation is determined by the slowest process within that job, multiplied by the number of processes.

For comparison, they also describe a "Basic Shortest Path algorithm" (B-SCG) that is equivalent to their OP-SCG but without the parallel job handling, effectively representing the state-of-the-art for serial job co-scheduling.

Datasets

Not discussed in the paper. The authors mention using a "prediction model developed by Dhruba et.al [2]" to compute degradation values for nodes in their graph. They also state that the simulation used "artificially generated jobs" with randomly generated cache hit/miss profiles, but these are not presented as formal datasets.

Key Insights and Ideas

  • Parallelism is a Game Changer: The most significant insight is that ignoring parallel jobs leads to suboptimal performance. The way parallel jobs experience degradation (limited by their slowest thread) requires a different modeling approach than serial jobs.
  • Optimal is Achievable (Theoretically): By framing co-scheduling as a shortest path problem on a carefully constructed graph, the authors demonstrate a method to find the theoretically optimal solution.
  • Graph Representation Simplifies Complexity: The graph model effectively visualizes and structures the complex combinatorial problem of assigning jobs to cores.
  • Trade-off Awareness: Knowing the gap between current scheduler performance and the optimal solution (as provided by their method) is vital for system designers to understand where to focus optimization efforts.

Key Results

The paper's primary quantitative result comes from simulations comparing their OP-SCG algorithm (handling parallel jobs) against B-SCG (handling only serial jobs).

  • Performance Improvement: The OP-SCG algorithm achieved 31% better performance on average compared to the B-SCG algorithm when scheduling a mix of parallel and serial jobs. This was measured by lower cache misses, which correlate to lower performance degradation.
  • Core Count Impact: The simulations also showed that as the number of cores increases (while cache size remains constant), performance degradation tends to increase due to more jobs competing for limited cache resources.

Limitations and Future Work

  • Scalability of Graph Approach: The paper acknowledges that the number of nodes in the co-scheduling graph can grow exponentially with the number of jobs. While their OP-SCG algorithm is an adaptation of Dijkstra's, the sheer size of the graph for large job sets could be a practical limitation.
  • Assumption of Single Job per Core: The current model assumes each core executes only a single job. The authors suggest that their approach can still be an "essential component" for finding optimal schedules within time slices if multiple jobs share a core via time-sharing.
  • Future Work: The authors imply that their optimal model can serve as a benchmark for evaluating practical, heuristic-based co-schedulers. They also suggest that with accurate performance prediction models, proactive schedulers could leverage their algorithm to determine optimal or near-optimal schedules in real-time.

Summary updated

Abstract

In a multicore processor system, running multiple applications on different cores in the same chip could cause resource contention, which leads to performance degradation. Recent studies have shown that job co-scheduling can effectively reduce the contention. However, most existing co-schedulers do not aim to find the optimal co-scheduling solution. It is very useful to know the optimal co-scheduling performance so that the system and scheduler designers can know how much room there is for further performance improvement. Moreover, most co-schedulers only consider serial jobs, and do not take parallel jobs into account. This paper aims to tackle the above issues. In this paper, we first present a new approach to modelling the problem of co-scheduling both parallel and serial jobs. Further, a method is developed to find the optimal co-scheduling solutions. The simulation results show that compare to the method that only considers serial jobs, our developed method to co-schedule parallel jobs can improve the performance by 31% on average.
BibTeX
@inproceedings{zhu2013graph,
  author = {Huanzhou Zhu and Ligang He},
  title = {{A Graph based approach for Co-scheduling jobs on Multi-core computers}},
  booktitle = {ICCSW},
  year = {2013},
  url = {https://openreview.net/forum?id=buXTI2DEa3},
}
Figure