Bounds on the Performance of Work-greedy Assignment Schemes

Sathiamoorthy Manoharan (Department of Computer Science, University of Auckland,, New Zealand)

Abstract: The heuristics most of the current assignment schemes use is based on satisfying the following rule of thumb: keeping the processors busy leads to a 'good' assignment. Such schemes are said to be work-greedy. This paper presents new bound s on the performance of work-greedy schemes, taking into account the degree of parall elism visible between the tasks and the inter-task communication delays.

Keywords: Allocation, Dependency graphs, Instruction-level parallelism, Processor assignment., Scheduling

Categories: A.0