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
```