大规模场耦合纳米计算电路中定位与路由的分层策略

《ACM Transactions on Design Automation of Electronic Systems》：A Layered Strategy for Placement and Routing in Large-Scale Field-Coupled Nanocomputing Circuits

　　摘要：场耦合纳米计算（FCN）设备是一种新兴的纳米技术，用于下一代逻辑计算，其发展受到CMOS技术物理限制的驱动。随着电路设计规模的增加，自动布局和布线（P&R）对于优化设备性能和确保可扩展制造变得至关重要。现有的算法在解决大规模布局和布线问题时面临着挑战，尤其是在当前的时钟方案下。本文提出了一种新的方法，用于在FCN逻辑电路的设计中分离布局和布线问题。通过采用分层方法，这些问题被限制在每层内部，同时通过节点排序消除了层间长的连线，并减少了交叉点。A*算法被用来解决逻辑门之间的布线问题，而创新的时钟分配机制则确保了时钟同步。标准单元库用于实现从门级布局到纳米单元级布局的映射。与现有的最先进方法（如Fiction、Ropper和遗传算法（GA）相比，所提出的方法表现出更优的性能，具体来说，它实现了更高的成功率、更少的门数量和更快的执行时间，以及更低的延迟——特别是在与Ropper和GA相比时。此外，该方法能够实现具有超过1000个节点的FCN电路的自动布局和布线，使其更适合大规模FCN电路设计。

1 引言
CMOS设备中特征尺寸的微型化增加了功耗并扩展了互连区域，从而产生了诸如传输延迟和漏电流等挑战。场耦合纳米计算（FCN）设备[1]由于其高集成密度、快速速度和低功耗而成为下一代逻辑计算的新兴纳米技术。简单的电路已在实验室中得到验证[2, 3]，而复杂的电路（如存储单元[4, 5]和算术逻辑单元[6, 7]也已在理论上设计并进行了仿真。随着电路设计规模的扩大，人们对自动布局和布线（P&R）技术的关注也在增加。除了物理差异外，FCN和CMOS在P&R过程中还面临不同的设计约束。时钟影响计算单元的量子隧穿或磁化行为[8]，这使得全局时钟同步在FCN P&R中成为一个重大挑战。
时钟方案通过使用固定的时钟区域和定义信息流来简化全局时钟同步，从而允许通过逻辑门之间的路径长度评估时钟延迟。使用时钟方案的FCN P&R算法可以分为三类：图论算法[9, 10, 11, 12, 13]、精确算法[14, 15, 16]和启发式搜索算法[17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]。这些方法将电路映射到AND-OR-INV逻辑网表，并将布局和布线问题视为一个整体问题。它们在这些时钟方案的固定信息流拓扑结构内确定逻辑门的位置，然后解决门之间的布线问题。然而，随着门数量的增加，探索额外的信息流拓扑结构会导致效率降低。目前，能够实现全局时钟同步的自动电路通常仅限于几十个逻辑门的配置。
本文提出了一种用于大规模FCN电路P&R的分层策略。该方法适用于具有增强表达能力的大型逆变器逻辑网表的FCN电路。P&R问题将被分解为两个子问题并独立解决。该工作的主要贡献如下：
(1) 分层布局策略：在布局阶段，提出了一种方法，将电路的P&R问题限制在每层内部，同时通过节点排序减少长的连线和交叉点。
(2) 灵活的布线策略：在布线阶段，使用A*算法找到节点之间的路径，并为节点之间的路径执行时钟分配机制以确保全局时钟同步。
(3) 大规模自动设计：提出了一种标准单元库，用于从门级布局映射到纳米单元级布局。所提出的方法能够处理具有1000多个节点的电路，与最先进的方法相比，表现出更高的效率和速度，更适合大规模电路的自动布局和布线。
文章的组织结构如下：第2节介绍FCN的基本概念；第3节回顾时钟方案及相关P&R算法；第4节介绍分层布局和布线方法；第5节展示实验结果；第6节提供结论。

