NER: Rules for the Physical Implementation of Computations

提案编号：0404380机构：California institute of technology首席研究员：Martin， alain标题：NER：计算物理实现规则摘要：现代数字芯片是一个复杂的分布式系统，其中许多动作同时执行。到目前为止，这个困难的并发性问题已经通过分发全局计时参考信号（全局“时钟”）和估计每个操作所需的时间来解决，虽然粗糙但很方便。（这些估计对于调度时钟信号是必要的。）这种方法在纳米技术中不起作用，主要是因为由于制造不精确导致的物理参数的变化将使使用全局时间参考太脆弱或太昂贵！因此，纳米技术实现的数字计算很可能是异步的，也就是说，计算步骤的排序和定时将在不参考时钟信号的情况下进行，也可能不知道延迟。这种方法被称为“延迟不敏感”。“这种方法的优点是巨大的，因为延迟的独立性意味着与许多物理参数变化的独立性。但现在的问题是：在物理介质中，将部分有序二进制跃迁（数字计算的低级描述）的集合实现为可证明的等效事件集合（电压跃迁或其他）的要求是什么：深亚微米CMOS芯片、纳米线和纳米管网络、DNA链的细胞复制或其他。特别是，我们如何证明用物理量的连续变化来替换布尔变量上的二进制转换，并能够证明变量在任何时候都有一个定义良好的值。（对于时钟，我们只需要在明确的时刻观察物理量。）我们如何保证信号能够吸收噪声和退化：换句话说，我们如何系统地向系统注入能量以恢复信号？同样，如果没有全局时间参考，我们如何将单个信号（例如门的输出）分配到电路的不同部分，并假设接收到的值在使用它们的时间是一致的？为了构建大型系统，我们需要定义一组规则，以保证遵循规则的任何实现在构建时都是正确的：考虑到此类系统的复杂性，工程师无法对每一个门进行微调，以确保它的行为正确。这些规则将基于计算的数字方面的通用模型，我们认为这既是计算的任何高级表示的方便的“目标代码”，也是与物理设备的“薄”直接接口。这些规则是什么以及如何将它们从一种技术移植到另一种技术是这项探索性研究的主题。我们认为我们可以将深亚微米硅技术的规则正规化，然后将它们首先推广到SiNW和CNT，这要归功于加州理工学院在这一领域的强大活动。

PROPOSAL NO: 0404380INSTITUTION: California Inst of TechPRINCIPAL INVESTIGATOR: Martin , AlainTITLE: NER: Rules for the Physical Implementation of ComputationsAbstract: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 andassume 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.