Optimal simulations between mesh-connected arrays of processors
Authors:
Open Access
- 1 June 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (3) , 635-650
Abstract
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.Keywords
This publication has 6 references indexed in Scilit:
- On Embedding Rectangular Grids in Square GridsIEEE Transactions on Computers, 1982
- A Model of SIMD Machines and a Comparison of Various Interconnection NetworksIEEE Transactions on Computers, 1979
- Encoding Data Structures in TreesJournal of the ACM, 1979
- Bounds on the costs of data encodingsTheory of Computing Systems, 1978
- Preserving average proximity in arraysCommunications of the ACM, 1978
- Data encodings and their costsActa Informatica, 1978