loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
International Parallel and Distributed Processing Symposium (IPDPS'03)
An Efficient Scaling-Simulation Algorithm of Reconfigurable Meshes by Meshes with Partitioned Buses
Nice, France
April 22-April 26
ISBN: 0-7695-1926-1
Susumu Matsumae, Tottori University of Environmental Studies
This paper presents an efficient scaling-simulation algorithm that simulates operations of the reconfigurable mesh (RM) of size n × n using the mesh with partitioned buses (MPB) of size m × m (m < n). The RM and the MPB are the two-dimensional mesh-connected computers equipped with broadcasting buses. The broadcasting buses of the RM can be used to dynamically obtain various interconnection patterns among the processors during the execution of programs, while those of the MPB are placed only to every row and column and are statically partitioned in advance by a fixed length. We show that the RM with n × n processors can be simulated in 0(\frac{n}{m}(\frac{n}{m} + m^{{\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 3}}\right.\kern-\nulldelimiterspace}\!\lower0.7ex\hbox{$3$}}} )\log n\log m) steps by the MPB with m × m processors (m < n). Although the time-complexity of our algorithm is less efficient than that of the fastest RM scaling-simulation algorithm, the simulating model of our algorithm is the MPB model where the bus-reconfiguration is not allowed.
Citation:
Susumu Matsumae, "An Efficient Scaling-Simulation Algorithm of Reconfigurable Meshes by Meshes with Partitioned Buses," ipdps, pp.183b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.