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:
- 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.
- 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:
- Edges are dynamically established as the algorithm progresses.
- Invalid paths (containing duplicate jobs) are disregarded.
- 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