✦ LIBER ✦

Scheduling Interval Ordered Tasks in Parallel

✍ Scribed by Sivaprakasam Sunder; Xin He

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 148 KB
Volume: 26
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0895

No coin nor oath required. For personal study only.

✦ Synopsis

We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority concurrent read, concurrent write parallel Ž 2 . Ž 5 . Ž 3 . random access machine in O log n with O n processors, or in O log n time Ž 4 . with O n processors. The algorithm constructs the same schedule as the one Ž . produced by the sequential algorithm list scheduling . On the other hand, we show that when the precedence constraints are allowed to be arbitrary, the construction of the list schedule is P-complete.

📜 SIMILAR VOLUMES

List scheduling of parallel tasks

✍ Qingzhou Wang; Kam Hoi Cheng 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 940 KB

An Optimal Algorithm for Scheduling Inte

An Optimal Algorithm for Scheduling Interval Ordered Tasks with Communication on N Processors

✍ H.H. Ali; H. Elrewini 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 506 KB

The problem of scheduling task graphs on multiprocessor systems have received considerable attention in recent years. This problem is known to be NP-hard in its general form as well as many restricted cases. Few polynomial algorithms have been developed for solving special cases of the scheduling pr

Scheduling of stochastic tasks on two pa

Scheduling of stochastic tasks on two parallel processors

✍ Michael Pinedo; Gideon Weiss 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 457 KB 👁 1 views

Real-time scheduling of linear speedup p

Real-time scheduling of linear speedup parallel tasks

✍ Maciej Drozdowski 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 508 KB

Optimizing layer-based scheduling algori

Optimizing layer-based scheduling algorithms for parallel tasks with dependencies

✍ R. Kunis; G. Rünger 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 485 KB

Models and Scheduling Algorithms for Mix

Models and Scheduling Algorithms for Mixed Data and Task Parallel Programs

✍ Soumen Chakrabarti; James Demmel; Katherine Yelick 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 400 KB

An increasing number of scientific programs exhibit two forms of parallelism, often in a nested fashion. At the outer level, the application comprises coarse-grained task parallelism, with dependencies between tasks reflected by an acyclic graph. At the inner level, each node of the graph is a data-