CaltechTHESIS
  A Caltech Library Service

A Greedy Algorithm for Tolerating Defective Crosspoints in NanoPLA Design

Citation

Naeimi, Helia (2005) A Greedy Algorithm for Tolerating Defective Crosspoints in NanoPLA Design. Master's thesis, California Institute of Technology. doi:10.7907/Z5AS-8A57. https://resolver.caltech.edu/CaltechETD:etd-05052005-164226

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%.

Item Type:Thesis (Master's thesis)
Subject Keywords:defect tolerant; molecular electronic; nanoscale design
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • DeHon, Andre
Thesis Committee:
  • Unknown, Unknown
Defense Date:11 May 2005
Record Number:CaltechETD:etd-05052005-164226
Persistent URL:https://resolver.caltech.edu/CaltechETD:etd-05052005-164226
DOI:10.7907/Z5AS-8A57
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1624
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:13 May 2005
Last Modified:07 May 2020 22:59

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

637kB

Repository Staff Only: item control page