To provide routing support for LEBs, the router PathFinder negotiated congestion-delay algorithm, did not need to be modified. The only modification required was to the routing graph which represented the FPGA routing architecture. As described in [Betz1997] the VPR router performs routing on a routing resource graph that represents the FPGA which is generated from the architectural specification. When modifying the routing resource generator to provide LEB routing support, we ensured that other routines using the routing resource graph could interpret any new modifications. The position of the routing resource graph generator in the VPR flow is shown in Figure 1.

Figure 1. Routing resource graph in the VPR flow

The routing resource graph is a directed graph, whose nodes are conducting routing resources (such as pins, wire segments etc.) and edges are potential connections (switches). There are six routing resource (rr) node types: source, sink, input-pin, output-pin, chan-x (horizontal) wire segment, chan-y (vertical) wire segment. Pins can be logically equivalent which are reflected by source and sink rr nodes. The source and sink nodes are not physical entities, but are devices to represent the logical equivalence of pins. A source/sink rr node (called a pin class) is present for each group of logically equivalent output/input pins, respectively. Each source rr node has outgoing edges to rr nodes of all output pins in its class, and each sink rr node has incoming edges from rr nodes of all input pins in its class. An example rr graph is shown in Figure 2.

Figure 2. Example of a simple routing resource graph

For routing, single width and multiple height LEBs (Nx1) are supported. The upgrades to rr graph generator and decisions we made to support LEBs, are presented in the following sections.

Since VPR originally had to deal with CLBs of unit width and height, the rr nodes are grouped by their position (i, j) in the FPGA grid (wire segments that span multiple positions, belong to their starting position (i, j) group). To support LEBs that span multiple vertical positions, this grouping convention gives problems. We made the choice to group all of the LEB’s source, sink, and pins rr nodes at the head LEB block (offset 0, see Figure 3.). However, this does not mean that the pins are all physically located in the head LEB block. The architect specifies pin physical locations, and the locations are properly reflected in data structures described later on.

Figure 3. The head (offset 0) and part block (offset 1) of a 2x1 LEB

To properly reflect the physical locations of the LEB pins, we adopted the following convention. We refer to the outer edges of the LEB, that span 1 grid position, unit sides (usides). These are the edges, on which LEB pins can be specified. For example, a 2x1 LEB has 6 usides: top, bottom, left0, left1, right0, and right1, as shown in Figure 4.

Figure 4. The 6 usides of 2x1 LEB

To reflect that LEB pins are physically located at various parts of the LEB (not just the head block), data structures leb_opin_to_tracks and leb_ipin_to_tracks are created, to keep track of which uside(s) each LEB pin is located and the tracks it can connect. The rr graph generator uses this information extensively. When an output pin (opin) rr node is being created, the generator looks up leb_opin_to_tracks to determine where that output pin is physically located (hence determine that pin’s adjacent channel segment), and which tracks in the adjacent channel segments are connectable to it.

Similarly, when an wire segment rr node is being created, the generator looks up leb_ipin_to_tracks (actually a modified version of it called tracks_to_leb_ipin) to determine which uside this wire segment is adjacent to and, hence which LEB input pins are connectable to that wire segment.

For a wire segment of length >1, the rr graph generator steps through each channel segment it spans where it connects the segments to other wire segments and adjacent pins. As mentioned previously, when a wire segment passes an uside of a LEB, the generator finds the LEB input pins adjacent to that wire segment using tracks_to_leb_ipin. However, if a wire segment goes through the LEB (horizontally cross inside the LEB as shown in Figure 5.), it is not passing any LEB usides. A problem may arise where if the architect specified that there is a connection block at that position, the rr graph generator would attempt to connect the wire segment to LEB pins in that channel segment which is clearly illegal. This is because we decided that no pins can exist inside the LEB. In this situation, we made sure the rr graph generator would not attempt to connect the wire segment to any LEB pins in that channel segment, even if there is a connection block.

