Some new designs of 2-D array for matrix multiplication andtransitive closure |
| |
Authors: | Jong-Chuang Tsay Pen-Yuang Chang |
| |
Affiliation: | Inst. of Comput. Sci. & Inf. Eng., Nat. Chiao Tung Univ., Hsinchu; |
| |
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: | |
|
|