平博88s代表计数器状态

 公司新闻     |      2019-10-07 06:15

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  4状态异步细胞自动机通用计算能力证明 摘 要 细胞自动机是一种离散的模型,能够完成复杂计算和模拟自然界的现象变化。作为细胞自动机的一种,异步细胞自动机在细胞演化时是不需要统一时钟控制的,对其研究要比同步细胞自动机复杂得多。作为对异步细胞自动机计算能力研究的一个重要方式,模拟同步细胞自动机演化是一种很好的方式。细胞自动机的本质通用性使得一个细胞自动机能够模拟另一个细胞自动机。生命游戏是最著名的同步细胞自动机,因其简单的控制规则和展现复杂的特性使得对其研究不断增多,如自我复制,超平行计算能力,以及在仿生学中的重要作用。特别的已经存在Moore相邻条件下的8状态下异步细胞自动机对生命游戏的模拟,但是利用了上百条状态转换规则。如果要模拟一个细胞自动机,那么其状态转换规则的计算是必不可少的,本文利用延时不敏感电路是异步电路的一种,在计算正确性和电路设计上的特性,同时能很好地嵌入到异步细胞自动机中的特性,设计了具备计算生命游戏状态转换规则的延时不敏感电路,可以有规则的在细胞自动机空间中摆放电路模块。然后利用几十条状态转换规则分别在von Neumann相邻条件下的4状态和5状态异步细胞自动机上模拟生命游戏演化。 虽然不同状态下模拟的生命游戏细胞配置大小不同,但是其最终模拟结果是一样的。von Neumann相邻条件下4状态异步细胞自动机的计算能力虽然已经被证明出,但是其计算能力是有限的,本文通过在其上模拟生命游戏,为证明其通用计算能力和超并行计算能力提供了一种便捷的方法。 关键字:异步细胞自动机,延时不敏感电路,生命游戏,通用计算能力,本质通用性 Abstract Cellular Automata is a discrete model, that could complete complex computing and simulate phenomena of natural. So as a kind of cellular automata, Asynchronous Cellular Automata(ACA) evolution without central clock make it more difficult to study. Emulating transition of synchronous Game of Life in Asynchronous Cellular Automata is an approach to demonstrate its computational universality. Intrinsically universal of cellular automata makes a cellular automata to simulate another cellular automata, Game of Life (GL) is one of the most famous Cellular Automata for its simple transition rules with complex behavior, such as self-replication, massive parallel computation and simulation in bionics. especially there exists completely simulation of GL under 8-states Asynchronous Cellular Automata with Moore neighborhood and hundreds of transition rules. To simulate a cellular automata one has to simulate transition rules of cellular automata also information transfer among cells. In this paper, we design a Circuit which could compute transition rules of GL and information transfer among cells, the circuit is Delay-Insensitive Circuit(DI-Circuit) that has been proved its computing universal with computational correctness and facility in design. The DI-Circuit is so-well embedded in ACA that we can simulate GL cell by the circuit with uniformly array. We simulate evolution of GL in 5-state and 4-state ACA with von Neumann neighborhood and tens of transition rules, separately. Even though, space consumption, to emulate cell of GL, is different in different cellular automata, but the result is no different in global evolution. 4-state Cellular Automata with von Neumann neighborhood have been proved its computing ability, In this paper we can achieve the computational universal and parallel computing of 4-state ACA by simulate GL. Key Words: Asynchronous Cellular Automata, Delay-Insensitive Circuit, Game of Life, Computing universal, Intrinsic Universal 目 录 摘要 1 Abstract 2 目录 3 1 绪论 4 1.1研究背景 4 1.2研究现状 5 1.3研究内容意义 6 1.4论文结构 7 2 细胞自动机 7 2.1细胞自动机定义 7 2.2细胞自动机的特性 9 2.2.1 细胞自动机的计算能力 9 2.2.2 细胞自动机的本质通用性 10 2.3 生命游戏 12 2.3.1生命游戏演化模式 12 2.3.2生命游戏通用计算能力 13 2.4本章小结 14 3 延时不敏感电路 15 3.1延时不敏感电路及定义 15 3.2双向缓冲延时不敏感电路 19 3.2 本章小结 23 4 生命游戏嵌入到5状态异步细胞自动机 24 4.1延时不敏感电路在5状态ACA下配置 24 4.2 计数器设计及5状态ACA下配置 26 4.3解析器设计及5状态ACA下配置 32 4.4 DI电路模块构成生命游戏细胞及在4状态ACA下配置 34 4.5同步器设计及5状态ACA下配置 37 4.6在5状态ACA中模拟生命游戏简单演化 39 4.7 本章小结 41 5 生命游戏嵌入到4状态异步细胞自动机 42 5.1 延时不敏感电路在4状态ACA下的配置 42 5.2计数器及其在4状态ACA下配置 44 5.3解析器及其在4状态ACA下配置 45 5.4 DI电路构成的生命游戏细胞及其在4状态ACA下配置 46 5.5同步器及其在4状态异步细胞自动机中配置 46 5.6生命游戏嵌入到4状态ACA中 47 5.7 本章小结 47 6 总结 51 致谢 52 参考文献 53 1 绪论 1.1研究背景 细胞自动机作为计算模型的一种,有能力高效的完成复杂计算,同时模拟自然界的复杂系统,由于这些原因,细胞自动机及其相关的模型被广泛研究,并取得不错成果应用到实际当中,如在自然科学,数学,计算机科学中被广泛研究,在物理学和生物学中被用来模拟现象,如液体流动,气体形成,地震,生物模式形成等现象。利用细胞自动机的平行计算能力模拟高速的科学模型和图像上处理,数字加密等,同时细胞自动机还被用来当作复杂系统中行为收集等。 随着大规模集成电路的发展,在同步电路占主导地位的电子器件中能量消耗问题和计算速度问题变得越来越突出,因其需要统一时钟控制,虽然在实时性上对处理速度的提升有较大作用,但是在大规模电路情况下其时钟延时和能量消耗问题变得越来越严重,相反异步电路在电路设计中不需要时钟控制而是把时钟控制信号细化到模块间的信息同步,同时在每个模块和传输线允许的延时下,电路的计算能力和平均计算速度是很高的。 异步细胞自动机作为细胞自动机的一种模型,模拟同步细胞自动机的演化是证明异步细胞自动机计算能力的一中便捷的方式。在细胞空间中按照统一方式摆放好细胞块,将能够计算细胞转换规则的配置放进块中,使得模拟同步细胞成为可能。延时不敏感电路作为异步电路的一种,能够很好的嵌入到异步细胞自动机中,利用其在计算上的特性从而证明异步细胞自动机的计算能力。 所以,设计具备细胞状态转换规则的电路,然后嵌入到细胞自动机中,是异步细胞自动机模拟同步细胞自动机的一种便捷的方式,同时可以间接证明异步细胞自动机的许多特性。 1.2研究现状 细胞自动机(Cellular Automata-CA)是由一组相同的细胞构成的离散动态系统,细胞之间局部互联,是有限自动机的一种[1][2],最初由von Neumann提出并证明其超并行计算能力。绝大多数细胞自动机假设所有的细胞在同一中央时钟的控制下,根据变换规则来改变自身状态,我们称这类细胞自动机为同步细胞自动机( Synchronous Cellular Automata-SCA),简称CA。相对的,异步细胞自动机(Asynchronous Cellular Automata-ACA )则允许各个细胞根据变换规则在任意时间独立的改变自身状态。由于缺少中央时钟的统一控制,异步细胞自动机在状态变化时会产生不可预测的全局行为[3],因此一种便捷的策略是利用时钟机制强制所有的细胞的同步性来实现异步细胞自动机的计算[4][5][6],在模拟同步细胞自动机的全局变换特性同时,是以细胞状态和变换规则数量急剧扩张为代价得来的。文章[6]展示的异步生命游戏(Asynchronous Game of Life)模拟著名的同步生命游戏[7],就用到了8个细胞状态和上百个变换规则。 然而证明异步细胞自动机计算能力的一种更高效的方法被发现了,即直接将异步电路直接嵌入到异步细胞自动机中[8][9][10],例如文章[10]展示了在von Neumann相邻条件下的异步细胞自动机能够构建任意延时-不敏感电路(Delay-Insensitive Circuit-DI-Circuit) ,同时说明了异步细胞自动机的计算普适性和平行计算能力。文章中用到的细胞状态数为5,变换规则数量为55,在数量上明显少于异步生命游戏。在文章[23]中展示了在von Neumann相邻条件下4状态异步细胞自动机的通用计算能力。 延时不敏感电路是一类特殊异步电路,不因模块的延时或信号在传输线中的延时而影响其正确性。异步电路是有限输入和输出的模块化系统,模块通过信号在输入输出线与外界通信。每个传输线代表一个单值信号。 Keller在文章[11]中规划了几条延时不敏感电路的操作条件,任意由符合条件的延时不敏感电路模块构成的带有外部输入输出的电路都可视为延时不敏感电路模块。特别的,Keller提出的条件中都不允许在一根互交线上同时出现两个信号。如果有两个信号出现在了一根互交线上,那么第二个信号只会在第一个信号被接受后才会出现,所以必须对第一个输入信号对应一个输出信号,以保证延时不敏感的特性。在文章[14]中重新定义了一组具有通用计算能力的DI电路模块,这组电路模块需要更少的输入输出线,同时能够完成平行计算能力。 与传统逻辑电路相似,任意延时不敏感电路都可由一组固定的延时不敏感电路基础模块构成。基础模块包括MERGE,P-MERGE、FORK、IOM和S-JOIN,虽然这几个模块不能构建所有的延时不敏感电路,但是它们能够完成生命游戏细胞的逻辑功能。 1.3研究内容意义 虽然von Neumann相邻条件下4状态异步细胞自动机的计算能力在文章[23]中通过将有限的延时不敏感电路模块嵌入证明了其计算能力,但是这些模块无法证明其通用计算能力。本文就利用细胞自动机的本质通用性和其通用计算能力的特性,在von Neumann相邻条件下4状态异步细胞自动机上模拟生命游戏演化,而生命游戏已经被证明出具有自我复制,通用计算能力和超平行计算能力,由此可以证明von Neumann相邻条件下4状态异步细胞自动机的通用计算能力和超平行计算能力。 本文利用延时不敏感电路模块,能够很好的嵌入异步细胞自动机中的特性,在文章[10][8][23]中已经的到证实,要模拟生命游戏演化,则必须模拟细胞自动机的状态转换规则和细胞间信息传递。针对生命游戏状态转换规则,分别构建了计数器,解析器。针对细胞之间细胞通信和同步控制设计了同步器。然后分别在von Neumann相邻条件下的4状态和5状态异步细胞自动机中模拟生命游戏的演化,虽然不同状态细胞自动机下模拟的配置不尽相同,但是最终的模拟结果时一样的。 1.4论文结构 针对5状态和4状态异步细胞自动机和延时不敏感电路的研究,本文设计了能够完成生命游戏细胞逻辑功能的异步电路,并在4、5状态异步细胞自动机上模拟生命游戏演化。为证明细胞自动机的本质普适性提供了一种便捷的方法,同时也证明了4状态和5状态异步细胞自动机的计算普适性。本文分为7个章节,分别介绍如下: 第1章,研究背景和研究内容及意义。 第2章,细胞自动机的定义及其计算能力特性引证。 第3章,延时不敏感电路定义及其计算能力引证。 第4章,设计具有生命游戏细胞逻辑功能的延时不敏感电路并在von Neumann相邻条件下5状态异步细胞自动机中模拟生命游戏演化。 第5章,设计具有生命游戏细胞逻辑功能的延时不敏感电路并在von Neumann相邻条件下4状态异步细胞自动机中模拟生命游戏演化。 第6章,全文总结。 2 细胞自动机 2.1细胞自动机定义 细胞自动机是由一组d-维空间(d≥1)上规则排列的细胞组成的,每个细胞均处于有限状态集中的一种,并且每个细胞只与相邻细胞进行通信。每个细胞都遵循局部变换规则。某个t时刻的细胞状态只与前t-1时刻的细胞本身和其周围细胞状态有关。有一个特殊状态我们称之为静状态,当一个细胞的相邻细胞都处于静状态时其状态在下一时刻会保持不变。 大多数细胞自动机的细胞状态转换都是同时进行,通过中央时钟的同步控制或者按步数进行同步进行,所以这类细胞自动机可称为同步细胞自动机。同步细胞自动机由于细胞状态变化的同时进行,使得细胞自动机通常拥有确定的变化规律。相对的,每个细胞的状态变化独立进行,则细胞自动机的规律就边的不可预测。 这篇文章里所涉及的细胞自动机都是由2维空间细胞构成,中央细胞与其上下左右四个方向上相邻细胞通信,这种相邻条件称为von Neumann相邻条件,图2.1(b)展示了一个在von Neumann相邻条件下的2维空间细胞自动机。 (a) (b) Fig 2.1 State transition of cellular automata (a),two-dimension of cellular automata with von Neumann neighborhood. 图2.1 细胞自动机的状态转换(a),von Neumann相邻条件下2-维细胞自动机(b) 下面给出在von Neumann 相邻条件下细胞自动机的一些定义: 定义2.1:确定性的二维细胞自动机在von Neumann 相邻条件下,可以定义成Α=Ζ2,Ε,f,v0,其中Z是整数集合,E是每个细胞的状态集合,其中(Ε≠?)。f为局部映射函数f=E5→Ε。局部映射函数和相邻细胞状态决定了下一刻细胞变化状态,因此一个映射函数可以定义为fc,u,r,d,l=c,其中c、u、r、d、l代表每个细胞的状态,c代表下一时刻c细胞的状态,如图2.1(a)。状态v0∈Ε,是静状态,满足局部函数fv0,v0,v0,v0,v0=v0。 定义2.2:如果细胞自动机Α=Ζ2,Ε,f,v0满足von Neumann相邻条件,则 i) 细胞自动机的局部转换函数是旋转对称的: ?c,u,r,d,l∈Ε,fc,u,r,d,l=fc,l,u,r,d ii) 细胞自动机的局部转换函数是反射对称的: ?c,u,r,d,l∈Ε,fc,u,r,d,l=fc,u,l,d,r?fc,u,r,d,l =f(c,d,r,u,l) 定义1、2说明了细胞自动机在各个方向是相同的 定义2.3:如果细胞自动机Α=Ζ2,Ε,f,v0满足von Neumann相邻条件,conf(Ε)代表自动机上所有状态配置集合。 i) 如果A为同步细胞自动机,那么函数F:confV→confV称为A的全局函数,定义为: ?x,y∈Z2,Fcx,y=fcx,y,cx,y-1,x+1,y,cx,y+1,cx-1,y ii) 如果A为异步细胞自动机,则对任意的ci,cj∈confE,则:对任意的x,y∈Z2,cix,y=cjx,y∨cjx,y=fcix,y,cix,y-1,cix+1,y,cix,y+1,cix-1,y,存在ci→cj的状态转换,任意的cm,cn∈confE,如果存在cm→cn或cm→ci→cn,则可表示为cm?cn 2.2细胞自动机计算能力 细胞自动机作为一种可计算的自动机模型,以其简单的转换规则展现出复杂计算能力特性,被广泛的研究。如自我复制特性,通用计算能力,平行计算能力,平行形式语言识别平,平行数学运算等。本节主要引证细胞自动机的通用计算能力和本质通用性。 2.2.1 细胞自动机的通用计算能力 Von Neumann最早证明了细胞自动机的通用计算能力,然后Alvy Ray Smith构建了一系列的具有计算通用性的细胞自动机[15][16][39],Smith直接利用细胞状态代表图灵机的状态和输入带子符号,在2-维无限空间静态细胞数量有限的情况下构建了一个“实时”的图灵机,即细胞自动机与图灵机在时间迭代上是一一对应的[]。与von Neumann证明细胞自动机计算能力通用性不同的是Smith构建的是一个特殊的图灵机而von Neumann构建的图灵机是在正确初始条件下能够模拟其他图灵机的。关于在细胞自动机上模拟图灵机的研究一直进行,例如Lindgren和Nordahl[22]在1-维细胞自动机上构建了图灵机,同样利用固定的细胞状态代表输入带,但是带头是利用能够左移或者右移的粒子代替,并得出结论任何有m状态和n输入符号的机器能够通过m+n+2状态的细胞自动机构建。 另一种证明细胞自动机具有通用计算能力的方式就是在其上模拟逻辑功能函数,最著名的生命游戏(game of life)最初由John Conway提出,与构建图灵机不同,证明生命游戏具有通用计算能力的方法是建立逻辑功能函数,通过glider模块构建了逻辑门NOT,AND,OR。在生命游戏中通过这种方式构建的逻辑函数是由glider流构成的能够构建任意递归函数[7]。 与同步细胞自动机不同,异步细胞自动机在细胞演化时不需要同步时钟控制但是要比同步细胞自动机复杂得多,更接近实际,其通用计算能力的证明是通过在其上模拟具有通用计算能力的延时不敏感电路。这些模块被证明出具有通用计算能力,包括MERGE,FORK,TRIA,JOIN等[11],在文章[8]中通过将这些延时不敏感电路嵌入到5状态异步细胞自动机中,证明了在Moore相邻条件下5状态异步细胞自动机的通用计算能力和von Neumann相邻条件下4状态异步细胞自动机的通用计算能力[23]。在文章[10]中利用双向带缓冲的延时不敏感电路模块证明了von Neumann相邻条件下的5状态异步细胞自动机的通用计算能力,并且充分利用模块的特性证明了其超平行计算能力。 2.2.2 细胞自动机的本质通用性 计算能力普适性并且作为细胞自动机自我复制能力的一个重要因素被von Neumann[2]提出,随后Codd[1]等人同样在构建细胞自动机通用性上取得了成果。具有普适性是复杂机器在计算能力方面最简单的形式,同时,普适性在机器中将数据编码传输方面也是很方便的工具。细胞自动机的普适性在现实中通过模拟布尔电路、传输线路、信号交叉、传输门等部件之后,通过这样一个合理的假设:利用布尔电路模拟图灵机或者通过将转换规则编码后构成一个规则的配置块,利用传输线将各个块连接起来,模拟被编码的细胞自动机的行为。 在平行算法和语言识别研究的驱动下,细胞自动机的研究转移到一维上,布尔电路同样在一维细胞自动机上适用,形式如同磁带计来模拟图灵机[38],其明确性为细胞自动机的计算能力通用性提供了基础概念[7]。但是图灵普适性缺少明确的形式和通用定义的表达。主要原因有:1)一种能够正式定义图灵机的普适性的概念很难找到。2)把有限编码转换成无限配置,直观上讲就很难,同时在解码时也是很复杂的工作。在细胞自动机上证明固有性和构建图灵机的简便方法就是在其上模拟实现逻辑电路功能。为了能够在细胞自动机中模拟布尔电路,则必须配置下功能: 传输线:传输信号在空间中传播,其传输路径就是传输线。目前有几种不同的传输线形式。传输路径用带有明确方向向量的细胞组成[18],带有矢量方向的移动粒子碰撞到细胞墙壁然后转向[19],无方向的传输路径对在一对不同信号细胞间传播如Codd[1]或者Banks[20]. 转弯和延时:布尔电路传输信号在细胞空间中应能够转向,并且延时到达使得信号同步。 信号交叉:为了能够编码所有的布尔电路,信号交叉必须通过明确的或者不明确的延时技术或者布尔电路技术完成。 门:信号必须与布尔门结合,如结合AND,OR,NOT等通用的布尔门,单独使用NAND或者NOR也是可以的,在文章[7]中在生命游戏上实现了NOT、OR、AND。 扇出:信号必须能够复制通过明确的扇出门或者专门的分离规则。 在文章[7][8][9][10]中分别成功将逻辑电路嵌入到同步或者异步细胞自动机中。 虽然细胞自动机的本质普适性的证明没有通用的方法,但是下面给出一些构建技术: 基于平行图灵机规则查找:一种获得本质普适性的方法是用同步平行图灵机上去检查编码后的细胞自动机的转换规则。但是用在这里的图灵机不是普适性的图灵机,它们的计算能力非常有限但是能够提供精确的任务移动。 单程极权查找:根据Albert和Culik[21],通过模拟单向极权细胞自动机来简化前面的机器,这种方法能够模拟所有的细胞自动机。 本质通用性是细胞自动机递归可枚举特性,一个通用性的细胞自动机可以模拟一组具有本质通用性的细胞自动机,这一点可以很容易证明,但是模拟一个细胞的块配置通常是不确定的,在目标细胞自动机中有可能膨胀到很大。一个本质通用的细胞自动机必须模拟细胞的全部的计算转换规则和传输信息到其相邻细胞。 2.3 生命游戏 Conway[17]为了寻找验证由von Neumann 在1940年提出的一种能够自我复制的理想机器模型,成功找到了在直方格中复杂规则下的一种数学模型。并且得出结论:Conway生命游戏能够构计算任何有计算能力的算法。随后在计算机、物理、生物、数学等众多领域得到了很高的关注,因其简单的规则却展现出了复杂的模式。生命游戏是二维空间下垂直相交的方格组成的细胞自动机,每个细胞有两种变化状态活或者死,同时只与其相邻周围8个细胞进行信息通信,即Moore相邻条件。在每个迭代时间内,细胞遵循以下变换规则: 1) 任何活细胞,当周围相邻活细胞数量少于2时,细胞变死。 2) 任何活细胞,当周围相邻活细胞数量为2或者3时,细胞保持状态不变。 3) 任何活细胞,当周围相邻活细胞数量超过3时,细胞会变死。 4) 任何死细胞,当周围相邻细胞数量为3时,细胞会变成活。 2.3.1生命游戏演化模式 本节展示生命游戏中几个经典的演化模式,包括静止的“生命”和在跌带上重复的模式图2.2和图2.3展示了生命游戏的几种演化模式,其中图2.2(a)是两个时钟周期的重复模式,2.2(b),2.2(c),2.2(d)是静止模式,2.3是四个时钟周期的重复模式,并且形式上向前移动的。 (a) (b) (c) (d) Fig2.2 Patterns of Game of life, Blinker(a), Boat(b), Beehive(c),Block(d) 图2.2 生命游戏演化模式,Blinker(a),Boat(b),Beehive(c),Block(d) Fig2.3 Pattern of Glider of Game of life 图2.3 生命游戏的Glider模式演化,经过4个周期回到初始状态,想左下角移动 2.3.2生命游戏通用计算能力 生命游戏的规则是很简单的,但是却能演化出复杂的模型,如果相邻方格活着的细胞数量过多,这个细胞会因为资源匮乏而在下一个时刻死去;相反,如果周围活细胞过少,这个细胞会因太孤单而死去。 生命游戏中的glider模块和glider发射器,可以够构建基础逻辑功能函数,如某些情况下当两个glider相撞时,它们会消失。利用这些特性可以构建NOT门,如图2.4(a)输入流A代表glider流,那么glider就代表1,缺少glider的代表0,输入流与从glider发射器G发射的glider流垂直相遇,两个glider相撞会直接销毁,那么从glider发射枪产生的glider就会被保留下来,从而产生输出。相应的结果就是输入A的NOT输出。 同样适用于AND和OR门,AND门有两个输入A和B和一个输出,这个输出在A或者B中包含1和0时会有输出,发射器G作为持续发射流不断发射glider,当B中包含0时,G发射的glider会与B作用保留下来,同时A端的glider会与相应的0或者G产生的glider对应,使A的输入会与B的输入同步 对应。作用后的G流如果是0则会产生输出1,如果是1则会产生输出0(如图2.4(b))。AND门的功能得以实现。这种方法构建的逻辑功能在时间和空间上消耗是无法估量的,但能够证明生命游戏具有通用计算能力。 (a) (b) Fig2.4 NOT logic gate construct by glider(a), AND gate construct by glider(b). 图2.4由 glider 实现的NOT逻辑门(a),由glider实现的AND逻辑门(b) 2.4本章小结 细胞自动机的通用计算能力是通过在其上构建据有计算能力的模型,如图灵机或者实现逻辑功能电路,而细胞自动机的本质通用性意在说明细胞自动机之间存在着某种映射关系,使得一个细胞自动机能够模拟另一个细胞自动机,而且这一特性很明显是递归的。 细胞自动机的通用计算能力和本质通用性是细胞自动机两个基本的特性,利用这两个特性,可以间接证明某个细胞自动机的某些特性,这些特性在另一个细胞自动机上已经得到证明。 就目前实现技术来说,证明细胞自动机的通用计算能力只能说明其计算能力同其他架构的计算机在计算能力方面是一样的。实际当中细胞自动机的计算能力并没有真正的被用来计算,因为初始化一个计算模型就要花费很大的开销,同时其计算速度与目前的计算机速度相比是非常慢的,但是作为计算模型的一种细胞自动机在其他方面为计算机的发展提供了更多的可能。3 延时不敏感电路 3.1延时不敏感电路及定义 延时不敏感电路(Delay-Insensitive Circuit)是异步电路的一种,具有很好的鲁棒性,电路的正确性不随信号在电路中的模块或者传输线的延迟而改变,I电路不需要中央时钟信号来驱动,由于这个原因,DI电路被称为异步的。因为与同步电路相比DI电路拥有如下优势,DI电路已经获得了日益增长的关注,相比优势如下: 1.更低的能量耗损和更少的热量消耗,因为异步电路只有活跃的部分才需要能量, 2.更少的线路,平博88因为不需要分布全局时钟信号。 3.更快的平均速度,因为时钟不需要调节到与电路最慢的部分一致。 4.更少的依赖于与正确操作电路有关的物理条件和物理实现。 5.更少的噪声和电磁干扰。 6.问题会随着信号的时间(the timing of signals)消失,比如时钟相位脉冲差(clock-skew)——电路不同的部分收到的时钟信号是有时间偏差的,以及竞争情况(race conditions)——在一个时钟周期之内信号到达目的地失败。 7.更适合模块设计技术,因为DI电路可以分为很多模块,这些模块能够独立的设计并且可以在不考虑模块间时钟关系的情况下进行连接。 尽管这些优势在更高的集成密度下会更加显著,但是在它们说服同步电路设计社区方面还是失败了,不仅仅是因为缺乏可靠的设计、测试和制造基础框架,而且因为在CMOS实现技术下,能量耗损、电路需求和速度方面异步设计确实表现得更加糟糕。一个原因是由于异步电路的信号协议造成的总开销。在异步电路中初始一个动作的通常方式是发送一个请求信号(request signal),然后电路通过发送确定信号(acknowledge signal)标志动作完成。这种用信号通知的方式叫做信号握手(handshaking)[24],需要许多连接和反馈连接使得各个模块可以一起顺利的运作。因此,由于需要额外的操作时间和额外的环路,导致了实践中异步电路的优势减小了。 异步电路的另外一个不利因素是其需要附加的硬件用来避免危险(hazard)[25],电路表现异常时信号的值会非单调的改变。因为同步电路允许信号在一个时钟周期内的任何时间到达,所以它们比异步电路更容易设计,而异步电路的信号在第一次到达目的地必须是正确的。危险(hazard)不是什么大问题,因为在一些技术领域异步电路的实现不同于固态电子学,比如RSFQ超导技术[26][27],molecular electrics[28],molecule cascades[29],和quantum dots cellular automata[30][31]。而且,在这些可选择的技术中,由于在电路中全局时钟是极其昂贵甚至是不可行的,与时钟电路相比, DI电路的实现可能更小更快。因此,在不同的计算体系结构下研究异步电路是否更有用变得有意义了。比如基于细胞自动机的计算架构[9]。 异步电路的需求和操作条件会随着使用的技术和体系结构而改变,例如,细胞自动机,其体系结构原本由纳米技术实现,但是由于其结构规则,也可能认可基于分子自组装的有效结构[9][32][33][34]。在嵌入到细胞自动机上的电路中,细胞(代表着电路元素)结构之间相互连接,与固态技术的线路相比较,这种相互连接方式有着不同的特征。细胞自动机内的相互连接表现为细胞线性连续区域的形式。这样的结构使得信号的传输,不仅能够在线上同时传输多个信号,而且能够允许信号在线上双向传输,但是双向传输不能同时进行[8][9][10]。在DI电路中,如果线路是不同的,那么其电路元素也将是不同的。 在DI电路中,标准逻辑门的使用是有限的[29][35],比如,与非门和与或门,因为其仅仅提供逻辑功能而不提供定时功能。为了用硬件来实现带有某些特性的DI电路,需要定义一组基元模块集,通过它可以构造任意的DI电路。 在[11]中,Keller描述了有关条件,在满足条件的情况下任意的DI电路都可以通过某个固定的基元模块集来构造。后来,Patra和Fusell [27]共同提出了一个可代替的通用(alternative universal)基元模块集,而且他们证明满足Keller提出的通用性条件,并且每个模块总的输入输出线]。直观地说,模块拥有的输入输出线数量越少,模块间互相连接的复杂度就越小,以至于可以简化实践中的设计和实现。虽然模块的传输线数量越少其物理实现越能够简化,但是必须要意识到,模块设计所能达到的简单程度取决于运用的技术。找到一个带有最少传输线数量的基元模块集是很重要的,尤其是细胞自动机的实现方面,因为每一个细胞进行输入输出的邻接细胞数量是有限的,如果细胞自动机是二维的这种限制感觉更加强烈[8][9][37]。 下面出一些关于延时不敏感电路相关的概念和模块定义。 定义3.1:序列机(Mealy型状态机[26])定义为Q,q0,,?,f,g,其中Q是状态集合,q0是初始状态,是是输入符号集,?是输出符号集,f:Q×→Q是状态转换函数,g:Q×→Q是输出函数。 定义3.2:模块定义为I,O,N,其中I是有穷输入线路集,O是有穷输出线路集,而且N=(Q,q0,,?,f,g)是一个和 I一一对应的序列机,并且?和2O一一对应。 在定义3.1中,通过序列机处理输入信号的相继次序,从而简化了定义,但同时也保证了充分的表现力。序列机是模块的核心,然而模块中与外界相连接的输入输出线,虽然支持信号并行输入输出,但是信号由内核按顺序进行处理。输出符号集?和输出线路O的幂集之间的对应关系,表达了模块可以同时地由多条线路输出其操作结果。输入符号集对应于输入线路I而不是I的幂集,表达了每次只能有一个输入。由于模块可以控制输出但不能控制输入,以至于模块能够同时输出多个信号,但输入信号只能一个接一个的到达,这就是模块输入输出不对称的原因。即使有多个输入信号同时到达,模块也会将他们循序地转发到内核。由模块内核中序列机实现的序列化方式简化了模块的形式描述。实际上,有人推荐了更加有效的(平行)实现方式。 定义3.3:信号代表的是状态改变或者线路值的变化,并且从一个模块的输出端到一个模块的输入端,模块间利用信号进行通信,当一个模块接收了一个输入信号后,信号进入序列机的内部核心,一个悬挂信号表示信号被模块接收之后还没有作用输出,只有当其他信号到达后才会产生输出。 如果同时有多个信号,内核会将这些信号序列化为适合处理的方式。序列机一次只会收到一个信号,并且依照定义3.1改变信号的状态。只有某些状态和输入信号的组合,才会使序列机初始化输出信号,比如,这些组合与输入信号的某些能触发模块输出信号的特殊集合相一致。序列机的规范完全明确了模块的状态该怎样改变,以及模块在收到不同的输入信号的组合后应该产生怎样的输出信号。 定义3.4:网络是由许多模块以及模块间相互连接的线路组成的。带有收场的线路是网络的输入或者输出线。如无明确说明,本文中网络是指有限模块组成的网络。 定义3.5:如果不管内部模块或连接线路中有任意延迟,模块的外部输入输出行为(如,I/O轨迹集合[12])始终保持不变,那么则称模块网络是延迟不敏感的。 定义3.6:用一组延时不敏感电路模块集构成的模块是延时不敏感电路集的网络,其输入输出特性与模块相同。 延迟不敏感(DI)模块可以通过用某种方式让基元模块互相建立连接的方式实现。在[11]中,Keller为描述他的DI模块的特性,明确地阐述了几个运行条件,总结为如下几点: 条件1:输入I和输出O是不相交的,即一个模块的输入线和输出线是固定的、分离的。 条件2:一条线路最多连接两个模块,一端用来输入,另一端用来输出。 条件3:模块一旦输出信号,就不能对此信号进行撤销。 条件4:模块可以忍受任意的(但是有限的)延迟,但是这种延迟是要在输入信号被吸收与相匹配的输出信号产生之间的。 条件5:线路上的信号最终必须被其目标模块吸收,因此信号在其到达之前,经历了任意(但有限的)延迟。 条件6:如果一个模块的两个不同输入线上同时有信号到达,那么模块就会任意选择信号执行,先执行一个,再执行另一个,就如同模块指定了信号顺序出现。这叫做任意性(arbitration)条件。 条件7:如果模块的某个输入线上有输入信号,那么必须在信号被吸收之后,才能在此输入线告诉我们如果有两个连续的信号出现在同一个模块的同一条输入线上,只能是以下情况:在第二个信号出现在输入线上之前,模块至少有一个输出信号来作为第一个输入信号的响应。结合条件6来看,如果有两个连续的输入信号出现在模块的相同的或是不同的输入线上,而且这两个输入信号所需的输出线路集合是非空的,那么,只有当模块中由第一个输入信号产生的所有信号全部输出后,第二个信号是才能放到输入线: 如果在模块吸收下一个输入信号之前,模块中每一个输入线上的信号紧接着就有一个信号在输出线上,那么则称这个模块是串行的(serial)。 定义 3.8:如果一个模块允许多个信号同时出现在其不同的输入线上,而且他们不会由输出线上的信号分隔开来;或者一个输入信号可以产生多个不同输出线上的输出信号,那么则称这个模块是并行的(parallel)。 并行模块的定义和Keller的条件7[11]相一致的。 定义 3.9:模块的网络是非忙等(without busy waiting),当有一个足够长的时间内网络中所有的输入线上都没有信号时,就意味着模块间不需要进行无限期的交换。 非忙等待的实际意义是,这个条件保证了网络在没有输入信号的条件下,最终处于稳定状态,因此,最小化了网络的能量耗损。 定义3.10:如果基元模块集合中的模块网络可以实现任意的串行模块,那么则称此基元模块集是串行通用的(serial universal)。 定义3.11:如果一个基元模块集合中模块的非忙等待网络可以实现DI模块类中任意的模块,那么则称这个基元模块集对于DI模块类是非忙等待通用的。 Keller[11]提出了一个基元模块的非忙等待通用集合,通过这个集合可以构造满足Keller条件的任意DI电路。后来,Patra和Fussell[32]提出了另一个模块通用集合。在这篇论文中我们采用的Patra和Fussell的集合是包含了四个基元模块的集合,详细描述如下。为了阐述模块的功能,我们使用了状态转换图,它是基于能够输出转变状态的有限自动机。这些状态转换图用有向加权图来表示,其中,圆圈(节点)代表状态,节点之间的弯箭头代表状态之间的过渡。当一个输入信号到达输入线I的时候就会产生以下变化:模块的状态从p转变为q,并且产生输出信号到输出线,…,On,那么对应的状态转换图就包含:两个分别带有标签p,q的节点,和从p指向q并且带有标签I/O1,…,On的弯箭头。状态转换图的初始状态是通过一个直的箭头指向的,其尾部是开放的。 1. MERGE[31]:如图3.1(a),模块若吸收了输入线)上的信号,就会产生输出信号到输出线(b),模块若吸收了输入线I上的信号,就会产生两个信号分别由输出线输出。 (a) (b) (c) Fig 3.1 Symbol of DI-Circuit, MERGE(a),FORK(b),TIRA(c) 图3.1 MERGE(a),FORK(b),TIRA(c)的代表符号 3. TRIA[34]:如图3.1(c),模块若吸收了输入线)和输入线\{i}上的两个信号,就会产生一个输出信号到输出线三条输入线同时输入信号。若是只有一个输入线上有信号到达,那么模块就会等待另一条输入线上的信号达到。 通过上面总结的Keller的条件1至7,产生了一种新的模块间的互连线,它是双向的并充当缓冲区的。双向性暗示了模块的某一条线在这一时刻可以作为输入线,而另一时刻也能作为输出线,这种优势直接表现在减少了模块上输入输出线路的数量。互连线缓冲信号的能力,使得模块大部分情况下能连续处理输入信号而不需要信号交换,并且当线路缓冲区未满时模块可以随时输出信号。因此提高了信号的吞吐量。此外,缓冲也使得模块的一个单操作可以产生多个输出信号。因为Keller的定义及条件没有包括双向缓冲线,所以我们重新定义模块。首先,我们来定义多重集。 定义 3.11: O表示有限集合。O上的一个多重集(Bag)M是一个函数 M:O→N,其中,N是一个非负整数集,Mo表示o∈O在M中的重复度。多重集M可简记为a1,a2,…,an}M,a2∈O。M(O)表示O上的所有多重集的集合。 定义 3.12. 定义一个模块为(I,O,TO,N),其中,I和O的定义与定义3.2中相同,TO 是O上多重集的一个有限集合,于是TO∈M(O)和{}M∈TO。N=(Q,q0,∑,?,f,g)是一个序列机,∑和I一一对应,△和T(O)一一对应。 定义 3.13. 假设一个模块M=(I,O,TO,N)和一条线路a∈I∪O。当且仅当a∈I∩O时,a被称为双向线,由?表示。同时,若线路a被称为缓冲线,当且仅当它一次可以缓存多个信号,并且当a∈I,所有缓存信号能够转发到模块M,当a∈O时,信号能够转发到与M相连接的模块。对于线路a,有一个正整数na与其关联,为了使a缓存的信号数量不会超过na。na叫做a的缓存容量,是有限的。 它是没有必要的在缓冲区制定一个特殊的区分原则,比如FIFO(见[24]),因为信号是不可区分的,这暗示着信号到达和离开的顺序是不重要的。 这里定义的新DI模块类除了需满足Keller的条件2到6外,还需要满足以下三个条件: 条件8:在一个双向线上,模块在没有吸收完所有的输入信号之前,是不能在此线上输出信号的。这个条件保证了在相同的双向线上,模块的输入信号是不会碰到输出信号的。 条件9:某一时刻,一条线上的所有信号向同一方向移动。这暗示了设计DI电路时,应确保一条双向线两端的模块不会同时输出信号。 条件10:当某线路的缓冲区装满时,输出到此线路的信号会延迟。这个条件避免了在有限大小的缓冲线路上信号的溢出。 串行模块与定义3.7的定义相同。为了实现并行计算重新定义了并行模块,这里的并行计算比定义2.8中实现的更加高效。 定义 3.14:若一个模块在多信号输入时,输入的信号不会被一个输出信号所隔开,或者这个模块在输出多个信号时,这些输出信号不会被一个输入信号所隔开,那么就称次模块为并行模块。 因此,由定义3.12,可知模块一次最多只能产生一个有限信号集作为一个单操作的结果。当一个并行模块在足够长的时内没有输入信号时,暗示着模块最终处于稳态。证明我们所设计的DI模块类包含了满足Keller条件的模块类是容易的。 现在我们要介绍一种新的基元模块集合,每个基元模块最多有三条输入线、输出线或者双向线,并且每条线路都具有缓存作用。这个集合由已知的FORK模块和四个新的模块构成,它们分别是P-MERGE,S-JOIN,IOM和(见图3.2),我们即将证明,这个新的集合对于新DI模块类是通用的。新基元模块的描述如下: 1. P-MERGE(Parallel MERGE):如图3.2(a),来自于输入线a或者b的一个信号会被吸收并产生输出信号到c。与MERGE不同的是,P-MERGE若输入线a和b同时有输入信号,会产生两个连续的输出信号到c上。 2. S-JOIN(Symmetric JOIN):在图3.2(b)中,来自于线路x和y(x,y∈a,b,c,x≠y)的信号被吸收后会产生一个信号输出到剩下的一条线路z∈a,b,c{x,y}中;并且不允许三条线路同时有输入信号。如果模块的某条线路上有等待信号,那么这条线上的后续信号会被延迟吸收,直到有信号从另外的线. IOM(Input-Output Multiplexer):如图3.2(c),输入线a上的信号被吸收后会产生信号输出到b上。模块吸收来自于b上的信号后会产生输出信号到c上。IOM与[4]中的单信道到双信道转换器是相似的,但是IOM的功能更加简单。 4. (a) (b) (c) Fig3.2 Symbol of P-MERGE(a), S-JOIN(b), IOM(c) 图3.2 P-MERGE(a),S-JOIN(b),IOM(c)的符号标识 为了正式定义个一个基于定义3.12的S-JION模块,当模块只有一条线路上输入信号是,模块必须吸收且记录所有的来自于此线路上的输入信号,直到另外一条线路有输入信号为止,因此,S-JOIN状态所需的状态个数必须至少等于其所有线路缓存容量之和。以上说明在图3.2(b)的详细描述中是没被包含的。实际上,有可能实现S-JOIN模块的规格独立于线路实际缓存容量的,比如在细胞自动机中[1][21][37]。 3.2 延时不敏感电路通用计算能力 首先,我们来展示{P-MERGE,FORK,S-JOIN,IOM}集合形成了一个串行通用类。我们仅仅需要实现与定理3.3中相一致的TRIA模块,在这里我们仍然使用FORK模块,P-MERGE可以被当作普通的MERGE使用。 引理3.1. {S-JOIN,IOM}可实现TRIA模块。 证明: 图3.3中给出了详细的实现结果。这个网络中输入线}和输出线}之间的扩充的模块与TRIA是等价的,这个容易证明的。此外,根据TRIA模块的定义,同时考虑到在输入线上不能同时输入信号,因此内部的双向线 TRIA implemented by S-JOIN and IOM 图3.2 由S-JOIN和IOM模块构成的TRIA 定理3.1. {(P-)MERGE, FORK, S-JOIN, IOM}是串行通用的。 证明:可以直接由引理3.1和定理3.3推出。 例子3.1. 在异步电路中与非门的功能可以由布尔等式c=?(a∧b)来描述,其中,a和b表示输入,c是输出,且a,b,c∈{0,1}。考虑到这篇论文中信号是单值的,因此我们用所谓的双轨编码[9]表示来自于门的输入和输出。用两条线比特,由信号在这条线,在另一条线中的双轨与非门。输入线上的输入信号,将会产生输出信号到c1上,且线上的一对输入信号将会产生信号输出到c0上。如果只有ai或bj(i,j∈{0,1})上有一个信号,那么这个信号一直等待直到bj或ai上的信号到达。这里不允许a0或b0和a1(b1)同时有信号到达。图9b给出了用我们的基元模块构造的DR-NAND(双轨与非门)。 Fig3.3 Realization of a DR-NAND by S-JOIN, IOM, PMERGE, and FORK modules. 图3.3 由S-JOIN,IOM,P-MERGE和FORK构成的双轨编码NAND门 3.3 本章小结 本章主要真对DI电路的基本定义和DI电路计算能力的证明,定义和证明只包括本文中用到的一些DI电路模块,其中MERGE,FORK,TRIA是被证明了串行通用的,同时可以用来构建平行DI模块[11]。随着模块输入输出线的减少,对电路设计还是能够带来很大的便利性的,在祛除某些限制条件之后,可以重新定义一组具备通用性的DI模块,这些模块可以处理连续输入的信号而不用给出握手信号,其正确性是不变的,同时可以提高信号处理速度。如P-MERGE,S-JOIN,IOM等模块,这些模块在[]中被证明出了以实现,并完成计算,同时证明了他们是更够完成平行计算的模块。 4 生命游戏嵌入到5状态异步细胞自动机 在文章[9][10]中已经展示了5状态异步细胞自动机的通用计算能力,和平行计算能力,即在异步细胞自动机中实现一般图灵机。在文章[10]中证明了,在von Neumann相邻条件下,5状态异步细胞自动机的通用计算能力,即将延时不敏感电路嵌入到异步细胞自动机中,从而大大降低了在异步细胞自动机上建立计算模型的难度。 由于生命游戏细胞逻辑功能是由延时不敏感电路实现的,所以需要对生命游戏的细胞状态变换规则转换,将规则重新规划祛除冗余,使其更适合计算。转换如下: 1) 无论细胞出于何种状态,只要其相邻细胞有且只有两个状态为1,即处于活着的状态,则下一时刻细胞状态保持不变。 2) 无论细胞处于何种状态,只要其相邻细胞有且只有三个状态为1,即处于活着的状态,则下一时刻细胞状态会变成1状态(活)。 3) 其他情况下,细胞都会变成0状态或保持0状态(死)。 经过转换之后,生命游戏的转换规则的侧重点偏向于周围活状态细胞数量,而自身状态作用则显得不是很重要,因此在以上规划之后,要完成生命游戏细胞的逻辑功能则边的相对于以前的转换规则边的容易多了。同时我们是构建延时不敏感电路,然后将其嵌入到5状态异步细胞自动机上,所以我们可以只考虑如何构建能够完成上述功能的延时不敏感电路即可。 为了实现上述功能,设计电路分成了几个部分,分别为计数器、解析器和外围控制电路。 4.1延时不敏感电路在5状态ACA下配置 在5状态异步细胞自动机中,用 ,,, 和,5个符号分别代表细胞的5种状态0,1,2,3,4。由此,可得到延时不敏感电路模块的配置和信号的配置如图,由于异步细胞自动机的旋转-反射对称性,使得延时不敏感电路在异步细胞自动机中的配置也是各向同性的。模块间链接线是静状态细胞构成。连接线状态细胞自动机中的配置。 信号在5状态细胞自动机中的传递规则详见[10],用来构建生命游戏细胞逻辑功能的模块及其配置见图 Fig4.1 Symbol of FORK and its configuration on right 图 4.1 FORK模块符号标识及其配置(5状态异步细胞自动机) Fig4.2 Symbol of P-MERGE and its configuration on right 图4.2 P-MERGE 模块符号标识及其配置(5状态异步细胞自动机) Fig4.3 Symbol of IOM and its configuration on right 图4.3 IOM模块符号标识及其配置(5状态异步细胞自动机) Fig4.4 Symbol of S-JOIN and its configuration on right 图4.4 S-JOIN模块符号标识及其配置(5状态异步细胞自动机) Fig4.5 Symbol of TURN and its configuration on right 图4.5 TURN模块符号标识及其配置(5状态异步细胞自动机) 下面介绍几个模块的输入输出特性: P-MERGE:I1,I2作为模块的输入端,O作为模块的输出端。信号在I1,I2端输入会在O端输出,在I1,I2两条输入线上同时有输入信号是不允许的。 FORK:I作为模块的输入端,O1,O2作为模块的输出端,信号在I端输入会在O1,O2端同时产生输出。 IOM:总共有3个输入输出端,其中信号在a端输入会在b端输出,b端输入会在c端输出,信号不能同时在a和b端同时出现,b端还是输入输出复用端。 S-JOIN:同样有三个输入输出端a、b、c,3个端口都是输入输出复用端,其中只有输入信号同时在a,b,b,c,a,c端输入时,才会分别在c,a,b端产生输出。 TURN:该模块只会改变信号传输方向,不参与实际电路功能运算。 4.2 计数器设计及5状态ACA下配置 本质上讲,在同步电路设计中主要考虑的是时序问题,在寄存器传输级表示的电路中,寄存器级间组合逻辑延时必须小于时钟周期,对于多周期运算步骤,必须小于时钟周期的相应倍数,并且其裕量还要满足建立时间和保持时间。判断所有操作正确完成的条件都是基于始终概念,通常对于寄存器而言,其时钟端用作触发捕获数据端的输入,所以在后端分析时钟通路通常也被称为捕获路径,而数据路径被称为发射路径。 在异步电路设计当中,由于引入了握手的概念,相当于将同步设计当中的全局触发时钟细化为元件级间请求和应答信号,这时更关心的是数据在细化的握手行为中相对于请求信号的数据建立时间和相对于应答信号的数据保持时间,每一步操作的完成也不受限于时钟周期,从而淡化了整体的时钟概念。 同步计数器电路利用同一公共时钟信号作为统一时钟控制,所有元件工作在此时钟下,异步电路是利用模块间的级联,将一个模块的输出作为另一个模块的输入。 传统的同步计数器和异步计数器(行波计数器)是利用JK触发器在同步时钟控制之下或者模块级联来完成计数功能。与传统电子元件不同,本章利用的是MERGE、FORK、S-JOIN、IOM这几个延时不敏感电路模块设计计数器,那么从最简单的二进制计数器开始考虑,计数器要能够达到: 1) 计数器有两种状态0和1,同时还能够保持状态 2) 有两个输入端,一个输入端I1作为置1端,另一个输入端I2作为置0端,。 3) 计数器初始状态为0,每种状态下的输入都应该有相应的输出信号,那么根据条件2)可以看出计数器应该有4个输出。 那么不考虑计数器内部结构,单从外部输入输出特性看,一个二进制的计数器如图4.6(a)所示。 三个条件的必要性:1)作为一个二进制计数器的基本条件,在传统计数器 中也是必不可少的。2)和3)结合考虑,由于要实现能够计数0-8的计数器,同时还要能够读取计数器状态,所以单纯靠一个有效信息输入端作为计数器状态判断是不够的。异步电路设计由于没有时钟控制,所以各个模块间信息同步控制是通过握手实现,那么两个输入和两种状态应该对用4中输出。 由于计数器需要保持某一状态,所以必须有包含S-JOIN,该模块包含三个可复用的输入和输出端,要实现一个二进制计数器: 1) 一个S-JOIN模块是不能完成的,其原因是:计数器需要一个输入输出端用作状态记录,同时需要一个固定输入端作为有效信息输入,其只能实现类似图4.6(b)的电路模块逻辑功能的模块,增加一个S-JOIN模块。 2) 如果只实现一个模2的计数器可设计为图4.6(c)所示的电路。如果使用该计数器,只能实现2的倍数的计数器如0、2、4?,同时只能根据一个有效数据输入端来判断计数状态,而没有办法读取计数状态,不符合本章设计需求。 异步电路设计的关键在于模块间数据的建立时间和应答信号相应时间的控制,图用延时不敏感电路模块设计了一个二进制计数器,I1, I1为输入,O1-4为输出,初始状态下计数器为0状态,即在两条传输线a上同时有信号,当计数器计数为1时,在b两条线上同时有信号。计数模块的功能描述如下: (a) (b) (c) Fig4.6 Symbol of binary counter(a), a kind of structure by one S-JOIN(b), a structure of a binary counter with two S-JOIN. 图4.6 二进制计数器的外部特征(a),一个S-JOIN可能构建的电路(b),两个S-JOIN构建的二进制计数器 1) 当输入信号在I1端输入时,如果计数器处于0状态,那么按照各个模块功能特性,会有输出信号在O3输出,同时在两条传输线b上有传输信号,即计数器转为1状态,表示计数1。 2) 当输入信号在I1端输入时,如果计数器处于1状态,那么按照各模块的功能特性,会有信号在输出端O1输出。两条传输线端输入时,如果计数器处于1状态,那么按照延时不敏感电路模块的功能特性,会有输出信号在O2段输出,并且改变计数器状态为0,两条传输线a上有信号。 由于两个信号不能同时出现在一根传输线上,所以每个输入都应该有一个对应输出,如I1→O3,s=0,I1→O1,s=1,I2→O2,s=1,I2→O4,s=0,s代表计数器状态。综上,可以把计数模块当作黑盒看待,对应不同输入可以得到不同输出。那么,输入端I1作为有效信息的输入,输入端I2作为计数器的状态读取,但是这只是能够完成计数为1的计数器,如何构建能够记录更多数的计数器呢? Fig4.8 Congratulation of binary counter correspond with Fig4.7 under 5-state ACA with von Neumann neighborhood 图4.8 5状态异步细胞自动机下二进制计数器的配置,与图4.7相对应 Fig4.7 A kind of binary counter with two input lines and four output lines 图4.7 带有2个输入端和4个输出端的二进制计数器 根据输入输出及状态转换,当计数状态为1时,输入I1对应输出O1,计数状态不变,则可将O1作为下一个计数器的输入,如果下一个计数器为0状态,则会相应改变其状态,并在相应O3输出信号。如果下一个计数器为1状态,则不会改变其状态,并在相应的O1有信号输出。则可完成数值更大的计数器,图4.9展示了一个由图4.7中二进制计数器级联构成的能够计数到4的计数器。计数器初始状态为0,其功能特性如下: 1) 当在I1端输入时,如果计数器处于0状态,则计数器C1会置1,并且在O13有输出,如果C1为1状态,在O11上有输出,根据图4.9中连接方式可以看出O11是作为下一个计数器的有效输入,其他计数器以此类推。当C1-4计数器都为1时,从I1的输入产生O41输出。 Fig4.9 Counter constructed by binary counter correspond with Fig4.7. 图4.9 由图4.7所示的二进制计数器级联构成的计数器 2) 当在I2端输入时,如果计数器器处于0状态,则在O14输出,如果C1状态为1,即计数1,则会输出信号到O21,O21作为下一个计数器的I2输入。以此类推,当四个小计数器都为状态1时,I2端输入会产生O42信号输出。 图计数器可以计数0-4,输出端与代表数值分别对应为:O14→0,O24→1,O34→2,O44→3,O42→4,可以看出前一个计数器读取状态为1后,是再去读取下一个计数器状态,如果为0则在相应的输出端O4输出,从而确定计数器计数 状态。当最后一个计数器状态为1时,则直接在相应O2输出。 虽然计数器只能最大计数4,但是针对生命游戏中转化规则来说,当周围活细胞数量大于4时与数量等于4的结果相同。固,最大计数为4恰好满足生命游戏规则所需,而且不会增加电路规模和冗余。由于异步电路的特性,所以应有必要的反馈控制信号控制信号间同步。同样的,输入I1,I2在不同的状态下对应不同输出,而且一定会有一个相应输出。,在I1输入时,会产生输出O41和O13-O43, Fig4.10 Configuration of counter correspond with Fig4.9 under 5-state ACA with von Neumann neighborhood 图4.10 与图4.9相对应的计数器在5-状态ACA下的配置 这几个输出信号可视为输入的反馈,其作用在后边将会介绍。 I1→Oi3,1≤i≤4且s=i-1 I1→O41,s=4 I2→Oi4,1≤i≤4且s=i-1 I2→O42,s=4 综上,由计数器可以得到一个细胞周围活细胞的数量,当然并不是全部活细胞数量,因为当数量多于4个时,跟数量等于4个信息产生的结果是相同的。至此,生命游戏转换规则所需的外围细胞信息已经得到,下面一章考虑如何将这些信息与细胞自身状态结合,以完成相应规则功能。 4.3解析器设计及5状态ACA下配置 在上一章,设计的计数器能够计数周围活细胞数量为0-4,平博88根据前面规则划分,每个数量对细胞状态产生的相同,可分为0,1,4,2,3。用模块MERGE将代表0,1,4的输入线的输入线不会改变细胞自身状态,而3则会将细胞状态变成1,0,1,4则会将细胞状态变成0。因此,对应的解析器有3种输入,和2种细胞状态。同时解析器必须存储着细胞自身状态信息。再考虑几个延时不敏感电路模块的功能特性,输入线最多的模块是S-JOIN,同时也只有它才能够等待两个信号同时到达后产生输出,所以可以用S-JOIN的特性来存储信息。 1)考虑一个S-JOIN模块能否满足解析功能:如果三条输入线分别作为其输入,就无法记录细胞自身状态。 2)那么增加一个S-JOIN模块,2输入会保持细胞自身状态,即会产生两种输出。而0,1,4,和3分别会置换细胞状态为0和1,两个模块共有6个输入端,如果每个模块上记录一种状态信息,那么需要两个输入端口,但是三种输入还是要跟每种状态作用,结果还是不能达到要求。 3)综合考虑,每个输入必须有一个输出信号作为反馈控制信号,由于在向外界传送自身转变后状态的同时,还要改变自身状态,所以必须增加一个S-JOIN模块,同时细胞状态的记录不能分开记录,就必须在两个S-JOIN模块上都要记录有状态信息。在读取状态信息后利用第三个S-JOIN模块来产生相应规则下的状态信息。借助计数器的设计,图 T1,T2两模块共同记录细胞状态信息,两根传输线a上有信号时,代表细胞状态为0,传输线b上有信号时,代表细胞状态为1,那么0,1,4,2,3三种输入其实就是读取细胞状态,即输入到T1,T2读取细胞状态,并给出读取完信号到T3,T3的结构图可以考虑为图4.11 一个输入端考虑为读取完信号的接收端,0,1,4输入和2输入时细胞状态为0时产生的输出作为一组给T3的另一端,3输入和2输入时细胞状态为1时产生的输出作为一组给T3。最后将细胞状态传送给周围细胞,并且同时将新的细胞状态存储到两个S-JOIN模块中。只考虑每个输入的功能,0,1,4,3输入可以视为只置空细胞状态,并给出完成信号。2输入则是去读取细胞状态。 Fig4.11 Structure of Decoder. 图4.11 解析器结构 Fig4.12 Configuration of Decoder under 5-state ACA with von Neumann neighborhood 图4.12 von Neumann相邻条件下5状态ACA下解析器的配置 ACA 4.4 DI电路模块构成生命游戏细胞及在4状态ACA下配置 4.2和4.3章分别介绍了两个完成生命游戏细胞功能的重要组成部分。计数器模块完成周围细胞信息收集处理,解析器模块则完成信息与自身状态的作用转换,即规则转换。由于4.2中所设计的计数器是线性模块,即每个输入要对用一个输出,然后才能继续工作,所以每个周围细胞状态信息不能在前一个输入没有作用产生输出结果时后一个输入信号就到达,所以对周围细胞的信息到达要有必要的同步控制。在4.2章中延时不敏感计数器的不同输入(不同状态的下I1,I2输入)对应不同输出,其中I2视为读取计数器状态信息的控制信号,其对应输出视为周围细胞信息收集的结果。I1作为有效信息输入,其作用是改变计数器计数状态,并在完成后给出反馈信号,在不同状态下分别为I1→Oi3,1≤i≤4且s=i-1和I1→O41,s=4,其中I1→O41,s=4周围细胞数大于4,但是这个信息对细胞状态转换规则失效,所以这几个输出信号就是计数完的反馈信号。虽然O13-O43这几个信号可以区分开,但是当周围细胞数大于4时反馈输出都是O41,所以这几个信号分别去控制周围信号读取是无法实现的,只有将其合并到一起,然后利用TOGGLE模块去控制读取。 考虑周围有八个细胞要去读取,一个TOGGLE模块能够实现控制两个细胞信息读取,但是输入只有一个,那么就需要将TOGGLE模块级联,其数量N0与对应输出N1关系为(式): N0=N1-1 那么产生8个控制信号就需要7个TOGGLE模块。当读取完8个细胞信号之后即计数器记录完后,还要有一个信号去读取计数器状态。如果TOGGLE的8个信号全部去控制读取细胞状态,例如周围细胞状态全部为1,则在计数器I1输入后,当计数大于4时输出都在O41,当第8个细胞信息读取后,输出O41会作用到达TOGGLE,最终再次到达第1个细胞控制信号。而此时还没有读取计数器状态,后续演化过程也无法进行。目前解决办法有两种: 1) 再增加一个TOGGLE,模块这样8个模块对应9个控制输出,最后一个信号加好作为计数器I2的输入,来读取计数器。后续计算过程也得以继续进行。但是还缺少一个开始信号使的电路去读周围细胞状态,当然可以把电路设计的复杂些,比如在细胞向外界输出信息后同时给自身一个开始信号。 2) 从生命游戏整体演化考虑,由于1)中缺少开始信号,同时需要8个TOGGLE,这会加大整个电路规模,如果第一个细胞信息的读取不需要控制信息而是直接输入到计数器,那么8个控制输出就会多出一个,而这一个恰好可以作为读取完所有细胞信息的反馈信号输入到计数器的I2如图4.13(b)。 (a) (b) Fig4.13 TOGGLE implemented by IOM, S-JOIN and FORK(a), Structure of seven TOGGLE 图4.13 由IOM,S-JOIN,FORK实现的TOGGLE(a),7个TOGGLE组成的电路结构 2)方案虽然都能够解决周围细胞信息读取的控制,但是这种方法都存在缺陷,无论是延时不敏感电路还是异步细胞自动机,都有延时特性,就可能存在这样一种情况:当读取计数器的信号还没到达计数器的输入I2,但是周围细胞的状态信息再一次到达细胞的第一个细胞信息输入口,则直接会对以后的细胞演化终止,即生命游戏的不同步。对此在5.5章节提供了一个解决办法,不仅能解决上述问题,同时还有异步细胞自动机中信号碰撞问题。 综上,2)方法无论在规模还是实现难易程度上都比1)方法好。由于细胞状态分为两种:0,1,在上面我们只提及状态为1时细胞信息处理过程,在设计计 Fig4.14 A cell of GL implemented by DI-Circuit 图4.14 由延时不敏感电路模块构成的生命游戏细胞 数器时,其初始状态就为0,那么当控制信号读取到细胞状态为0时可以不进行计数,而是作为控制信号输出给TOGGLE。现在具备实现一个生命游戏细胞逻辑功能要处理信息的各个模块。将各个模块按输入输出特性组合到一起就完成一个具备生命游戏细胞逻辑功能的电路模块。 Fig4.15 Configuration of GL cell correspond with Circuit in Fig4.14 under 5-stateACA with von Neumann neighborhood 图4.15 生命游戏细胞配置在5状态异步细胞自动机下的配置,与图4.14相对应 4.5同步器设计及5状态ACA下配置 在5.4章节将延时不敏感电路设计成的生命游戏细胞各个部分组成到一起,构成一个在逻辑功能上与Moore相邻条件下的生命游戏细胞相同的延时不敏感电路模块。能够接收周围细胞信息,并且按照局部转换规则改变细胞自身状态,然后向周围细胞传送信息。如果按照现在的说法,只要把电路构成的细胞统一摆放,然后将细胞间连线对应链接。给出每个细胞状态然后在异步细胞自动机上模拟的同步生命游戏就能进行演化。虽然由于异步电路的延时特性会使得每个细胞间产生不同步,但是只有周围细胞状态信息全部收集到之后,一个细胞才会进行后续演化计算过程。所以从宏观上看模拟的生命游戏,细胞状态变化还是同步的,细胞演化按着步数迭代同步进行。 但是当我们把模拟生命游戏细胞按照延时不敏感电路在异步细胞自动机上的配置构建生命游戏细胞自动机时,当细胞间进行信号传递时,会发生碰撞,使信号无法传播,究其原因是因为1)本文涉及的细胞自动机是在2维平面上的,2)异步细胞自动中,每个细胞下一时刻细胞状态变化是独立的,这就造成了各个信号传递时是不同步的3)信号在5状态细胞自动机上向前演化时,只是按照规则简单进行演化,所以当两个信号发生正面或者侧面的碰撞时,是没办法进行躲避的。为了使信号能够正常的传递给周围相邻细胞,我们增加了同步模块。图4.16就是一个同步模块。这个模块不仅解决了信号碰撞的问题,同时还解决了细胞迭代的同步问题。图4.16所展示的同步模块,只有当两边信号同时到达输入端才能相互穿过同步器,由于生命游戏是在Moore相邻条件下的细胞自动机,所以信息输送要送到周围8个细胞,那么不管如何摆放细胞总会有信号在细胞间传递时发生碰撞的可能。而且当斜对角上细胞相互通信时有可能产生四次碰撞,那么就需要增加四个同步器,这将大大增加整个生命游戏的模拟规模,所以采用每个细胞只向上下左右4个方向的相邻细胞传送信息,这时需要4个同步器,当信号穿过同步器后再利用FORK模块将信息传送给对角线 由于采用双线的信号不在同一个传输线上,所以代表细胞的两种状态同样需要两条不同的传输线传输,那么同步器的设计必须考虑两个细胞信号传输时交叉碰撞会有4种组合情况:0,0,0,1,1,0,1,1。同步器的输入输出特性如下: a和b、c和d输入线不能同时有输入信号出现,只有a与c或者d、b与c或者d上有信号输入时才会产生输出。 由此可见同步器是将两个将要互交的信号进行同步处理,使其不在同一个时间点上发生碰撞。 (a) (b) Fig4.16 Structure of a synchronizer (a), Its configuration under 5-state ACA with von Neumann neighborhood 图4.16 同步器的结构(a),5状态异步细胞自动机下其配置 4.6在5状态ACA中模拟生命游戏简单演化 Fig4.17 Six GL cells in 5-state ACA with von Neumann neighborhood 图4.17 von Neumann相邻条件下4状态异步细胞自动机中模拟的生命游戏细胞 图4.17所示展示将具有生命游戏细胞逻辑功能的异步电路嵌入到5状态异步细胞自动机中的配置图,由于空间有限,在模拟过程中总共包含了6个模拟的生命游戏细胞,细胞间通过5.6节介绍的同步器进行通信,同时6个细胞周围细胞状态模拟为0状态,图中灰色方块代表活细胞,则上面三个细胞为或状态,下 F