๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Speed of parallel processing for random task graphs

โœ Scribed by Marco Isopi; Charles M. Newman

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
681 KB
Volume
47
Category
Article
ISSN
0010-3640

No coin nor oath required. For personal study only.

โœฆ Synopsis

The random graph model of parallel computation introduced by Gelenbe et al. depends on three parameters: n, the number of tasks (vertices); F, the common distribution of T i , . . . , T,, the task processing times, and p = p,, the probability for a given i < j that task i must be completed before task j is started. The total processing time is R,,, the maximum sum of T,'s along directed paths of the graph. We study the large n behavior of Rn when np,, grows sublinearly but superlogarithmically, the regime where the longest directed path contains about enp,, tasks. For an exponential (mean one) F, we prove that R,, is about 4np,. The "discrepancy" between 4 and e is a large deviation effect.

Related results are obtained when np,, grows exactly logarithmically and when F is not exponential, but has a tail which decays (at least) exponentially fast. 01994 John Wiley L Sons, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Optimal parallel processing of random ta
Optimal parallel processing of random task graphs
โœ Zhen Liu; Rhonda Righter ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Springer US ๐ŸŒ English โš– 180 KB

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

A Randomized Parallel Algorithm for Plan
A Randomized Parallel Algorithm for Planar Graph Isomorphism
โœ Hillel Gazit; John H Reif ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 223 KB

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph ลฝ ลฝ 2 . 1 q โ‘€ which can be computed by known algorithms in O log n time with