2 FCN综述
2.1 FCN单元和通用原语
FCN设备分为三种类型：量子点元胞自动机（QCA）[3]、纳米磁逻辑（NML）[30]和硅悬挂键（SiDBs）[2]。它们的基本计算单元是QCA单元、纳米磁体或悬挂键。QCA单元具有方形结构，包含四个量子点和两个电子，如图1(a)所示。它有两种稳定的极化状态，分别编码为数字逻辑1和0。QCA中的基本逻辑元素包括一个逆变器（或INV）和一个三输入多数门。通过将对角排列QCA单元可以简单构建一个逆变器，当信息通过这种对角配置传输时，信号会发生反转。多数门的布尔逻辑表达式为F=M(A,B,C)=AB+AC+BC，这意味着输出F始终与三个输入A、B和C中的多数值一致。如果其中一个输入值固定为0或1，则该门分别作为两输入AND门或OR门工作。如图2所示，QCA交叉点可以通过两种方式实现：共面交叉点（使用旋转的QCA单元），存在与信号稳定性和旋转开销相关的问题；多层次交叉点（涉及将QCA单元堆叠在类似CMOS结构的三维排列中），在纳米尺度制造中存在挑战。

2.2 多数逆变器图
任何AND-OR-INV逻辑网表都可以用多数逆变器图（MIG）[31]表示，如图3所示。在MIG中，每个节点充当具有三个输入边的多数门，而互补边实现逆变器逻辑。MIG表示为一个有向无环图M=(V,E,Y)，其中V=X∪N∪{0}表示MIG中的节点集，X=(x1,…,xn)表示输入节点集，N=(n1,…,nm)表示多数节点集，{0}表示常量节点集。集合E中的pi表示边ei的极性是常规的还是互补的，而Y={o1,…,ok}表示输出节点。与AND/OR门相比，多数门提供了更优越的逻辑表达能力。然而，当前的FCN P&R算法依赖于时钟方案来解决时钟同步问题，而这些方案在多数门设计中面临挑战——这导致算法主要依赖于AND-OR-INV逻辑。

2.3 时钟机制
在FCN电路中，极化/磁化状态的传输依赖于局部场。FCN时钟对于电路中的信号稳定性和信息流至关重要。它可以区分为NML设备的三相时钟或QCA和SiDBs技术的四相时钟。图4中给出的QCA时钟机制使用绝热切换，包括四个阶段：切换、保持、释放和放松。在切换阶段，QCA单元从非极化状态转变为极化状态。在保持阶段，保持高势垒，稳定极化状态并驱动相邻单元。在释放阶段，势垒降低，导致极化逐渐减弱。最后，在放松阶段，势垒降至最低，完全解除单元的极化，为下一个周期做准备。根据四相时钟机制，创建了四个不同的时钟：Clock0、Clock1、Clock2和Clock3。同一时钟区域内的QCA单元在相同阶段极化，而相邻区域相位相差一个周期。在FCN电路中，保持时钟同步至关重要。局部同步是指确保逻辑门输入端的时钟数量一致，而全局同步要求所有初始输入到逻辑门的时钟数量均匀。

2.4 时钟方案
时钟方案最初源自一维时钟方案[32]，该方案旨在将QCA单元层沿水平轴划分为多个规则矩形区域，标记为时钟区域0、1、2和3。然而，单个时钟区域内过长的连线可能会由于热力学效应导致电路错误。2DDWave时钟方案[33]使用对角排列的方形时钟区域，每个区域从顶部和左侧接收信息，并将处理后的数据向下和向右传输。由于2DDWave方案中的信息流是固定的，设计反馈路径变得具有挑战性，因此引入了USE时钟方案[34]。在物理实现中，该方案使用“金属垫+时钟线”配置来精确控制每个区域的时钟。同时，USE时钟方案允许灵活设计任何长度的反馈路径，如图5所示。此外，还相继提出了其他独特的时钟方案[35, 36, 37, 38, 39, 40, 41]，包括专门为SiDBs和NML设计的方案。所有这些时钟方案都具有固定的时钟区域和预定义的信息流，其中给定位置的延迟相当于两个时钟区域之间的路径长度。

3 相关工作
FCN时钟是电路逻辑实现的基础。因此，P&R问题的核心在于确保物理可行性并满足FCN时钟的全局同步约束。时钟方案的引入简化了FCN电路中时钟同步约束的复杂性。然而，这些时钟方案中信息流方向的固有限制（例如USE时钟方案中的限制）在电路设计中带来了挑战，特别是对于涉及三输入多数门和XOR门的电路[42]。使用USE时钟方案的先前P&R方法的过程首先将电路转换为AND-OR-INV逻辑网表。然后，在时钟方案内解决逻辑门的布局问题。最终，根据时钟方案下的信息流解决布线问题，从而获得纳米单元级布局。图6更详细地描述了这一过程。

