FPGA Floorplanning (1 of 1)

Floorplanning is the process of identifying structures that should be placed close together, and allocating space for them in such a manner as to meet the sometimes conflicting goals of available space (cost of the chip), required performance, and the desire to have everything close to everything else.

Within the Xilinx chips it is often the case that the smallest area design is also the highest performance design. This flies in the face of many design methodologies, where area and speed are considered to be things that should be traded off against each other.

The reason this is so is probably because there are limited routing resources, and the more routing resources that are used, the slower the design will operate. Optimizing for minimum area allows the design to use fewer resources, but also allows the sections of the design to be closer together. This leads to shorter interconnect distances, less routing resources to be used, faster end-to-end signal paths, and even faster and more consistent place and route times. Done correctly , there are no negatives to Floorplanning.

What negatives could there be? Well, if the Floorplanning is done with no regard for the architecture of the chip, then it is possible to actually do a worse job than the Xilinx placer section of the place and route software. It is also possible that there are constraints that are not well understood until placement is complete, and routing commences. So the issue then is what constitutes the "Done correctly".

As a general rule, data-path sections benefit most from Floorplanning, and random logic, state machines, and other non-structured logic can safely be left to the placer section of the place and route software.

Data paths are typically the areas of your design where multiple bits are processed in parallel with each bit being modified the same way with maybe some influence from adjacent bits. Example structures that make up data paths are Adders, Subtractors, Counters, Registers, and Muxes.

Although there are no hard and fast rules to Floorplanning, this section outlines the basic structure for a Floorplanned design, and highlights the issues you need to consider when Floorplanning a design. As described above, Floorplanning has its greatest return when applied to data path elements. The Xilinx XC4000 devices, and all of the derivative families  (the A, D, E, EX, H, L, XL, Spartan, and SpartanXL families) all have the following basic structure:

• A rectangular array of Configurable Logic Blocks (CLBs). These logic blocks contain two main function generators, and two flip-flops. The function generators can represent any number of gates that as a group has no more than 4 inputs, one output, and no internal loops (that would implement latch like behavior). The flip-flops are either rising or falling edge triggered, include a clock-enable function that is implemented with a re-circulation multiplexer from the Q output to the D input, and can have either an active high asynchronous reset or set function. Associated with each CLB are two tri-stateable buffers.
• Segmented interconnect including short interconnect for local signals, and long-lines for spanning the width or height of the chip. In many of the devices, the horizontal long-lines can be split into a left and a right half, allowing up to twice as many lines, that span half the width of the chip.
• The two tri-stateable buffers associated with each CLB are pre-connected to two of the horizontal long-lines.
• Input and Output pins on all 4 sides of the array.
• Pre-built Carry logic that is pre-connected vertically in column of CLBs.

To support these characteristics, consistently implement all data path elements with a bit pitch of two bits per row, and data path elements are always vertical structures, of one or more columns.

The Xilinx FPGAs are biased to have data flow along horizontal interconnect, and to have arithmetic functions operate in vertical columns. The bias comes from the horizontal long lines with tri-stateable buffers, and the vertical pre-built and routed carry logic.

The carry logic is also used to build fast counters, so although you may not initially think of a counter as an arithmetic function, it falls into the same pattern as adders, subtractors, and arithmetic comparisons, because of its use of the carry chain. This view can be clarified by thinking of a counter as an incrementor, followed by a holding register.

The bit pitch of two bits per row is driven primarily by the structure of the carry logic, but is also the bit pitch that the tri-stateable buffers implement. What this means is that the natural structure of arithmetic functions in these devices implements 2 bits of a function (a two bit slice) in one row of CLBs, and for simple functions, in one column. A simple function such as a ten bit synchronous up-counter will therefore take 5 rows and 1 column, a total of 5 CLBs.

Although the XC4000 devices and the A, D, E, H, and L derivatives allow the carry signal between CLBs to interconnect in both an up and down direction within a column, the more recent XC4000EX, XC4000XL, Spartan and SpartanXL devices only support the carry signals being routed up a column. For all devices, within a CLB, the carry routing is up, with regard to the two function generators. It is expected that this up only bias will exist in future products from Xilinx. To be compatible with all these products, you should only uses the up direction for carry, and this bias then affects all other functions that are generated. For the example 10 bit counter described in the previous paragraph, the Floorplan will have bit 0 and 1 in the CLB at the bottom of the column of 5 CLBs, and the top CLB will have bits 8 and 9.

Following Xilinx's standard, the two main function generators are shown on the left of diagrams, and are labeled F and G, and the two flip-flops are shown on the right and are labeled X and Y. For the example counter, in the CLB at the bottom of the five CLB group (the one with the RLOC=R4C0 attribute), the F function generator will be used to implement the logic that feeds the D pin of the X flip-flop, the output of which, is the least significant bit of the counter, Q0. The G and Y sections of the same CLB implement bit 1 of the counter. The next CLB above (the one with the RLOC=R3C0 attribute) implements bit 2 and 3. This continues up the column, through to the top CLB which implements bits 8 and 9.

When two or more functions of your design are Floorplanned in this way and placed side by side, with the signals that flow from one function to the next aligned on the same row, and in near or adjacent columns, the design will place and route much faster and the resulting design will perform faster than a design without Floorplanning, and that relies on the Xilinx place and route software to decide on placement. Of course, custom building each function section of your design with detailed Floorplanning for each function generator and flip-flop can be a complex, time consuming, and potentially error prone process.

