Some new designs of 2-D array for matrix multiplication and transitive closure

摘要

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.