4 提出的算法
本文提出了一种用于大规模FCN电路布局和布线的分层策略。提出的方法首先将路由与门级放置分离，然后将多数反相器逻辑网表映射到门级布局，从而实现纳米单元级的全连接网络（FCN）布局与物理实现（P&R）。4.1 逻辑网表预处理逻辑网表预处理是分层P&R策略的基础步骤。其核心目标是将原始电路网表转换为符合FCN电路物理约束和所提算法输入要求的标准化形式，为后续的放置和路由提供兼容的网表数据。多数反相器逻辑网表：该电路通过ALSO工具[45]进行优化并转换为多数反相器逻辑网表，该工具提供了增强的表达能力。此外，反相器可以集成到多数节点中以降低放置节点的难度[40]。扇出约束：方形时钟区域通过“金属垫+时钟线”配置[34]支持精确的时钟控制，确保物理可行性。所提出的P&R算法也采用了这种配置。由于方形时钟区域内的信息流约束，逻辑网表中的所有节点的最大扇出必须在3以内。如公式(1)所定义，ai表示虚拟节点的数量，bi表示边的总数（包括虚拟边）。对于扇出为3< />< />0.2M×Dmin，其中M表示每个时钟的最大计算单元数，Dmin表示层与层之间的最短曼哈顿距离。算法1概述了放置过程，它以预处理后的有向无环图G′=(V′,E′)和节点层分配rank(V′)作为输入。它从首次排序开始，根据rank(V′)生成初始的层内节点排序并初始化最大迭代次数。曼哈顿距离Lman(v,w)=|xv?xw|+|yv?yw|用于评估连接节点之间的导线长度。对于每次迭代，v1,w1被识别为层间曼哈顿距离最大的节点对（即arg?maxLman(v,w)对于(v,w)∈E′），而v2,w2对应于距离最小的节点对（即arg?minLman(v,w)对于(v,w)∈E′）。限制（在本文中设置为3）代表了Lman(v1,w1)/Lman(v2,w2)比率的上限。对于每次迭代中该比率低于限制的情况：- weightmedian(sort,iter)通过曼哈顿距离标准化和网格占用加权来细化当前的节点排序，生成sorted-by-median；- transposing(sorted-by-median)然后通过局部交换最小化交叉，生成newsort。如果newsort减少了交叉计数（通过q(?)评估，即q(newsort)大多数标准单元的规格格式存储在计算机中，如图10(b)所示。当使用QCA-E工具[47]进行仿真时，该标准单元在25 GHz的时钟频率下表现出0.6525 meV的功耗。图10。(a) 标准单元示例。(b) 大多数门标准单元的规格。

5.2 Mux4_1
如图11所示，MUX4_1是一个用于说明QCA电路从原理图到门级布局，再到纳米级布局的自动布局和路由过程的示例。电路原理图使用ALSO工具转换为多数逆变器逻辑网表。最初，逆变器逻辑被集成在多数节点内。如图11(b)所示，节点5和7之间的逆变器逻辑以适当的权重集成到节点7中。权重集{W}用于存储该层所有节点的权重值。此外，使用灰色节点（虚拟节点）来满足严格的边缘约束并减少节点5的扇出。在分层布局阶段，利用节点排序来消除长导线并减少交叉点。应用A*算法来确定路径，然后分配合适的时钟，从而得到门级布局。使用所提出的标准单元库的MUX4_1的QCA纳米级布局如图11所示，其仿真结果如图12所示。图11. MUX4_1的流程图，从(a)原理图到(b)带权重的节点图，再到(c)门级布局，最后到(d)纳米级布局。图12. MUX4_1的仿真结果。

该示例在配备Intel Core i7-9700F处理器的机器上执行，运行频率为3GHz，拥有16GB的RAM，算法使用C++语言。布局区域包括13×16网格，其中关键路径的延迟为11个时钟周期，算法执行时间为1.31秒。

