异步逻辑电路的层障碍及其分析方法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记283（2012）159-177www.elsevier.com/locate/entcs异步逻辑电路与层障碍迈克尔·罗宾逊1，2宾夕法尼亚大学数学系209S。33号Philadelphia，PA摘要这篇文章展示了一个特殊的编码逻辑电路成一个层形式主义。的核心结果这篇文章的重点是，在这种设置中，电路设计者可以获得的信息严格地多于静态真值表中的信息，但少于事件级仿真中的信息。这些信息与逻辑电路的时序行为，从而提供了一个关键词：逻辑电路，异步系统，层上同调，电路结构分析1引言异步逻辑电路的验证通常需要大量的仿真和适当的测试覆盖率。本文提出了一种新的技术，用于检测某些行为特性的逻辑电路，使用不太详尽的结构分析。在这个分析中，线延迟是未知的和有限的，但与其他人在这种情况下的工作不同，线延迟是隐含的。我们不需要假设它们随时间的推移有一个固定的值，我们甚至从不将它们指定为变量。我们展示了如何潜在的危险的竞争条件（这往往会导致毛刺或不必要的闭锁）对应于非平凡的第一上同调类的一个特定的层，编码这个隐式的定时模型的电路。1这项工作得到了AFOSR FA 9550 -09-1-0643的支持2电子邮件：robim@math.upenn.edu1571-0661 © 2012 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2012.05.010160M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）1591.1历史讨论异步逻辑电路的综合是一个古老的课题，在计算的最早期，Hu Jumman [19]就已经研究过了。虽然使用异步硬件比同步硬件的好处是巨大的（更好的模块组合性，更低的功耗，更低的电磁干扰，更快的速度），但它的挑战通常阻碍了它的广泛接受。异步设计的大部分困难涉及电路内延迟的仔细控制以及竞争条件的避免[21]。然而，由于涉及切换阈值的微妙之处，即使是正确的定时也不足以确保正确的操作[38]。也就是说，越来越多的组织使用包含一些异步部分的设计[12]。一些处理器，例如ILLIAC [33]，加州理工学院的异步微处理器[23]和ACT 11 [15]已经被构造成没有全局时钟。异步设计的挑战围绕着时序不稳定性和敏感性，这通常意味着验证需要详尽的仿真。由于这些好处和挑战，围绕异步逻辑的设计和验证已经出现了一系列生动的文献。基本上有三个主要的调查线索：(i) 电路的语义或行为模型的具体化(ii) 根据本规范合成门级电路，以及(iii) 仿真电路，以验证其正确的性能。语义规范通常使用进程代数给出，如π-演算[31]或CSP [17]。当Martin [22]描述如何将CSP的一个版本编译成门级逻辑电路时，后者获得了一些牵引力。他后来改进了这种编译，只生成准延迟不敏感电路[24]，这是一类后来被证明是图灵完备的电路[21]。准延迟不敏感性要求电路对导线延迟不敏感，除非某些信号对被假设几乎同时到达。完全的延迟不敏感似乎更理想，但Brzozowksi [5]表明，这不适当地限制了可以构建的电路。在这些最初的尝试之后，异步电路规范的基础理论继续发展，通常借鉴数学[16]，逻辑[39]和计算机科学[10]的形式证明方法除了马丁其中，有一部分人，在《易经》中有详细的记载。熟悉Petri网的读者会发现[14]中的统一综合处理特别令人满意。在某些情况下，研究人员成功地采用了更详尽的特设方法，如[9]。其他方法集中在对故障的鲁棒性上[30]或分层设计[32]。一旦一个电路被合成，它的行为应该根据原始规范进行验证。最直接的仿真涉及生成电路中电压或逻辑信号的精确时间序列既然有M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159161制造变化，有助于在开关转换期间传播模糊的逻辑值[7]。大多数现代验证方法通常涉及由时序逻辑驱动的符号事件级模拟[4]。然而，这种方法通常会导致状态爆炸，除非考虑原始规范[8]。使用代数操作[20]也减少了这种模拟的计算负荷。解决这个问题的一个不同的方法是切换到一个直觉主义的逻辑模型，其中延迟是显式不确定的。这种方法在Mendler [27]和他随后的命题稳定化理论[28]的一个非常优雅的工作中得到了利用验证工具已统一为用于设计的硬件描述语言[13]，并解决分层设计工作流程[37]。我们建议读者参考调查[26]和[1]，以获得更广泛的异步仿真处理。与通过时序逻辑或时间序列模拟进行验证相比，本文中采用的方法表明，逻辑电路的拓扑结构在确定其行为方面起着重要作用。这似乎与[29]中最近的方法，但电路的拓扑分析并不是新的。 实际上，代数拓扑可以用来证明电路定律的通常公式可以得到电压和电流的解[34]。布拉宁[2]展示了拓扑方法如何扩展到解决广泛的网络相关问题。此外，Smale [36]表明，描述电网络行为的微分方程可以从同调理论导出。斯梅尔这种动力学观点也可以使用流形的拓扑来理解[25]。1.2我们的方法为了缩短异步电路的设计周期，需要在静态逻辑状态计算和事件级仿真之间架起一座桥梁。理想情况下，这种技术将避免详尽模拟的细节水平和本文描述了一种编码比网表（门和连接）和线路上的逻辑值稍多的信息的方法。具体地说，我们假设一致的逻辑状态可以扩展到电路的部分或整个电路。不能在整个电路上一致地扩展的一致逻辑状态对应于瞬态：不一致性发生在逻辑值发生变化的线路上。通过这种方式，我们能够以隐式方式检查涉及线路上未知延迟的电路行为：我们不需要像[20]中那样将延迟指定为变量，也不需要假设延迟在电路操作期间保持固定。由于这些信息是局部的，在通常的拓扑结构上诱导的有向图描述电路连接，自然的计算框架是层理论。从一开始，直接应用层理论的逻辑电路的结果在重大的计算困难，因为自然层是不是阿贝尔162M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159组然而，通过将逻辑值从二进制值提升到一个由逻辑0和逻辑1构成的抽象向量空间中，我们从层中获得了新的信息（在其全局部分的水平上，而不仅仅是在其相对上同调中），并且计算成为线性代数中的简单练习。这个看似抽象的技巧对应于使用one-hot信令[11]，用于在现有的异步接口中提供错误检测。在数学上，使用这种编码给了所得到的切换层足够的自由度来描述作为两个过渡状态的叠加的全局逻辑状态;基本上通过捕获未定义的信号和信号碰撞。因此，通过检查切换层的上同调主要的结果是，第一个上同调组的开关滑轮是由所有的反馈回路，有可能闩锁或导致毛刺。另一方面，我们表明，组合逻辑电路中，每个输入只使用一次（因此不能毛刺）有平凡的第一上同调。因此，似乎第一个上同调群包含真正异步行为的证明。顺便说一句，我们注意到，如果没有一个热信号，这个问题的层理论方法仍然可以通过寻找扩展局部逻辑状态的障碍来进行。我们希望存在一个更粗糙的障碍理论（用于切换层，使用单热信号），它比本文中提出的更精细，但比完整的模拟更不详尽1.3文件概要在第2节中，我们给出了基本定义，并强调了层理论的相关结果 第3节描述了我们将逻辑电路编码为开关层。 在第4节中，我们展示了切换层的上同调群如何捕获持续反馈所产生的逻辑状态。我们在第5节中给出了三个切换层的例子，并计算了它们的上同调，最后证明了切换层的上同调比逻辑状态的列表携带了更多的最后，在第6节中讨论了结果。2层理论层是用于存储域上的局部信息的数学工具它将某个代数对象，在我们的例子中是一个向量空间，分配给每个开集，服从一定的相容性条件。这些条件分为两类：（1）限制信息从较大的开集到较小的开集的条件，以及（2）将小开集上的信息组合成较大开集上的信息的条件。特别感兴趣的是全局信息与该图的拓扑的关系，全局信息在整个图上是有效的。这是由层的上同调捕获的，我们在这里总结了这种方式M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159163UUUUWUiVWU2.1层的基本定义在这一节中，我们遵循[18]的附录7中给出的层的介绍，主要是因为它直接处理了驯服空间上的层。要了解更一般、更传统的方法，请将我们的讨论与[3]进行比较。在本文中，我们将把图作为一维拓扑空间来处理，而不是顶点和边的有限集合。具体来说，我们将使用与有向图G=（V，E）相关联的几何实现通常，每个边e∈E是一个有序对（v1，v2），其中v1，v2∈VH<$。我们用e表示边e不与图中的任何顶点相连，或者简单地表示e有外部连接。设Y是以V为索引的点和以E为索引的闭区间[0，1]的不交并。（我们设X是由Y通过如下方式将区间附加到点而形成的空间：对于由e=（v1，v2）∈E索引的区间，(i) 如果区间的左端点不是顶点，则将此端点附着到折点v1. 我们称e为v1的输出边.(ii) 如果区间的右端点不是顶点，则将此端点附着到折点v2. 我们称e为v2的输入边.所得到的拓扑空间捕获图形结构，并且标签传入和传出捕获图形的方向结构拓扑空间X上的预层F是向量空间F（U）对每个开集U和分配一个线性映射ρV：F（U）→F（V），包含V.这个赋值必须是函式的，如果U<$V<$W，则ρU=ρU<$ρV，ρU是单位元。 我们称之为将ρV映射为从U到V的限制性映射。 F（U）的元素称为F定义为U。层F是满足胶合公理的预层F• （单重层）设u∈F（U）且{U1，U2，. }是U的开覆盖。如果对每个i，ρ u =0，则在F（U）中u = 0。简单地说：在局部各处都一致的部分也在全局上一致。• （合取性）设u∈F（U）和v∈F（V）是截面，使得ρU<$Vu=v. 则存在一个w∈F（U<$V）使得ρU w=u和ρV w=v。V UVUV换句话说，在其域的交叉点上达成一致的部分可以是“粘在一起”成一个部分，定义在他们的定义域的联盟。滑轮的标准示例为• 拓扑空间上连续实值函数C（X，R）的集合X.• 局部常数函数的集合，它本质上为每个开集的每个连通分量分配一个常数。相反，常数函数的集合不形成层。164M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159−−−−→−−−−→UV12你... Uk+1我1k+1层通常最容易通过层化过程构造，将一个预层取为一个保持其结构的唯一层直观地说，给定空间X上的一个预层F，我们可以用它在任意开集上的截面来定义层FU通过粘合U中所有重叠部分的所有部分来粘合X。为了精确地定义这一点，我们需要在点x∈X处的预层的茎Ax的概念，它是所有U包含x的A（U）上的直接极限。然后，我们定义函数集F（U）为所有函数f∈x∈UAx的集合，使得对于每个x∈U，存在一个包含x和g ∈ F（V）的开子集V<$U，其中f |V= g。层上有六种著名的运算在通论中很重要，但本文只讨论其中之一（上同调）2.2同调我们可以将合取性公理改写为度量线性映射的核d：F（U）<$F（V）→ F（U <$V）由d（x，y）= ρ U<$Vx − ρ U<$Vy给出。事实上，这种线性映射的核的元素对应于截面的一致性在U盘上。另一方面，复层公理表明，映射d下的零原像对应于这些胶合截面对U和V的限制。事实上，d的像的任何非零元素都不可能是U∈V上的截面。这两点激发了一个用于处理层的计算框架，称为Ce ch构造。假设F是X上的层，并且U ={U1，U2，. }是X的封面。我们定义C_（？）K（U;F）是上截空间的直和在U. ThatisCk（U; F）=F（Ui. （i）。K本文定义了一个线性映射序列dk：Ck（U;F）→Ck+1（U;F）byk+1d k（α）（U，U，...， U）=<$（−1）iρU0<$.. . 你好Uk+1α（Ui=0我... 你... U），其中帽子意味着从列表中省略一个元素。请注意，这些组合在一起形成一个序列，称为Cechcochaincomplex：0→C0（U;F）d0C-1（U;F）d1...一个标准的计算表明d kd k−1= 0，因此我们可以定义第k个Cechohomology spaceH k（U; F）=k e rdk/imagedk−1。H_∞ k很大程度上取决于C_v_U的选择，但对于G_d C_v_s_3（m_u_c_h），如在神经引理中），这种依赖性消失。层的Leray定理指出，对于每个层，H_k（U ; F）是相同的。 所以我们写Hk（X; F） =Hk （U; F），这是在U是一个G的情况下的Shea f上同调。稍微思考一下图上的好覆盖，就会发现两个重要的事实：一个好的覆盖U是由可收缩集合组成的覆盖，其中U的有限个元素的所有交集也是可收缩的。k+10M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159165δ→我2一B22• 如果X是一个图的几何实现，则对于k>1，Hk（X;F）= 0，且• H 0（X; F）同构于整体截空间F（X）.通过类比同调的Mayer-Vietoris序列，存在层上同调的Mayer-Vietoris序列[3]。设A，B是图X的两个覆盖X的开子空间，F是X上的层。那么下面的Mayer-Vietoris序列是正合序列：... →Hk（X;F）−r−→Hk（A;F）<$H k（B;F）−δ−→H k+1（X; F）→.−d−→H k（A<$B;F） −−−−→在这个序列中，r以明显的方式来自限制映射，d是限制映射和差的组成：d（x，y）=ρA<$Bx−ρA<$By，δ是连通同态记法在上面被稍微滥用了：Hk（A;F）我们指的是层F限制于位于A中的子集的k次上同调。Mayer-Vietoris正合序列简化，如果A和B不相交。在这种情况下，简单地得到对于每个k，Hk（X;F）=Hk（A;F）<$Hk（B;F）。3从电路本节描述了一种将层结构与编码逻辑电路的有向图相关联的方法。每个顶点表示一个逻辑门，其中入度表示输入的数量。图中的每条边对应于一个1位信号，该信号将一个门的输入连接到另一个门的输出。 我们允许边是自环（将门的输入连接到同一门的输出）和外部连接。由于现有的逻辑电路包含有限多个门，我们假设底层图是有限的，但不一定是连通的。3.1静态逻辑状态、独热编码和自定义我们首先简要描述要编码的电路模型。由于层结构要求逻辑函数是线性函数，我们对它们进行了分类。这是通过逻辑值的相对标准的独热编码来实现的假设X是一个有向图，其中每个顶点都有有限度。一逻辑电路是将函数fv：Fm（v）→Fn（v）分配给每个顶点v，其中m（v）是v的入度，n（v）是v的出度。我们称fv为逻辑门在V。给定一个逻辑电路，静态逻辑状态（QLS）是一个赋值s：EF2的二进制值，使得对于每个顶点v，f v（s（e+），s（e+），. ）=的1 2（s（e−1），s（−2），. 其中，e{e+}是传入边atv，{e−i}是传出边在V的边缘。在这篇文章中，我们研究了逻辑电路中二进制值的独热编码T也就是说，我们考虑函数T：F2→F2，其中166M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159⎝⎠12⎝⎠0222T（0）=0.01T（1）=0.00000。这样，F2的元素就变成了F2的标准向量空间基的元素。在逻辑电路和逻辑状态的定义中，将这种替换应用于每次出现的F2，会导致逻辑电路的特定简化实际上，每个逻辑门fv都成为F2向量空间之间的线性函数Tfv对赋形过程的随意检查表明，除了代数结构略有增强外，几乎没有什么变化。但是，出现了两个新情况：• 逻辑问题现在可以用线性代数的框架通过计算来解决这可以导致渐进计算复杂度的增益。而不是被迫枚举状态，可以执行标准的多项式时间线性代数（在有限域F2上）。• 可以叠加两个逻辑状态，从而研究逻辑状态之间的某些类型的转换。这是微妙的，有点令人惊讶：我们没有明确描述任何关于电路的时间演化，事实上，检查逻辑电路的QLS的通常方法并不关注时间。然而，通过允许叠加状态，我们能够同时研究电路3.2切换滑轮设X是具有通常拓扑的有向图，设U={Uα，Vβ}为X的拓扑的基，其中每个Uα是连通的，并且只包含一个顶点，每个Vβ包含在一条边的内部。X上的切换层S是以下定义在U上的预层S的层：• S（Uα）是副本F2的张量积，每个副本对应于进入到Uα中包含的唯一顶点，• S（Vβ）=F2，• 如果Vβ<$Uα且Vβ包含在第n条引入边中，则限制映射S（Uα）→S（Vβ）是S（Uα）的第n个F2• 若Vβ<$Uα且Vβ包含在n条出边中，则存在固定的F2-线性映射φv：（Uα）→S（Vβ）仅依赖于包含在Uα中的顶点v和n（出边）.这个顶点v的映射集合{φv}是位于顶点v的逻辑函数fv的独热编码φv=Tfv，如前一节所述。M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159167⎜⎝⎟⎠⎜⎝⎟⎠K0S1我0112K我C一x和yz.Σ⎛xy轴11 1 0 xYb0的0 0 1 XyXY.Σ⎛ xy轴从A到C的限制10 1 0 xY01 0 1 Xy XY从A到B的Fig. 1. 一个切换层的例子（在这个图中，xY表示xy）图1给出了一个在一个顶点上的交换层的例子，它代表一个与门。注意，B和C上的层的维数是2，而A上的层的维数是4。当我们相对于曲线U处理C_（？）c_h上同调时，我们将使用符号H_（？） k（X; S）而不是H_（？） k（U; S），以强调使用了曲线的这种选择。命题3.1假设S是逻辑电路X上的开关层。该逻辑电路的每个QLS通过T提升到H0（X; S）的元素。 相反，H0（X; S）的每个元素在每个边缘上限制为（1）或（0）是QLS的图像，通过这个电梯。 任何这样的部分都是非零的。证据给定一个QLSs，很明显，σ=Ts定义了在X的边上S的一个截面。我们只需要在顶点处处理这个提升部分的值。正确的答案很容易得到。假设v是一个有引入边的顶点关于我们{e1，e2，...，ek}。则σ（v）的适当定义为（Ts）（e1）<$（Ts）（e2）<$... （Tφv=Tfv的定义确保每个输出通过T的边与我们对σ（v）的选择一致因此，σ提升到H0（X;S），我们定义为Ts。相反，假设我们有一个全局截面τ，限制为（1）或（0）在每个边缘上。假设U是包含单个顶点v的可收缩开集，其传入边{e+，e+，...，e+}。 由于映射S（U）→ S（e+），每个进入的边缘e+是第i个因子的收缩，我们有τ（v）=（Ta1）τ（Ta2）τ· · ·τ（Tan）其中，（Tai）是第i个输入边沿上的τ显然，这是很好定义的，因为T在F2上的像是二元集{（1），（0）}。0 1如果V包含v的所有向外边的内部，则通过定义切换层S，S（U）→ S（U<$V）是线性映射φv（τ（v））=φv（（Ta1）<$（Ta2）<$··<$（Tan））=（Tfv）（（Ta1）（Ta2）· ··（Tan））=T（f v（a1，a2，. a n）），168M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159SK22F2nfv2m这表明τ是某些QLS的图像，其在v处的输入边缘具有值a1，a2，.一个;这种计算利用了交换图F22nT fv=φ v22m2−→F2T T2−→F2S的这样一个部分是非零的：对于任何QLSs，函数（Ts）在边缘上显然是非零的。 在顶点处，提升取的值是传入边值的张量积，这些值都是非零的。Q4切换层上同调的容度在这一节中，我们使用迈耶-越托瑞斯序列来研究交换层上同调如何随着电路的逐步组装而变化通过这种方式，我们描述了一个增量的方法来计算开关层上同调，模仿的方式原型电路可以增加一个未连接的门的效果是直接的，但增加一个连接线揭示了H1的含义：H1的非平凡元素对应于持续的反馈状态。因此，它们的存在表明可能存在闭锁（稳定反馈）或毛刺（不稳定反馈，通常由竞争条件引起）。目前，我们不知道如何使用切换层来区分这两种反馈，因为形式主义显然对应于无界线延迟模型。我们首先考虑在电路A中增加一个新的门G，但不连接两者的效果。因此，我们考虑X=AHG上的切换层S，其中G是单顶点。 在这种情况下，Mayer-Vietoris序列仅同构Hk（X; S）<$=Hk（A; S）<$Hk（G; S）对所有k. 但是我们注意到由于G覆盖维数为零，所以当k >0时H（Gi）是平凡的。这样，在电路中增加一个不相连的逻辑门，H1不变，而H0的维数增加了G的2#个输入端.为了解释将导线W连接到现有电路A的效应（见图2），我们构造了X=A<$W上的开关层S的梅耶-维托里斯序列。为了确保正确的解释，我们假设W是边的连通子集，A是同伦等价于X-W。在这种情况下，Mayer- Vietoris序列是（我们从符号中删除层0→H0（X）→H0（A）→F2−Δ−→F4→H1（AW）→H1（A）→0.注意，精确性要求dimH1（A<$W;S）≥dimH1（A;S）。观察到M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159169⎝⎠⎝⎠⎧⎪⎨外部输入AWA的外部输出图二. 电路A，连接有反馈线W差异图采用以下形式Δ =ΔP2×kI2×2Ω，Q2×kI 2×2其中I2×k是2 × 2单位矩阵，P2×k和Q2×k是2 ×k矩阵，k是H0（A;S）的维数.矩阵P2×k表示A上的截面对导线W的输出的限制，或者等价地对导线所连接的A同样，Q2×k是从A的截面到A的特定输出的限制，该输出连接到导线。观察到在Δ上的一对行缩减导致矩阵P2×kI2×2Q2×k−P 2×k0 2×2其具有秩2、3或4。 Δ的秩取决于导线参与信号反馈的程度，因此我们为三种可能性命名• 秩Δ = 2：完全反馈，其中Q2×k=P2×k.当导线连接的A的输入和输出总是一致时，就会发生这种情况。• 秩Δ = 3：部分反馈。• 秩Δ = 4：无反馈。这种情况尤其发生在导线W连接A的两个断开的分量时，但更一般地，当W连接的输入和输出完全独立时。因此，我们认为，dimH0（X;S）= dimH0（A;S）−0如果反馈1如果部分反馈2002年，一170M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159Σ和dimH1（X;S）= dimH1（A;S）+4−rank Δ（通过精确性）如果完成费用，则为2000美元bck= dimH1（A;S）+如果部分反馈，则为1不过，这样也行附加W的效果最好用以下口号来描述• 附加一条不参与反馈的导线会抑制逻辑状态，使H1保持不变.• 附加一条参与反馈的导线使逻辑状态保持不变，并增加了H1的维度。这一结果表明，底层空间的切赫上同调在由此产生的切换层上同调中起着作用。切换层检测到的竞争条件和反馈回路就是这样：它们只能在底层空间中存在切赫上循环的情况下出现，这些上循环相对于电路中的逻辑门具有特定的结构。5交换层及其上同调的例子在这一节中，我们展示了切换层的上同调及其解释的方式三个说明性的例子：组合电路与不共享的输入和一个RS的pk-pk-op。这些例子表明，H0的开关层包含至少一样多的元素作为一组QLS。此外，如第4节所示，切换层的H1捕获关于反馈或竞争条件的存在的信息我们给出两个明确的例子来说明这一事实。5.1无共用输入的让我们考虑连通有向树X上的交换层S的情况。(The在X的边上选择方向不影响S的上同调。）这表示在每一外部产出的生产中每一外部投入最多使用一次的情况。在这种情况下，{X}本身就是一个好的覆盖，所以我们得出结论，H1（X;S）是平凡的。通过同样的推理，观察X的组合欧拉特征线是1，因此X的顶点数比内部边数多1因此，如果存在具有入度{m1，.m n}，ndimH 0（X; S）=d i mC0−dimC1=2 mi−2（n−1）。i=1查看H0（X;S）的基础是有益的，因此考虑图3所示的逻辑电路。该电路由一个m输入逻辑门组成.其中一个输入边沿（标记为信号a和a′）被扩展为包括单个单输入缓冲器M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159171221···共2m−1个···1 0···0 1 0个Vm个总输入边emem−1em− 2a，a'Ue1图3.第三章。具有扩展输入沿的单逻辑门识别函数（identity function）我们计算层的上同调和一个基础，这个上同调使用Ce CH复杂。这个复合体的形式是00→F2···F2F2→ 0。d0的矩阵形式为`mfapacemakerxd0=00···0 1···共2m−1个···1 0 1个显然是满秩的因此，H1（X;S）的维数为零。H0（X; S）的维数为2 m，与逻辑电路的QLS个数相同. 因此我们期望H∈ 0（X; S）由QLS的T下的y象所张成，并且情况是这样的.了依据a+e1e2···ema+e1e2···em...a+e1e2···ema+e1e2···em a+e1e2···em...a+e1e2···em其中a在V上支持，另一项在U上支持。特别要注意的是，所有部分都支持整个X，并且所有部分都限制为−−−−→2D172M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159S⎝⎠n个输入n−1D1Dnm个总输入边em em−1em− 2Va，a'Uv见图4。 两个逻辑门组成（0）或（1）在边缘上。因此，该基础由QLS的图像组成1 0给定一个类似于图4中的图Y所示的情况，我们观察到，存在的QLS的数量是2n+m−1。然而，H0（Y1）的维数不同于此数。我们构造了矩阵形式的C_（？）d0=0.1···1 0··· 0fv，0··· 0 1··· 1fv其中fv是指1× 2n的子矩阵，对应于输出值为0的门v上边界映射显然是满秩的，使得H0（Y;S）的维数为2n + 2m− 2，而H1（Y;S）是平凡的。假设fv有k个非零元素n次尝试。我们注意到H∈ 0（x;S）h作为一个基，由T下QLS的图像组成。有k+ 2n−1− 1个基元的形式（特别是，第一项是其中fv非零，e1参与（第二届）d1···d n+ e1···e m.另外还有2m−k +2n−1− 1个形式的元素（其中e1参与第二项）d1···d n+ e1···e m.这证明了一个明显的事实，即如果组合电路中没有共享输入，那么整个电路就没有有趣的异步行为。因此，应该有可能证明下面的猜想，尽管我们还没有成功。猜想5.1如果S是有向树X上的交换层，则H0（X;S）有一个基础，包括取消QLS。这意味着X上任何在任何地方消失的截面必须是两个或多个QLS的线性叠加，因此描述了不确定性或瞬态。M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159173⎜⎜⎟⎟⎜⎜⎝⎟⎟⎛⎜⎞⎟一D图五、具有共享输入信号的组合逻辑电路5.2具有共享输入的图5所示的电路不满足猜想5.1的假设。特别地，它包含用于输入a的两个单独的信号路径。应该清楚的是，作为逻辑电路，它有两个QLS：每个二进制输入值一个。然而，假设电路中存在一些延迟，标记为e的信号将从理想信号a延迟。这意味着电路中存在一定的时间敏感性，因此当输入改变时，它可能会产生毛刺（输出端的窄脉冲）。如果我们考虑逻辑电路上的一个交换层，我们会得到一个具有以下形式的C-交换有界矩阵：1 0 1 0 0 0 0 00 1 0 1 0 0 0 0d0 =1 0 0 0 1 1 0 0.0 1 0 0 0 0 1 10 0 0 1 1 0 1 00 0 1 0 0 1 0 1⎠该矩阵的行缩减揭示了整个图上支持的部分的基础：a+c+dea+c+dea+a+c+c+de+de不或Ce174M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159WQ见图6。 一种R-S双稳态电路很明显，前两个基础元素是QLS的提升。然而，第二个显然既不是QLS的提升，也不是它们的线性组合实际上，它表明输入逻辑值中的模糊性（例如在转换期间发生的模糊因此，它是电路存在时间敏感性的代数指示除了存在H_ ∞（Y;S）的离散基元是附加信息的另一个指示。H_∞ 1（Y;S）在以下情形下是不平凡的：由c+c+d+d+e+e生成，这表明，时间敏感性的来源是用于输入的两个分离的信号路径该计算证明了以下内容定理5.2逻辑电路上的开关层的上同调包含的信息不同于其静态逻辑状态的集合。5.3一个R-S ip-op在一个有一个（无向）循环的图上，还可以构造其他的交换层结构。毛刺是一种时间敏感行为，另一种是瞬态输入的锁存。因此，我们给出了一个典型的例子，一个电路，展示锁存，R-S的ip-op。考虑图6所示的电路X，我们将其分为两部分：具有3输入门的组合电路A和反馈线W。下表总结了该电路[35]一BCQ描述0011危险0111设置1000复位1100保持零1111执一aBC一M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159175P=⎛⎞Q=.查看Mayer-Vietoris序列的差异图Δ，我们注意到，1 0 1 0 1 0 1 0⎝0 1 0 1 0 1 0 1⎠和0 0 0 0 1 1 1 0⎝1 1 1 1 0 0 0 1⎠Δ的所得矩阵具有秩3，使得H0（X;S）具有维度7，H1（X; S）的维数为1。下面是H0（X;S）的基础H 0（X;S）的元素描述危险一套a重置a保持零abc拿一个abc+abc过渡 之间 危险 和复位abc+abc过渡 之间 危险 并设置最令人感兴趣的是最后两个基本元素。这些是两项的线性组合，其中任何一项都不是QLS的提升。最具启发性的解释是，它们暗示了退出危险状态时的不确定性。当输入a和b都从逻辑0转变为逻辑1时，存在竞争条件。只有其中一个会先转换，因此在进入保持状态之前，会有一个短暂的转换到设置或重置状态。如果我们将最后两个基本元素相加，我们得到abc+ abc，这表明关于发生了a或b跃迁的不确定性导致了信号c的不确定性。6讨论开关层的上同调是逻辑电路行为的一个新的信息来源，特别是那些异步的电路特别是，H1的非平凡元素的存在表明电路具有反馈或竞争条件。这是一个粗略的电路行为描述符，因为应该从这样一个全局拓扑不变量的上同调预期。然而，在更短的时间尺度上，关于细节仍然存在重要问题。特别是，切换滑轮的上同调是否能区分毛刺和闭锁？如果H1是平凡的，则H0不包含与逻辑状态相同的信息.实际上，H0的基通常包含较少的信息。（QLS的集合包含在176M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159H0，视为集合。见命题3.1。）在回答这些问题时，与异步逻辑的流行语义模型之一的更清晰的联系可能是必不可少的引用[1] Baker，W.和A. Mahmood，并行同步和保守异步逻辑模拟方案的分析，在：第六届IEEE并行和分布式处理研讨会，1994年，pp. 92比99[2] Branin，F.H、网络类比和向量演算的代数拓扑基础，技术报告，IBM（1966）。[3] Bredon，G.，“Sheaf theory,” Springer,[4] 布朗，M.，E. Clarke，D. Dill和B. Mishra，使用时序逻辑，IEEE计算机学报C-35（1986）。[5] 张志荣，门电路之延迟敏感性，国立成功大学电子工程研究所硕士论文（1992）。[6] Calvert，B.，单曲线电阻网络，电路系统信号处理16（1997），pp.307-324[7] Chappell，S.G.，使用模糊门模型模拟大型异步逻辑电路，在：1971年秋季联合计算机会议，pp。651-661[8] Clarke，E.M.和O.Gru？mberg，Aavoidingthestateexplosionproblemintemporallogicmodelcheckingalgorithms ， in ： Proceedings of thesixth annual ACM Symposium on Principles of distributed computing，1987，pp.294-303.[9] 考克斯，D.，具有置位和复位输入的D-运放的完整综合方法，见：第9届NASA超大规模集成电路设计研讨会，2000年。[10] Dalrymple，D.一、“Asynchronous Logic Automata,” Master’s thesis, MIT[11] 戴维斯，A.和S.陈文辉，异步电路设计，国立成功大学计算机科学系硕士论文（1997）。[12] 爱德华兹，D。A.和W. B.汤明，异步电路设计在工业中的地位，技术报告IST-1999-29119，异步电路设计工作组（2004）。[13] Endecott，P.和S. Furber，使用LARD硬件描述语言，在：第12届欧洲仿真多人会议论文集，1998年，pp.39比43[14] 等人，J.C.的方法，[15] 等人、N. K.，基于低温多晶硅TFT技术的可扩展，见：IEEE国际固态电路会议，2005年。[16] 哈里森，J.，形式证明-理论和实践，AMS55（2008）的通知，pp。公元1395-1406年。[17] 霍尔角A. R.，“Communicating Sequential Processes,”[18] Hubbard，J. H、“TeichmüllerTheory，volume1.” MatrixEditions，2006.[19] Hu Jiangman，D.一、顺序开关电路的综合，技术报告274，电子学研究实验室，麻省理工学院（1954年）。[20] Ishiura，N.，M. Takahashi和S. Yajima，逻辑电路异步行为，第26届ACM/IEEE设计自动化会议，1989年。[21] 马诺哈尔河和A.李文，准延迟不敏感电路是图灵完备的，第二届异步电路与系统高级研究国际研讨会，1995年。[22] Martin，A.，将通信过程编译成延迟不敏感的VLSI电路，技术报告5210：TR：86，加州理工学院计算机科学系（1986）。[23] Martin，A.，一种异步微处理器的设计，技术报告Caltech-CS-TR-89-2，计算机科学系，加州理工学院（1989）。M. Robinson/Electronic Notes in Theoretical Computer Science 283（2012）159177[24] Martin，A.，异步电路中延迟不敏感性的限制，技术报告Caltech-CS-TR-90-02，计算机科学系，加利福尼亚理工学院（1990年）。[25] Matsumato，T.，On several geometric aspects of nonlinear networks（O