Lucas, Joshua Michael
(2006)
Technology Mapping for Circuit Optimization Using Content-Addressable Memory.
Master's Thesis, University of Pittsburgh.
(Unpublished)
Abstract
The growing complexity of Field Programmable Gate Arrays (FPGA's) is leading to architectures with high input cardinality look-up tables (LUT's). This thesis describes a methodology for area-minimizing technology mapping for combinational logic, specifically designed for such FPGA architectures. This methodology, called LURU, leverages the parallel search capabilities of Content-Addressable Memories (CAM's) to outperform traditional mapping algorithms in both execution time and quality of results. The LURU algorithm is fundamentally different from other techniques for technology mapping in that LURU uses textual string representations of circuit topology in order to efficiently store and search for circuit patterns in a CAM. A circuit is mapped to the target LUT technology using both exact and inexact string matching techniques. Common subcircuit expressions (CSE's) are also identified and used for architectural optimization---a small set of CSE's is shown to effectively cover an average of 96% of the test circuits. LURU was tested with the ISCAS'85 suite of combinational benchmark circuits and compared with the mapping algorithms FlowMap and CutMap. The area reduction shown by LURU is, on average, 20% better compared to FlowMap and CutMap. The asymptotic runtime complexity of LURU is shown to be better than that of both FlowMap and CutMap.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| Date: |
31 January 2006 |
| Date Type: |
Completion |
| Defense Date: |
16 August 2005 |
| Approval Date: |
31 January 2006 |
| Submission Date: |
3 November 2005 |
| Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Swanson School of Engineering > Electrical Engineering |
| Degree: |
MSEE - Master of Science in Electrical Engineering |
| Thesis Type: |
Master's Thesis |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
CAM; Content-Addressable Memory; Field Programmable Gate Array; FPGA; Technology Mapping |
| Other ID: |
http://etd.library.pitt.edu/ETD/available/etd-11032005-135126/, etd-11032005-135126 |
| Date Deposited: |
10 Nov 2011 20:03 |
| Last Modified: |
15 Nov 2016 13:51 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/9561 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}