PARADIGMS ADMITTING SUPERUNITARY BEHAVIOUR IN PARALLEL COMPUTATION *
Authors:
S. G. Akl a;
L. Fava Lindon b
| Affiliations: | a Dept. of Computing and Information Science, Queen's University at Kingston, Kingston, Ontario |
| b Dept. of Mathematics and Computer Science, Laurentian University, Sudbury, Ontario |
DOI:
10.1080/10637199708915591
Publication Frequency:
6 issues per year
Published in:
International Journal of Parallel, Emergent and Distributed Systems,
Volume
11,
Issue
1 &
2
1997
, pages 129
- 153
Subjects:
Algorithms & Complexity;
Computer Engineering;
Computer Science (General);
Distributed Network Systems;
Distributed Systems;
Internet & Multimedia;
Neural Networks;
Parallel Algorithms;
Parallel Systems;
Programming & Programming Languages;
Quantum Information;
Systems & Computer Architecture;
Formats available:
PDF
(English)
Previously published as:
Parallel Algorithms and Applications
(1063-7192)
until 2005
View Article:
View Article (PDF)
Abstract
With the expanding role of computers in society, some assumptions underlying well known theorems in the theory of parallel computation no longer hold universally. In particular, the speedup theorem and Brent's theorem do not apply to dynamic computers that interact with their environment. The phenomenon of a disproportionate decrease in execution time of P2 over p1 processors for p2 > p1 is referred to as superunitary speedup. An analogous phenomenon that we call superunilary 'success ratio' occurs in dealing with tasks that can either succeed or fail, when there is a disproportionate increase in the success of p2 over p1 processors executing a task. We identify a range of conditions that may lead to superunitary speedup or success ratio, and propose several new paradigms for problems that admit such superunitary behaviour. Our results suggest that a new theory of parallel computation may be required to accommodate these new paradigms.
|
|
*This work was supported by the Natural Sciences and Engineering Research Council of Canada.
|
| Keywords: superlinear speedup; superunitary speedup; parallel computation; speedup theorem; Brent's theorem |
| Classification Categories: 1.2.9 (Robotics); F.1.1 (Models of Computation); F.1.2 (Modes of Computation); F.2.2 (Nonnumerical Algorithms and Problems); G.3 (Probability and Statistics) |
| view references (34) |

Download Citation

CiteULike
Del.icio.us
BibSonomy
Connotea