74 September 2007/Vol. 50, No. 9 COMMUNICATIONS OF THE ACMCOMMUNICATIONS OF THE ACM September 2007/Vol. 50, No. 9 35In the 1950s, computers were built using a variety of components, includ-ing vacuum tubes and relays. These devices had the tendency to burn outduring a computation, which was a significant disruption since the opera-tor had to physically replace the component and restart the computation.There was also a high probability a device would fail intermittently, whichmeant the computations had to be performed multiple times and the resultscompared in order to assure the results were correct. Thus, computer scien-tists of that time, including John von Neumann [12] and Claude Shannon[6]1, began to seriously examine the possibility of building machines thatcould operate perfectly even if their components were defective or unreli-able. This pioneering work slipped into obscurity in the 1960s with theadvent of integrated circuits, which were so trustworthy they were essen-tially flawless. However, after 40 years of refinement, the dramatic shrink-age of the device sizes in integrated circuits is reaching a point where suchquality will no longer be possible. We will soon be back to the point atwhich we will want to know how to build absolutely reliable systems withcrummy [6] components.COMPUTING WITH A TRILLIONCRUMMY COMPONENTSBy Warren Robinett, Gregory S. Snider,Philip J. Kuekes, and R. Stanley WilliamsAttempting to build nanometer-scale circuits that are both defect- and fault-tolerant.1Moore and Shannon provided a technical definition of the word “crummy” with respect to a relay based on the probabilities that itwould fail to open or close properly when required.36 September 2007/Vol. 50, No. 9 COMMUNICATIONS OF THE ACMAt this stage, it is not even certainwhat those components will be.At size scales less than 10nanometers (which is equivalentto approximately 40 silicon-sili-con atomic bond lengths—seethe sidebar “The NanometerChallenge”), the operation of transistors will behighly problematic. It is possible and even likelythat new types of switching devices will be utilizedin future circuits, either in combination with sometransistors or all by themselves. These switches willhave very different operating characteristics fromstandard silicon devices, and they may have operat-ing characteristics similar to the relays used in the1950s—those that are being studied today are builtfrom small clusters of molecules or a very thin layerof an oxide material between two metal electrodes.They are essentially nanometer-sized electrochemi-cal cells—similar to batteries but smaller than avirus—that can be toggled open (high resistance)or closed (low resistance) by placing a potentialacross the device that exceeds a threshold voltage.The opening and closing threshold voltages usuallyhave opposite polarities that drive chemical reac-tions involving only a few molecules or atoms inthe switch, but which change the electrical resis-tance of the device dramatically by four or moreorders of magnitude. The new components, in thisquantity and at this scale, will probably work asdesired, but some will not work at all and otherswill fail at random intervals. We call the com-pletely broken components defects, and the inter-mittent mistakes faults. Our goal is to buildnanometer-scale circuits that are both defect- andfault-tolerant [3], since we cannot replace brokendevices and we prefer not to rerun a computationunless absolutely necessary.Switches can be utilized as the basis for a mem-ory or a logic circuit. The trick is wiring up a hugenumber of them to perform a useful task. Since weanticipate that these switches will eventually be lessthan 10 nanometers (nm) wide, one trillion (1012)of them will fit onto a one-square-centimeter chipsurface. Thus, we will require a large number ofvery small wires to connect up all of these switches.The simplest architecture to accomplish this task isthe crossbar [5], which is a very familiar structurein various types of networks. To connect 1012switches in a single crossbar, one would have onemillion parallel wires spaced 10nm from center tocenter on the bottom crossed over by another mil-lion wires at right angles to the first set, with aswitch at the intersection of each pair of crossingTHE NANOMETER CHALLENGEIn the future, it may be more convenient to allow selected cir-cuit components to form themselves rather than fabricatingthem by using some type of lithography. This image shows aset of parallel wires that are 2nm wide and separated on aver-age by 9nm, just the size that we need to make our trillion-device crossbar. In order to see the wires at all requires aspecial experimental probe called a scanning tunnelingmicroscope (STM), which collects data by raster scanning anextremely sharp needle over a sample and measuring theflow of electrons, called a tunneling current, from the needleto the sample. The measured current vs. position data areturned into a visual image using computer graphics. Thistechnique is so sensitive that one can observe individualatoms, which are evident as the small bumps in the image. These wires are only six atoms wide, and they were formed by aprocess called self-assembly during a chemical reaction between a thin film of vapor-deposited erbium atoms and the atomson the surface of a standard silicon wafer. This image demonstrates that at this scale, matter is not smooth but really ismade of discrete atoms. Just one or two atoms out of place will create a significant defect in a wire.Thermodynamics guarantees such defects will occur, and occur fairly frequently. Just as we have for some time had Ein-stein the traffic cop telling us our signals cannot exceed the speed of light, we now also have Boltzmann the construction fore-man waving the Second Law of Thermodynamics at us, saying we will never get every atom in the desired place. We mustaccept these fundamental physical limits. But just as houses get built imperfectly, yet rarely fall apart, we can “overengineer”our nanoscale computers to tolerate imperfection. Thus, a new set of ground rules for computer design is emerging, and thiswill provide a new set of challenges for the forthcoming generation.cA set of 2nm-wide parallel wires.wires. However, the expenseof ensuring that all of theswitches will operate per-fectly would be astronomi-cal, so in order to keepmanufacturing costs reason-able, a significant fraction(estimated to be ~10% fromprototype