通过并行前缀计算的优化的包容亚稳态的排序

摘要

为了提供更小、更快且更不易出错的电路用于对可能的亚稳态输入排序，提供了一种新的排序电路。根据本发明，该电路是包容亚稳态的。

说明书

技术领域

本发明涉及用于对任意数量的输入排序的包容亚稳态的电路。

背景技术

亚稳态是在跨时钟域时的基本障碍，潜在地导致具有严重后果的软错误。由于已表明亚稳态是不能被确定地避免的，因此采用同步器来将错误可能性减小至可容忍的水平。这种方法用宝贵的时间来换取可靠性：分配给亚稳态解决的时间越多，亚稳态引起故障的可能性就越小。

最近，不同的方法已被提出，创造了包容亚稳态(MC)的电路(S.Friedrichs、M.Függer和C.Lenzen，“Metastability-Containing Circuits”，在IEEE Transactions onComputers中，第67卷，第8期，第1167-1183页，2018年8月1日)。它接受在给数字电路的输入中的有限量的亚稳态，并确保了其输出的有限的亚稳态，使得结果仍然是有用的。尤其是在对输入排序时，在对产生于时间-数字转换器的输入排序时可以包容亚稳态，即，可以在不首先使用同步器来解决亚稳态的情况下对测量值正确地排序。

相关工作

排序网络：排序网络通过将来自全序域(totally ordered universe)的n个输入馈送到由2-排序元件、即对两个输入排序的子电路连接的n条并行线中来对这n个输入排序；每当它们不依赖于彼此的输出时，这些就可以并行地作用。正确的排序网络对所有可能的输入排序，即，线被标记为1至n，使得第i条线输出所排序的输入列表中的第i个元素。排序网络的大小是该排序网络的2-排序元件的数量，以及该排序网络的深度是输入可以经过直至到达输出的2-排序元件的最大数量。

并行前缀计算：Ladner和Fischer(R.E.Ladner，M.J.Fischer，“Parallel prefixcomputation”，JACM，第27卷，第4期，第831-838页，1980年)研究了结合性算符对长度l的输入串(在任意字母表上)的所有前缀的并行应用。他们给出了深度O(logl)和大小O(l)的并行前缀计算(PPC)电路(给定实现算符的恒定大小的电路)。已为加法器开发了许多附加构造，并且Ladner和Fischer的构造的特殊情况(极有可能)是被独立地发现的，参阅[24]。然而，没有同时地实现渐近最优的深度和大小的其它构造。

发明内容

本发明的目的是提供用于对可能的亚稳态输入排序的更小、更快且更不易出错的电路。

这个目的是通过根据独立权利要求1所述的电路实现的。在从属权利要求中定义了有利的实施例。

根据本发明的一方面，基本门的CMOS实施实现了克林逻辑(Kleene logic)。比较输入的任务可以被分解为执行对两个输入串的每个前缀对的四值比较，随后推断出对应的输出位。将用于B位输入的所得的2-排序(B)电路插入到用于n个值的排序网络中容易产生用于n个有效串的MC排序电路。

以上将MC排序的任务简化为并行前缀计算(PPC)问题，对于这，由于Ladner和Fischer的著名结果(Richard E Ladner和Michael JFischer，Parallel PrefixComputation.JACM，27(4):831–838，1980),已知电路在深度和大小上被同时(渐近)优化。根据本发明的一方面，可以使用他们的构架来推导出本发明的电路，该构架允许在2-排序电路的深度与大小之间的权衡。最显著的是，针对深度的优化将电路的深度减小至优化的

所设计的电路的布局后面积和延迟与直接的非包容性实施所提供的基线相比是有利的。

附图说明

图1示出了CMOS技术中的反相器(左)、NAND(中)门和NOR(右)门的标准晶体管级实施。可以通过附加反相器将NAND门和NOR门分别转变为AND和OR。

图2示出了确定两个格雷码输入g,h∈B

图3示出了产生于本发明构造的对于扇出f＝3的2-排序(9)电路的计算的示例。输入为g＝101010110和h＝101M10000；参见表10的

图4示出了递归树T

图5示出了来自[19]的平衡递归与我们的递归的比较。无界扇出的曲线是所获得的精确大小，而“上界”是指推论5.7中的界限；扇出3曲线示出了非平衡策略对于来自我们接下来推导的定理5.18(对于f＝3且k＝0)的构造也执行得更好。

