背压控制延迟不敏感系统通信流动 在理论计算机科学中的应用.

理论计算机科学电子笔记146（2006）61-80www.elsevier.com/locate/entcs背压在实现延迟不敏感系统中的作用卢卡山口Carloni计算机科学系哥伦比亚大学纽约市，纽约，NY摘要背压是一种逻辑机制，用于控制延迟不敏感系统（LIS）的通信信道上的信息的流动背压对于构建开放式LIS是必要的，并且对于封闭式LIS，它也代表了一种有趣的设计替代方案，因为它可以实现高度模块化的实现，在设计开销（面积、功率）方面具有更可预测的特征。在讨论背压的作用时，我们重新审视了必要的构建块的逻辑，并解释了系统拓扑结构的影响在系统性能上。关键词：延迟不敏感设计，GALS，标记图，片上系统（SOC），构造校正方法。1介绍延迟不敏感设计理论是通过组装预先设计的模块来设计复杂数字系统的正确构造方法的基础[8，9]。这些模块通过在通信架构上交换数据进行交互，该通信架构由点对点无损FIFO通道组成，并基于延迟不敏感协议工作该协议保证了一个正确的系统行为独立于通信信道的延迟。该理论的一个重要应用是延迟不敏感的设计方法，以构建具有纳米技术的千兆级片上系统（SOC）[7]。这里，延迟不敏感设计提供了各种1电子邮件：luca@cs.columbia.edu1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.05.03662L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61中继站中继站壳1中继站中继站壳3壳体2中继站壳4中继站壳5珍珠5号珍珠4号珍珠2号珍珠3号珍珠1号图1.外壳封装，中继站插入和通道背压。实际优点：（1）它简化了预先设计和预先验证的知识产权（IP）核的重用，只要它们是可停止的，就可以与通信协议接口，而不改变它们的内部结构，（2）它通过插入任何数量的顺序中继器（中继站）来实现长导线的后验自动流水线，以及（3）它促进了直到设计过程的后期阶段此外，延迟不敏感设计不需要工程师在他们的实践中进行革命：因为它是基于同步范式[1]，它代表了一个理论上合理的框架，通过使用传统的CAD工具，为纳米设计开发了一类新的设计流程图1显示了LIS实现的典型结构及其主要在这个简单的例子中，五个预先设计的模块（珍珠或核心）被封装在尽可能多的接口逻辑块（外壳）中，并通过八个点对点通道进行通信。一些频道通过插入六个中继站进行了管道传输在LIS的信道上传输的数据以真数据包或空数据包来区分。根据AND-因果规则，由壳/核对处理分组：如果新的真分组在每个输入通道上可用，则核消耗来自每个通道的分组，从而更新其内部状态并在每个输出通道上产生新的真分组;相反，在单个输入通道上不存在真分组（并且相应地，存在空分组）足以迫使壳（1）使核停止，（2）将可能存在于其他通道上的那些真分组存储在其输入队列中以供以后使用，以及（3）在每个输出通道上发出空分组在图1的特定实施方式中，每个通道呈现用于将所述信号转换为所述信号所必需的反流信号（由虚线箭头表示）。L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6163实施背压。背压是一种逻辑机制，因此在给定的信道上，下行链路外壳可以请求上行链路外壳暂时停止其真实分组的产生[7]。这个请求的原因是shell在输入队列方面的缓冲能力是有限的。因此，为了避免在被迫使其核心停滞许多连续周期的同时丢失真实分组，外壳最终必须激活对应于正在变满的那些队列的输入信道上的背压许多连续失速循环的原因是来自输出通道的背压或输入通道上的对应真实数据包持续缺乏对齐（或可能是两者的组合）。由于无限长队列在物理上是不可实现的，因此可以认为背压始终是任何LIS的基本实现特征然而，情况未必如此。事实上，为了得到LIS的最终实现，设计人员有时可能会选择是否使用背压或其他仍然不需要无限队列的实现风格这种选择的存在取决于所设计的系统的性质此外，当存在选择时，必须在考虑系统的计算结构与替代解决方案引入的不同设计开销之间的相互作用后做出最终决定在本文的其余部分，我们将进一步讨论这个问题，并解释在哪些条件下这种选择不会影响系统性能。在这样做的同时，我们重新审视了基于背压的LIS的参考实现。2具有背压的延迟不敏感系统的构造块不管特定的实现风格，延迟不敏感的系统是由外壳封装核心，通道连接外壳，和中继站管道通道。在本节中，我们将重新讨论带背压的参考实现（首先在[7]中介绍），并提供有关这些构建块逻辑的更多详细信息通道和背压。 通道是将源壳/核对连接到接收壳/核对的点对点单向链路。数据通过数据包在信道上传输：数据包由可变数量的字段组成。在一个基本的参考实现中，数据包由两个字段组成：payload（有效载荷），包含传输的数据;void package（空包），是一个一位信号，如果设置为1，则表示数据包中不存在数据（空包）。如果分组确实包含void被设置为0），它被称为真包。在一实现中64L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61图2. 中继站的电路原理图在背压的情况下，停止触发信号在通道上以从接收器到源的反向方向传播。在实际的硬件设计中，通道可以被实现为一组导线：与编码要传输的数据所需的导线一样多的导线，加上分别用于空标签和停止标签的两条附加导线通道可以通过在其上分布有限数量的中继站来实现管道化除了提供一个系统的方法来执行有线流水线，在信道上插入中继站创建一种分布式队列。此外，队列的控制逻辑也是分布式的，因为它是由背压机构实现的，其本质上是模块化的。由于SOC [41]的分布式特性日益增强，分布式队列代表了一种比在每个IP核心模块旁边设置长的集中式通信队列更有前途的设计解决方案中继站。在[7，11]中给出了中继站的可能RTL电路实现的图。图2包含对该实现的更详细的描述。该电路针对单时钟同步集成电路：在每个时钟周期t ， 中 继 站 将 分 组 packetInt 和 停 止 分 组 stopInt 作 为 输 入 ， 并 发 射 分 组packetOutt+1以及停止信号stopOutt+1作为输出。PacketpacketInt包含有效载荷dataInt和void表示voidt。分组packetOutt+1具有与有效载荷dataOutt+1和无效dataOutt+1相同的结构。停车标志主要RegdataIndataOutAuxReg无效主要虚空voidOutAux虚空停止inDemuxCtrl FSMstallRegs outMuxCtrl停止输出停止Regmuxmux多工多工muxmuxL.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6165输出编码：[inDemuxCtrl outMuxCtrl stallRegs]sIn正在处理sIn * vIn拖延sInsInsIn/100千分之一ReadAuxWriteAuxsIn/010图3.状态转换图的有限状态机控制中继站。stopInt和stopInt+1支持背压机制。中继站的一个关键特性是其输入和输出之间不存在组合路径。因此，停止信标信号也需要一个时钟周期才能在中继站上反向传播。 由于LIS由无损通道组成，因此我们必须避免在传播停止信号所需的一个周期期间丢失数据。这一事实，结合支持最佳情况下的最大通信吞吐量（等于1）的目标，意味着中继站必须有两倍的存储容量。与简单的边缘触发的缓冲器，它可以类似地用于管道通道没有背压，一个中继站的COM-，提出了字符-IST的双重缓冲能力（连同必要的控制逻辑）：一个次要（或辅助）寄存器耦合到主寄存器。如图2所示，三个内部信号控制中继站上的数据流：inDemuxCtrl、stallRegs和outMuxCtrl。 当设置为1时，信号stallRegs确保主寄存器和辅助寄存器中存储的数据包当stallRegs等于0时，相反，基于信号inDemuxCtrl的值，用传入分组更新主寄存器或辅助寄存器。信号outMuxCtrl控制输出多路复用器，以决定输出通道是否66L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61.- 是 的Σ由主寄存器或辅助寄存器驱动图3包含有限状态机（FSM）的状态转换图，表示中继站控制逻辑的可能详细说明，该控制逻辑完善了[7，11]中的控制逻辑。FSM具有2个输入信号（stopIn、voidIn）、3个输出信号（inDemuxCtrl、outMuxCtrl、stallRegs）和4个状态（Processing、WriteAux、Stalling、ReadAux）。输出信号outMuxCtrl和stallRegs仅取决于FSM当前状态，而输出信号inDemuxCtrl取决于FSM当前状态和输入信号stopIn两者。因此，outMuxCtrl和stallRegs是然而，请注意，因为它是必要的，没有组合路径从主输入，把中继站的主要输出，因为输入多路复用器的输出是由主寄存器或辅助寄存器采样。请注意，如果FSM处于Processing状态且voidInt= 1，则无论stopInt的值如何，它都将保持在processing状态。给定的FSM描述它简单地等于stopInt的值，除非中继站在处理状态和voidInt= 1：在这种情况下，stopOutt+1被设置为等于0.最后，注意由该中继站实现的延迟不敏感协议的以下特性：如果下行链路模块（中继站或外壳）仅在一个时钟周期内将stopIn信号保持为高，则中继站不会真正停止（即，没有分组在输出端口上保持超过一个周期）。相反，当满足以下逻辑条件时，中继站知道下行链路模块在给定时间t停止t= 0∨stopInt= 1 stopInt−1= 0。外壳封装。 给定一个特定的核心模块M，可以自动合成为包裹物以包裹M并将其与通道连接，使得它们的组合成为患者系统，即，非正式地，一个“理解”延迟不敏感协议的系统延迟不敏感设计理论保证了唯一必要的前提条件是M是可失速的[9]：在每个时钟周期，只有当所有输入都到达时，内核的内部计算才必须被触发换句话说，只有当对应的真分组已经到达每个输入通道时，M的计算才可以在给定的时钟周期发生真分组的不存在通过空分组（即，空分组标记设置为1的分组）的到达来明确表示。保证这种输入同步是核心模块外壳的首要任务，它与核心停顿严格结合在一起。外壳会使内核停止工作，这可能是因为在输入通道上丢失了一个真正的数据包，也可能是因为至少有一个输出L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6167dInVINsOutMUX非循环组合逻辑regregregdOutvOutsIn核心（珍珠）dInVINsOutMUXCTRL时钟dOutvOutsIn图4.外壳封装：制作IP核患者。通道，其中下行链路（接收器）外壳已经保持高的止动块持续两个或更多个连续循环（通过背压）。当停止核心时，外壳需要执行输入缓冲和输出传播。通过输入缓冲，shell通过将它们存储在专用队列中来避免丢失那些定期到达给定通道（并且还不能被核心处理）的真实数据包相反，输出传播是一种机制，用于保证真实的数据包在通过背压请求的通道的输出端口上保持所需的时间另一方面，在核心停止期间，外壳必须使用无效标记来使没有做出这种请求的通道的每个输出端口上的分组如果不这样做，可能会由于同一数据包的当它实现上面概述的协议时，组合壳-核根据AND-因果关系语义[23]操作，就像普通标记图的转换[17]或同构同步数据流的作用者[31]。这些模型的计算提出了几个有用的属性，包括计算效率和准确的整个系统的性能的可能性。图4显示了一个shell的RTL实现的概念图，该shell封装了一个具有两个输入通道和两个输出的核心模块通道3通道4通道1通道268L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61渠道控制逻辑实现上述各种任务。停止/触发机制简单地通过门控时钟信号来获得，该时钟信号控制内核的寄存器2注意，所有输出信号都被正确锁存：对于输出分组的有效载荷字段，外壳依赖于可失速核心模块3的输出锁存器，而辅助信号，即空隙标签和止动标签由壳体本身锁定最后，请注意输入通道上存在可旁路队列使它们可旁路的原因是为了保证如果新的一组传入真分组可用并且没有来自输出通道的停止请求，则在恰好一个时钟周期中产生新的一组传出真分组，即，不向核的原始延迟添加任何周期外壳封装的设计开销通常取决于内核的大小。当然，核越大，壳封装的相对影响就越小。此外，开发一个优化的shell库是一项可行的任务，因为它们通常可以在许多不同的核心模块中重用。事实上，无论内核的内部复杂性如何，外壳的控制逻辑都保持不变，外壳队列的数量只取决于内核所提出的延迟不敏感协议的这一重要优势不仅简化了外壳的设计，而且还保证了其广泛的适用性：只要核心模块是一个可失速的时序电路，就没有必要知道其内部结构或行为。换句话说，延迟不敏感的设计可以应用于任何失速的3延迟不敏感系统的性能分析无论在信道上引入多少中继站，延迟不敏感的系统，其功能正确性被保证被保持：系统可以在输出通道上产生更多的空分组，以及在输入通道上施加更多的反压力，但是，尽管如此，其处理活动在没有死锁的情况下进行。然而，自然地，延迟不敏感设计的效率与在存在增加的通道延迟的情况下保持足够性能的能力密切相关标称与有效时钟频率。为了正确评估延迟不敏感系统的性能，有必要2回想一下，时钟门控是低功耗硬件设计中的常用技术图4的核心模块是一个摩尔有限状态机，但它可以被任何可失速的顺序模块取代，只要它没有从输入到输出的任何直接组合路径因此，任何任意复杂的流水线电路都可以类似地封装在外壳内。L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6169检查它在输出端口产生void包的频率。因此，延迟不敏感系统S的吞吐量θ（S）被定义为S在给定时间间隔内产生的真实数据包这当然对应于真实分组与真实分组加上空分组之和的比率（如在这样的间隔期间在系统输出处观察到的），并且它是零和一之间由此可见，给定标称时钟频率φ，延迟不敏感系统S的有效频率为φeff（S）=φ · θ（S）投入θ（S）取决于两个因素：S的内部结构和与S运行的环境EVoid Packets的起源延迟不敏感的系统S可以在其主输入处从其操作的环境E接收空分组，显然，在第一种情况下，E影响S的吞吐量θ（S）。从设计的角度来看，第二种情况更有趣，因为它对S可以维持的最大吞吐量设置了限制，而不管它运行的环境如何。设计正确的shell只有在被迫停止时才会在其输出通道上发出空包。实际上，当系统启动时，作为顺序进程的每个核心都用真数据包初始化其输出寄存器。4相反，系统S内部空包的产生是由于中继的存在站的更准确地说，每个中继站在系统中引入一个空分组。空分组对应于中继站的存储元件的初始化值5然后，基于S的计算结构，这些空包中的一些可能在过渡阶段之后离开系统，或者继续在其中永远循环。在后一种情况下，它们对θ（S）有负面影响。4这直接源于这样一个事实，即LIS是从正确的严格系统中导出的，其中每个过程都是严格过程，并且不存在停滞事件[9]。5由于中继站是一种换句话说，在不改变其组件的内部逻辑也不危害其整体功能行为的正确性的情况下，将额外的有状态中继器插入到顺序系统中的最简单方法是确保这些中继器使用不会被接收它们的组件处理的值进行初始化对于延迟不敏感的协议，这可以系统地完成，因为中继站引入无效数据包，并且外壳确保核心看不到它们。注意，中继站的初始化通常不能用用于重定时的相同方法来处理[32，48]，因为它们的插入可以在没有重定时不变规则给出的限制的情况下以任意数量发生（位于同步电路的任何反馈路径上的存储元件的数量必须通过重定时保持恒定）[37]。70L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61MG⎪、、、MG最大可持续产量。 由于LISS的结构决定了S可以维持的最大吞吐量，而不管它所处的环境E如何，因此我们有兴趣定义S的内在基本性能指标。我们称这个量为最大可持续吞吐量，因为S有效地以这个吞吐量运行，除非E通过不提供足够的真实数据包来处理或要求它通过背压等待来迫使它减速如下面所讨论的，可以通过建立标记图模型MGS来分析。特别地，S的最大可持续吞吐量可以通过基于以下定义对S标记图模型MGS的最大可持续吞吐量定义为公司简介⎧1）=10000000⎪一，一π（MGS）、如果MGS是无环的;如果MGS是循环的，强连接;、⎪⎩min∀MGSCC∈MGS（MGSCC）否则，请执行以下操作。其中π（MGS）表示MG S的循环时间。首先，由于非循环标记图可以维持任何生产/消费速率，因此通过定义将其最大可持续吞吐量设置为1是合理的第二，当MGS是强连通的时，周期时间的倒数（MGS）等于它的任何临界周期所决定的周期时间的倒数。7最后，当MGS是具有多个强连通分量（SCC）的循环时，则S（S）由其中最慢的分量有效地确定。事实上，如果一个“较慢”的SCC喂养一个“较快”的SCC，它隐含地降低了后者的吞吐量。相反，如果较快的SCC相对于较慢的SCC位于上行链路，则系统没有边界，并且在连接两者的地方有令牌积累SCC。在这种情况下，我们必须将SCC（MGS）解释为实现S的设计约束，即设计者必须通过“减慢”更快的SCC或“加速”更慢的SCC来满足的约束[6]这证实了直觉，因为没有循环的标记图表示没有反馈路径的流水线系统因此，对于任何可能的初始标记，存在有限数量的步骤K，在此之后，系统中最初的所有令牌空缺（停滞事件）都已通过其输出端口被弹出，并且只要每个输入端口在每个步骤继续接收令牌，则系统中的每个位置都包含令牌。7强连通标记图的圈时与其临界圈的圈度量之间的关系在包括[6，35，36，38，40]在内的几篇文章中有报道L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6171用标记图对延迟不敏感系统建模。基于标记图的构造性建模方法可以有效地捕获LIS实现的结构和行为。该方法是建设性的，因为它在LIS的构建块和一些预定义的标记图形结构之间应用了一对一的详细描述如何使用标记的图超出了本文的范围，我们参考[12]。8然而，观察到“经典LIS”实现可以方便地标记的图，因为在协议级，它作为确定性系统操作，一旦在初始状态中将空分组与真分组区分开，就完全确定了该确定性系统的行为当然，可以引入其他延迟不敏感协议，以便利用以下事实：对于某些核心模块，并非必须在每个时钟周期对每个输入通道进行采样（如[42]中所提出的然而，这样的协议的正确设计将需要更多的信息，核心的内部结构比什么是“黑盒子”IP核给出和他们的性能分析将可能需要超越简单的标记图，而不是使用更强大的基于标记图的构造性建模方法捕获了两种虚拟实现，其中外壳具有无限的内存空间来存储接口信号（有限队列），以及基于有限队列和背压组合的实现。在这两种情况下，我们可以使用标记图的理论性质来证明任何LIS都是通过构造而活的，以确定它是否有界，并静态地计算其最大可持续吞吐量。对于无限队列的情况，这些模型可以用于确定系统的吞吐量是否最后，该模型允许我们得出具有重要实际后果的结果：对于任何给定的LIS，我们可以基于背压和长度等于2的有限队列构建物理实现，其与具有无限队列的虚拟8在[10]中，我们提出了一个基于ad-hoc形式主义的LIS性能分析（称为lis图，即延迟不敏感系统图）。由于lis-图被证明等价于标记图，在[12]中我们用标记图代替了它们。72L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61MGB一S4e'CeD中继站S3壳S2壳S1壳图5.一个非强连接的循环延迟不敏感系统，其SCC之间插入一个中继站。B一一个'CeDS3壳S2壳S4中继站S1壳图6.一种非强连接循环延迟不敏感系统，其中一个中继站插入SCC中。4讨论我们在这里提供了一个定性分析的一些关键方面，应该考虑，而实现一个延迟不敏感的系统。系统拓扑的作用。如在第3节中所讨论的，最大可持续吞吐量SNR（S）以及最终延迟不敏感系统S的性能基本上取决于中继站被插入的位置（以及数量在这方面，我们只需要分析系统的计算结构，这是由其相应的标记图模型捕获的。我们有四个主要场景：L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6173MGMGMG名爵(i) MGS是一个无圈图。9在S的任何信道上插入中继站不会对SNR产生影响（S）。 一些空包是ob- 在系统的输出端口处提供，从而迫使相应的真分组以附加等待时间的某些时钟周期到达，但是最终，系统达到稳定状态，并且不再观察到空分组此外，在系统内不会发生无限制的令牌累积在具有多个输入通道的壳中，有限长度的线是必要的，并且这些通道中至少有一个接收一些空包。然而，这些通道可以根据中继站的位置和中继站的总体拓扑（MGS）。(ii)S是一个具有多个强连通分支的循环图，中继站被插入到强连通分支之间。为了不失一般性地分析这种情况，考虑如图5所示的仅具有两个SCC的LIS的情况是足够的。中继站在连接MGS的两个不同SCC的任何信道上，对最大可持续吞吐量QoS（MGS）也没有这一事实似乎有悖常理。毕竟，下行链路SCCSdown是循环系统，并且Sdown的外壳s4在从流水线信道接收到空分组时作出反应，产生在Sdown内传播的空分组。然而，shells4也是在完成围绕S向下的循环之后“退休”这个空包的shell(iii) MGS是一个强连通分支。中继站在MGS的任何信道上的插入总是对最大可持续吞吐量QoS（MGS）产生负面影响。这种影响随MGS的循环结构而变化，通过计算S的循环时间可以精确计算。无论实现是否基于背压，系统内都不会发生然而，无限的代币积累可能发生在系统和它运行的环境之间的边界(iv) MGS是一个具有多个强连通分支的循环图，中继站被插入到其中的一些分支中。 对于每个不同的SCC这种情况归结为前面的情况，并且可以精确地计算相应的最大可持续吞吐量的相互作用9严格地说，如果我们使用背压实现非循环LIS，最终实现不可能是非循环的（这由其有限队列标记图模型反映然而，在这种情况下，事实证明，如果我们使所有重新收敛的前馈路径对上的中继站的数量相等，那么就没有吞吐量下降。Casu和Macchiarulo在[13]中进行了这种观察，他们称之为优化路径均衡。74L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）613然而，需要小心地管理SCC之间的令牌累积，因为这是取决于其SCC的最大可持续吞吐量的相对值而在系统内部可能发生无界令牌累积的情况。如果SCCSup位于相对于另一SCCSdown的上行链路位置中，并且n（Sup）>n（Sdown），则保证发生无界令牌累积例如，图5示出了一个LIS，其中该场景发生，因为S（Sup）= 1而S（Sdown）=2。为了避免无限制的令牌累积，有必要实施背压或减慢更快的SCC。下面讨论这两种选择之间的背压力的作用。在完成在环境E内操作的延迟不敏感系统S的物理实现时是否使用背压机制的选择不是直接的。在第3节结尾处报告的结果保证，这种选择不会影响系统的最大可持续吞吐量ΔS换句话说，只要环境总是能够提供新的真实分组并且不生成任何延迟请求，背压就不是确定系统性能的因素。另一方面，背压是保证延迟不敏感系统S的任何规范可以在任何可能的通道流水线配置下物理实现事实上，背压机制总是可以取代（不可行的）无限长队列的需要，提供一个正确的，物理的系统实现，以相同的吞吐量运行，并且不会遇到任何超过队列的队列然而，反压伴随着这样的假设，即只要系统发回一个停止事件，操作环境就准备好停止。在这方面，物理实现的完成通常归结为在两个备选方案之间进行选择，以便处理令牌累积问题：(i) 使用背压并动态地降低环境E的代币生产率以匹配S的最大可持续吞吐量;(ii) 不使用背压，并且通过以与S的有效时钟频率φeff（S）匹配的标称时钟频率φ（E）运行E来静态地降低E的令牌生产率。然而，当S是一个开放系统，即一个必须被设计而不能控制构成其操作环境E的其他系统的设计的系统时，这种选择可能受到限制。在这种情况下，如果E是延迟不敏感的，则必须使用背压，而如果E不是延迟不敏感的，则S的最终设计仅适用于以有效时钟频率S运行的环境。L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6175相反，当S是封闭系统时，上述决定仅受对替代解决方案的面积和功率开销的考虑的影响我们知道，在一个带有反压的实现中，将所有shell输入队列的长度设置为2就足够了。因此，背压使得能够创建非常模块化的设计。此外，每个壳的面积影响可以容易地从关于对应的芯的输入通道的数量的信息来估计此外，有必要考虑到用于实现背压信号的额外电线以及每个中继站内的双重存储空间。另一种方法是不使用背压，从而去除这些额外的电线，并在每个中继站的位置部署单位容量的状态中继器。然而，在这种情况下，需要均衡系统中每个SCC组件的吞吐量值，以避免无限制的累积。此外，系统中每个shell的每个输入队列的大小都必须特别确定，并且其有限长度可能会有明显的变化10这是另一个原因，为什么它是重要的，以作出一个平衡的尝试，设计，即通信和计算延迟很好地平衡的设计5相关工作用Petri网和标记图进行电路建模。雅科夫列夫等人编辑的文集总结了Petri网在数字系统和电路设计中的应用[50]。Ramchandani是第一个将时间Petri网应用于分析异步并发系统的人[39]。Williams提出了两种类型的标记图，分别称为依赖图和折叠图，作为针对确定性自定时管道的精确吞吐量和延迟的有效计算的特殊模型[49]。Greenstreet和Steiglitz提出了类似的方法来分析自定时流水线[21]，Thiele提出了类似的方法来分析自定时处理器阵列[46]。Nielsen和Kishinevsky使用展开和时序模拟来确定并发系统的周期时间和关键周期，可以表示为“定时信号图”，这为了对异步电路建模，Burns引入了事件规则系统，它等价于标记图，并将异步系统的周期定义为同一事件连续发生之间的渐近平均时间间隔[5，6]。在他的论文[6]中，Burns讨论了计算最小圈的问题[10]静态平衡φ（E）和φeff（S）的最优策略的研究，同时为S导出一个好的通道规划，是一个需要进一步研究的问题。76L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61||||O| | · ||O| | · | | ·并说明了该问题与线性规划的关系。这种联系最初是由Magott观察到的，他用T + 1变量和P制定了LP问题约束，并解决了它，一个通用的多项式算法[33]。在[ 51 ]中已经提出了这个LP问题的替代公式，并讨论了它们之间的关系。Burns提供了一个专门的算法，利用这个LP问题的特定结构在低阶多项式时间内解决它时间标记图的周期时间是一个类似于最大利润时间比的概念，Lawler为此提供了一个（V A logB）算法，其中V是G的顶点集，A是弧集，B是与结果的期望精度相关的变量[30]。正如在[19]中所讨论的，最大周期均值问题是最大利润时间比问题的一个特例。1978年，卡普发表了一个计算最大循环平均值的优雅定理，以及一个复杂度（VA）的同伴算法[28]。从那时起，已经提出了其他几种算法来解决最大周期平均值问题，如[19，24]所述。与对偶优化问题的关系，即。求最小周期平均值和最小成本时间比，在[19]中讨论。作为普通的Petri网，其中每个地方都有一个输入转移和一个输出转移，标记图是一个等价于同构同步数据流的计算模型[31]。同步数据流是最初由Dennis [20]开创的计算的数据流模型的限制版本，并且与Karp和Miller在[29]中提出的计算图与延迟不敏感设计相关的作品。Casu和Macchiarulo已经提出了一种用于延迟不敏感系统的构建块的替代实现，该实现适用于每个核心模块的计算可以静态调度的特定情况[14]。他们的implement- mentation包括建立一个外壳电路，根据一个周期性的调度序列，这是存储在一个本地移位寄存器的核心失速因此，这样的shell不需要读取无效信号和停止信号的值，因此可以删除这些值。而且，由于在这种特定情况下不需要背压，中继站被正常的单位容量有状态中继器（诸如边缘触发的IP-VoIP）取代当然，这种实现方式只适用于封闭系统。基于他们以前在POLYCHRONY设计环境[22，45，47]上的工作他们表明，组件包装器的合成可以使用接口类型描述所携带的行为信息进行优化，以产生最小的L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6177×最大限度地提高生产效率[44]。延迟不敏感设计已被采用作为“管道”组件的操作模式，“管道”是一种可扩展的高性能片上网络（NOC）架构，在将延迟不敏感设计应用于NOC构造的背景下，Singh和Theobald提出了“广义延迟不敏感系统”，并扩展到：具有任意拓扑结构的通信架构（即超越点对点通道）、多时钟系统和“更灵活的同步模块”，其中每个输入通道不必在每个时钟周期进行Hassoun和Alpert在他们的方法中采用了中继站的概念作为基本的同步元素，以实现SOC设计中GALS架构的同时路由和总线插入[25，26]。Chelcea和Nowick开发了一个强大的接口电路库，使得扩展延迟不敏感协议的想法成为可能 混合时序域（同步、异步、多时钟）的设计[15，16]。该库包含几个低延迟，高吞吐量，FIFO队列以及两个新的混合定时中继站。这些电路使用模块化方法设计：它们定义了一组基本接口，包括同步和异步接口，可以组装这些接口以获得FIFO，该FIFO满足“接收器”和接收器端的期望时序假设因此，混合定时FIFO的设计减少到重用和组装一些预先设计的组件。这项工作的重要贡献之一正是混合异步/同步接口的中继站的新设计。Jacobson等人关于作者分享了一些动机（例如，互连延迟在纳米设计中的主导地位），同时他们非常强调开发仅按需执行计算的功率感知技术的需要此外，潜在的哲学--找到“在同步环境中提供异步特性优势的技术中间地带”的目标-这两种方法之间的一个重要区别在于实现级别，特别是在用于实现以下阶段的电路中：78L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）61×同步流水线。中继站提供与每个“级寄存器”并行的相反，在[27]中，没有插入并行的额外寄存器，并且通过使用串联的每隔一个寄存器来避免数据丢失因此，Jacobson等人报告说，当没有发生停顿时，流水线的最大占用是N/2个数据项，其中N是（串行）级寄存器的数量。这等同于具有N个中继站的类似管道的占用，然而，其中，低吞吐量是1而不是0。5.最后，Borgatti et al. 提出了一种可重构的片上通信网络，该网络由多上下文、可编程交叉开关组成，该交叉开关使用改进的Flash-EEPROM器件矩阵实现[4]。为了提高可编程互联网的速度，他们将弹性互联的概念[34]与新设计的通信协议相结合。这与具有背压的延迟不敏感系统类似地操作，因为它通过使用拥塞信号来保证无损通信，该拥塞信号相对于数据和控制的流在相反的方向上传播引用[1] A. Benveniste，P. Caspi，S. Edwards，N. Halbwachs，P. Le Guernic，and R.德·西蒙尼。十二年后的同步语言。 Proceedings of the IEEE，91（1）：64[2] D. Bertozzi和 L. 贝 尼 尼pipes ： 千 兆 级 片 上 网 络 架 构芯 片 IEEE Circuits and SystemsMagazine，4（2）：18[3] D. Bertozzi，A. Jalabert，S.穆拉利河Tamhankar，S.斯泰久湖Benini和G.德·米凯利。片上多处理器系统的NoC综合流程。IEEE Transactions on Parallel and Distributed Systems ，16（2）：113[4] M.博尔加蒂角奥里基奥河佩利科尼河卡内加洛角Gazzina，A. Tosoni和P. Rolandi。采用0.18µ mEEPROM开关和弹性互连的多上下文6.4Gb/s/通道片上通信网络。ISSCC技术文件摘要，2003年2月[5] S. M. Burns和A. J·马丁异步电路的性能分析与优化。 在VLSI的高级研究中，第71MIT Press，1991.[6] Steven M.伯恩斯异步电路的性能分析与优化。博士论文，加州理工学院，1991年。[7] L. P. Carloni，K.L. McMillan，A.Saldanha和A.L. 桑吉瓦尼-文森泰利一种“按构造纠正”延迟不敏感设计的方法计算机辅助设计国际会议论文集，第309-315页，加利福尼亚州圣何塞，1999年11月。美国电气与电子工程师协会。[8] L. P. Carloni，K. L. McMillan和A. L.桑吉瓦尼-文森泰利延迟不敏感协议。 在N. Halbwachs和D.Peled ， editors ， Proceedings of the 11th International Conference on Computer-AidedVerification，volume 1633，pages 123-133，Trento，Italy，July 1999.施普林格出版社[9] L. P. Carloni ， K. L. McMillan 和 A. L. 桑 吉 瓦 尼 - 文 森 泰 利 延 迟 不 敏 感 设 计 理 论 。 IEEETransactions on Computer-Aided Design of Integrated Circuits and Systems，20（9）：1059L.P. Carloni/Electronic Notes in Theoretical Computer Science 146（2006）6179×[10] L. P. Carloni和A. L.桑吉瓦尼-文森泰利延迟不敏感系统的性能分析和优化。设计自动化会议论文集，第361- 367页美国电气与电子工程师协会。[11] L. P. Carloni和A. L.桑吉瓦尼-文森泰利处理SOC设计中的延迟。 IEEE Micro，22（5）：24-[12] 卢卡·P·卡洛尼延迟不敏感设计。博士论文，加州大学伯克利分校，电子研究实验室，工程学院，伯克利，CA 94720，2004年8月。备忘录编号UCB/ERL M04/29。[1