Caltech Library System

About | Browse | Search | Caltech Student Instructions

Type of Document	Master's Thesis
Author	Naeimi, Helia
Author's Email Address	helia AT caltech.edu
URN	etd-05052005-164226
Persistent URL	http://resolver.caltech.edu/CaltechETD:etd-05052005-164226
Title	A greedy algorithm for tolerating defective crosspoints in nanoPLA design
Degree	Master of Science
Option	Computer Science
Advisory Committee	Advisor Name Title Andre' DeHon Committee Chair
Keywords	molecular electronic defect tolerant nanoscale design
Date of Defense	2005-03-20
Availability	unrestricted
Abstract Recent developments suggest both plausible fabrication techniques and viable architectures for building sublithographic Programmable Logic Arrays using molecular-scale wires and switches. Designs at this scale will see much higher defect rates than in conventional lithography. However, these defects need not be an impediment to programmable logic design at this scale. We introduce a strategy for tolerating defective crosspoints in PLA architecture. We develop a linear-time, greedy algorithm for mapping PLA logic around crosspoint defects. The mapping algorithm matches the PLA logic to the defect configuration of each device. We note that P-term fanin must be bounded to guarantee low overhead mapping and develop analytical guidelines for bounding fanin. We further quantify analytical and empirical mapping overhead rates. Including fanin bounding, our greedy mapping algorithm maps a large set of benchmark designs with 13% average overhead for random junction defect rates as high as 20%.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    main.pdf 637.82 Kb 00:02:57 00:01:31 00:01:19 00:00:39 00:00:03