Some types of programmable logic devices (PLDS) (e.g. FPGAs) are implemented with a combination of configurable logic blocks (CLBs) that include lookup tables (LUTs) capable of implementing any function of their input signals, flip-flops for storing data, and dedicated resources such as fast carry chains and cascade structures capable of implementing a limited number of functions. These elements within a CLB can be interconnected to form more complex functions without having to use general routing resources, causing these complex functions to be implemented with less delay. Also, within a CLB, delay is predictable, since there is no unknown routing delay.
Mapping software selects the kinds of resources in the FPGA (or other PLD) that will implement each portion of a user's logic design, and typically attempts to optimize area, delay, or a combination of area and delay when choosing the types of resources. For an FPGA implementation, some conventional mapping software implements combinational logic portions of a user's logic design in a combination of LUTs and dedicated resources, but doesn't take full advantage of the dedicated resources. For example, mapping software may use dedicated fast carry chains to implement the carry portion of an arithmetic function but may not use fast carry chains to implement additional logic functions such as AND, OR, or MUX that these fast carry chains can also implement. In particular, conventional mapping software does not map common sum-of-products (SOP) functions to architectural features such as a combination of fast carry chains, cascade structures, and LUTs that can efficiently implement SOP functions.
Examples of conventional mapping software include Chortle-crf and FlowMap. The Chortle software is described in “Chortle-crf: Fast Technology Mapping for Lookup Table-Based FPGAs” by Robert Francis, Jonathan Rose, and Zvonko Vranesic, proceedings of the Design Automation Conference 1991, pp 227–233. The FlowMap software is described in “FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs” by J. Cong and Y. Ding, IEEE Transactions on CAD, February 1994, vol. 13, No. 1, pp 1–12. Flowmap must map to LUTs of a single size, but given a LUT size, Flowmap can map any given circuit into a network of LUTs.
Mapping software may model area as the total number of LUTs or CLBs required for the mapping, and typically models delay in terms of the number of levels of logic in the path from an input of the design to an output of the design that is determined to be the critical (slowest) path. Chortle-crf attempts to produce a mapping having optimized delay and area, and FlowMap attempts to produce a mapping having optimized delay. Other mapping software focuses on other features of the PLDs to which designs are to be mapped. One such algorithm for multiple sized LUTs is described in a paper by Jianshe He and Jonathan Rose entitled “Technology Mapping for Heterogeneous FPGAs” (1994 ACM International Conference on FPGAs). Another mapping software package described by Jason Cong and Songjie Xu for mapping a design to multiple sizes of LUTs entitled “Delay-Optimal Technology Mapping for FPGAs with Heterogeneous LUTs,” presented at the 1998 Design Automation Conference improves upon the process by He and Rose. Another process for mapping to a plurality of sizes of LUTS is described by Mohan and Chaudhary in U.S. Pat. No. 6,336,208 B1, entitled “Delay Optimized Mapping For Programmable Gate Arrays With Multiple Sized Lookup Tables.”
Conventional methods of mapping don't make full use of the dedicated resources available on a particular architecture. A method that expands mapping considerations to the other dedicated resources in addition to LUTs, as well as addressing other related problems, is therefore desirable.