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
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb