Pipelined Decomposable BSP Computers

Martin Beran

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 36, Issue: 1, page 43-65
  • ISSN: 0988-3754

Abstract

top
The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.

How to cite

top

Beran, Martin. "Pipelined Decomposable BSP Computers." RAIRO - Theoretical Informatics and Applications 36.1 (2010): 43-65. <http://eudml.org/doc/92690>.

@article{Beran2010,
abstract = { The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines. },
author = {Beran, Martin},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {BSP; complexity theory; models of compuation; parallel computing; pipelining.; bulk synchronous parallel machine model; decomposable BSP},
language = {eng},
month = {3},
number = {1},
pages = {43-65},
publisher = {EDP Sciences},
title = {Pipelined Decomposable BSP Computers},
url = {http://eudml.org/doc/92690},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Beran, Martin
TI - Pipelined Decomposable BSP Computers
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 36
IS - 1
SP - 43
EP - 65
AB - The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.
LA - eng
KW - BSP; complexity theory; models of compuation; parallel computing; pipelining.; bulk synchronous parallel machine model; decomposable BSP
UR - http://eudml.org/doc/92690
ER -

References

top
  1. M. Beran, Decomposable bulk synchronous parallel computers, in Proc. of SOFSEM '99. Springer-Verlag, Lecture Notes in Comput. Sci. 1725 (1999) 349-359.  Zbl0964.68063URIhttp://www.ms.mff.cuni.cz/~beran/publications.html
  2. M. Beran, Formalizing, analyzing, and extending the model of bulk synchronous parallel computer, Technical Report V-829. Institute of Computer Science, Academy of Sciences of the Czech Republic (2000).  URIhttp://www.cs.cas.cz/research/library/reports_800.shtml
  3. O. Bonorden, B. Juurlink, I. von Otte and I. Rieping, The Paderborn University BSP (PUB) library - design, implementation and performance, in Proc. of 13th International Parallel Processing Symposium & 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP). San Juan, Puerto Rico (1999).  URIhttp://www.uni-paderborn.de/~pub/
  4. P. van Emde Boas, Machine models and simulations, edited by J. van Leeuwen. Elsevier Science Publishers, Amsterdam, Handb. Theoret. Comput. Sci. A (1990) 1-66.  Zbl0900.68265
  5. P. van Emde Boas, The second machine class, model of parallelism, edited by J. van Leeuwen, J.K. Lenstra and A.H.G. Rinnooy Kan. Centre for Mathematics and Computer Science, Amsterdam, Parallel Computers and Computations, CWI Syllabus 9 (1985) 133-161.  
  6. A.V. Gerbessiotis and C.J. Siniolakis, Primitive operations on the BSP model, Technical Report PRG-TR-23-96. Oxford University Computing Laboratory, Oxford (1996).  
  7. A.V. Gerbessiotis and L.G. Valiant, Direct bulk-synchronous parallel algorithms. J. Parallel Distributed Comput.22 (1994) 251-267.  
  8. D.Q. Goldin, S.A. Smolka and P. Wegner, Turing machines, transition systems, and interaction (submitted).  Zbl1260.68267URIhttp://www.cs.umb.edu/~dqg/papers/mfcs.ps
  9. J.M.D. Hill, W. McColl, D.C. Stefanescu, M.W. Goudreau, K. Lang, S.B. Rao, T. Suel,T. Tsantilas and R. Bisseling, BSPlib: The BSP programming library. BSPlib reference manual with ANSI C examples (1998).  URIhttp://www.bsp-worldwide.org/implmnts/oxtool/
  10. B.H.H. Juurlink and H.A.G. Wijshoff, Communication primitives for BSP computers. Inform. Process. Lett.58 (1996) 303-310.  Zbl1023.68878
  11. R.M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines, edited by J. van Leeuwen. Elsevier Science Publishers, Amsterdam, Handb. Theoret. Comput. Sci. A (1990) 869-941.  Zbl0900.68267
  12. J. van Leeuwen and J. Wiedermann, The Turing machine paradigm in contemporary computing, edited by B. Enquist and W. Schmidt. Springer-Verlag, Mathematics Unlimited -- 2001 and Beyond (2001) 1139-1155.  Zbl1012.68068
  13. W.F. McColl, Bulk synchronous parallel computing, edited by J.R. Davy and P.M. Dew. Oxford University Press, Abstract Machine Models for Highly Parallel Computers (1995) 41-63.  
  14. C. Slot and P. van Emde Boas, On tape versus core; an application of space efficient perfect hash function to the invariance of space, in Proc. of STOC'84. Washington D.C. (1984) 391-400.  
  15. L.G. Valiant, A bridging model for parallel computation. Comm. ACM33 (1990) 103-111.  
  16. P. Wegner, Models and paradigms of interaction. OOPSLA Tutorial Notes (1995).  
  17. J. Wiedermann, Weak parallel machines: A new class of physically feasible parallel machine models, in Mathematical Foundations of Computer Science 1992, 17th Int. Symposium (MFCS'92), edited by I.M. Havel and V. Koubek. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 629 (1992) 95-111.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.