A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
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.[12]. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.
- 一般社団法人電子情報通信学会の論文
- 1998-05-25
著者
-
Funabiki Nobuo
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
-
Funabiki Nobuo
The Department Of Information And Computer Sciences School Of Engineering Science Osaka University
-
KITAMICHI Junji
the Department of Information and Computer Sciences, School of Engineering Science, Osaka University
-
Kitamichi Junji
The Department Of Information And Computer Sciences School Of Engineering Science Osaka University
関連論文
- Relaxation of Coefficient Sensitiveness to Performance for Neural Networks Using Neuron Filter through Total Coloring Problems
- A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization
- A Massive Digital Neural Network for Total Coloring Problems
- A Minimal-State Processing Search Algorithm for Graph Coloring Problems
- A Binary Neural Network Approach for Link Activation Problems in Multihop Radio Networks
- A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems(Special Section on Discrete Mathematics and Its Applications)