Mapping arbitrary logic functions onto carry chains in FPGAs

Abstract

Current Field Programmable Gate Arrays (FPGAs) provide fast routing links and special logic to perform carry operations; however, these resources can also be used to implement non arithmetic circuits. In this paper, a new approach for mapping logic functions onto carry chains is presented. Unlike other approaches, the proposed technique can be applied to any logic function. The presented technique includes: (1) an architecture that is composed of blocks that implement AND and OR functions (called CANDs and CORs, respectively) by means of Look-Up-Tables (LUTs) and carry-chain resources; and (2) a mapping algorithm to reduce both the delay of the critical path and the number of used FPGA resources. The algorithm uses a heuristic to interconnect CORs and CANDs in order to reduce the delay. The problem of mapping the maxterms (or minterms) of a function to LUTs has been modelled as a Set Bin Packing (SBP) problem. Since SBP is NP-Hard, a greedy algorithm has been proposed, which is based on the First Fit Decreasing (FFD) heuristic. The results obtained have been compared with the conventional technique using both speed and area optimization. For this purpose, a large synthetic set of test cases has been generated. The proposed technique improves both the speed and area results for the vast majority of functions whose conventional implementation requires more than four logic levels. It is important to highlight that the improvement of one parameter (speed or area) is not achieved at the expense of the other.