Figure 5. Connection blocks not allowed inside LEBs

The number of clusters required for the circuit determines the FPGA array size. However, the architect arbitrarily chooses the LEB height. Hence, sometimes, a LEB column may be incompletely filled. For example, a 23x23 array, containing columns of height 2 LEBs, would have 1 grid position unfilled for each LEB column. This is illustrated in the Figure 6.

Figure 6. Incompletely filled LEB columns contain empty blocks

Two alternatives exist for handling the unfilled positions: 1) have CLBs in those positions and 2) have empty blocks (no logic, but routing tracks exist in adjacent channels). Both alternatives are equally realizable for the rr graph generator. However, for placer concerns and to be consistent with today’s embedded FPGA architectures, such as the Xilinx Virtex-II [Xilinx2005] and Altera Stratix II [Altera2005] architectures, we decided on alternative 2. To implement this model, we disallow any connection blocks to empty blocks.

The switch pattern of connection blocks for LEBs is based on the uniform switch pattern used for CLBs. We distributed all LEB input/output pins evenly across the tracks. This ensures that each pin connects to spaced out tracks in its connection block and that the other pins (potentially in other connection block) connect to the remaining tracks first. Distributing pins evenly leverages the fact that usually lots of pins are logically equivalent. This improves routibility. The same switch pattern is applied to input and output pins.

To support LEB in VPR routing, only the routing resource graph generator had to be modified. Since the VPR router algorithm was not changed, we didn't conduct experiments to test the effect of any router parameter. We could have experimented with architectural parameters such as LEB connection block flexibility, but due to the limited time to complete this project we did not run any architectural experiments.

We did, however, run our modified VPR to map a number of MCNC benchmark circuits to validate that the router correctly supports LEBs. The LEB architecture we used contained three LEB columns spread evenly across the chip where each LEB was 2x1 in size. First, we placed and routed each circuit with CLBs only and compared the final route quality against the LEB modified circuit. The modified circuits contained approximately 15% LEB content. When generating LEBs, we select random CLB pairs and join them to form one LEB. This process is described in detail here. This LEB generation ensures the total pin and net count of circuit is not changed, hence the routing demand of the circuit is the same with or without LEBs. The placement algorithm used is bounding_box, the router algorithm used is breadth_first, and the router is asked to route with a very high channel width (W=1000). The test is meant to find out whether the circuit containing LEBs can be routed which validates the correctness of the LEB modifications.

Only eleven circuits completed, due to lack of time. The first circuit, 5xp1 result is erased because the LEB generation did not generate any LEBs in the netlist due to its small size.

The routed circuits show that the total wiring segments used increased by an average of 5.50% (averaged over 9 circuits that contained LEBs). The 2x1 LEBs are generated from merging 2 CLBs, which preserves the total pin and net count. Therefore the routing demand of the circuit compared to the CLB only netlist should be the same. The increase in wiring segments used by circuit netlist containing LEBs indicate that having LEBs resulted in worse final route quality. To explain the loss in final route quality, consider the fact that each 2x1 LEB is essentially two CLBs that are forced to be placed adjacent to each other. This limits the placer's ability to optimize for wire length, hence the final route quality is lowered.

The elliptic circuit didn't route at all. This failure indicates an issue in the rr graph generator. Upon reviewing the modifications, we believe this failure comes from the LEB connection block switch pattern design. Because we chose to use the same switch pattern for input and output pins, we possibly could be building pathologically bad switch topologies in which it is impossible to route from certain output pins to certain input pins. This is particularly true when one uses subset/domained switch block switching topology, as we did by default. This failed case requires us to further test and ensure LEB connection blocks do not have pathologically bad switch topologies.

Despite the failed test case, the majority of tests yielded successful results giving us confidence to say that the rr graph generator is creating rr graphs that support circuits containing LEBs. These circuits are routable if no pathologically bad connection block switch topologies exist.

Last updated Dec 2005