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

dc.contributor.advisor Arun K. Somani
dc.contributor.advisor Srinivas Aluru
dc.contributor.advisor Akhilesh Tyagi Frederick, Michael
dc.contributor.department Electrical and Computer Engineering 2018-08-22T15:38:45.000 2020-06-30T07:47:06Z 2020-06-30T07:47:06Z Tue Jan 01 00:00:00 UTC 2008 2008-01-01
dc.description.abstract <p>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. ChainMap creates delay-optimal generic logic chains in polynomial time without HDL macros. It maps both arithmetic and non-arithmetic logic chains whenever depth increasing nodes, which 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 chains when cluster resources are abundant and significantly better in cluster-constrained arrays.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 16770
dc.identifier.contextkey 7043031
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/15771
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 20:46:19 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Electrical and Electronics
dc.subject.keywords Electrical and computer engineering;Computer engineering
dc.title Beyond the arithmetic constraint: depth-optimal mapping of logic chains in reconfigurable fabrics
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
18.58 MB
Adobe Portable Document Format