A family of efficient regular arrays for algebraic path problem

Author

Chang, Pen-Yuang ; Tsay, Jong-Chuang

Author_Institution

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

Volume

43

Issue

7

fYear

1994

fDate

7/1/1994 12:00:00 AM

Firstpage

769

Lastpage

777

Abstract

The method of decomposing a dependence graph into multiple phases with an appropriate m-phase schedule function is useful for designing faster regular arrays for matrix multiplication and transitive closure. In this paper, we further apply this method to design several parallel algorithms for the algebraic path problem and derive N×N 2D regular arrays with execution times [9N/2]-2 (for the cylindrical array and the orthogonal one) and 4N-2 (for the spherical one)

Keywords

computational complexity; graph theory; matrix algebra; parallel algorithms; systolic arrays; VLSI architecture; algebraic path problem; cylindrical array; dependence graph decomposition; efficient regular arrays; execution times; m-phase schedule function; matrix multiplication; multiple phases; orthogonal array; parallel algorithms; spherical array; systolic array; transitive closure; Algorithm design and analysis; Design methodology; Iterative algorithms; Matrix decomposition; Parallel algorithms; Phased arrays; Pipeline processing; Processor scheduling; Systolic arrays; Very large scale integration;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.293256

Filename

293256