𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation algorithms for general parallel task scheduling

✍ Scribed by Oh-Heum Kwon; Kyung-Yong Chwa

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
281 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for both preemptive and nonpreemptive cases in the general setting. Next we focus on linear array network of m processors. We give an approximation algorithm of ratio O(log m) for nonpreemptive scheduling, and another algorithm of ratio 2 for preemptive scheduling. Finally, we give a nonpreemptive scheduling algorithm of ratio O(log 2 m) for m Γ— m two-dimensional meshes.

πŸ“œ SIMILAR VOLUMES

An efficient parallel algorithm for sche
An efficient parallel algorithm for scheduling interval ordered tasks
✍ Yoojin Chung; Kunsoo Park πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 187 KB

We present an efficient parallel algorithm for scheduling n unit length tasks on m identical processors when the precedence graphs are interval orders. Our algorithm requires Oðlog 2 v þ ðn log nÞ=vÞ time and Oðnv 2 þ n 2 Þ operations on the CREW PRAM, where v can be any number between 1 and n: By c

Approximation algorithms for scheduling
Approximation algorithms for scheduling trees with general communication delays
✍ Alix Munier πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 101 KB

We consider the problem of scheduling a tree with general communication delays. Jakoby and Reischuk proved that this problem is NP-hard for binary trees and unlimited number of processors. Firstly, we develop a clustering procedure based on the same lower bounds as Papadimitriou and Yannakakis for a

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-

Scheduling algorithm for nonpreemptive m
Scheduling algorithm for nonpreemptive multiprocessor tasks
✍ J.-F. Lin; S.-J. Chen πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 619 KB

This paper considers the problem of scheduling nonpreemptive multiprocessor tasks in a homogeneous system of processors. The problem proposed in this paper is different from the conventional scheduling problem, where each task requires only "one" processor whenever it is in processing. In our multip