Premium
Speed of parallel processing for random task graphs
Author(s) -
Isopi Marco,
Newman Charles M.
Publication year - 1994
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.3160470307
Subject(s) - mathematics , task (project management) , random graph , combinatorics , graph , management , economics
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 1 ,…, T n , the task processing times, and p = p n , the probability for a given i < j that task i must be completed before task j is started. The total processing time is R n , the maximum sum of T i 's along directed paths of the graph. We study the large n behavior of R n when np n grows sublinearly but superlogarithmically, the regime where the longest directed path contains about enp n tasks. For an exponential (mean one) F , we prove that R n is about 4 np n . The “discrepancy” between 4 and e is a large deviation effect. Related results are obtained when np n grows exactly logarithmically and when F is not exponential, but has a tail which decays (at least) exponentially fast. © 1994 John Wiley L Sons, Inc.