Wasted resources in gang scheduling

Author

Feitelson, Dror G. ; Rudolph, Lany

Author_Institution

Dept. of Comput. Sci., Hebrew Univ. of Jerusalem, Israel

fYear

1990

fDate

22-25 Oct 1990

Firstpage

127

Lastpage

136

Abstract

Gang scheduling (the scheduling of a number of interacting threads to run simultaneously on distinct processors) can leave processors idle if the sizes of the gangs do not match the number of available processors. Given an optimal offline algorithm it is shown that the wasted processing power can range from 0% to 50%, depending on the distribution of gang sizes. Focusing on the uniform and the harmonic distributions, rather than worst-case distributions, it is shown that if there are no restrictions on how the processors are partitioned, these distributions cause no waste with an offline algorithm but a waste of 20% to 37% for online algorithms. Using the distributed hierarchical control scheme, which is similar to buddy systems for memory allocation, a waste of 10% to 20% should be expected for offline algorithms, and 21% to 51% for online algorithms

Keywords

distributed processing; operating systems (computers); scheduling; buddy systems; distributed hierarchical control; gang scheduling; harmonic distributions; memory allocation; optimal offline algorithm; wasted resources; worst-case distributions; Automatic control; Centralized control; Computer science; Control systems; Distributed control; Parallel processing; Partitioning algorithms; Processor scheduling; Switches; Yarn;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Technology, 1990. 'Next Decade in Information Technology', Proceedings of the 5th Jerusalem Conference on (Cat. No.90TH0326-9)

Conference_Location

Jerusalem

Print_ISBN

0-8186-2078-1

Type

conf

DOI

10.1109/JCIT.1990.128278

Filename

128278