JUCS - Journal of Universal Computer Science 3(7): 803-812, doi: 10.3217/jucs-003-07-0803
Bounds on the Performance of Work-greedy Assignment Schemes
expand article infoSathiamoorthy Manoharan‡
‡ Department of Computer Science, University of Auckland,, Auckland, New Zealand

Corresponding author: Sathiamoorthy Manoharan ( mano@cs.auckland.ac.nz )

© Sathiamoorthy Manoharan.
This article is freely available under the J.UCS Open Content License.
Citation: Manoharan S (1997) Bounds on the Performance of Work-greedy Assignment Schemes. JUCS - Journal of Universal Computer Science 3(7): 803-812. https://doi.org/10.3217/jucs-003-07-0803
Open Access
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, Scheduling, Processor assignment.