Digital FPGA implementation for Bellman-Ford computation

The binary relation inference network (BRIN) is an architecture for the realisation of the Bellman-Ford and Floyd-Warshall algorithms. It has been used to solve a range of path problems, including shortest path and minimum spanning tree (MST) on graphs. Previous implementation was performed on an analog platform, by connecting op-amp chips externally. However, physical size of circuits would become impractical as the problem size grows. The external connections would also lead to bandwidth problems. The advancement of field programmable gate arrays (FPGAs) in recent years, allowing millions of gates on a single chip and accompanying with high level design tools, has allowed the implementation of very complex networks. With this exemption on manual circuit construction and availability of efficient design platform, the BRIN architecture could be built in a much more efficient way. Problems on bandwidth are removed by taking all previous external connections to the inside of the chip. By transforming BRIN to FPGA (Xilinx XC4010XL and XCV800 Virtex), we implement a synchronous network with computations in a finite number of steps. Two case studies are presented, with correct results verified from both simulation and circuit implementation. Resource consumption on FPGAs is studied showing that Virtex devices are more suitable for the expansion of network in future developments.