SCHEDULING TASK-TREES WITH ADDITIVE SCALES ON PARALLEL DISTRIBUTED MACHINES/

Authors
Citation
Xd. Yu et Mt. Yung, SCHEDULING TASK-TREES WITH ADDITIVE SCALES ON PARALLEL DISTRIBUTED MACHINES/, Theoretical computer science, 181(2), 1997, pp. 357-378
Citations number
22
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
ISSN journal
03043975
Volume
181
Issue
2
Year of publication
1997
Pages
357 - 378
Database
ISI
SICI code
0304-3975(1997)181:2<357:STWASO>2.0.ZU;2-2
Abstract
We consider a family of jobs that are organized as a task-tree which, in particular, captures the behavior of divide-and-conquer algorithms in many typical cases !examples are QuickSort and Brute-Force Search j obs). These jobs can be described as a rooted task tree, where the cos t of work at a node v in the tree is additive in the cost of v's child ren. We give a lower bound on the time to perform such jobs. We then p rovide a general algorithm that assigns these tasks to processors in a large set of parallel/distributed architectures (which includes: mesh es, linear arrays, and rings). We analyze our scheme's time, showing w hen it is optimal or nearly optimal. We consider the cases when the tr ee structure is known at the node (i.e., the static case), when the di vision of work among children is known (the semi-dynamic case), and ca ses when no structure is known (i.e. fully dynamic cases).