Share Email Print

Proceedings Paper

Digital FPGA implementation for Bellman-Ford computation
Author(s): Wai-ming Fung; Hoi-shing Ng; Kai-pui Lam
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 24 July 2001
PDF: 12 pages
Proc. SPIE 4525, Reconfigurable Technology: FPGAs and Reconfigurable Processors for Computing and Communications III, (24 July 2001); doi: 10.1117/12.434370
Show Author Affiliations
Wai-ming Fung, Chinese Univ. of Hong Kong (Hong Kong)
Hoi-shing Ng, Chinese Univ. of Hong Kong (Hong Kong)
Kai-pui Lam, Chinese Univ. of Hong Kong (Hong Kong)

Published in SPIE Proceedings Vol. 4525:
Reconfigurable Technology: FPGAs and Reconfigurable Processors for Computing and Communications III
John Schewel; Peter M. Athanas; Philip B. James-Roxby; John T. McHenry, Editor(s)

© SPIE. Terms of Use
Back to Top