Core allocation to minimize total flow time in a multicore system in the presence of a processing time constraint
Author:
Open Access
- 26 August 2024
- journal article
- research article
- Published by Springer Nature in Queueing Systems
- Vol. 108 (3-4) , 475-577
Abstract
Data centers are a vital and fundamental infrastructure component of the cloud. The requirement to execute a large number of demanding jobs places a premium on processing capacity. Parallelizing jobs to run on multiple cores reduces execution time. However, there is a decreasing marginal benefit to using more cores, with the speedup function quantifying the achievable gains. A critical performance metric is flow time. Previous results in the literature derived closed-form expressions for the optimal allocation of cores to minimize total flow time for a power-law speedup function if all jobs are present at time 0. However, this work did not place a constraint on the makespan. For many diverse applications, fast response times are essential, and latency targets are specified to avoid adverse impacts on user experience. This paper is the first to determine the optimal core allocations for a multicore system to minimize total flow time in the presence of a completion deadline (where all jobs have the same deadline). The allocation problem is formulated as a nonlinear optimization program that is solved using the Lagrange multiplier technique. Closed-form expressions are derived for the optimal core allocations, total flow time, and makespan, which can be fitted to a specified deadline by adjusting the value of a single Lagrange multiplier. Compared to the unconstrained problem, the shortest job first property for optimal allocation is maintained; however, a number of other properties require revising and other properties are only retained in a modified form (such as the scale-free and size-dependence properties). It is found that with a completion deadline the optimal solution may contain groups of simultaneous completions. In general, all possible patterns of single- and group-completion need to be considered, producing an exponential search space. However, the paper determines analytically that the optimal completion pattern consists of a sequence of single completions followed by a single group of simultaneous completions at the end, which reduces the search space dimension to being linear. The paper validates the Lagrange multiplier approach by verifying constraint qualifications.Keywords
Funding Information
- Macquarie University
This publication has 29 references indexed in Scilit:
- Scheduling2022
- Scheduling and Control of Queueing Networks2021
- Open problems in queueing theory inspired by datacenter computingQueueing Systems, 2021
- Optimizing job completion time with fairness in large-scale data centersFuture Generation Computer Systems, 2021
- heSRPT: Parallel scheduling to minimize mean slowdownPerformance Evaluation, 2020
- A Deadline Constrained Preemptive Scheduler Using Queuing Systems for Multi-Tenancy Clouds2019
- Toward holistic performance management in clouds: taxonomy, challenges and opportunitiesThe Journal of Supercomputing, 2018
- Supporting Malleability in Parallel Architectures with Dynamic CPUSETsMapping and Dynamic MPI2010
- The Cauchy-Schwarz Master Class2004
- Theory and practice in parallel job scheduling1997