loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)
Optimal Simulation of Meshes with Dynamically Separable Buses by Meshes with Statically Partitioned Buses
Hong Kong, SAR, China
May 10-May 12
ISBN: 0-7695-2135-5
Susumu Matsumae, Tottori University of Environmental Studies, Japan
This paper studies the simulation problem of meshes with separable buses (MSB) by meshes with multiple partitioned buses (MMPB). The MSB and the MMPB are the mesh-connected computers enhanced by the addition of broadcasting buses along every row and column. The broadcasting buses of the MSB, called separable buses, can be dynamically sectioned into smaller bus segments by program control, while those of the MMPB, called partitioned buses, are statically partitioned in advances. In the MSB model, each row/column has only one separable bus, while in the MMPB model, each row/column has L partitioned buses (L ≥ 1). We present an algorithm that simulates the MSB of size n × n in O(n{1/(2L+1)}) steps using the MMPB of size n × n, and prove that the time-complexity of the algorithm is optimal in the worst case.
Citation:
Susumu Matsumae, "Optimal Simulation of Meshes with Dynamically Separable Buses by Meshes with Statically Partitioned Buses," ispan, pp.475, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.