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
dc.contributor.author	Frederick, Michael
dc.contributor.department	Electrical and Computer Engineering
dc.date	2018-08-22T15:38:45.000
dc.date.accessioned	2020-06-30T07:47:06Z
dc.date.available	2020-06-30T07:47:06Z
dc.date.copyright	Tue Jan 01 00:00:00 UTC 2008
dc.date.issued	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/lib.dr.iastate.edu/rtd/15771/
dc.identifier.articleid	16770
dc.identifier.contextkey	7043031
dc.identifier.doi	https://doi.org/10.31274/rtd-180813-16975
dc.identifier.s3bucket	isulib-bepress-aws-west
dc.identifier.submissionpath	rtd/15771
dc.identifier.uri	https://dr.lib.iastate.edu/handle/20.500.12876/69436
dc.language.iso	en
dc.source.bitstream	archive/lib.dr.iastate.edu/rtd/15771/3337382.PDF\|\|\|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
thesis.degree.level	dissertation
thesis.degree.name	Doctor of Philosophy

File

Original bundle

Now showing 1 - 1 of 1

Name:: 3337382.PDF
Size:: 18.58 MB
Format:: Adobe Portable Document Format
Description:

Download

Collections

Theses and Dissertations