Some combinatorial aspects of parallel algorithm design for matrix multiplication

Author

Tsay, Jong-Chuang ; Yuan, Sy

Author_Institution

Inst. of Comput. Sci. & Inf. Eng., Nat. Chiao Tung Univ., Hsin Chu, Taiwan

Volume

41

Issue

3

fYear

1992

fDate

3/1/1992 12:00:00 AM

Firstpage

355

Lastpage

361

Abstract

Some combinatorial characteristics of matrix multiplication on regular two-dimensional arrays are studied. From the studies, the authors are able to design many efficient varieties of the cylindrical array and the two-layered mesh array for matrix multiplication. To design a cylindrical array for matrix multiplication, a systematic design procedure is proposed. In this design procedure, Latin square (a special type of matrix) plays an important role. To design a two-layered mesh array, it is found that there is a transformation procedure to transform a cylindrical array to a two-layered mesh array

Keywords

combinatorial mathematics; matrix algebra; parallel algorithms; Latin square; combinatorial aspects; cylindrical array; matrix multiplication; parallel algorithm; transformation procedure; two-dimensional arrays; two-layered mesh array; Algorithm design and analysis; Equations; Iterative algorithms; Parallel algorithms; Position measurement; Q measurement; Scheduling; Systolic arrays; Time measurement; Transmission line matrix methods;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.127449

Filename

127449