| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Optimal Matrix Multiplication on Fault-Tolerant VLSI Arrays
February 1989 (vol. 38 no. 2)
pp. 278-283
A fault-tolerant array for matrix multiplication that explicitly incorporates mechanisms for easy testability and reconfigurability is described. All signals in the array travel only a constant distance (independent of array size) in any clock cycle. An optimal-time algorithm, designed for multiplying matrices, is described. The algorithm is an efficient simulation of a 2-D systolic algorithm f
[1] 278J. Bentley and T. Ottmann, "The power of one-dimensional vector of processors," Universitat Karlsruhe, Bericht 89, Apr. 1980.[2] B. Chazelle and L. Monier, "A model of computation for VLSI with related complexity results,"J. ACM, vol. 32, pp. 573-588, July 1985.[3] A. L. Fisher, personal communication.[4] W. M. Gentleman, "Some complexity results for matrix computations on parallel processors,"J. ACM, vol. 25, pp. 112-115, 1978.[5] J. W. Greene and A. Gamal, "Area and delay penalties in restructurable wafer-scale arrays,"J. ACM, Oct. 1984.[6] K. S. Hedlund, "Wafer scale integration on parallel processors," Ph.D. dissertation, Comput. Sci. Dep., Purdue Univ., Aug. 1982.[7] A. V. Kulkarni and D. W. L. Yen, "Systolic processing and an implementation for signal and image processing,"IEEE Trans. Comput., vol. C-31, pp. 1000-1009, Oct. 1982.[8] I. Koren, "A reconfigurable and fault-tolerant VLSI multiprocessor array," inProc. 8th Int. Symp. Comput. Architecture, Minneapolis, MN, May 1981, pp. 425-442.[9] H. T. Kung and M. Lam, "Wafer-scale integration and two-level pipelined implementation of systolic arrays," inProc. MIT Conf. Adv. Res. VLSI, Jan. 1984.[10] H. T. Kung and C. E. Leiserson, "Systolic arrays (for VLSI)," inSparse Matrix Proc. 1978, I. S. Duff and G. W. Stewart, Eds., SIAM, 1979, pp. 256-282.[11] F. T. Leighton and C. E. Leiserson, "Wafer-scale integration of systolic arrays,"IEEE Trans. Comput., vol. C-34, pp. 448-461, May 1985.[12] F. P. Preparata and J. E. Vuillemin, "Area-time optimal VLSI networks for multiplying matrices,"Inform. Processing Lett., vol. 11, no. 2, pp. 77-80, 1980.[13] J. I. Raffel, "On the use of nonvolatile programming links for restructurable VLSI," inProc. Caltech Conf. VLSI, Jan. 1979.[14] I. V. Ramakrishnan, D. S. Fussell, and A. Silberschatz, "Systolic matrix multiplication on a linear array," inProc. Twentieth Annu. Allerton Conf. Comput., Contr., Commun., Oct. 1982.[15] I. V. Ramakrishnan and P. J. Varman, "Modular matrix multiplication on a linear array,"IEEE Trans. Comput., vol. C-33, pp. 952-958, Nov. 1984.[16] A. Rosenberg, "The Diogenes approach to testable fault-tolerant networks of processors,"IEEE Trans. Comput., vol. C-32, pp. 902- 910, Oct. 1983.[17] J. E. Savage, "Area-time tradeoffs for matrix multiplication and related problems in VLSI models,"J. Comput. Syst. Sci., vol. 20, no. 3, pp. 230-242.[18] P. Varman and I. Ramakrishnan, "On matrix multiplication using array processors," inProc. Automata, Languages Programming, 12th Colloquium, Nafplion, Greece, July 1985, pp. 487-496.[19] P. J. Varman, "Wafer-scale integration of linear processor arrays," Ph.D. dissertation, The Univ. Texas, Austin, Aug. 1983.[20] P. J. Varman and I. V. Ramakrishnan, "A fault-tolerant VLSI matrix multiplier," inProc. 1986 Int. Conf. Parallel Processing, Aug. 1986, pp. 351-357.
Index Terms:
optimal matrix multiplication; fault-tolerant VLSI arrays; testability; reconfigurability; clock cycle; optimal-time algorithm; simulation; 2-D systolic algorithm; fault tolerant computing; VLSI.
Citation:
P.J. Varman, I.V. Ramakrishnan, "Optimal Matrix Multiplication on Fault-Tolerant VLSI Arrays," IEEE Transactions on Computers, vol. 38, no. 2, pp. 278-283, Feb. 1989, doi:10.1109/12.16505