5.3 数据分析
所提出方法的有效性通过基准测试套件进行评估，并与现有最先进方法进行了比较：Exact in fiction [43]、SA in Ropper [18] 和 GA [21]。所有比较方法的实验结果都是在USE、2DDWave (2DD.)、RES和BANC (BAN.)时钟方案下获得的。表1显示，所提出的方法在所有基准电路中实现了100%的成功P&R；对于定量分析，我们关注所有方法都成功完成P&R的电路，性能指标作为每种比较方法每个电路结果的平均值计算，然后与所提出方法的结果进行比较。当确保P&R完成时：在门数方面，与三种现有方法相比，所提出的方法减少了8.1%；在布局面积方面，与Exact算法（生成最优面积解决方案）相比增加了21.23%，但与SA和GA方法相比分别减少了31.94%和26.15%；在关键路径延迟方面，它的性能优于所有三种方法，延迟分别减少了61.18%（与Exact相比）、78.54%（与SA相比）和79.12%（与GA相比）；在算法效率方面，其执行时间进一步减少了99.71%（与Exact相比）、94.18%（与SA相比）和99.13%（与GA相比）。

表1. 基准测试
| 方法 | 名称 | 节点数 | 独立输出数 | 关键路径长度 | 时钟周期数 | 时钟方案 |
|--------------|-----------|---------|---------|----------|---------|
| Exact [43] | | | | | USE |
| SA [18] | | | | | RES |
| GA [21] | | | | | BAN |
| 所提出的方法 | MUX4_1 | 8 | 6 | 13 | 25 | 2DD |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

该示例在配备Intel Core i7-9700F处理器的机器上执行，运行频率为3GHz，拥有16GB的RAM，算法使用C++语言。布局区域包括13×16网格，关键路径的延迟为11个时钟周期，算法执行时间为1.31秒。

5.3 数据分析
所提出方法的有效性通过基准测试套件进行评估，并与现有最先进方法进行了比较：Exact in fiction [43]、SA in Ropper [18] 和 GA [21]。所有比较方法的实验结果都是在USE、2DDWave (2DD.)、RES和BANC (BAN.)时钟方案下获得的。表1显示，所提出的方法在所有基准电路中实现了100%的成功P&R；对于定量分析，我们关注所有方法都成功完成P&R的电路，性能指标作为每种比较方法每个电路结果的平均值计算，然后与所提出方法的结果进行比较。当确保P&R完成时：在门数方面，与三种现有方法相比，所提出的方法减少了8.1%；在布局面积方面，与Exact算法（生成最优面积解决方案）相比增加了21.23%，但与SA和GA方法相比分别减少了31.94%和26.15%；在关键路径延迟方面，它的性能优于所有三种方法，延迟分别减少了61.18%（与Exact相比）、78.54%（与SA相比）和79.12%（与GA相比）；在算法效率方面，其执行时间进一步减少了99.71%（与Exact相比）、94.18%（与SA相比）和99.13%（与GA相比）。

表1. 基准测试
| 方法 | 名称 | 节点数 | 独立输出数 | 关键路径长度 | 时钟周期数 | 时钟方案 |
|--------------|-----------|---------|---------|----------|---------|
| Exact [43] | | | | | USE |
| SA [18] | | | | | RES |
| GA [21] | | | | | BAN |
| 所提出的方法 | MUX4_1 | 8 | 6 | 13 | 25 | 2DD |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

该示例在配备Intel Core i7-9700F处理器的机器上执行，运行频率为3GHz，拥有16GB的RAM，算法使用C++语言。布局区域包括13×16网格，其中关键路径的延迟为11个时钟周期，算法执行时间为1.31秒。

5.3 数据分析
所提出方法的有效性通过基准测试套件进行评估，并与现有最先进方法进行了比较：Exact in fiction [43]、SA in Ropper [18] 和 GA [21]。所有比较方法的实验结果都是在USE、2DDWave (2DD.)、RES和BANC (BAN.)时钟方案下获得的。表1显示，所提出的方法在所有基准电路中实现了100%的成功P&R；对于定量分析，我们关注所有方法都成功完成P&R的电路，性能指标作为每种比较方法每个电路结果的平均值计算，然后与所提出方法的结果进行比较。当确保P&R完成时：在门数方面，与三种现有方法相比，所提出的方法减少了8.1%；在布局面积方面，与Exact算法（生成最优面积解决方案）相比增加了21.23%，但与SA和GA方法相比分别减少了31.94%和26.15%；在关键路径延迟方面，它的性能优于所有三种方法，延迟分别减少了61.18%（与Exact相比）、78.54%（与SA相比）和79.12%（与GA相比）；在算法效率方面，其执行时间进一步减少了99.71%（与Exact相比）、94.18%（与SA相比）和99.13%（与GA相比）。