图6示出了PPC(C，T

图7示出了PPC

图8示出了所修改的构造的大小关于f的依赖性。为了比较，也示出了具有无界扇出的电路的来自推论5.7的上界。

图9示出了根据本发明的实施例的用于实现◇

图10示出了根据out

图11示出了4位输入的仿真摘录，其中，X＝M。行示出了(从上到下)输入g和h、单个非包容性电路的两个输出和我们的设计的两个输出。输入g和h是随机生成的有效串。列1和列3示出了无法实现2-排序(4)电路的较简单的设计。

图12示出了本发明解决方案的PPC排序与标准非包容性排序的比较。对于后者，在B＝16处的意外的延迟减少是用更强的门自动优化的结果，本发明的解决方案没有使用该更强的门。

具体实施方式

我们对于

输入的标准二进制表示是不合适的：可以通过编码来任意地放大输入值的不确定性。例如，将未知的值表示为被分别编码为1011、1100的11或12将产生位串1MMM，即，在对两个串而言不同的每个位置处都是亚稳态的串。然而，1MMM可以表示从8至15的区间中的任何数，放大了在从11至12的区间中的初始不确定性。对于连续值而言不损失准确度的编码为格雷码。

B位二进制反射格雷码

由于每个B位串是码字，所以码是双射的且编码函数也定义了解码函数。用

对于两个二进制反射格雷码串g，

例如：

max

min

到排序电路的输入可以具有一些亚稳态位，其意味着从布尔逻辑的角度看，相应的信号表现为不合规范。然而，它们是本发明意义上的有效串。有效串具有至多一个亚稳态位。如果这个位解决为0或是1，则所得的串对于一些x编码x或是x+1，参阅表2。

更正式地，如果

算符*被称为叠加并被定义为

可以通过考虑亚稳态位的所有可能解决来将max

闭包是关于包容具有使用标准寄存器的时钟逻辑的亚稳态可以实现的最好的，即，当f

如果人们想要构造计算两个有效串的最大值和最小值的电路，从而允许建立用于有效串的排序网络，他还需要回答意味着寻求有效串的最大值或最小值的问题。为了这个目的，假设对于一些x∈[N-1]，有效串是rg

定义

我们旨在关于这个顺序来排序。结果是实现了关于这个顺序的2-排序电路相当于实现了max

因此，我们的任务是实现

定义(2-排序(B))。对于

输入：

输出：

函数：

图1示出了CMOS技术中的反相器(左)、NAND(中)门和NOR(右)门的标准晶体管级实施。NAND门和NOR门可以通过附加反相器而分别转变为AND和OR。

本发明寻求使用仅标准部件和组合逻辑。尤其是，可以使用a+b＝OR

可以证明图1中示出的基本CMOS门根据这个逻辑运转，即，它们实现表3中给出的真值表，由此证实了该模型。

图2示出了确定两个格雷码输入g，h∈B

更具体地，图2描绘了执行两个格雷码串的四值比较的有限状态机。在处理输入g，h∈BB的每个步骤中，它被馈送第i个输入位g

因为奇偶性保持跟踪是否关于标准或“反射”顺序来比较剩余的位，所以状态机正确地执行关于图2中指示的状态的含义的比较。

对于所有i∈[1，B]，我们有

为了将这种方法扩展到潜在的亚稳态输入，所有涉及的算符都被替换为它们的亚稳态闭包：对于i∈[1，B]，(i)计算s

读者可能提出问题，为什么我们不是用将产生较小的电路的◇

虽然这种方法产生正确的输出并非是明显的，但可以正式地证明：(P

虽然手动地验证所有3

为了读者的方便，表6给出了◇

可以观察到，对于

推理是基于区分两种主要情况的：一种是

还可以观察到，如果对于任何i∈[B+1]，

算符out：B

图3示出了产生于本发明构造的对于扇出f＝3的2-排序(9)电路的计算的示例。输入为g＝101010110和h＝101M10000；对于

为了从上面推导出小电路，我们利用了Ladner和Fischer的PPC构架。他们描述了适用于将B个输入符号的序列转换为B个输出符号的任何有限状态机的泛型方法(genericmethod)，以获得大小O(B)和深度O(logB)的电路。他们通过注意到每个输入符号定义限制转换函数来将问题简化为并行前缀计算(PPC)任务，该限制转换函数的关于起始状态评估的组成产生在对应数量的步骤之后的机器的状态。这匹配了我们的需求，因为我们需要确定对于每个i∈[B]的

我们重新审视了构架中的与我们的构造相关的部分，从而还在该过程中提供了关于他们的结果的小改进。为了这个目的，我们首先针对结合性算符的特殊情况正式地指定了PPC任务。

定义5.1(PPC

输入：d∈D

输出：π∈D

函数：对于所有i∈[1,B]，

在我们的情况下，

图4示出了递归树T4(中)。右节点被描绘为黑色，左节点为灰色并且叶被描绘为白色。在左节点和右节点处应用的递归模式分别被示出在左侧和右侧。在根及其左子节点处，我们有

更具体地，假设C和P分别是针对一些B∈N实现

图4c中示出的第二递归模式避免了将电路的深度增加至超出针对每个递归级必要的d(C)。现在假定B是2的幂。我们将递归表示为树T

定义.T

现在如下地定义递归构造。右节点将图4中给出的模式应用于右侧，其中，R

下面，用PPC(C,T

可以证明，如果C实现了

它保持了对电路的大小的限制。用F

渐近地，在

由此可见，对于B∈N和实现

我们注意到，人们可以通过进行关于右递归的情况区分来给出更精确的界限，为了简要的缘故，这里我们省略了这些界限。替代地，我们对于B≤70计算了精确数。

图5示出了来自Ladner等人的平衡递归与我们的递归的比较。无界扇出的曲线是所获得的精确大小，而“上界”是指上方给出的界限；扇出3曲线示出了非平衡策略对于我们接下来推导的构造(对于f＝3和k＝0)还执行得更好。

从以上结果的迭代应用推导出的构造可以与PPC(C,T

假设C实现了

图6示出了PPC(C,T

优化的深度构造引致过大的扇出Θ(B)，因为左递归调用的最后输出需要驱动将其与对应的右调用的输出中的每个输出组合的C的所有副本。这牵涉到，尽管其深度较低，但它将不会得到与简单地递归应用来自图4a的构造相比物理延迟更小的电路。当然，人们可以插入缓冲树，以确保恒定的扇出(并且因此确保延迟与深度之间的恒定有界的比率)，但这将深度增加至Θ(log

我们现在修改递归构造，以确保恒定的扇出，代价是电路大小的有限增加。结果为具有大小O(B)、优化的深度和恒定的扇出的第一构造。

下面，我们用f≥3表示我们正试图实现的最大扇出，其中，我们假定向电路提供输入的门或存储器单元不需要驱动任何其它部件。为了简单起见，我们考虑C是单个门。

我们在两个步骤中进行。首先，我们将2B个缓冲器插入到电路中，从而确保扇出在除了在提供每个子电路的与右节点对应的最后输出的门处之外的每个地方都以2为界。在第二步骤中，我们将通过足够频繁地重复这样的门来解决这，从而使改变顺着树递归地传播。这些改变都将不影响电路的输出或其深度，所以主要的挑战是表明我们对最终电路的大小的界限的扇出的主张。

步骤1：几乎以2为界的扇出

在进行到详细构造之前，我们需要对电路的一些结构了解。

对于节点v∈T

·如果v是根，那么R

·如果v是在R

·如果v是在R

·如果v是左节点p的右子节点，那么R

假设PPC(C,T

那么，

(i)它具有2

(ii)

(iii)如果v是右节点，那么它的所有输入都是其子节点的子电路的输出，以及

(iv)如果v是左节点或叶，那么仅它的偶数输入由其子节点(如果它有子节点的话)提供，而对于奇数k∈[1,2

这导致电路PPC(C,T

根据这个表示，我们将推导出PPC(C,T

1)在将聚合树中的任何聚合树的非根节点连接到其对应的子电路的每条线上添加缓冲器(参见图6a)。

2)对于与具有范围R

3)对于具有范围[i，i+j]的每个右节点r，在输出

除了提供子电路的与T

保持对插入的缓冲器的计数。下面的helper语句对此将是有用的，但以后也一样。

用

接下来，考虑对于b≥2由L'

用s表示缓冲器的大小。那么，

|PPC(C，T

步骤2：以f为界的扇出

在第二步骤中，我们需要解决PPC(C,T

我们通过定义a(v)开始，并且然后讨论如何使用这些值用于修改电路以获得我们的扇出f的电路。此后，我们将分析与PPC(C,T

定义(a(v))。固定b∈N

假设对于每个叶v∈T

保持修改聚合树，使得根的输出值的足够多的副本是可用的。

考虑与叶v∈T

最后，我们需要对我们在对电路实现这些修改时添加的门的总数进行计数。

对于f≥3，通过根据引理5.15和5.16修改PPC(C,T

我们将我们的发现总结如下：

假设C实现了

由于篇幅限制，我们未分析对于不是2的幂的B的值的构造大小。然而，在图8中，我们绘制了对照B的k＝0且所选择的值f的精确界限(在没有缓冲器的情况下)。

图7示出了作为整个所得构造的示例的PPC

图8示出了修改的构造的大小关于f的依赖性。为了比较，还示出了具有无界扇出的电路的上界。

图9示出了根据本发明的实施例的用于实现◇

首先，我们需要指定计算◇

根据表5a和表5b，对于s，b∈B

通常，分别通过反相器、AND门和OR门来替换取反、乘法和加法来实现布尔表达式f并不导致实现

-_______________________

1例如，

我们看到，事实上，具有适当连线的(和可能的取反的)输入的单个电路可以实现所有四个运算。至于

表8列出了如何映射输入以计算◇

我们注意到，这个电路不是特别高效的XMUX实施；晶体管级实施将小得多。然而，这里我们的目标是验证正确性，并对所得电路的大小给出一些初步指示—完全优化的ASIC电路超出了本文的范围。可以通过移动取反来略微减小实施的大小。由于空间限制，这里我们未详述这个修改，但要注意图12和表9考虑了它。

我们现在已将所有零件就位以组装包容性2-排序(B)电路。如上所述，◇

图10示出了从out

跟随在以上解释之后的是这个构造的正确性，在该解释中我们可以插入任何

更具体地，我们使用以上针对k＝0描述的

图11示出了来自对4位输入的仿真的摘录，其中，X＝M。行示出了(从上到下)输入g和h、单个非包容性电路的两个输出和我们的设计的两个输出。输入g和h是随机生成的有效串。列1和列3示出了无法实现2-排序(4)电路的较简单的设计。

对于

在行为仿真之后,我们继续比较我们的设计与标准排序方法Bin-comp(B)。如之前提到的，通过在每个递归步骤中从算符中取出取反来略微地优化图9中给出的2-排序(B)实施[3]。在如上所述的设计输入之后，我们使用Encounter RTL Compiler用于合成以及Encounter用于定位和定路线。两个工具都是Cadence工具集的部分，并且在两个步骤中，我们使用NanGate 45nm Open Cell Library作为标准单元库。

由于亚稳态包容的电路可以包括在传统布尔逻辑中不需要的额外的门，因此布尔优化可能损害亚稳态包容特性。相应地，我们被迫使在电路的合成期间禁用优化。

图12示出了本发明解决方案的PPC排序与标准非包容性排序的比较。对于后者，在B＝16处的意外的延迟减少是用更强的门自动优化的结果，本发明的解决方案没有使用该更强的门。

Bin-comp被作为二进制基准使用：简言之，Bin-comp包括比较两个二进制编码输入并相应地输出最大值和最小值的简单VHDL语句。它遵循与2-排序相同的设计处理，但然后经历使用一组更强的基本门的优化。例如，标准单元库提供了预构建的复用器。这些复用器由Bin-comp而不是由2-排序使用。我们强调这些更强的门提供了多个布尔函数的优化实施，虽然它们中的每一个仍被作为单个门计数。因此，将我们的设计与二进制设计在门计数、面积和延迟方面进行比较不利于我们的解决方案。而且，我们注意到，优化例程在从B＝8至B＝16行进时切换到采用更强的门(参阅图12)，从而导致Bin-comp实施的延迟的减少。

虽然如此，我们的设计在延迟方面执行得与非包容性二进制设计相当，参阅图12和表9。因为通过在晶体管级上优化我们的设计来进一步优化它是可能的，因此这是非常值得注意的，具有显著的预期增益。对于保持了显著差距的门计数和面积，同样是适用的，然而，记得Bin-comp设计通过使用更先进的门隐藏了复杂性，并且不包容亚稳态。

我们强调，我们未通过利用所有可用的门或构想晶体管级的实施来优化设计，因为这样的方法受所利用的库的束缚或者需要标准单元的设计。

总之，我们证实了有效的包容亚稳态的排序电路是可能的。我们的结果指示了优化的实施可以实现与非包容性解决方案相同的延迟，而电路大小没有急剧增加。这在激励我们设计MC排序电路的预期应用：容错高频时钟同步中是非常受关注的。排序是具有改善的同步精度的Lynch-Welch算法的所设想的实施中的关键步骤。由于本文中提出的有效MC排序网络，同步器延迟的完全解决是可能的；从而使得能够递增应用时钟校正的速率，从而显著减少本地时钟资源的相位偏移对算法精度的负面影响。

更一般地讲，在其性能依赖于非常短的响应时间的混合信号控制回路中，如同这里提出的MC电路被关注。当不期望模拟控制时，传统解决方案在能够对任何输入变化反应之前就引起了同步器延迟。使用MC逻辑节省了用于同步的时间，而输出的亚稳态对应于测量的初始不确定性；因此，可以在较短的时间内实现相同质量的计算结果。注意的是，我们的电路是纯组合性的，所以它们既可以用于时钟又可以用于异步控制逻辑。

这样的控制回路的示例是时钟同步电路，但MC已被证明对于自适应电压控制和快速路由是有用的，还具有可接受的低数据损坏可能性。