Efficient simulation of the acyclic DR-mesh on the LR-mesh
José Alberto Fernández‐Zepeda, Daniel Fajardo‐Delgado, José Antonio Cárdenas-Haro, A.G. Bourgeois · 2004
Summary form only given. We present a simulation of an acyclic n/spl times/n DR-Mesh on an n/spl times/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(n/sup 2/) 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(log/sup 2/ n) time with O(n/sup 4//log/sup 2/ 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 R-Mesh and the LR-Mesh.