A NEURAL-GREEDY COMBINATION ALGORITHM FOR BOARD-LEVEL ROUTING IN FPGA-BASED LOGIC EMULATION SYSTEMS

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-pro grammable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient l ogic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goa l of BLRP, known to be NP-complete in general, is to find a net assign ment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number o f I/O pins designated for each crossbar m is limited in an FPGA. In th e proposed combination algorithm, DNN is applied for m = 1 and MGA is for m greater than or equal to 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N x M digi tal neurons of binary outputs and range-limited non-negative integer i nputs with integer parameters. The MGA is modified from the algorithm by Lin et al. [12]. The performance is verified through massive simula tions, where our algorithm drastically improves the routing capability over the latest greedy algorithms.