ebooks logo journals logo reference works logo abstract databases logo
bullet  SIGN IN Register | Why Register? | Got a Voucher? alerts   marked lists   shopping cart 

informaworld

HOME   |   SEARCH   |   BROWSE
    Issues List       Latest Issue       Forthcoming Articles       Volume 11 Issue 1 & 2       Subscribe       Article       References       Related articles      
<< firstfirst   < prevprev   Table of contentstoc   next >next   last >>last
Publisher Logo Publication Cover
Search within this journal

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: journal International Journal of Parallel, Emergent and Distributed Systems, Volume 11, Issue 1 & 2 1997 , pages 129 - 153
Formats available: PDF (English)
Previously published as: Parallel Algorithms and Applications (1063-7192) until 2005
Article Requests: Order Reprints : Request Permissions
View Article: View Article (PDF) 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)
Bookmark with:
  • CiteULike
  • Del.icio.us
  • BibSonomy
  • Connotea
  • More bookmarks
Privacy Policy | Terms & Conditions | Accessibility | RSS
FAQs in: English . Français . Español . 中文(简体和繁體)
© 2009 Informa plc