Placing a circuit design on a programmable integrated circuit (IC) refers to the process of assigning components of the circuit design to physical sites, or elements, of the programmable IC. The programmable IC includes a variety of different types of sites, e.g., look-up tables or flip-flops, that may be used to implement various components or combinations of components of the circuit design. For example, one or more logic gates that perform a particular function can be assigned to a particular look-up table (LUT) within a configurable logic block of the programmable IC. To implement the circuit design within the programmable IC, each component must be placed.
To better process the possibly hundreds of thousands of movable components of a circuit design, modern placement techniques utilize abstract models. Some placement techniques utilize a floating point coordinate system representing the programmable IC within which the circuit design will be implemented. Each site on the programmable IC has a particular coordinate in the floating point coordinate system. Components of the circuit design are initially assigned to locations on the programmable IC using the floating point coordinate system. The assigned location, however, may not coincide with available sites on the device. The component, for example, may be initially assigned a location that is between two available sites.
During placement, each component can be “snapped,” or moved, to the nearest site that can accommodate the component being moved. In order for such a technique to yield acceptable results, an underlying assumption must hold true. The assumption is that a significant number of sites able to accommodate the component being moved are available and are nearby the current location of the component. The large number of LUTs and flip-flops in a programmable IC, being arranged in grid-like fashion, ensures that this is the case. While this assumption may hold true for components such as LUTs and flip-flops, it does not hold true for other more complex components referred to as complex function blocks (CFBs).
In general, CFBs refer to components such as block random access memories, digital signal processors, or the like. Typically, a programmable IC has significantly fewer sites for receiving CFBs, as compared to sites that may receive LUTs and flip-flops. For example, there may be only a single column of sites capable of receiving a CFB on the programmable IC, which violates the assumption that, given floating point coordinate, there will always be a nearby site of this type to which the component may be moved. The CFBs of the circuit design must be assigned to the limited number of CFB sites on the programmable IC. Accordingly, it is often the case that conventional placement techniques do not yield satisfactory results when placing CFBs due to the relative scarcity of CFB sites on the programmable IC.