Superlinear performance in real-time parallel computation

被引:24
作者
Akl, SG [1 ]
机构
[1] Queens Univ, Sch Comp, Kingston, ON K7L 3N6, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
parallelism; superlinear speedup; superlinear quality-up; real-time computation; optimization; cryptography; numerical analysis;
D O I
10.1023/B:SUPE.0000022574.59906.20
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Can a parallel computer with n processors solve a computational problem more than n times faster than a sequential computer? Can it solve it more than n times better? New computational paradigms offer an affirmative answer to the above questions through concrete examples in which the improvement in speed or quality is superlinear in the number of processors used by the parallel computer. Furthermore, the improvement is consistent and provable. All examples are characterized by the presence of one or several real-time input streams. In one of the examples, an exponential improvement in speed is achieved despite the fact that the processors of the parallel computer are significantly slower than their sequential counterpart. In another example, the improvement in quality is unbounded. A metaphor from everyday life motivates each computational paradigm in which a superlinear improvement in performance is exhibited.
引用
收藏
页码:89 / 111
页数:23
相关论文
共 22 条
[1]  
Akl S. G., 1999, Parallel Processing Letters, V9, P499, DOI 10.1142/S0129626499000463
[2]  
Akl S.G., 1997, Parallel Computation: Models and Methods
[3]   Parallel real-time computation: Sometimes quantity means quality [J].
Akl, SG .
I-SPAN 2000: INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES ALGORITHMS AND NETWORKS, PROCEEDINGS, 2000, :2-11
[4]  
AKL SG, 1997, PARALLEL ALGORITHMS, V11, P129
[5]   PARALLEL SIMPLEX FOR LARGE PURE NETWORK PROBLEMS - COMPUTATIONAL TESTING AND SOURCES OF SPEEDUP [J].
BARR, RS ;
HICKMAN, BL .
OPERATIONS RESEARCH, 1994, 42 (01) :65-80
[6]  
BESTAVROS A, 1997, REAL TIME DATABASE I
[7]   The characterization of data-accumulating algorithms [J].
Bruda, SD ;
Akl, SG .
THEORY OF COMPUTING SYSTEMS, 2000, 33 (01) :85-96
[8]   A case study in real-time parallel computation: Correcting algorithms [J].
Bruda, SD ;
Akl, SG .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2001, 61 (05) :688-708
[9]  
BRUDA SD, 2001, P WORKSH ADV PAR DIS
[10]   REEVALUATING AMDAHL LAW [J].
GUSTAFSON, JL .
COMMUNICATIONS OF THE ACM, 1988, 31 (05) :532-533