Robust Computation through Percolation: Synthesizing Logic with Percolation in Nanoscale Lattices

Robust Computation through Percolation: Synthesizing Logic with Percolation in Nanoscale Lattices

Mustafa Altun (University of Minnesota, USA) and Marc D. Riedel (University of Minnesota, USA)
Copyright: © 2011 |Pages: 19
DOI: 10.4018/jnmc.2011040102
OnDemand PDF Download:
$37.50

Abstract

This paper proposes a probabilistic framework for digital computation with lattices of nanoscale switches based on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. This phenomenon is exploited to compute Boolean functions robustly in the presence of defects. It is shown that the margins, defined in terms of the steepness of the non-linearity, translate into the degree of defect tolerance. Achieving good margins entails a mapping problem. Given a target Boolean function, the problem is how to assign literals to regions of the lattice such that no diagonal paths of 1’s exist in any assignment that evaluates to 0. Assignments with such paths result in poor error margins due to stray, random connections that can form across the diagonal. A necessary and sufficient condition is formulated for a mapping strategy that preserves good margins: the top-to-bottom and left-to-right connectivity functions across the lattice must be dual functions. Based on lattice duality, an efficient algorithm to perform the mapping is proposed. The algorithm optimizes the lattice area while meeting prescribed worst-case margins. Its effectiveness is demonstrated on benchmark circuits.
Article Preview

Introduction

As current CMOS-based technology is approaching its anticipated limits, research is shifting to novel forms of nanoscale technologies including molecular-scale self-assembled systems (Whitesides & Grzybowski, 2002; Yan, Park, Finkelstein, Reif, & LaBean, 2003). Unlike conventional CMOS that can be patterned in complex ways with lithography, self-assembled systems generally consist of regular structures such as crossbar arrays (Ziegler & Stan, 2003; Eshaghian-Wilner, Flood, Khitun, Stoddart, & Wang, 2006). In particular, with self-assembly, nanoscale technologies are often characterized by high defect rates. A variety of techniques have been proposed for mitigating against defects (Huang, Tahoori, & Lombardi, 2004; Kuekes, Robinett, Seroussi, & Williams, 2005; Sun & Zhang, 2006; Hogg & Snider, 2007; Snider & Williams, 2007).

In prior work, we discussed strategies for implementing Boolean functions with lattices of four-terminal switches (Altun & Riedel, 2010, in press). We addressed the synthesis problem of how best to assign literals to switches in a lattice in order to implement a given target Boolean function, with the goal of minimizing the lattice size, measured in terms of the number of switches. We presented an efficient synthesis algorithm for this task. The algorithm has polynomial time complexity (significantly, it does not exhaustively enumerate paths). It produces lattices with a size that grows linearly with the number of products of the target Boolean function.

In this paper, we address the problem of implementing Boolean functions with lattices of four-terminal switches in the presence of defects. We assume that such defects occur probabilistically. Although not tied to any particular technology, our model could be applicable for emerging technologies such as nanowire crossbar arrays (Cui & Lieber, 2001) and magnetic switch-based structures (Khitun, Bao, & Wang, 2008).

Our approach is predicated on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly, within prescribed error margins.

The paper is organized as follows. In the next section, we present our circuit model, followed by our defect model. We then discuss the mathematics of percolation and how this phenomenon can be exploited for tolerating defects. We examine potential technologies that fit our model. We then present our main technical result: a method for assigning Boolean literals to sites in a switching lattice that optimizes the lattice area while meeting prescribed defect tolerances. We evaluate our method on benchmark circuits.

Circuit Model

Our circuit model consists of regular two-dimensional arrays of four-terminal switches. A four-terminal switch is shown in the top part of Figure 1. It has two states, ON and OFF, that are controlled by a Boolean literal. If the literal takes the value 1 then the four ends of the switch are mutually connected – the switch is ON. If the literal takes the value 0 then the four ends of the switch are mutually disconnected – the switch is OFF. A network of four-terminal switches is shown in Figure 1(b). The Boolean function for the network evaluates to 1 iff there is a closed path between the top and bottom plates of the lattice. It can be computed by taking the sum (OR) of the product (AND) of literals along each path. These paths are x1x2x3, x1x2x5x6, x4x5x2x3, and x4x5x6.

Figure 1.

(a) Four-terminal switch with its ON and OFF states, and (b) Four-terminal switching network implementing the Boolean function x1x2x3 + x1x2x5x6 + x2x3x4x5 + x4x5x6

Complete Article List

Search this Journal:
Reset
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing