Competitive dynamic multiprocessor allocation for parallel applications
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 448-455
- https://doi.org/10.1109/spdp.1995.530717
Abstract
In this paper we use competitive analysis to study preemptive multiprocessor allocation policies for parallel jobs whose execution time is not known to the scheduler at the time of scheduling. The objective is to minimize the makespan (i.e., the completion time of the last job to finish executing). We characterize a parallel job, J i , by two parameters: its execution time, l i , and its parallelism, P i , which may vary over time. The preemption and reallocation of processors can take place at any time. We devise a preemptive policy which achieves the best possible competitive ratio and then derive upper and lower bounds for scheduling N parallel jobs on P processors Author(s) Brecht, T. Dept. of Comput. Sci., York Univ., Toronto, Ont., Canada Deng, X. ; Nian GuKeywords
This publication has 13 references indexed in Scilit:
- Scheduling parallelizable tasks to minimize average response timePublished by Association for Computing Machinery (ACM) ,1994
- A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessorsACM Transactions on Computer Systems, 1993
- Processor scheduling in shared memory multiprocessorsPublished by Association for Computing Machinery (ACM) ,1990
- Process control and scheduling issues for multiprogrammed shared-memory multiprocessorsPublished by Association for Computing Machinery (ACM) ,1989
- Characterizations of parallelism in applications and their use in schedulingPublished by Association for Computing Machinery (ACM) ,1989
- Speedup versus efficiency in parallel systemsIEEE Transactions on Computers, 1989
- Approximation schemes for constrained scheduling problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Complexity Results for Multiprocessor Scheduling under Resource ConstraintsSIAM Journal on Computing, 1975
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966