EFFICIENT SIMULATION OF AN ACYCLIC DIRECTED RECONFIGURABLE MODEL ON AN UNDIRECTED RECONFIGURABLE MODEL.

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(logn). The fastest existing simulation takes O(logn) time, but it uses an extremely large number of processors. On the other hand, the most efficient simulation in terms of size takes O(log2n) time with O(n4/log2n) processors. Both of the existing simulations are for the unrestricted DR-Mesh. This paper provides an important step towards efficiently simulating the unrestricted DR-Mesh on weaker models such as the R-Mesh and the LR-Mesh. [ABSTRACT FROM AUTHOR]