Optimal simulations between mesh-connected arrays of processors

ABSTRACT

Let G and H be two mesh-connected arrays of processors, where G = g1, X g2 X … X g1, H = h1 x h2 x … x hd, and g1 … g1 ≤ h1 … hd. The problem of simulating G by H is considered and the best possible simulation in terms of the gi's and hi'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.

REFERENCES

• 1: ALELIUNAS, R., AND ROSENBERG, A.L. On embedding rectangular grids in square grids. IEEE Trans. Comput. C-31, 9 (Sept. 1982), 907-913.
• 2: ATALLAH, M.j. Simulations between mesh-connected processor arrays. In Proceedings of the 23rd Annual Allerton Conference on Communication, Control, and Computing (Monticello, Ill., Oct. 2). Univ. of Illinois at Urbana, Urbana-Champaign, Ill., 1985, pp. 268-269. (Also Tech. Rep. 528, Computer Science Dept., Purdue Univ., West Lafayette, Ind., July 1985.)
• 3: BHATT, S., CHUNG, F., LEIGHTON, F. T., AND ROSENBERG, A. L. Optimal simulations of tree machines. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (Toronto, Ont., Canada, Oct.). IEEE Press, New York, 1986, pp. 273-282.
• 4: Richard A. DeMillo , Stanley C. Eisenstat , Richard J. Lipton, Preserving average proximity in arrays, Communications of the ACM, v.21 n.3, p.228-231, March 1978 [doi>10.1145/359361.359447]
• 5: LEISERSON, C.E. Fat-trees: Universal networks for hardware-efficient supercomputing. In Proceedings of the 1985 IEEE International Conference on Parallel Processing (St. Charles, Ill., Aug.). IEEE Press, New York, 1985, pp. 393-402.
• 6: ROSENBERG, A.L. Preserving proximity in arrays. SIAM J. Comput. 4, 4 (Dec. 1975), 443-460.
• 7: ROSENBERG, A.L. Data encodings and their costs. Acta Inf. 9, 3 (May 1978), 273-292.
• 8: Arnold L. Rosenberg, Encoding Data Structures in Trees, Journal of the ACM (JACM), v.26 n.4, p.668-689, Oct. 1979 [doi>10.1145/322154.322160]
• 9: ROSENBERG, A. L., AND SNYDER, L. Bounds on the costs of data encodings. Math. Syst. Theory 12, 1 (Dec. 1978), 9-39.
• 10: SIEGEL, H.J. A model of SIMD machines and a comparison of various interconnection networks. IEEE Trans. Comput. C-28, 12 (Dec. 1979), 907-917.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification