Title :
Augmenting work-greedy assignment schemes with task duplication
Author_Institution :
Dept. of Comput. Sci., Auckland Univ., New Zealand
Abstract :
This paper analyses the effect of task duplication on the assignment of task dependency graphs onto concurrent processor systems. It presents a scheme to augment work-greedy assignment schemes with task duplication. Such augmentation results in a time-complexity increase which is well below that of comparable assignment schemes with task duplication. The paper shows empirical results comparing the augmented assignment schemes
Keywords :
computational complexity; parallel algorithms; resource allocation; augmented assignment schemes; concurrent processor systems; task dependency graphs; task duplication; time-complexity; work-greedy assignment schemes; Clocks; Computer science; Costs; Optimal scheduling; Polynomials; Processor scheduling;
Conference_Titel :
Parallel and Distributed Systems, 1997. Proceedings., 1997 International Conference on
Conference_Location :
Seoul
Print_ISBN :
0-8186-8227-2
DOI :
10.1109/ICPADS.1997.652629
