ISU Electrical and Computer Engineering Archives

Beyond the arithmetic constraint:depth-optimal mapping of logic chains in reconfigurable fabrics

Frederick, Michael (2008) Beyond the arithmetic constraint:depth-optimal mapping of logic chains in reconfigurable fabrics. PhD thesis, Iowa State University.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.


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. Obstacles to using the carry chain for generic logic operations include lack of architectural and computer-aided design support. Current carry-select architectures facilitate carry chain reuse, although they do so only for (K-1)-input operations. Additionally, hardware description language (HDL) macros are the only recourse for a designer wishing to map generic logic chains in a carry-select architecture. A novel architecture that allows the full K-input operational capacity of the carry chain to be harnessed is presented as a solution to current architectural limitations. It is shown to have negligible impact on logic element area and delay. Using only two additional 2:1 pass transistor multiplexers, it enables the transmission of a K-input operation to the carry chain and general routing simultaneously. To successfully identify logic chains in an arbitrary Boolean network, ChainMap is presented as a novel technology mapping algorithm for FPGAs. ChainMap creates delay-optimal generic logic chains in polynomial time and requires no HDL macros. It maps both arithmetic and non-arithmetic logic chains whenever depth increasing nodes, nodes that increase logic depth but not routing depth, 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 a potential average optimal speedup of 1.4x is revealed. Post place and route experiments indicate that ChainMap solutions perform similarly to HDL-based chains when cluster resources are abundant and significantly better than HDL in cluster-constrained arrays.

EPrint Type:Thesis (PhD)
Uncontrolled Keywords:Carry chain, FPGA, depth optimal, technology mapping
Subjects:Computer Engineering > VLSI > VLSI CAD
Research Excellence Awards
Computer Engineering > COMPUTER SYSTEMS ARCHITECTURE > Computer Architecture
Computer Engineering > COMPUTER SYSTEMS ARCHITECTURE > Embedded Systems
ID Code:424
Identification Number:Identification Number UNSPECIFIED
Deposited By:Michael Frederick
Deposited On:24 April 2008

Archive Staff Only: edit this record