SEGA Routing Results

Last modified September 26, 1997.

The FPGA routing architecture assumed by SEGA in these results is similar to a Xilinx-4000 style FPGA. Namely, there are 3 switches per wire in the S blocks and the C blocks are fully populated (completely connected). However, unlike the Xilinx-4000 FPGAs, all wires are assumed to be the length of a single logic block (ie, no long wires are used). Also, it is sometimes assumed that routing doglegs can be performed at the input pins in a C block.

The figure below shows the FPGA routing model used. As well, details about the lookup table are described here.

How does it measure up?

Comparison to Previous Routers

A set of 9 benchmarks from previous publications is used to compare the effectiveness of the routing tools.

In the graph below, we sum the number of routing tracks required to route each benchmark to get a total channel width.

Comparison to Previous Routers and Placers

In the graph below, the tools are allowed to modify the placement of the logic blocks. Each tool uses it's own placement algorithm, so these results measure the effectiveness of the entire place and route tool chain.

There are two columns of results with the VPR placement. The first column assumes that routing doglegs can only occur at the output (driver) pin. This represents the capabilities of Xilinx and Lucent FPGAs. The second column assumes that routing doglegs are allowed to occur at input and output pins. No array-based FPGA can perform doglegs at input pins, but the row-based Actel FPGAs can. Since input-pin doglegs are not very realistic, we encourage future routing investigators to consider the output-pin dogleg case.

New Results

Text description.

Here is an example of a partially-routed circuit, s298. The multi-point nets have already been broken up into two-point nets, and a few of the long two-point nets are shown as being routed. These two-point nets are quite long, and they appear to meander around the device. This happens because each of these nets are not completely formed. Other connections to other logic blocks, usually consisting of short branches from this long `trunk' line, must still me made. A long path results for some of the two-point nets because the global router, which plans the path, considers the total cost of the multi-point net, not its individual constituents.

Although the two-point net appears to meander, the global router does apply a strict bounding box so the net is not allowed to travel outside of the rectangular region defined by the pins. Also, a penalty cost is applied during global routing to reduce the number of bends.

Raw Data

The routing results are presented below.

NOTE: The data here is identical to what was presented in the ISPD'97 paper. We have since noticed a small problem with our code which computes the clique numbers. For some circuits, the clique numbers reported here (and in the ISPD'97 paper) are too small (by one or two). This happened because some edges in the confronting graph were accidentally ignored. We have computed the true clique numbers now, but have not had time to include them in this web page.

Maximum channel density , given from the global route.

Clique numbers when input-pin and output-pin doglegs are allowed. , given from the global route of the two-point netlist with doglegs.

Clique numbers when only output-pin doglegs are allowed.

Clique numbers when no doglegs at all are allowed.

SEGA routing results when input-pin and output-pin doglegs are allowed.

SEGA routing results when only output-pin doglegs are allowed (input-pin doglegs are NOT allowed).

The web counter says you're visitor