Nonplanar switchable arrays
Tóm tắt
On-line signal processing and automatic control applications give rise to numerous examples of computationally intense algorithms. Architectures which are algorithmically specialized and provide massive parallelism are necessary to cope with such computational requirements. Systolic arrays, which feature parallelism, local communications, and VLSI compatability appear to match up well with these computational requirements. This paper summarizes recent research on a general class of nonplanar systolic arrays. These arrays feature closed-loop data flow. The arrays may be switched dynamically to facilitate I/O simplicity and to accommodate iterative calculations without intermediate I/O interdiction. The closed-loop data flows also facilitate restructuring of the array to accommodate specific algorithmic requirements. The potential for multiuser, multialgorithm operation is also enhanced. Matrix operations are used as examples in the development. Algorithms as diversified as the Riccati equation, LU factorization, the Faddeev algorithm, FFT calculation, and controllability Grammians can be implemented on the nonplanar architectures.
Từ khóa
Tài liệu tham khảo
Kung, H. T., Why systolic architectures?,Computer,15, 37–46, 1982.
Cappello, P. R., and Steiglitz, K. Unifying VLSI array designs with geometric transformations,Proc. Int. Conf. Parallel Processing, 1983, pp. 448–457.
Fortes, J. A. B., Algorithm transformations for parallel processing and VLSI architecture design, Ph.D. dissertation, University of Southern California, Los Angeles, CA, 1983.
Hwang, K., and Cheng. Y. H., VLSI computing structure for solving a large-scale linear system of equations,Proc. Int. Conf. Parallel Processing, 1980, pp. 217–227.
Kung, H. T., Ruane, L. M. and Yen, D. W. L. A two-level pipelined systolic array for convolutions,VLSI Systems and Computations, pp. 255–264, Computer Science Department, Carnegie-Mellon, 1981.
Liu, K. Y., A pipelined tree machine architecture for computing a multidimensional convolution,IEEE Trans. Circuits and Systems,29, 201–206, 1982.
Wold, E. H., and Despain, A. M., Pipeline and parallel-pipeline FFT processors for VLSI implementation,IEEE Trans. Comput.,33, 414–426, 1984.
Zhang, Ch., and Yun, D., Multidimensional systolic networks for discrete Fourier transforms,Proc. ICCD, pp. 215–222, 1984.
Owens, R. M., and Ja' Ja', J., A VLSI chip for the Winograd prime factor algorithm to compute DFT,IEEE Trans. Acoust. Speech Signal Process.,34, 979–989, 1986.
Aravena, J., Triple matrix product architectures for fast signal processing,IEEE Trans. Circuits and Systems,35 (1), 1988 (to appear).
Nikias, C. L., Chrysafis, A. P., and Venetsanpoulos, A. N., The LU decomposition theorem and its implication to the realization of 2-D digital filters,IEEE Trans. Acoust. Speech Signal Process.,33, 694–711, 1985.
Guo-Jie, L., and Wah, B., The design of optimal systolic arrays,IEEE Trans. Comput.,34, 66–77, 1985.
Horowitz, E., VLSI architecture for matrix computations,Proc. Int. Conf. Parallel Processing, 1979, pp. 124–127.
Hwang, K., and Cheng, Y. H. VLSI computing structure for solving large-scale linear system of equations,Proc. Int. Conf. Parallel Processing, 1980, pp. 217–227.
Montoye, R. K., and Lawrie, D. H., A practical algorithm for the solution of triangular systems on a parallel processing systems,IEEE Trans. Comput., 1980.
Porter, W. A., and Aravena, J. L., Cylindrical arrays for matrix multiplication,Proc. 24th Allerton Conf., 1986.
Kung, S. Y.,et al., Wavefront array processor: language, architecture and applications,IEEE Trans. Comput.,31, 1982.
Kung, S. Y., On supercomputing with systolic/array processors,Proc. IEEE,72, 531–548, 1984.
Martin, A. J., The torus: an exercise in constructing a processing surface,Proc. VLSI Conf., 1981.
Sequin, C. H., Double Twisted Torus Network for VLSI Processors Arrays, Computer Sciences Division, University of California, Berkely, 1981.
Johnsson, S. L., Dense matrix operations on a torus and a Boolean cube,AFIPS Proc. Nat. Comput. Conf., 1985, pp. 307–318.
Snyder, L., Introduction to the configurable highly parallel computer,Computer,15, 47–56, 1982.
Gollakota, N. S., and Gray, F. G., Reconfigurable cellular architecture,Proc. ICCD, 1984, pp. 377–379.
Khurshid, A., and Fisher, P. D., Design of a reconfigurable systolic array using LSSD techniques,Proc. ICCD, 1984, pp. 171–175.
Choi, Y., Han, S. H., and Malek, M., Fault diagnosis of reconfigurable systolic arrays,Proc. ICCD, 1984, pp. 451–455.
Pradhan, D. K., Dynamically restructurable fault-tolerant processor network architectures,IEEE Trans. Comput.,34, 434–447, 1985.
Porter, W. A., Nonplanar array processing,Proc. 20th Asilomar Conf., 1986, pp. 595–602.
El-Amawy, A., Porter, W. A., and Aravena, J. L., Array architectures for iterative matrix calculations,Proc. IEE-E,134, 149–154, 1987.
Kak, S., Mesh architectures (Private communication).
El-Amawy, A., A systolic architecture for optimal filter design support,Circuits Systems Signal Process., this issue, 151–172, 1988.
Porter, W. A., and Aravena, J. L., Array resolutions of linear maps,Circuits Systems Signal Process.,6, 127–137, 1986.