Optimal simulations between mesh-connected arrays of processors
S. Rao Kosaraju, Mikhail J. Atallah · Journal of the ACM · 1988
Let G and H be two mesh-connected arrays of processors, where G = g 1 , X g 2 X … X g 1 , H = h 1 x h 2 x … x h d , and g 1 … g 1 ≤ h 1 … h d . The problem of simulating G by H is considered and the best possible simulation in terms of the g i 's and h i 's is characterized by giving such a simulation and proving its optimality in the worst-case sense. Also the same bound on the average cost of encoding the edges of G as distinct paths in H is established.