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

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 x₁ − x₂ − x₃, x₁ − x₂ − x₅ − x₆, x₄ − x₅ − x₂ − x₃, and x₄ − x₅ − x₆.

Figure 1.

(a) Four-terminal switch with its ON and OFF states, and (b) Four-terminal switching network implementing the Boolean function x₁x₂x₃ + x₁x₂x₅x₆ + x₂x₃x₄x₅ + x₄x₅x₆