Speed of parallel processing for random task graphs
Speed of parallel processing for random task graphs
复制标题
随机任务图的并行处理速度
DOI：
10.1002/cpa.3160470307
复制
发表时间：
1994
影响因子：
3
通讯作者：
C. Newman
中科院分区：
文献类型：
--
作者：
M. Isopi;C. Newman
Gelenbe等人提出的并行计算的随机图模型。取决于三个参数：N，任务(顶点)的数量；F，T1，…的共同分布，Tn，任务处理时间，以及p=pn，对于给定的i&j，任务i必须在任务j开始之前完成的概率。总的处理时间为Rn，即图中沿有向路径的最大和。我们研究了当NPN以超对数方式亚线性增长时，Rn的大n行为，即最长有向路径包含关于enpn任务的区域。对于指数(平均)F，我们证明了Rn约为4npn。4和e之间的“差异”是一个很大的偏差效应。当NPN以精确对数增长时，当F不是指数增长，但有一个(至少)指数快速衰减的尾巴时，得到了相关结果。©1994约翰·威利L儿子公司
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 T1,…, Tn, the task processing times, and p = pn, the probability for a given i < j that task i must be completed before task j is started. The total processing time is Rn, the maximum sum of Ti's along directed paths of the graph. We study the large n behavior of Rn when npn grows sublinearly but superlogarithmically, the regime where the longest directed path contains about enpn tasks. For an exponential (mean one) F, we prove that Rn is about 4npn. The “discrepancy” between 4 and e is a large deviation effect. Related results are obtained when npn 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.