The Xilinx Place and Route software uses a hierarchical placement constraint system called relative location attributes. Each level of the hierarchy has an origin in the top left corner that has a relative location of row zero and column zero. As a constraint this is represented as R0C0. Rows are numbered from top to bottom, and columns are numbered from left to right. When a relative location attribute (RLOC) is assigned to a part of the hierarchy that is not a single CLB, then the underlying RLOCs are added to the attached attribute to calculate the RLOC value for each of the underlying RLOCs. This process continues throughout the hierarchy, resolving each CLB RLOC to a value that is relative to the RLOC at the top of the hierarchy. This process, and other issues related to how RLOCs are processed are discussed in full in the Xilinx "Libraries Guide" document, in the "Attributes, Constraints, and Carry Logic" chapter, in the "Relative Location (RLOC) Constraints" section. Although this section of Xilinx's documentation is quite complex, it is recommended that you review it to better understand how the RLOCs in the modules support Floorplanning.

This section examines the results of Floorplanning, and compares the resulting structure, the place and route time, and the design performance. The example while contrived is typical of the types of logic that benefit from Floorplanning. The example design comprises four sixteen bit binary up counters, that all feed into a selection multiplexer. The output of the selection multiplexer is registered, and the output of this register is connected to the FPGA pins.

There are two basic timing path categories that need to be analyzed. The first is the maximum delay in any of the counters. And the second is the maximum delay from any of the counters to the multiplexer output register. For the counter, the maximum delay will be from the clock to out time of the LSB flip-flop, through the logic that establishes the next counter value, to the D input of the MSB flip-flop, and meeting its setup time. The reciprocal of this maximum internal delay within the counter is the maximum clock rate at which the counter will count reliably.

Seven different levels of Floorplanning are applied to this simple design, using the XC4005E, XC4010E, and XC4010XL as targets. The '-2' speed grade is used for all examples, and place and route programs used are as follows:

The combination of running the XC4010E devices with both place and route programs allows comparison of these programs on the XC4000E families. Running both the XC4010E and XC4010XL on the M1.4 program, allows comparison of these two product families. While the goal is to show the value of Floorplanning, the program and product comparisons are interesting.

The same seven levels of Floorplanning were applied to each of these four product/program combinations. The seven design styles have the following characteristics:

To understand the differences in the results for these design styles, the following descriptions of the behavior of the place and route software, as well as an analysis of the device resources should be helpful.

Style 1 uses no Floorplanning or guidance on using the carry logic that is available in these products. The results are consistently the poorest. Style 2 changes the structure of the counters to use carry logic, and for this style through to style 7, the performance and size of the counters does not change much. There is no direct Floorplanning of the counters with regard to their relative placement. While this does not affect the counters, it may not be optimal for the routing from the counters to the multiplexer. As can be seen in the following diagrams, the style 2 designs have placed the counters near each other, but they are not aligned.

Style 3 adds Floorplanning to the counters, and by aligning the counters, the routing to the multiplexer should be more straightforward. This should improve the delays from the counters through the multiplexer to the output register. As can be seen in the diagrams, the multiplexer logic is placed somewhat randomly around the core of the 4 counters.

Style 4 places the output register in the next column to the right of the four counters, and the flip-flops of this register are aligned with the counter bits. Although this should help significantly, it does not, because the 8 logic blocks that hold the 16 flip-flops of the output register do not have sufficient gate resources to implement the 16 four-input multiplexers. Some of the multiplexers are placed with the flip-flops, and some are placed near by.

Style 5 attempts to alleviate the problems with style 4, by moving the output register to the next column to the right, leaving room for the 8 multiplexers that couldn't fit in with the flip-flops. None of the place and route programs take full advantage of this opportunity for improvement.

Style 6 resolves the performance issue of the multiplexer, by replacing it with a Floorplanned multiplexer with output register. This multiplexer performs an additional optimization of not placing all the flip-flops in the same column, but rather, placing the flip-flops with the multiplexers. A four-to-one multiplexer requires all the gate resources of a CLB, so to build a 16 bit wide multiplexer with four inputs will require 16 CLBs. Strictly maintain a Floorplanning structure of two bits of data path implemented per row of structure. The 16 CLBs are Floorplanned to use two columns by eight rows, with bits 0 and 1 on the row at the bottom, and bits 14 and 15 at the top. This exactly matches the bit position of the counters, except the counters have an additional block at the top, for the TC and CEO outputs. This is resolved by placing the counters with RLOC-ORIGINS on row 1, but the multiplexer is placed on row 2.

At this point you may wonder what additional improvement could be made to style 6. Consider the routing from the left most counter to the multiplexer. It must pass through the other three counters to get to the multiplexer. Similarly, the output of counters two and three must also pass through the fourth counter to get to the multiplexer. Therefore, there is more routing congestion around counter four, although it has the shortest path to the multiplexer. The output of the first counter must traverse the furthest distance to get to the multiplexer. In synchronous designs like this, the slowest path out of a group of paths will be the limiting factor. For the counters to run at their fastest, they need to have their routing congestion minimized. For the paths from the four counters to the multiplexer to be minimized, the multiplexer and the four counters need to be placed so as to minimize the worst-case distance. Both of these goals are achieved in style 7 by placing the multiplexer and its output register in the middle of the structure, with two counters to its left, and two counters to its right.

As can be seen from the following tables and diagrams, style 7 delivers the fastest counters, the fastest counter to multiplexer output register time, the fastest placement time, and the fastest routing time. Studying the schematics for design styles 1 and style 7 shows almost no additional effort to create design 7's result. Selecting counters and multiplexers that are pre-Floorplanned, together with five placement attributes is all that is required. (Some thought as to what the placement constraints should be, obviously is also needed)

The full manual has all the pictures for all 8 of the above tables of data. This page only has the pictures for the last table, Which is the M1 PAR V1.4.12, with -L 5 and -D 5, which represent high effort in both placer and router.

At the time of writing this page, the XC4000XL is Xilinx's leading FPGA family, and the M1 PAR version 1.4.12 is the current version of the place and route software.