Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
Authors: Alexander Lindermayr, Nicole Megow, Martin Rapp
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | These seem to be the first empirical results for scheduling algorithms with predictions that are evaluated in a non-synthetic hardware environment. Finally, we compare algorithms for these models with heuristics in experiments on an actual modern heterogeneous chip. These are the first empirical results which show the benefit of learning-augmented algorithms and validate theoretical findings on real hardware. |
| Researcher Affiliation | Academia | 1Faculty of Mathematics and Computer Science, University of Bremen, Bremen, Germany 2Department of Informatics, Karlsruhe Institute of Technology (KIT), Germany. |
| Pseudocode | Yes | Algorithm 1 Maximum Density, Algorithm 2 Greedy WSPT, Algorithm 3 Proportional Fairness, Algorithm 4 Maximum Density for speed-ordered machines, Algorithm 5 Round Robin for speed-ordered machines, Algorithm 6 Iterative Greedy. |
| Open Source Code | No | The paper does not contain an explicit statement or direct link confirming the release of source code for the methodology described in this paper. |
| Open Datasets | Yes | Our workload comprises 100 randomly selected single-threaded jobs from the well-established PARSEC-3.0 (Zhan et al., 2016), SPLASH-3 (Sakalis et al., 2016), and Polybench (Yuki & Pouchet, 2015) benchmark suites. |
| Dataset Splits | No | The paper uses benchmark suites and generated workloads, but does not provide specific details on training, validation, or test dataset splits. |
| Hardware Specification | Yes | The setup uses a Hi Key 970 board (Linaro 96Boards) with a Kirin 970 Arm big.LITTLE So C featuring 4 big cores and 4 LITTLE cores, running Android 8.0. |
| Software Dependencies | No | The paper mentions 'Android 8.0' and 'Linux affinity masks' but does not provide specific versions for key software dependencies or libraries used in the implementation of the schedulers. |
| Experiment Setup | Yes | The schedulers compute a schedule every 2 s based on the currently active jobs and their (predicted) characteristics. Speed predictions are created with controllable error by ˆsij = sij yij, where yij follows a log-normal distribution ln(yij) N(0, σ2). The arrival times are drawn from a Poisson distribution with varying rate parameter to study different system loads. |