Michael T. Frederick
Arun K. Somani
ABSTRACT
Look-up table based FPGAs have migrated from a niche technology for design prototyping to a valuable end-product component and, in some cases, a replacement for general purpose processors and ASICs alike. One way architects have bridged the performance gap between FPGAs and ASICs is through the inclusion of specialized components such as multipliers, RAM modules, and microcontrollers. Another dedicated structure that has become standard in reconfigurable fabrics is the arithmetic carry chain. Currently, it is only used to map arithmetic operations as identified by HDL macros. For non-arithmetic operations, it is an idle but potentially powerful resource
This work presents ChainMap, a polynomial-time delay-optimal technology mapping algorithm for the creation of generic logic chains in LUT-based FPGAs. ChainMap requires no HDL macros be preserved through the design flow. It creates logic chains, both arithmetic and non-arithmetic, in an arbitrary Boolean network whenever depth increasing nodes are encountered. Use of the chain is not reserved for arithmetic, but rather any set of gates exhibiting similar characteristics. By using the carry chain as a generic, near zero-delay adjacent cell interconnection structure an average optimal speedup of 1.4x is revealed, and an average relaxed speedup of 1.25x can be realized simultaneously with a 0.95x LUT utilization decrease
- Altera. Stratix Series User Guides. www.altera.com.Google Scholar
- J. Cong and Y. Ding. FlowMap: an optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(1):1--12, 1994.Google ScholarDigital Library
- A. Farrahi and M. Sarrafzadeh. Complexity of the lookup-table minimization problem for fpga technology mapping. IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems, 13(11):1319--1332, 1994.Google ScholarDigital Library
- L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962.Google Scholar
- M. Frederick and A. Somani. Non-arithmetic carry chains for reconfigurable fabrics. In Proceedings of the 15th International Conference on Computer Design, pages 137--143, October 2007.Google ScholarCross Ref
- S. Malhotra, T. Borer, D. Singh, and S. Brown. The quartus university interface program: enabling advanced fpga research. In Proceedings of the 2004 IEEE Int'l Conference on Field-Programmable Technology, pages 225--230, Dec. 2004.Google ScholarCross Ref
- OpenCores. www.opencores.org.Google Scholar
- E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. K. Brayton, and A. L. Sangiovanni--Vincentelli. Sis: A system for sequential circuit synthesis. Technical Report UCB/ERL M92/41, EECS Department, University of California, Berkeley, 1992.Google Scholar
- S. Singh, J. Rose, P. Chow, and D. Lewis. The effect of logic block architecture on fpga performance. Journal of Solid-State Circuits, 27:281--287, March 1992.Google ScholarCross Ref
Index Terms
- Beyond the arithmetic constraint: depth-optimal mapping of logic chains in LUT-based FPGAs
Recommendations
Automated Design of High Performance Integer Arithmetic Cores on FPGA
DSD '15: Proceedings of the 2015 Euromicro Conference on Digital System DesignWe present the principles of operation and functioning of a CAD software tool for the automated realization of high performance integer arithmetic circuits targeting Xilinx Field Programmable Gate Arrays (FPGAs). The key ideas behind the improvement of ...
Compressor tree synthesis on commercial high-performance FPGAs
Compressor trees are a class of circuits that generalizes multioperand addition and the partial product reduction trees of parallel multipliers using carry-save arithmetic. Compressor trees naturally occur in many DSP applications, such as FIR filters, ...
Comments