Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Technology Mapping for Circuit Optimization Using Content-Addressable Memory

Lucas, Joshua Michael (2006) Technology Mapping for Circuit Optimization Using Content-Addressable Memory. Master's Thesis, University of Pittsburgh. (Unpublished)

Primary Text

Download (20MB) | Preview


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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Lucas, Joshua Michaeljmlst79@pitt.eduJMLST79
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairJones, Alex Kakjones@ece.pitt.eduAKJONES
Committee MemberKourtev,
Committee MemberCain, James Tcain@ee.pitt.eduJTC
Committee MemberHoare, Raymondhoare@pitt.eduHOARE
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:, etd-11032005-135126
Date Deposited: 10 Nov 2011 20:03
Last Modified: 15 Nov 2016 13:51


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item