NER: Rules for the Physical Implementation of Computations

California Institute Of Technology, Pasadena CA

Investigators

Abstract

PROPOSAL NO: 0404380 INSTITUTION: California Inst of Tech PRINCIPAL INVESTIGATOR: Martin , Alain TITLE: NER: Rules for the Physical Implementation of Computations Abstract: A modern digital chip is a complex distributed system where many actions are performed concurrently. So far this difficult concurrency problem has been solved rather crudely but conveniently by distributing a global timing reference signal (the global ``clock'') and by estimating how long each action takes. (The estimations are necessary to schedule the clock signals.) This approach will not work in nanotechnology mainly because the variations of physical parameters due to fabrication imprecision will make the use of a global time reference either too brittle or too costly!. It is therefore very likely that nanotechnology-implemented digital computations will be asynchronous, i.e. the sequencing and timing of the steps of a computation will take place without reference to a clock signal and possibly without knowledge about delays. Such an approach is called ``delay-insensitive.'' The advantages of such an approach are enormous because independence of delay implies independence from many physical parameter variations. But now the question is: What are the requirements to implement a collection of partially ordered binary transitions (a low-level description of a digital computation) into a provably equivalent collection of events (voltage transitions or other) in a physical medium: a deep-submicron CMOS chip, a network or nanowires and nanotubes, a cellular replication of DNA strands, or other. In particular, how do we justify replacing binary transitions on Boolean variables with continuous variations of physical quantities and being able to argue that the variables have a well-defined value at any time. (With a clock, we only need to look at the physical quantities at well-defined moments.) How do we guarantee that the signals are able to absorb noise and degradation: in other words how systematically do we inject energy in the system to restore the signals? Again, without a global time reference, how do we distribute a single signal (say the output of a gate) to different parts of the circuit and assume that the values received are consistent at the times they are used? In order to construct large-scale systems, we need to define a set of rules that guarantee that any implementation that follows the rules will be correct by construction: Given the complexity of such systems the engineer cannot afford to finetune every single gate to make sure that it behaves correctly. Those rules will be based on a universal model of the digital side of the computation that we think is both a convenient ``object code'' of any high-level representation of the computation, and a ``thin'' direct interface to the physical device. What those rules are and how they can be ported from one technology to another is the subject of this exploratory research. We think we can formalize the rules for deep submicron silicon technology and then extrapolate them to first SiNW and CNT thanks to the strong activity in this area at Caltech.