The shortest path problem in graph theory is an abstraction of many practical problems; it arises in many applications in network routing and distributed computing. A regular linear systolic array for computing the all-pairs shortest path in a given graph is presented in this paper. The proposed systolic array has a number of processing elements equal to the number of nodes in the graph. Several issues, like optimal size of the systolic array, the estimation of the execution time, and its optimization by reordering input data items, as well as space optimization, are discussed. A field-programmable gate array (FPGA) implementation of the array was realized, and is also presented in the paper. The clock frequency is experimentally proven to be approximately the same for every node system, a good sign for the device’s efficiency.

The paper is systematically presented and well written. After a short description of the state of the art in systolic arrays, which will be particularly useful for readers who are not specialists in the field, the problem is clearly defined, and the existing approaches using systolic algorithms are discussed in detail. Particular attention is paid to three new systolic algorithms, one of which is proven to be optimal in terms of input issues, and is therefore considered for hardware implementation. Compared with other algorithms that were previously proposed, the selected one supports two-dimensional (2D) data streams. The performance analysis presented in the paper encourages the use of 2D data streams rather than the traditional linear approaches.

Particularly useful for FPGA designers will be the details related to the hardware implementation of the systolic algorithm. Readers who are not familiar with FPGA issues will find this paper interesting, since it follows the full path, from a concrete problem to a solving algorithm, to its efficiency studies and hardware implementation, and, finally, to a performance analysis.