A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems

Nobuo FUNABIKI; Junji KITAMICHI

A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems

Nobuo FUNABIKI, Junji KITAMICHI

Full Text Views

0

Cite this

Summary :

An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.5 pp.866-872

Publication Date: 1998/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Nobuo FUNABIKI, Junji KITAMICHI, "A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems" in IEICE TRANSACTIONS on Fundamentals, vol. E81-A, no. 5, pp. 866-872, May 1998, doi: .
Abstract: An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_5_866/_p

Copy

@ARTICLE{e81-a_5_866,
author={Nobuo FUNABIKI, Junji KITAMICHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems},
year={1998},
volume={E81-A},
number={5},
pages={866-872},
abstract={An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 866
EP - 872
AU - Nobuo FUNABIKI
AU - Junji KITAMICHI
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1998
AB - An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.
ER -