Parallel algorithms for the orthogonal multiprocessor

ABSTRACT

The orthogonal multiprocessor is a partially shared memory architecture. The architecture exhibits attractive characteristics specially with regards to the simplicity of the interconnection network. This architecture proves to be a powerful platform for a large class of scientific problems. A large set of algorithms have been mapped into this architecture including matrix multiplication, fast Fourier transform, sorting, and partial differential equations.The major contribution of this paper is the mapping of two popular algorithms into the orthogonal multiprocessor architecture. The first algorithm is the Jacobi method for evaluating eigenvalues of a symmetric matrix. The second algorithm is image component labeling based on image shrinking operation. Also a discussion of areas of further study for the orthogonal multiprocessor is included.

REFERENCES

• 1: Buehrer, R., Brudiers, H. J., Bens, H., Bron, B., Priess, H., Hale8, W., Halin, H. J., Isacon, A., Tadian, M., The ETH-Multiprocessor EM- PRESS: A Dynamically Configurable MIMD System. IEEE Trans. Comput., vol. 31, pp. 1035- 1044, 1982.
• 2: Cypher, R. E., Sans, J. L. C. and Snyder, L., Practicul Algorithms for Image Component Lsbeling sad SIMD Mesh Connected Computers, in Pvoc, Int. Conf. Parallel Processing 1987, pp. 772-779, 1987.
• 3: Gloub, G., and Van Loan, C., Matrix Computation, North Ozford, Academic Pveu, Offiford, 1983.
• 4: Hwang, K., and Kim, D., Parallel Pattern Clustering on a Multiproeessor with Orthogonally Shared Memory, in Proc. Int. Conf. Parallel Processing 1987, pp. 172-176, 1987.
• 5: Hwang, K., and Kim, D., Generalization of Or- Computation, in Proc. Frontiers Massively Parallel Comput. 88, Fs}rfax, VA, Oct. 11-13, pp. 391-398, 1988.
• 6: K. Hwang , D. Kim , P.-S. Tseng, An Orthogonal Multiprocessor for Parallel Scientific Computations, IEEE Transactions on Computers, v.38 n.1, p.47-61, January 1989 [doi>10.1109/12.8729]
• 7: S. Levialdi, On shrinking binary picture patterns, Communications of the ACM, v.15 n.1, p.7-10, Jan. 1972 [doi>10.1145/361237.361240]
• 8: T. N. Mudge , J. P. Hayes , D. C. Winsor, Multiple bus architectures, Computer, v.20 n.6, p.42-48, June 1987 [doi>10.1109/MC.1987.1663590]
• 9: I. D. Scherson , S. Sen, Parallel Sorting in Two-Dimensional VLSI Models of Computation, IEEE Transactions on Computers, v.38 n.2, p.238-249, February 1989 [doi>10.1109/12.16500]
• 10: I. D. Scherson , Y. Ma, Analysis and applications of the orthogonal access multiprocessor, Journal of Parallel and Distributed Computing, v.7 n.2, p.232-255, October 1989 [doi>10.1016/0743-7315(89)90019-1]
• 11: Tseng, P. S., Hwang, K., and Kumar, V. K. P., A VLSLBased Multiprocessor Architecture for Implementing Parallel Algorithms, in Proc. 13th International Conlerence on Parallel Proceaaing. Aug. 1985., pp. 657-664, 1985.

INDEX TERMS

Keywords:
Jacobi's method, Orthogonal multiprocessor, image component labeling, parallel algorithms