表1. 基准测试
| 方法 | 名称 | 节点数 | 独立输出数 | 关键路径长度 | 时钟周期数 | 时钟方案 |
|--------------|-----------|---------|---------|----------|---------|
| Exact [43] | | | | | USE |
| SA [18] | | | | | RES |
| GA [21] | | | | | BAN |
| 所提出的方法 | MUX4_1 | 8 | 6 | 13 | 25 | 2DD |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

该示例在配备Intel Core i7-9700F处理器的机器上执行，运行频率为3GHz，拥有16GB的RAM，算法使用C++语言。布局区域包括13×16网格，其中关键路径的延迟为11个时钟周期，算法执行时间为1.31秒。

5.3 数据分析
所提出方法的有效性通过基准测试套件进行评估，并与现有最先进方法进行了比较：Exact in fiction [43]、SA in Ropper [18] 和 GA [21]。所有比较方法的实验结果都是在USE、2DDWave (2DD.)、RES和BANC (BAN.)时钟方案下获得的。表1显示，所提出的方法在所有基准电路中实现了100%的成功P&R；对于定量分析，我们关注所有方法都成功完成P&R的电路，性能指标作为每种比较方法每个电路结果的平均值计算，然后与所提出方法的结果进行比较。当确保P&R完成时：在门数方面，与三种现有方法相比，所提出的方法减少了8.1%；在布局面积方面，与Exact算法（生成最优面积解决方案）相比增加了21.23%，但与SA和GA方法相比分别减少了31.94%和26.15%；在关键路径延迟方面，它的性能优于所有三种方法，延迟分别减少了61.18%（与Exact相比）、78.54%（与SA相比）和79.12%（与GA相比）；在算法效率方面，其执行时间进一步减少了99.71%（与Exact相比）、94.18%（与SA相比）和99.13%（与GA相比）。

表1. 基准测试
| 方法 | 名称 | 节点数 | 独立输出数 | 关键路径长度 | 时钟周期数 | 时钟方案 |
|--------------|-----------|---------|---------|----------|---------|
| Exact [43] | | | | | USE |
| SA [18] | | | | | RES |
| GA [21] | | | | | BAN |
| 所提出的方法 | MUX4_1 | 8 | 6 | 13 | 25 | 2DD |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |

该示例在配备Intel Core i7-9700F处理器的机器上执行，运行频率为3GHz，拥有16GB的RAM，算法使用C++语言。布局区域包括13×16网格，其中关键路径的延迟为11个时钟周期，算法执行时间为1.31秒。

5.3 数据分析
所提出方法的有效性通过基准测试套件进行评估，并与现有最先进方法进行了比较：Exact in fiction [43]、SA in Ropper [18] 和 GA [21]。所有比较方法的实验结果都是在USE、2DDWave (2DD.)、RES和BANC (BAN.)时钟方案下获得的。表1显示，所提出的方法在所有基准电路中实现了100%的成功P&R；对于定量分析，我们关注所有方法都成功完成P&R的电路，性能指标作为每种比较方法每个电路结果的平均值计算，然后与所提出方法的结果进行比较。当确保P&R完成时：在门数方面，与三种现有方法相比，所提出的方法减少了8.1%；在布局面积方面，与Exact算法（生成最优面积解决方案）相比增加了21.23%，但与SA和GA方法相比分别减少了31.94%和26.15%；在关键路径延迟方面，它的性能优于所有三种方法，延迟分别减少了61.18%（与Exact相比）、78.54%（与SA相比）和79.12%（与GA相比）；在算法效率方面，其执行时间进一步减少了99.71%（与Exact相比）、94.18%（与SA相比）和99.13%（与GA相比）。

表1. 基准测试
| 方法 | 名称 | 节点数 | 独立输出数 | 关键路径长度 | 时钟周期数 | 时钟方案 |
|--------------|-----------|---------|---------|----------|---------|
| Exact [43] | | | | | USE |
| SA [18] | | | | | RES |
| GA [21] | | | | | BAN |
| 所提出的方法 | MUX4_1 | 8 | 6 | 13 | 25 | 2DD |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | |