Table 1: The average wirelength % (normalized w.r.t. KMB) and average maximum pathlength (normalized w.r.t. optimal) for the various algorithms, run over grid graphs with three different levels of congestion.
Average Wirelength and Maximum Pathlength percentage for various congestion levels, over 50 nets
No Congestion (no pre-routed nets), w_avg = 1.00 5-pin nets 8-pin nets
Algorithm Wire Length Max Path Wire Length Max Path (w.r.t KMB) (w.r.t OPT) (w.r.t KMB) (w.r.t OPT)
KMB 0.00 23.51 0.00 40.30 ZEL -6.22 11.07 -7.85 23.42 IKMB -6.47 10.83 -8.19 24.04 IZEL -6.79 8.85 -8.31 21.47 DJKA 29.23 0.00 30.53 0.00 DOM 17.51 0.00 18.48 0.00 PFA -5.59 0.00 -5.02 0.00 IDOM -5.59 0.00 -4.89 0.00 Low Congestion (k=10 pre-routed nets), w_avg = 1.28 5-pin nets 8-pin nets
Algorithm Wire Length Max Path Wire Length Max Path (w.r.t KMB) (w.r.t OPT) (w.r.t KMB) (w.r.t OPT)
KMB 0.00 27.61 0.00 47.66 ZEL -4.64 19.14 -4.10 34.17 IKMB -5.68 17.12 -4.50 33.35 IZEL -5.98 14.56 -5.52 22.29 DJKA 26.64 0.00 32.48 0.00 DOM 22.27 0.00 28.09 0.00 PFA 8.95 0.00 13.91 0.00 IDOM 8.95 0.00 13.91 0.00 Medium Congestion (k=20 pre-routed nets), w_avg = 1.55 5-pin nets 8-pin nets
Algorithm Wire Length Max Path Wire Length Max Path (w.r.t KMB) (w.r.t OPT) (w.r.t KMB) (w.r.t OPT)
KMB 0.00 30.67 0.00 52.67 ZEL -4.37 21.54 -3.35 44.95 IKMB -5.09 17.77 -4.42 42.42 IZEL -5.57 15.26 -4.97 40.20 DJKA 22.94 0.00 36.79 0.00 DOM 21.78 0.00 33.89 0.00 PFA 13.93 0.00 22.65 0.00 IDOM 13.93 0.00 22.59 0.00
====================================================================
Table 2: Complete routing of benchmark circuits on a Xilinx 3000-type part, with switch-block flexibility of 6 and 60% connectivity on the channel edges.
Xilinx 3000-Series Maximum required channel width Circuits for a complete routing
Name FPGA size #nets CGE Ours
busc 12 by 13 151 10 7 dma 16 by 18 213 10 9 bnre 21 by 22 352 12 9 dfsm 22 by 23 420 10 9 z03 26 by 27 608 13 11
Totals: 1744 55 45 Ratios: 1.22 1.00
====================================================================
Table 3: Complete routing of benchmark circuits on a Xilinx 4000-type part, with switch-block flexibility of 3 and 100% connectivity on the channel edges.
Xilinx 4000-Series Maximum required channel width Circuits for a complete routing
Name FPGA size #nets SEGA GPB Ours
alu4 19 by 17 255 15 14 11 apex7 12 by 10 115 13 11 10 term1 10 by 9 88 10 10 8 example2 14 by 12 205 17 13 11 too_large 14 by 14 186 12 12 10 k2 22 by 20 404 17 17 15 vda 17 by 16 225 13 13 12 9symml 11 by 10 79 10 9 8 alu2 15 by 13 153 11 11 9
Totals: 1710 118 110 94 Ratios: 1.26 1.17 1.00
====================================================================
Table 4: Maximum channel width required for a successful routing using the various algorithms.
Xilinx Maximum required channel width 4000-Series for a complete routing Circuits Other Routers Our Router
Name SEGA GPB IKMB PFA IDOM
alu4 15 14 11 14 13 apex7 13 11 10 11 11 term1 10 10 8 9 9 example2 17 13 11 13 13 too_large 12 12 10 12 12 k2 17 17 15 17 17 vda 13 13 12 14 13 9symml 10 9 8 9 8 alu2 11 11 9 11 10
Totals: 118 110 94 110 106 Ratios: 1.26 1.17 1.00 1.17 1.13
====================================================================
Table 5: Percent increase in wirelength and decrease in maximum pathlength for PFA and IDOM (with respect to IKMB) on the benchmark circuits.
Xilinx 4000 Channel Wirelength Max Path Circuits Width PFA IDOM PFA IDOM
alu4 14 20.9 15.8 -15.2 -16.9 apex7 11 15.3 9.2 -4.2 -6.8 term1 9 11.4 12.0 -6.2 -2.0 example2 13 13.1 8.1 -4.6 -5.6 too\_large 12 17.9 15.2 -9.7 -9.4 k2 17 24.5 17.6 -7.1 -7.2 vda 14 18.7 11.9 -9.9 -11.5 9symml 9 18.3 11.4 -14.0 -14.4 alu2 11 23.9 14.1 -14.7 -18.0
Averages: 18.2 12.8 -9.5 -10.2