-
摘要:
由于快速单通量量子 (rapid single-flux-quantum, RSFQ)电路的高频特性，对电路的版图设计构成了巨大挑战. 针对RSFQ电路的高频特性带来的电路时延问题，可以在布线阶段通过使用延时元件如无源传输线来解决. 因为无源传输线的时延与它的长度近似成正比，且传输线的功耗不随着线长增加而增大，所以对于快速单通量量子电路而言长度匹配布线是一个非常重要的问题. 为此，提出了一种高效的考虑长度匹配的RSFQ电路布线算法，包括3个关键策略：1）在生成初始路径时，提出了一种迂回布线的方法，在不改变初始布线空间的情况下，满足无源传输线的部分长度匹配；2）提出了一种基于区域感知的迭代资源插入策略，减少需要添加的额外资源区域；3）提出了一种考虑阻塞代价的长度匹配驱动布线策略，提高了对布线空间的资源利用. 实验结果表明所提算法与现有的多端布线算法相比，布线所需的区域面积减少了8%，运行时间减少了36%，从而取得快速且高质量的布线结果.
Abstract:The high frequency characteristics of rapid single-flux-quantum (RSFQ) circuits poses a great challenge to circuit layout design. In order to solve the circuit delay problem caused by the high frequency characteristics of RSFQ, delay elements such as passive transmission line can be used in the routing stage. The delay of a passive transmission line is roughly proportional to its length, and the power consumption of the passive transmission line does not increase with the increase of the wirelength, so length matching routing is a crucial problem for RSFQ circuits. Therefore, we propose an efficient RSFQ circuit routing algorithm considering length matching, including the following key strategies: 1) when generating the initial path, a method of detour routing is presented to meet the partial length matching of passive transmission lines without changing the initial routing space; 2) an iterative resource insertion algorithm based on region-awareness is utilized to reduce the area of additional resources needed to be added; 3) a length-matching driven routing algorithm considering blocking cost is designed, which improves the resource utilization of routing space. Experimental results show that, compared with existing multi-terminal routing algorithms, the proposed algorithm reduces the area required for routing by 8% and the running time by 36%, thus achieving fast and high-quality routing results.
-
随着后摩尔时代的到来，传统的互补型金属氧化物半导体（complementary metal-oxide-semiconductor, CMOS）电路无法满足超大规模集成（very large scale integration, VLSI）电路设计中对高速计算和低功耗的要求[1]. 快速单通量量子（rapid single-flux-quantum, RSFQ）电路被认为是超导数字化应用中一项非常重要的技术[2]. 基于RSFQ的技术，可以进一步实现节能衍生产品以及高性能器件和计算机[2-5]. RSFQ电路与传统的CMOS电路不同之处在于，CMOS电路是以电压的高低电平表示数字信号的0与1，而 RSFQ电路以量化的电压脉冲的有无表示. 这些脉冲通过无源传输线（passive transmission line, PTL）传输. 由于PTL高速的传输速度（约为光速的1/3），因此被广泛地应用于大规模RSFQ数字电路的互连.
当前有关RSFQ领域的研究已经取得了一些成果. 一些工作表明，基于流水线架构的RSFQ电路可以在5～100 GHz的时钟频率范围内运行[6]，此外通过使用T型触发器实现的RSFQ电路可以在高达770 GHz的频率下工作[7]. 由于RSFQ电路的超高频率，因此每个逻辑门（单元）都需要一个时钟信号来处理数据. 在这种电路中，为了确保输入数据在正确的时间到达每个单元，电路必须是完全路径平衡的. 路径平衡确保电路中从任何主要输入到任何主要输出的所有路径具有相同数量的时钟单元（逻辑深度）[8].
与基于CMOS的器件不同，每个RSFQ的逻辑门只有1个扇出，需要分路器（splitters, SPL）来分割信号实现多个扇出，因此在RSFQ电路中每个标准单元都是由逻辑门与分路器组成的. 基于多阶段的流水线架构RSFQ电路，需要插入大量的D型触发器（D-type flip-flop, DFF）保持路径平衡，大量的DFF与SPL最终使得电路的版图设计变得越加复杂.
为了应对RSFQ电路的时序设计挑战，可以通过增加线网之间的传输时延来满足时序设计要求. 此外传输时延的大小与互连器件的特性息息相关. 无源传输线和约瑟夫森传输线（Josephson transmission line, JTL）都可以实现在超高频率下的正确操作，并且JTL是一种有源互连的传输线，它可以传输无反射的单通量子（single-flux-quantum, SFQ）脉冲，通过在每个阶段重新生成脉冲来识别噪声，但JTL的延迟时间随着偏置电流的变化而变化，使用JTL的时序调整会导致制造芯片的操作裕度和良率的降低. PTL的时延与它的长度大致成正比，并且PTL所消耗的功率与长度无关，因此在大规模时序感知的RSFQ电路物理设计时，采用PTL与逻辑门之间进行互连，并通过PTL的长度扩展完成时序的匹配. 然而，由于PTL与驱动器和接收器之间的部分反射和不完全匹配，在长PTL中可能发生谐振效应[9-13]. 这种谐振效应取决于PTL的长度和SFQ信号的频率，因此对于大规模的RSFQ电路布线问题需要考虑谐振效应对信号传输的完整性的影响.
针对RSFQ电路布线问题，文献[14]针对单通量量子电路PTL互连， 提出一种基于A*的算法，得到的电路尺寸和工作频率与手动设计的相当. 由于RSFQ电路的超高频率以及逻辑元件的特性，对电路之间的互连需要额外考虑时序匹配约束，因此，文献[15]针对时序匹配约束，提出通过单层蜿蜒扩展PTL的长度，满足时序匹配约束，并基于整数线性规划（integer linear programming, ILP）的方法获得相邻逻辑门柱之间的布线方案. 但ILP方法存在解空间大、运行时间久的问题. 基于文献[15]中的单层蜿蜒扩展PTL长度的方法，文献[16]使用模拟退火处理PTL的通道布线，并开发了一种自动版图设计工具. 为了提高CPU时间以及布线的质量. 文献[17]把SPL集成到布线过程中，并提出了一种多端长度匹配布线算法以最小化电路宽度. 文献[18]把布线问题分为全局布线和详细布线，并在全局布线中考虑线长预算. 文献[19]基于2层布线层模型，定义了一种新型曼哈顿布线模型，通过该模型进一步减小了布线空间的大小. 由于通孔对PTL阻抗匹配存在影响，从而破坏信号的完整性， 因此文献[20]考虑了通孔对PTL阻抗匹配的影响， 提出了一种面向通孔最小化的长度匹配布线算法. 文献[21]通过动态层分配算法最大限度减少了通孔的使用. 电路中的最大线长会影响芯片的性能，因此文献[22]提出了一种后布线的布线架构，减少了导线的最大线长，提高了芯片的运行频率. 相较文献[14-16, 18-22]，文献[17]将SPL进行了重分配，提高长度匹配布线的质量，但布线结果的质量很大程度受到初始布线路径和布线资源分配的影响. 此外，在进行长度匹配布线时，对同个布线区域的多个PTL进行贪心的线长延长，从而降低了布线资源整体利用率.
为了解决现有工作的不足，本文提出了一种考虑长度匹配的快速单通量量子电路布线算法. 主要贡献有4点：
1）为了生成高质量的初始布线路径，提出了一种基于PTL垂直段重调整的迂回布线方法. 该方法通过对PTL垂直段进行切割移动，从而很好地权衡生成的初始通道宽度和获得的绕线长度.
2）为了减少需要添加的额外布线资源，提出了基于区域感知的迭代资源插入算法，通过改变资源插入的位置，使得部分布线网格重新得到利用.
3）为了提高布线资源的利用率，基于PTL之间阻塞的定义，进一步提出了一种阻塞感知的双向蜿蜒布线，通过控制PTL进行蜿蜒布线的方向和长度， 减少资源的浪费.
4）实验结果表明，与现有考虑长度匹配的多端布线工作[17]相比，本文算法在布线区域的大小和CPU运行时间，分别能取得8%和36%的优化.
1. 问题模型
由于RSFQ电路严格的时序要求，每个逻辑元件需要在每个逻辑操作接收对应的时钟信号. 此外， 由于逻辑门的扇出能力不足，需要使用带有驱动器和接收器的SPL，使得一个逻辑门传输的数据能被多个逻辑门接收. 一般来说，PTL的连接时延与其本身的长度大致成正比. 为了设计时序感知的RSFQ电路，需要对每个PTL连接设置对应的长度匹配约束，并在布线过程中对相应的PTL进行扩展以满足对应的时序要求. 本文采用文献[15]中的RSFQ电路架构，RSFQ电路一共有2层布线层，在生成初始布线路径阶段，规定在生成初始布线路径时，一层用于水平布线，另一层用于垂直布线，将SPL放置在与布线层不同的活动层中. 图1给出了一个简单的基于SPL重分配的多端布线的示例. 图1(a)表示一个PTLi(ci)实现了多个1对1连接：ci,1, ci,2, …, ci,j，其中j表示PTLi扇出的数量. 图1 (b)为未重分配SPL的RSFQ电路单端布线，由于未重分配SPL，SPL与逻辑元件处于同一区域（逻辑门列区域），相邻的逻辑门列区域之间的区域称为PTL布线区域，用于PTL布线. PTL区域左右两端的所有连接，可以视为多个1对1的单端线网. 对于连接c1,1, c1,2, c2,1, c2,2, c3,1, c3,2对应的延长线长为c1,1(4), c1,2(2), c2,1(4), c2,2(0), c3,1(10), c3,2(8)，其中括号内的数字代表该连接需要延长的长度，最终布线区域的宽度为7.
当考虑SPL重分配时，SPL需要放置在逻辑门列区域之间. 由于SPL由1个接收器和多个驱动器组成，因此参照文献[17]，规定带有接收器和驱动器的SPL大小为2×2，同时为了算法易于扩展到不同的大小，将SPL的大小作为输入参数. 对于重分配SPL的RSFQ电路多端布线，如图1(c)所示，将布线空间映射为一个具有固定高度H和可变宽度的网格图. 网格图的固定高度H是由所有逻辑门列中高度最高的一列决定. 由于考虑了SPL的重分配，可以将每个具有1个源点、多个汇点的PTLi视为多端线网，并且得到最后的布线区域的宽度为6，因此考虑SPL重分配有助于缩小布线区域宽度.
长度匹配布线问题需要一组多端线网组G={g1, g2, …, gn}，一个多端线网组g包含多个连接ci, j (0<i<n). 为了保证同一线网组中的所有连接满足长度匹配要求，规定从时钟源到引脚ci的导线长度为偏斜的基本时延，通过延长PTL线长来满足时延匹配， 所以还需要一组扩展长度EL={el1, el2, …, elm}.
对于同一组gi中的连接ci,j， 长度匹配约束为：
l(ci,j)=Base(ci) + x(ci,j)+y(ci,j)+EL(ci,j)， (1) 其中l(ci,j)表示连接ci,j最终的布线长度，Base(ci)表示从时钟源到引脚的布线长度，x(ci,j)表示连接ci,j在PTL布线区域的水平距离，y(ci,j)表示连接ci,j在PTL布线区域的垂直距离，EL(ci,j)表示对应连接ci,j需要扩展的导线长度. 对于同一组的连接ci,j，最终布线后l(ci,j)的值要保持一致.
2. 算法分析
本节主要介绍长度匹配的快速单通量量子电路布线算法的细节. 图2为本文算法的流程图，在SPL感知的迂回布线阶段，目标是生成初始布线路径，获取合理的通道宽度，并且，在此基础上尽可能对部分PTL进行长度扩展. 因此，在该阶段先通过通道布线算法[23]生成最小的初始通道方案；然后，通过PTL切割转移的策略，以部分匹配对应PTL需要扩展的长度；最后进行SPL的分配以及预防重叠. 在资源分配和可布线性评估阶段，由于通过SPL感知的迂回布线生成的布线区域，并不能满足所有PTL进行长度匹配扩展，因此，通过基于网络流的资源分配和基于区域感知的迭代资源插入，在保证可布线性的同时， 添加合理的布线区域. 在长度匹配驱动布线阶段，为了保证完全匹配所有PTL的扩展长度以满足电路的时序要求，在长度匹配驱动布线过程中，提出基于不同PTL布线的优先级以及阻塞感知的启发式布线算法以获得最终的布线结果. 在得到最终的布线结果后，考虑电路的谐振效应对信号传输完整性的影响，提出了一种迭代中继器插入算法.
以上所提的每个阶段以及策略将在后续章节中进行详细描述.
2.1 SPL感知迂回布线
在SPL感知迂回布线阶段，本文的目标是获得初始化的布线路径，并且在保证生成最小的通道宽度的情况下满足部分PTL的长度扩展. 由于RSFQ电路流水线的结构，使得通道布线模型非常适用于RSFQ电路的布线. 在这种模型中，通道两侧分别为连接的源点和汇点，中间的通道区域用于布线. 通道布线算法的优点有：1）是目前最快的布线算法之一；2）可以在一次计算中找到多条布线路径；3）通常可以找到2点之间最短的连接.
由于通道布线具有以上的优点，本文通过文献[23]的通道布线算法生成PTL初始布线路径，并在此基础上提出一种对PTL垂直部分进行切割转移的迂回布线策略，以满足部分PTL长度扩展.
2.1.1 PTL切割转移策略
在生成PTL的初始路径过程中，每个布线层仅能进行对应方向的走线，此外PTL的长度扩展仅能够使用垂直布线层的布线网格，因此，在SPL感知迂回布线阶段，为了减少后续的布线难度以及提高最终的布线质量，本文提出了一种对PTL垂直段部分切割转移的策略. 该策略在保证生成最小通道宽度的初始布线（在不破坏垂直约束图的最短路径）情况下，尽可能地对每个需要延长长度的PTL进行切割和转移，延长其水平布线层的长度，以部分满足长度匹配约束.
在进行长度扩展时需要先对每个PTLi的垂直部分（trunki）进行切割. 对一个trunki进行切割后，trunki被分为trunki,l和trunki,r，规定trunki,l放置在trunki,r的前面. 切割点的不同会影响PTLi产生的绕线长度. 如图3所示，对trunk1不同的点进行切割、移动分别获得了绕线长度2和8，绕线长度是指将经过切割转移后PTL1的线长减去先前的PTL1的线长， 即图3(b)和图3(c)中虚线线段长度分别减去图3(a)中连接trunk1的水平线段部分. 对于切割点的选择，采用贪心的策略，使得每次切割的位置能够产生最大的绕线长度.
在确定切割点后，对于每个PTL，根据其源点与汇点的位置，规定源点位置高度大于汇点位置高度的PTL方向为下，源点位置高度小于汇点位置高度的PTL方向为上. 每个方向的PTL都有2种产生绕线的方式，如图4所示.
1）方向为下的PTL，如图4(a)所示. 连接源点的trunk向后移动产生绕线；连接汇点的trunk向前移动产生绕线.
2）方向为上的PTL，如图4(b)所示. 连接源点的trunk向后移动产生绕线；连接汇点的trunk向前移动产生绕线.
在转移过程中，PTLi的移动顺序会影响最终获得的绕线长度，为了确定拥有最高的优先级的候选PTLi，引入优先级函数：
P(PTLi)=slacki×cnivleni， (2) 其中slacki表示PTLi需要扩展的长度，cni表示PTLi可以进行切割的位置的数量，vleni表示PTLi的垂直部分长度.
2.1.2 SPL分配和防止重叠
当所有trunk都放置完成，就可以根据每个PTL的源路径和初始路径分配SPL. SPL的位置由ci,j最左边的trunk决定，如果该trunk被切割，那么规定SPLi由trunki,r决定，而不是由trunki,l决定. 当PTLi和PTLj的源点相邻时，SPLi和SPLj可能发生重叠. 为了防止重叠现象的发生，移动trunki,r或trunkj,r使得trunki,r和trunkj,r的距离至少为2，如果trunki,r和trunkj,r无法移动，则插入2列布线资源防止重叠.
2.2 资源分配及可布线评估
在生成初始布线路径后，布线空间无法满足所有的PTLi的长度匹配要求. 部分PTLi需要通过在垂直布线层插入绕线以完全匹配长度扩展. 如果垂直布线层剩余的布线资源无法满足PTLi的长度扩展，将导致最终的布线结果不可行. 因此，本文使用基于列扫描的资源分配器，评估初始路径在长度匹配约束下是否可布线. 如果现有布线区域无法满足所有PTLi的长度匹配布线，则通过基于区域感知迭代资源插入，使得所有PTLi满足长度匹配布线要求， 并有效地利用所有布线资源.
2.2.1 资源扫描和分配
PTL的长度扩展仅能在垂直布线层完成，生成初始布线路径后，通道区域被每个PTL的垂直部分划分为多个区域. 如图5(a)所示，由于PTL的长度扩展至少需要2列的网格进行布线，因此对于每2个相邻的列，使用宽度为2的网格的扫描线从通道顶端向底部进行扫描. 规定可用于布线的网格单元为可用单元，不可用于布线的网格单元作为阻塞单元，部分宽度为1的可用单元作为潜在可用单元. 此外如果部分潜在可用单元与可用网格单元相邻，则这些网格单元称为可合并网格单元.
经过线扫描后得到许多可用网格单元，从左到右将相邻的网格单元结合成布线区域Rj，并得到每个布线区域Rj的布线资源大小. 如图5(a)中，布线区域R1，R2，R3的布线资源大小分别为10，14，24.
如上所述，得到布线资源Rj后需要分配给每个PTLi. 为了尽可能地合理分配布线资源，提高布线质量，采用基于网络流的资源分配. 为此，本文构建了一个资源分配流图G(V，E)，如图5(b)所示. 资源分配流图的构建需要遵守节点规则和边规则.
1）节点规则. 节点集合V由Vrs和Vp两个集合组成，Vrs集合中的vrsi表示布线资源Ri（0<i<n, n为垂直层中可用的资源数），Vp集合中的vpj表示不满足长度匹配约束的PTLj（0<j<m, m为不满足长度匹配约束的PTL数量）. 此外 引入2个虚拟节点S和T，S表示源点，T表示汇点.
2）边规则. 对于每个节点，创建一条有向边S→vpi，表示PTLj需要的网格单元数. 对于每个节点vrsi，创建一条有向边vrsi→T，表示布线资源Ri 被使用的网格单元数. 此外，对于每个节点对(vrsi，vpj)， 当PTLj的初始路径经过Ri时，创建一条有向边vpj→vrsi，该边的权值表示PTLj可以使用Ri的网格单元数.
如图5(c)(d)所示，可以得到PTL1在R1，R2，R3布线区域上使用的资源数分别为10，12，0；PTL2在R1，R2，R3区域上使用的资源数分别为0，2，6；PTL3在R1，R2，R3区域上使用的资源数分别为0，8，4. 如果PTLi在所有区域使用的布线资源与其需要扩展的长度相等，在长度匹配约束下当前布线空间满足可布线性，否则，当前布线空间资源不足，无法保证可布线性. 对此，本文提出了基于区域感知的迭代资源插入策略，以保证电路的可布线性.
2.2.2 区域感知迭代资源插入
在长度匹配约束条件下，初始生成的通道区域无法保证电路的可布线性，因此，对于拥有固定高度H的通道，需要扩展其宽度（添加布线资源）. 在生成初始布线路径之后，存在部分宽度为1的布线区域无法用于布线. 为了充分利用布线空间的资源，通过在该网格单元的左右两侧插入额外布线资源，使得该区域变成可合并网格单元，之后再通过双向蜿蜒布线尽可能地在这些网格单元中布线，减少需要插入的额外布线资源. 为此，本文提出了基于区域感知的迭代资源插入策略. 如图6(a)所示，当把2列布线资源插入布线空间的右端，并重新执行资源分配时，发现布线资源仍然不够，需要另外再加入布线资源. 如果考虑布线资源插入位置，这时2列布线资源会被添加到如图6(b)所示的位置，并且能够满足布线需求.
空列插入的位置如果位于已切割trunk之间，相当于延长了4个单元长度的水平布线层绕线，进一步提高了切割转移策略的绕线长度. 如图7所示，左图的绕线长度为2，当把2列资源插入时，绕线长度增大到6. 如果插入位置中的PTL，通过绕线已经满足长度匹配，那么该位置无法插入布线资源.
当把布线资源插入布线空间时，存在2种情况能利用潜在可用的网格单元：
1）当线网i在当前2列的布线空间中，通过水平布线无法满足长度匹配所需的线长时，会通过垂直布线使用潜在可用单元；
2）当线网i在当前2列的布线空间中，通过水平布线能满足长度匹配所需的线长，但布线资源被其他线网j占用时，有机会通过垂直布线使用潜在可用单元.
如图8(a)所示，当前列的可用单元数量不满足PTL1的延长需求时，PTL1会通过水平布线使用潜在可用单元. 图8(b)表示当前列的可用单元满足PTL1的扩展需求时，由于布线资源可能被PTL1抢占，PTL2无法仅通过垂直蜿蜒布线使用当前2列布线区域资源完全匹配线长扩展的需求，因此更有机会使用潜在可用单元. 当PTL2需要延长的长度加上PTL2的延长布线初始位置的高度越接近布线区域边界时，使用潜在可用单元的概率越大.
为了加强布线空间的利用率，考虑布线资源插入的位置，引入了一个可利用网格单元函数（grid cell function，GF）. 由于PTLi进行长度扩展时可以沿着当前路径垂直向上和向下，因此将函数GF分为向上扩展和向下扩展. 向上扩展时的公式为：
GF(PTLi)=∑q∈Qoi×lenq+(1−oi)(extpiH)lenq， (3) 其中Q表示当前列包含的所有潜在可用单元集合， q代表潜在可用单元，extpi表示PTLi沿着当前方向进行线长扩展时所能达到的高度（extpi=starti+ slacki/2），starti 表示当前PTLi的起始扩展位置， lenq表示潜在可用单元大小，oi表示潜在可用单元q是否满足PTLi的线长扩展，满足时oi=1，否则oi=0. 根据当前所有需要扩展长度的PTL的GF之和，确认资源插入的位置. 向下扩展的公式为：
GF(PTLi)=∑q∈Qoi×lenq+(1−oi)(1−extpiH)lenq. (4) 如果频繁地在布线空间之中插入布线资源，在列扫描时会生成许多布线空间较小的布线区域R. 考虑到线网在大的布线空间中比在小的空间中布线灵活，设置一个阈值G，所有需要扩展长度的PTLi的GF之和小于阈值G时，将布线资源插入布线空间右端. 阈值G在实验中设置为H的1/2. 插入资源后，重新进行资源分配，直到当前电路可布线后停止迭代.
2.3 长度匹配驱动布线
在本阶段，我们需要对所有的在长度匹配约束下的PTLi进行布线，因此需要遍历每个ci,j，并在垂直于当前路径的方向进行蜿蜒布线.
2.3.1 布线优先级
经过资源扫描分配后，我们知道了每个PTLi可以使用的布线资源Rj，由于可能存在多个PTL竞争使用布线资源Rj，为了提高对总的布线资源的利用， 获得较好的布线结果，需要确定哪个候选PTLi在Rj具有布线的最高优先级. 将平均拥塞（average congestion，AC）引入，评估潜在布线空间的拥塞. 首先规定在网格图中bounding-box是从每个PTLi的初始路径水平部分以其剩余需要扩展长度的1/4为高，向上和向下构成. Gk表示网格单元，初始规定每个网格单元的大小为0，并通过计算可以使用bounding-box中的网格单元的PTLi数量定义最终网格单元的大小w(Gk). 当多个线网的bounding-box存在重叠时，引入一个常量K，在本文实验中设置K=2.
AC(PTLi)=∑Gk∈bounding-boxw(Gk)K+slacki. (5) 2.3.2 阻塞感知的蜿蜒布线
得到每个PTL布线的优先级后，需要确定PTL在多个可用布线区域R上的布线顺序. 因此提出了布线区域可用（routing area available，RAA）函数，公式如下：
RAA(Rm)=Resi∑k∈RPResk， (6) 其中Resi表示PTLi在该区域内可用的布线资源数， RP表示在布线区域Rm中所有可以布线的PTL.
对于长度匹配驱动布线方法，文献[17]提出了一种基于垂直蜿蜒和水平蜿蜒的双向蜿蜒布线方法. 由于双向蜿蜒布线要求先从相邻2行布线区域对应的PTLi水平部分进行垂直蜿蜒，并且仅当相邻2行布线区域无法满足PTLi长度扩展时，才会使用水平蜿蜒. 如果PTLi的起始点被其他PTLj用于垂直蜿蜒布线时，该PTLi将无法在该区域布线，进而导致该区域的利用率较低. 因此，为了提高布线资源的利用率，本文提出一种考虑阻塞代价的双向蜿蜒布线的方法，通过控制PTL的垂直蜿蜒长度，加强水平蜿蜒的能力，提高对布线区域的利用.
通过函数AC，我们确定了每个PTLi的布线的优先级，并计算了所有PTLi的AC值. 通过函数RAA确定了每个PTLi的可用布线空间Rj的优先级， 把所有能利用布线空间Rj的PTLi按照拥塞值的大小进行分组， 每个分组的大小为M，通过实验得到M=5时最佳. 在对每个分组内的PTLi进行布线时，考虑先布线的PTLi对同一区间内的PTLj的影响. 这样考虑是因为对当前PTLi进行布线只会影响拥塞值相近的能够在该布线空间布线的PTLj.
为了平衡蜿蜒布线长度和阻塞，使得长度匹配布线获得较好的结果，本文引入一个布线代价函数cost， 通过代价函数确定PTLi的布线方向和长度，充分利用布线空间Rj，从而减小布线空间的宽度.
cost(PTLi)=hi∑k=starti(bk−Bk)， (7) 其中Bk表示布线的长度，规定单位长度为1，bk表示布线过程中的网格的阻塞代价，starti表示PTLi的起点，hi表示PTLi可以在当前布线空间中扩展布线的最大长度.
由于PTL进行长度扩展时，可以沿着当前PTL路径垂直向上或向下扩展. 定义PTLi与PTLj的阻塞关系为：
1）垂直向上扩展时，starti+hi2⩾，当前网格列中PTLj被PTLi阻塞.
2）垂直向下扩展时，star{t_i} - \dfrac{{{h_i}}}{2} \leqslant star{t_j}，当前网格列中PTLj被PTLi阻塞.
因此，bk的更新为：
1）对于垂直向上扩展的PTLi
{b}_{k}=\left\{\begin{aligned} &0,\text{ if }PT{L}_{j}未阻塞\text{，} \\ &blen\times \frac{k}{star{t}_{i}+{h}_{i}}\text{，}\text{ 其他 }\text{，}\end{aligned}\right. (8) 2）对于垂直向下扩展的PTLi
{b}_{k}=\left\{\begin{aligned} &0,\text{ if }PT{L}_{j}未阻塞\text{，}\\ &blen\times \frac{k}{star{t}_{i}-{h}_{i}}\text{，}\text{ 其他}\text{，} \end{aligned}\right. (9) 其中blen代表的是PTLi与PTLj在当前布线资源列中被阻塞的长度.
阻塞感知的双向蜿蜒布线，考虑到优先布线的PTL会阻塞之后的PTL，并通过函数cost提高双向蜿蜒布线在水平方向扩展的能力，加强对布线资源的利用，减少需要插入的资源，以便生成较小的通道宽度. 如图9所示为考虑阻塞代价的双向蜿蜒布线与文献[17]中的双向蜿蜒布线对比结果.
2.3.3 迭代中继器插入
由于驱动器和接收器之间的不完全匹配，谐振效应发生在长PTL线路中. 这些效应是由输入SFQ脉冲与传输线中前一个脉冲的反射重合引起的，并且取决于PTL的特性和输入信号的时钟频率[13]. 此外，PTL的谐振效应会受到PTL具体线长的影响，因此， 当完成PTL长度匹配布线后，才可以得到所有的具体线长，并且根据线长计算可能发生谐振效应的具体位置，本文采用文献[19]中的计算模型.
当有效线长是波长的一半的倍数时，就会发生谐振. 谐振频率与互连线长度之间的关系为：
f = \frac{{m \times {v_{{\text{phase}}}}}}{{2{L_l}}} \text{，} (10) 其中f表示谐振频率，Ll为互连PTL的物理长度，m是一个整数，它决定谐振频率的谐波，vphase表示互连的相速度，其计算主要是通过互连微带中单位长度的电容C和电感L计算，具体的计算公式为：
{v_{{\text{phase}}}} = \frac{1}{{\sqrt {L \times C} }} . (11) 根据式（11）可知谐振与电路中互连的PTL长度有关，因此，定义一组禁止布线的PTL长度，该长度对应于谐振长度. 同时，提出类似于传统CMOS电路的中继器插入方法，通过插入中继器将连接分为较短的2个子段，保证2个子段位于禁止区域以外. 中继器是由1个驱动器和1个接收器组成的，插入中继器会增加电路的功耗以及时延，关于中继器的时延计算参考文献[23]，其中规定每个中继器时延为10个单位长度.
在完成对PTL的扩展后，计算所有PTL的线长. 根据谐振计算模型，评估可能产生谐振效应的PTL，并将之加入到队列Q中. 由于中继器的插入会破坏原先互连的时延匹配，因此需要把中继器的时延考虑到对应连接的时序匹配，并重新计算需要扩展的PTL长度. 对队列Q中的PTL根据线长降序排序，接着选取Q中线长最长的PTLi，并在PTLi的中间位置插入中继器，将连接分为2段子连接. 由于中继器和SPL一样位于有源层中，因此需要防止相邻连接的中继器重叠，如果中继器之间发生重叠，则从发生重叠的中继器的位置沿着PTL路径向左右两侧搜索，寻找合适的位置插入. 当把中继器插入PTLi后，对除PTLi以外的连接进行拆线重布，重新计算Q中剩余的连接的长度，判断PTLj的长度是否还位于禁止长度. 如果连接没有位于禁止长度区域，即该PTLj不存在谐振效应，从队列Q中移除. 重复以上操作，直到队列Q为空退出迭代.
3. 实验结果
本文提出的考虑长度匹配的快速单通量量子电路布线算法LMRouter用C/C++语言实现，实验环境是一个具有96 GB内存和2.0 GHz Intel Xeon CPU Linux服务器，实验所用的基准电路集均来自文献[15，17].
3.1 多端线网实验
为了验证本文整体算法以及各个策略的有效性， 将其应用到一个16位的Sklansky加法器上. 该加法器是7级流水线结构，拥有7个PTL布线区域，用RR0~RR6表示，其中电路的最大扇出为2，并且根据文献[15]中的假设，RR0对应电路输入，因此不考虑长度匹配. 此外，我们根据RSFQ电路的特点随机生成5个测试用例Newb1~Newb5，完善样例多样性. 每个测试用例具体信息如表1所示. 随后，将本文算法与文献[15]提出的基于ILP的算法和文献[17]提出的将SPL后分配的算法进行比较.
表 1 多端线网测试用例详细信息Table 1. Details of Test Cases for Multi-Terminal Nets基准
电路布线区域
高度连接
数量最大延长长度/
平均延长长度RR0 356 83 0.00/0 RR1 356 91 21.91/46 RR2 356 99 28.26/56 RR3 356 103 40.78/130 RR4 356 105 94.02/252 RR5 356 99 128.30/370 RR6 356 50 67.60/346 Newb1 356 99 126.30/370 Newb2 356 106 91.01/252 Newb3 356 91 64.30/260 Newb4 356 50 113.15/554 Newb5 356 105 95.24/288 3.1.1 基于PTL切割转移策略有效性验证
表2给出了基于PTL切割转移（cut and shift, CAS）策略所产生的结果与文献[15]基于ILP方法和文献[17]多端长度匹配布线算法进行对比. 由于引入PTL切割转移，在生成初始布线路径的同时满足了部分PTL的长度扩展，减小了长度匹配驱动布线的压力，所以布线区域宽度分别平均优化26%和4%.
表 2 基于PTL切割转移策略对比结果Table 2. Comparative Results of Strategies Based on PTL Cut and Shift3.1.2 基于迭代资源插入策略有效性验证
表3给出了基于区域感知的迭代资源插入（area-aware iterative resource insertion, AIRI）策略的实验结果. 对比文献[15，17]的实验结果，布线区域宽度分别优化25%和3%，这是由于区域感知的迭代资源插入策略，根据PTL需要扩展的长度和当前路径与布线边界的距离，计算插入资源的位置.
表 3 基于区域感知的迭代资源插入策略对比结果Table 3. Comparative Results of Strategies Based on Area-Aware Iterative Resource Insertion3.1.3 阻塞感知的蜿蜒布线策略有效性验证
表4给出了阻塞感知的蜿蜒布线（blocking aware snaking routing, BASR）策略的实验结果. 从实验结果可以看出，与文献[15，17]相比BASR在布线区域宽度方面分别平均优化27%和4%. 其中，在RR3， Newb4，Newb5上分别取得了7%，11%，9%的优化. 这是因为，通过阻塞感知的蜿蜒布线策略，将PTL根据拥塞值的大小进行分组，并且，根据同组PTL的阻塞关系，在相应的布线区域中为PTL重新分配可使用的布线网格并选择布线的方向，从而减少了对布线资源的浪费.
表 4 阻塞感知的蜿蜒布线策略对比结果Table 4. Comparative Results of Strategies Based on Blocking Aware Snaking Routing3.1.4 多端线网上的算法验证
为了验证本文算法，将本文完整流程的布线算法运行结果与文献[15，17]进行比较. 如表5所示，LMRouter所产生的布线结果，在所有分区的平均结果上，与文献[15，17]相比在布线区域宽度方面分别平均优化了31%与8%. 可以看出与文献[17]相比在布线区域宽度上，Newb4和Newb5区域芯片尺寸的缩减最为明显，分别面积减小了18%和12%.
表 5 多端线网布线结果对比Table 5. Comparison of Routing Results for Multi-Terminal Nets图10是来自RR5部分区域的布线图，由于LMRouter在生成初始布线路径的同时，通过对PTL的迂回布线，延长了水平布线层上的长度，满足其部分的长度扩展，并且通过考虑额外布线资源插入的位置，使得长度扩展能够使用死区的网格单元，减少了需要插入的额外资源数量，最后在长度匹配驱动布线阶段， 根据PTL之间的阻塞关系，合理地控制PTL对布线网格的使用，并加强了水平扩展的能力，进一步提高了对布线区域的利用.
从图11中可以看出LMRouter在运行时间上，平均优化了36%. 这是因为生成初始路径时，文献[17]通过添加空节点改变垂直约束图，获取PTL的扩展并避免SPL的重叠，然而，该方法在添加过多空节点时会增加算法的运行时间. 本文通过基于贪心思想的CAS策略，在生成初始路径后，通过对PTL的切割和转移，快速获取部分PTL的长度扩展.
3.2 单端线网实验
为了验证LMRouter对于单端电路同样有效，本节使用文献[15]的基准测试进行实验. 文献[15]的基准测试用例具有不同数量的终端对、区域高度和指定的PTL扩展. 根据文献[15]中的假设，SPL位于PTL区域的两侧，每个连接对应2个终端. 表6给出了我们提出的布线方法与基于ILP方法[15]和基于A*算法[17]的实验结果. 就布线区域宽度的平均结果，LMRouter分别取得了10%，8%的优化.
表 6 单端线网布线结果对比Table 6. Comparison of Routing Results for Single-Terminal Nets综上所述，本文所提出的考虑长度匹配的快速单通量量子电路布线算法通过设计多种有效的方法和策略，实现布线区域宽度的优化. 本文算法相对文献[15，17]等同类工作而言，在相关性能指标上均取得明显的优化效果.
4. 结 语
针对RSFQ电路的布线问题，本文提出一种考虑长度匹配的快速单通量量子电路布线算法. 在生成初始布线路径过程中，通过一种切割移动SPL的方法，完成了对部分SPL的长度扩展匹配. 并在之后的阶段，提出了一种区域感知的资源分配器保证了可布线性，最后提出了考虑阻塞代价的长度匹配驱动布线算法，实现最终的布线. 实验结果表明，与同类算法相比，本文提出的算法在解决多端和单端布线问题时，均取得了较好的有效性.
作者贡献声明：刘耿耿提出了算法思路和实验方案；余延涛负责完成实验并撰写论文；周茹平负责修改论文；魏榕山负责论文方案分析；徐宁负责理论指导和论文润色.
-
表 1 多端线网测试用例详细信息
Table 1 Details of Test Cases for Multi-Terminal Nets
基准
电路布线区域
高度连接
数量最大延长长度/
平均延长长度RR0 356 83 0.00/0 RR1 356 91 21.91/46 RR2 356 99 28.26/56 RR3 356 103 40.78/130 RR4 356 105 94.02/252 RR5 356 99 128.30/370 RR6 356 50 67.60/346 Newb1 356 99 126.30/370 Newb2 356 106 91.01/252 Newb3 356 91 64.30/260 Newb4 356 50 113.15/554 Newb5 356 105 95.24/288 
下载: 导出CSV
表 3 基于区域感知的迭代资源插入策略对比结果
Table 3 Comparative Results of Strategies Based on Area-Aware Iterative Resource Insertion
下载: 导出CSV
表 4 阻塞感知的蜿蜒布线策略对比结果
Table 4 Comparative Results of Strategies Based on Blocking Aware Snaking Routing
下载: 导出CSV
-
[1] 何小威,乐大珩,郭维,等. 高性能自研处理器物理设计频率提升方法[J],计算机研究与发展2024,61(6):1429−1435 He Xiaowei, Yue Daheng, Guo Wei, et al. Promoting frequency method for our own high performance processor physical design[J]. Journal of Computer Research and Development, 2024, 61(6): 1429−1435 (in Chinese)
[2] Sato R, Hatanaka Y, Ando Y, et al. High-speed operation of random access-memory embedded microprocessor with minimal instruction set architecture based on rapid single-flux-quantum logic[J]. IEEE Transactions on Applied Superconductivity, 2017, 27(4): 1−5 doi: 10.1109/TASC.2017.2684059
[3] Castellanos-Beltran M A, Olaya D I, Sirois A J, et al. Single-flux-quantum multiplier circuits for synthesizing gigahertz waveforms with quantum-based accuracy[J]. IEEE Transactions on Applied Superconductivity, 2021, 31(3): 1−9
[4] Ando Y, Sato R, Tanaka M, et al. Design and demonstration of an 8-bit bit-serial RSFQ microprocessor: CORE e4[J]. IEEE Transactions on Applied Superconductivity, 2016, 26(5): 1−5
[5] Fu Rongliang, Huang Junying, Wu Haibin, et al. JBNN: A hardware design for binarized neural networks using single-flux-quantum circuits[J]. IEEE Transactions on Computers, 2022, 71(12): 3203−3214
[6] Obata K, Takagi K, Takagi N. A clock scheduling algorithm for high-throughput RSFQ digital circuits[J]. IEICE Transactions on Fundamentals, 2008, 91(12): 3772−3782
[7] Chen W, Rylyakov A V, Patel V, et al. Rapid single-flux-quantum T-flip flop operating up to 770 GHz[J]. IEEE Transactions on Applied Superconductivity, 1999, 9(2): 3212−3215 doi: 10.1109/77.783712
[8] Katam N, Shafaei A, Pedram M. Design of complex rapid single-flux-quantum cells with application to logic synthesis[C/OL]// Proc of the 16th Int Superconductive Electronics Conf. Piscataway, NJ: IEEE, 2017[2024-08-17]. https://ieeexplore.ieee.org/abstract/document/8314236
[9] Kameda Y, Yorozu S, Hashimoto Y. A new design methodology for single-flux-quantum (SFQ) logic circuits using passive-transmission-line (PTL) wiring[J]. IEEE Transactions on Applied Superconductivity, 2017, 17(2): 508−511
[10] Schindler L, Roux P l, Fourie C J. Impedance matching of passive transmission line receivers to improve reflections between RSFQ logic cells[J]. IEEE Transactions on Applied Superconductivity, 2020, 30(2): 1−7
[11] Hashimoto Y, Yorozu S, Kameda Y, et al. Development of passive interconnection technology for SFQ circuits[J]. IEICE Transactions on Electronics, 2005, 88(2): 198−207
[12] Ortlepp T, Uhlmann F H. Impedance matching of microstrip inductors in digital superconductive electronics[J]. IEEE Transactions on Applied Superconductivity, 2009, 19(3): 644−648 doi: 10.1109/TASC.2009.2019284
[13] Jabbari T, Krylov G, Whiteley S, et al. Repeater insertion in SFQ interconnect[J]. IEEE Transactions on Applied Superconductivity, 2020, 30(8): 1−8
[14] Tanaka M, OBATA K, lto Y, et al. Automated passive-transmission-line routing tool for single-flux-quantum circuits based on A* algorithm[J]. IEICE Transactions on Electronics, 2010, 93(4): 435−439
[15] Kito N, Takagi K, Takagi N. Automatic wire-routing of SFQ digital circuits considering wire-length matching[J]. IEEE Transactions on Applied Superconductivity, 2016, 26(3): 1−5
[16] Kito N, Takagi K, Takagi N. A fast wire-routing method and an automatic layout tool for RSFQ digital circuits considering wirelength matching[J]. IEEE Transactions on Applied Superconductivity, 2018, 28(4): 1−5
[17] Kou Mingyang, Cheng Peiyi, Zeng Jun, et al, Splitter-aware multiterminal routing with length-matching constraint for RSFQ circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(11): 2251−2264
[18] Kitamura K, Takagi K, Takagi N. A two-step routing method with wire length budgeting for PTL routing of SFQ logic circuits[J]. Journal of Physics: Conference Series, 2020, 1590(1): 012043
[19] Yan Jintai. Length-matching-constrained region routing in rapid single-flux-quantum circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(5): 945−956
[20] Yan Jintai. Via-minimization-oriented region routing under length-matching constraints in rapid single-flux-quantum circuits[J]. IEEE Transactions on Very Large Scale Integration Systems, 2021, 29(6): 1257−1270 doi: 10.1109/TVLSI.2021.3059786
[21] Lin Tingru, Edwards T, Pedram M. qGDR: A via-minimization-oriented routing tool for large-scale superconductive single-flux-quantum circuits[J]. IEEE Transactions on Applied Superconductivity, 2019, 29(7): 1−12
[22] Lin Tingru, Pedram M. Reducing the maximum length of connections in single-flux-quantum circuits during routing[C/OL]// Proc of IEEE Int Superconductive Electronics Conf. Piscataway, NJ: IEEE, 2019[2024-08-16]. https://ieeexplore.ieee.org/abstract/document/8990897
[23] Oshimura T Y, Kuh E S. Efficient algorithms for channel routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982, 1(1): 25−35 doi: 10.1109/TCAD.1982.1269993
计量
- 文章访问数: 49
- HTML全文浏览量: 7
- PDF下载量: 13
