An optimal systolic array for the algebraic path problem
Paul S. Lewis, Sun‐Yuan Kung · IEEE Transactions on Computers · 1991
A systolic array design for the algebraic path problem (APP) is presented that is both simpler and more efficient than previously proposed configurations. This array uses N/sup 2/ orthogonally connected processing elements and requires 2N I/O connections. Total computation time is 5N-2, which is the minimum time possible in a systolic implementation. The data pipelining rate is one, so no pipeline interleave is required. For multiple problem instances a block pipeline rate of N can be achieved, which is optimal for an array of N/sup 2/ processing elements.>