✦ LIBER ✦

Optimal parallel processing of random task graphs

✍ Scribed by Zhen Liu; Rhonda Righter

Publisher: Springer US
Year: 2001
Tongue: English
Weight: 180 KB
Volume: 4
Category: Article
ISSN: 1094-6136
DOI: 10.1002/jos.70

No coin nor oath required. For personal study only.

✦ Synopsis

We consider scheduling of tasks of parallel programs on multiprocessor systems where tasks have precedence relations and synchronization points. The task graph structures are random variables in the sense that successors to a task do not become known until the task is executed. Thus, as is often the case with parallel processing, scheduling must occur at run time rather than compile time. We prove that a simple scheduling policy stochastically minimizes the processes of task completions and job (i.e. set of parallel tasks) completions for several classes of task graph structures.

📜 SIMILAR VOLUMES

Optimal Use of Mixed Task and Data Paral

Optimal Use of Mixed Task and Data Parallelism for Pipelined Computations

✍ Jaspal Subhlok; Gary Vondran 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 360 KB

This paper addresses optimal mapping of parallel programs composed of a chain of data parallel tasks onto the processors of a parallel system. The input to the programs is a stream of data sets, each of which is processed in order by the chain of tasks. This computation structure, also referred to a

Discussion of ‘square root algorithms fo

Discussion of ‘square root algorithms for parallel processing in optimal estimation’

✍ Donald J. Schmidt 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 97 KB

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

An Optimal Simple Parallel Algorithm for

An Optimal Simple Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

✍ Shan-Chyun Ku; Biing-Feng Wang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 91 KB

An outerplanar graph is a planar graph that can be imbedded in the plane in such a way that all vertices lie on the exterior face. An outerplanar graph is maximal if no edge can be added to the graph without violating the outerplanarity. In this paper, an optimal parallel algorithm is proposed on th

Reply to discussion of ‘square-root algo

Reply to discussion of ‘square-root algorithms for parallel processing in optimal estimation’

✍ M. Morf; T. Kailath; J.R. Dobbins; B. Friedlander; J. Newkirk 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 107 KB

Denumerable state markovian sequential c

Denumerable state markovian sequential control processes: On randomizations of optimal policies

✍ S. S. Chitgopekar 📂 Article 📅 1975 🏛 John Wiley and Sons 🌐 English ⚖ 287 KB

## Abstract We consider a denumerable state Markovian sequential control process. It is well known that when we consider the expected total discounted income as a criterion, there exists a nonrandomized stationary policy that is optimal. It is also well known that when we consider the expected aver