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.
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.
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.
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 constructed.
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.
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.
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.
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.