18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 7
Efficient Simulation of the Acyclic DR-Mesh on the LR-Mesh
Santa Fe, New Mexico
April 26-April 30
ISBN: 0-7695-2132-0
In this paper we present a simulation of an acyclic n?n DR-Mesh on an n?n LR-Mesh. The simulation is efficient in regards to size since both models use the same number of processors. The worst execution time for this simulation is O(n2) time, but we demonstrate that its average execution time is O(log n). The existing fastest simulation takes O(log n) time, but it uses an extremely large number of processors. On the other hand, the most efficient simulation in terms of size takes O(log2 n) time with O(n4/log2 n) processors. Both of the existing simulations are for the unrestricted DR-Mesh. This paper provides an important step to efficiently simulate the unrestricted DR-Mesh on weaker models such as the RMesh and the LR-Mesh.
Citation:
Jos? Alberto Fern?ndez-Zepeda, Daniel Fajardo-Delgado, Jos? Antonio C?rdenas-Haro, Anu G. Bourgeois, "Efficient Simulation of the Acyclic DR-Mesh on the LR-Mesh," ipdps, vol. 8, pp.173a, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 7, 2004