
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A NeuralGreedy Combination Algorithm for BoardLevel Routing in FPGABased Logic Emulation Systems
Nobuo FUNABIKI Junji KITAMICHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E81A
No.5
pp.866872 Publication Date: 1998/05/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: FPGA, boardlevel routing, NPcomplete, digital neural network, greedy algorithm,
Full Text: PDF>>
Summary:
An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the boardlevel routing problem (BLRP) in a logic emulation system based on fieldprogrammable 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 NPcomplete 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 NnetMcrossbar BLRP consists of N M digital neurons of binary outputs and rangelimited nonnegative 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.

