FPGA Architecture for the Challenge
The FPGA is an array or island-style FPGA. It consists of an array of logic blocks and routing channels. Two I/O pads fit into the height of one row or the width of one column, as shown below. All the routing channels have the same width (number of wires).
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/fpga_structure.gif" /%
Each circuit must be mapped into the smallest square FPGA that can accomodate it. For example, a circuit containing 14 logic blocks and 10 I/O pads would be mapped into an FPGA consisting of a 4x4 array of logic blocks. Note that three of the twenty benchmark circuits used in the FPGA challenge (bigkey, des, and dsip) are pad-limited in this FPGA architecture.
The FPGA logic block consists of a 4-input look-up table (LUT), and a flip flop, as shown below. There is only one output, which can be either the registered or the unregistered LUT output. The logic block has four inputs for the LUT and a clock input. Since the clock is normally routed via a special-purpose dedicated routing network in commercial FPGAs, do NOT route it or include it in your track count results. That is, you can completely ignore the clock net, since it is assumed to be routed on a special global network.
Logic Block Strucuture
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/logic_block.gif" /%
The locations of the FPGA logic block pins are shown below. Each input is accessible from one side of the logic block, while the output pin can connect to routing wires in both the channel to the right and the channel below the logic block.
Logic Block Pin Locations
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/logic_block_pins.gif" /%
Each logic block input pin can connect to any one of the wiring segments in the channel adjacent to it. Each logic block output pin can connect to any of the wiring segments in the channels adjacent to it. (In the usual FPGA terminology, then, Fc = the number of tracks per channel, W). The figure below should make the situation clear.
Logic Block Pin to Routing Channel Interconnect
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/Fc.gif" /%
Similarly, an I/O pad can connect to any one of the wiring segments in the channel adjacent to it. For example, an I/O pad at the top of the chip can connect to any of the W wires (where W is the channel width) in the horizontal channel immediately below it.
The FPGA routing is unsegmented. That is, each wiring segment spans only one logic block before it terminates in a switch box. By turning on some of the programmable switches within a switch box, longer paths can be
Unsegmented FPGA Routing
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/segmentation.gif" /%
Whenever a vertical and a horizontal channel intersect there is a switch box. In this architecture, when a wire enters a switch box, there are three programmable switches that allow it to connect to three other wires in adjacent channel segments. (In terms of the usual FPGA terminology then, Fs = 3.) The pattern, or topology, of switches used in this architecture is the planar or domain-based switch box topology. In this switch box topology, a wire in track number one connects only to wires in track number one in adjacent channel segments, wires in track number 2 connect only to other wires in track number 2 and so on. The figure below illustrates the connections in a switch box.
Switch Box Topology
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/switch_box.gif" /%
Input Pin Doglegs are Not Allowed!
Much of the prior research on FPGA routing architectures has assumed that input pin doglegs are possible. An input pin dogleg occurs when one connects more than one routing wire segment to the same logic block input pin. The input pin dogleg then, allows one to change tracks by connecting two wiring segments to a logic block input pin. Input pin doglegs are not allowed in the FPGA architecture to be used in the challenge; i.e. only one wire segment may be connected to a logic block input pin.
The figure below shows the architecture implicitly assumed when input pin doglegs are allowed. It assumes that connections between logic block pins and routing wire segments are made via independent pass transistors. In this architecture, then, it would be possible to turn on two pass transistors to connect two wire segments via a logic block input pin.
Routing Architecture Required for Input Pin Doglegs (Unrealistic Architecture)
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/dogleg1.gif" /%
However, the routing architecture above is not the routing architecture that is actually implemented by SRAM-based FPGAs. As shown below, commercial SRAM-based FPGAs normally place a buffer between routing tracks and the input pins to which they can connect to enhance speed. As well, to save area, the connection from routing wire segment to input pin is made via a multiplexer, not via a set of independent pass transistors. Accordingly, it is not possible to connect two wire segments together via an input pin, and input pin doglegs are not possible.
SRAM-based FPGAs do not Allow Input Pin Doglegs (More Realistic Architecture)
%img src="http://www.eecg.toronto.edu/%3C/p%3E%0D%0A%0D%0A%3Cp%3Evaughn/challenge/dogleg2.gif" /%
Note that it is possible to connect a logic block output pin to multiple wire segments in commercial FPGAs. Accordingly, such connections are allowed in the FPGA challenge.