𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling loosely connected task graphs

✍ Scribed by Abhiram G. Ranade

Book ID
104147718
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
165 KB
Volume
67
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We present a polynomial time algorithm for precedence-constrained scheduling problems in which the task graph can be partitioned into large disjoint parts by removing edges with high float, where the float of an edge is defined as the difference between the length of the longest path in the graph and the length of the longest path containing the edge. Our algorithm guarantees schedules within a factor 1:875 of the optimal independent of the number of processors. The best-known factor for this problem and in general is 2 Γ€ 2 p ; where p is the number of processors, due to Coffman-Graham. Our algorithm is unusual and considerably different from that of Coffman-Graham and other algorithms in the literature.

πŸ“œ SIMILAR VOLUMES

Scheduling task graphs optimally with A*
Scheduling task graphs optimally with A*
✍ Ahmed Zaki SemarΒ Shahul; Oliver Sinnen πŸ“‚ Article πŸ“… 2010 πŸ› Springer US 🌐 English βš– 818 KB
Benchmarking and Comparison of the Task
Benchmarking and Comparison of the Task Graph Scheduling Algorithms
✍ Yu-Kwong Kwok; Ishfaq Ahmad πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 467 KB

The problem of scheduling a parallel program represented by a weighted directed acyclic graph (DAG) to a set of homogeneous processors for minimizing the completion time of the program has been extensively studied. The NP-completeness of the problem has stimulated researchers to propose a myriad of

Efficient Scheduling of Arbitrary Task G
Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using a Parallel Genetic Algorithm
✍ Yu-Kwong Kwok; Ishfaq Ahmad πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 492 KB

Given a parallel program represented by a task graph, the objective of a scheduling algorithm is to minimize the overall execution time of the program by properly assigning the nodes of the graph to the processors. This multiprocessor scheduling problem is NP-complete even with simplifying assumptio