Title :
Some new designs of 2-D array for matrix multiplication and transitive closure
Author :
Tsay, Jong-Chuang ; Chang, Pen-Yuang
Author_Institution :
Inst. of Comput. Sci. & Inf. Eng., Nat. Chiao Tung Univ., Hsinchu, Taiwan
fDate :
4/1/1995 12:00:00 AM
Abstract :
We present some new regular iterative algorithms for matrix multiplication and transitive closure. With these algorithms, by spacetime mapping the 2-D arrays with 2N-1 and upper bound [(3N-1)/2] execution times for matrix multiplication can be obtained. Meanwhile, we can derive a 2-D array with 4N-2 execution rime for transitive closure based on the sequential Warshall-Floyd algorithm. All these new 2-D arrays for matrix multiplication and transitive closure have the advantages of faster and more regular than other previous designs
Keywords :
matrix multiplication; systolic arrays; 2-D array; iterative algorithms; matrix multiplication; sequential Warshall-Floyd algorithm; spacetime mapping; transitive closure; upper bound; Computer science; Councils; Design methodology; Equations; Iterative algorithms; Processor scheduling; Space technology; Systolic arrays; Vectors; Very large scale integration;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
