OPTIMAL PARALLEL EXECUTION OF COMPLETE BINARY-TREES AND GRIDS INTO MOST POPULAR INTERCONNECTION NETWORKS

Authors
BAMPIS E KONIG JC TRYSTRAM D
Citation
E. Bampis et al., OPTIMAL PARALLEL EXECUTION OF COMPLETE BINARY-TREES AND GRIDS INTO MOST POPULAR INTERCONNECTION NETWORKS, Theoretical computer science, 147(1-2), 1995, pp. 1-18
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
147
Issue
1-2
Year of publication
1995
Pages
1 - 18
Database
ISI
SICI code
0304-3975(1995)147:1-2<1:OPEOCB>2.0.ZU;2-9
Abstract
We consider an extension of the well-known PRAM model for parallel dis tributed-memory computers using local communications. We present sched uling algorithms for the execution of complete binary trees on hypercu be, de Bruijn, linear and grid interconnection networks on this model. We also show that a two-dimensional grid precedence graph can be exec uted in optimal time on all these networks.