Digital FPGA implementation for Bellman-Ford computation

W. Fung*, H. Ng, K. Lam

*Awdur cyfatebol y gwaith hwn

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddCyfraniad mewn cynhadleddadolygiad gan gymheiriaid

Crynodeb

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.

Iaith wreiddiolSaesneg
TeitlProceedings Volume 4525, Reconfigurable Technology: FPGAs and Reconfigurable Processors for Computing and Communications III
Is-deitlITCom 2001: International Symposium on the Convergence of IT and Communications, 2001
Tudalennau76-87
Nifer y tudalennau12
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 24 Gorff 2001
Cyhoeddwyd yn allanolIe
DigwyddiadReconfigurable Technology: FPGAs and Reconfigurable Processors for Computing and Communications III - Denver, CO, Yr Unol Daleithiau
Hyd: 21 Awst 200122 Awst 2001

Cynhadledd

CynhadleddReconfigurable Technology: FPGAs and Reconfigurable Processors for Computing and Communications III
Gwlad/TiriogaethYr Unol Daleithiau
DinasDenver, CO
Cyfnod21/08/0122/08/01

Dyfynnu hyn