S. Rao Kosaraju
Mikhail J. Atallah
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.
- 1 ALELIUNAS, R., AND ROSENBERG, A.L. On embedding rectangular grids in square grids. IEEE Trans. Comput. C-31, 9 (Sept. 1982), 907-913.Google Scholar
- 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.)Google Scholar
- 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.Google Scholar
- 4 DEMILLO, R. A., EISENSTAT, S. C., AND LIPTON, R.J. Preserving average proximity in arrays. Commun. ACM 21, 3 (Mar. 1978), 228-231. Google Scholar
- 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.Google Scholar
- 6 ROSENBERG, A.L. Preserving proximity in arrays. SIAM J. Comput. 4, 4 (Dec. 1975), 443-460.Google Scholar
- 7 ROSENBERG, A.L. Data encodings and their costs. Acta Inf. 9, 3 (May 1978), 273-292.Google Scholar
- 8 ROSENBERG, A.L. Encoding data structures in trees. J. ACM 26, 4 (Oct. 1979), 668-689. Google Scholar
- 9 ROSENBERG, A. L., AND SNYDER, L. Bounds on the costs of data encodings. Math. Syst. Theory 12, 1 (Dec. 1978), 9-39.Google Scholar
- 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.Google Scholar
Index Terms
- Optimal simulations between mesh-connected arrays of processors
Recommendations
Multithread Reconfiguration Algorithm for Mesh-Connected Processor Arrays
PDCAT '12: Proceedings of the 2012 13th International Conference on Parallel and Distributed Computing, Applications and TechnologiesMesh-connected processor array is a popular architecture used in parallel processing. Extensive studies have been conducted on reconfiguration algorithms for the processor arrays with faults, but few work is on parallel algorithm to accelerate the ...
Fragmented coprime arrays with optimal inter subarray spacing for DOA estimation: Increased DOF and reduced mutual coupling
AbstractSparse arrays possess attractive features compared to uniform linear arrays (ULAs) with increased degrees of freedom (DOFs), reduced mutual coupling, and enlarged array aperture, which improves the estimation performance of arrays. Recently, ...
Highlights- A fragmented coprime array concept is introduced to enlarge array aperture.
- Provide the location of holes in the difference coarray of FCAs.
- Two missing interlayer subarrays fills the holes in the difference coarray of FCAs.
- ...
Comments