An optimal systolic array for the algebraic path problem

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² 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² processing elements