中文题目：通过纠缠熵和投影释放AQFP逻辑电路的布局潜力

论文题目：Unleashing the Potential of AQFP Logic Placement via Entanglement Entropy and Projection

录用期刊/会议：61st ACM/IEEE Design Automation Conference (DAC '24) (CCF-A类会议)

DOI 链 接 ：https://dl.acm.org/doi/10.1145/3649329.3658467

发表时间：2024-6-23

作者列表：

1)柏一诺 中国石油大学（北京） 人工智能学院 本 19级

2)伊恩鑫 中国石油大学（北京） 人工智能学院 硕 21级

3)邢炜 谢菲尔德大学 教师

4)余备 香港中文大学 教师

5)金洲 中国石油大学（北京）人工智能学院 教师

背景与动机:

随着超导技术的发展，绝热量子磁通参数逻辑（AQFP）作为一种高效的超导逻辑技术，因其能耗显著低于传统超导逻辑（如RSFQ）和CMOS技术而备受关注。然而，随着电路规模的增大，AQFP电路的设计面临诸多挑战，特别是数据同步和最大线长约束问题，这些问题导致需要插入大量缓冲器来维持电路的正常运行，从而显著增加了电路的功耗和延迟。现有EDA工具针对CMOS技术设计，无法直接应用于AQFP电路，因此迫切需要开发专门针对AQFP电路的EDA工具。针对AQFP电路布局中缓冲器插入过多的问题，本文提出了一种创新的布局框架，旨在通过最小化额外缓冲器的需求来提升AQFP电路的性能。该框架利用纠缠熵进行拓扑初始化，并通过投影方法进行布局，有效减少了缓冲器的插入数量，同时显著加速了布局过程。这一研究不仅有助于推动AQFP电路的设计自动化，也为超导电子学领域的发展提供了新的解决方案。

设计与实现:

1.纠缠熵

拓扑初始化的主要目的是通过优化电路中各行的单元顺序，减少线长违规，从而降低后续布局阶段对缓冲器的需求，提高电路的整体性能。

图1.消除布线长度违规

我们定义一个叫做纠缠熵的术语用于初始布局，计算公式如下：

 

其中，Xl表示前一行中l的端点的顺序，而Yl表示后续行中端点的顺序。

我们展示了定义的纠缠熵可有效的用于电路拓扑的初始化过程。图1展示了三个不同的电路拓扑示例，可以观察到随着拓扑结构中交点个数（N）的减少，电路的布局效果逐渐提高。同时，我们还展示了纠缠熵这一指标与交点的数量紧密相关，且利用纠缠熵（E）的变化来优化初始布局要好于直接使用交点个数（如图2所示）。

 

 

图2.纠缠熵不同的示例

2.减少纠缠熵

在拓扑初始化阶段，算法通过在同一行内交换单元的位置来逐步优化电路拓扑。每次交换后，都会计算纠缠熵的减少量（ΔE），如果ΔE大于0，说明交换后拓扑的纠缠熵降低，电路布局得到优化，其计算公式如下:

 

将差值取为式中所示，即可得到ΔEi：

在算法开始时，通过对每行中的单元进行初始排序，可以进一步加速收敛过程。排序的依据是单元连接的线数，连接更多线的单元更有可能被放置在行的左端，这样有助于在初始阶段就获得一个相对较低的纠缠熵。算法通过多次迭代，不断交换单元位置，每次交换都旨在减少纠缠熵。随着迭代的进行，电路布局逐渐优化，直至达到收敛条件，即纠缠熵不再显著减少。

3.坐标初始化

坐标初始化旨在根据拓扑初始化阶段得到的电路拓扑结构，为每个单元分配初始的坐标位置，以便在后续的迭代过程中能够高效地调整单元位置并满足布线约束。

 

图3.(a)路径平衡前的电路，(b)路径平衡后的电路（通过插入buffer满足同步和线长约束）

在确定单元的y坐标时，确保每行中单元的顶部左角的最小y坐标等于上一行中单元底部左角的最大y坐标。这样做是为了减少布线长度，并确保数据能够同步到达每一层的单元。对于同一行中的单元，根据拓扑初始化阶段确定的顺序紧密排列，并且使所有单元的中心在y轴方向上对齐。对于第一行，将顶部左角的y坐标设置为0。在迭代过程中，主要调整单元的x坐标。初始时，将每行中最左侧单元的顶部左角的x坐标设置为0，其他单元则根据拓扑初始化阶段确定的顺序紧密排列。

4.单元的理想位置

在逻辑电路布局过程中，为每个单元找到一个理想的位置，以最小化与该单元相连的所有布线的最大长度，这是提高电路性能和效率的关键步骤之一。

 

图4.移动单元到理想位置

初始状态下，两个单元通过一条可能超出最大布线长度约束的长布线相连。为简化问题，我们采用基于投影思想的对称翻转方法，将某单元相邻的两行单元沿着单元所在的轴线对称地“翻转”到同一行上，同时保持布线长度不变。此步骤为理论操作，实际布局中不执行翻转。在对称处理的基础上，通过水平移动将单元移至中间位置。

确定单元理想位置的关键在于最小化与其相连的所有布线中的最长布线长度。通过将所有相连的单元投影到一条直线上，并计算最左侧和最右侧单元x坐标的平均值，得到该单元的理想x坐标位置。将单元放置在此理想位置上，可以确保与其相连的所有布线长度尽可能均衡，从而避免过长布线导致的信号衰减或延迟增加，实现电路布局的优化。

实验结果及分析: 

表1 测试电路信息

表1展示了用于评估所提出的AQFP逻辑电路布局算法的测试例的详细信息，包括每个电路的名称（如c17、c432等）、单元数量（从7个到7552个不等）以及所需缓冲器数量（从7个到3256个不等）。这些数据反映了测试例在电路规模和缓冲器需求上的多样性，为验证算法在不同规模和复杂度下的有效性提供了全面的基准。 

表2 测试结果对比

表2展示了三种算法（遗传算法GA、ASAP算法和本文提出的算法）在多个测试案例上的性能比较。结果显示，在插入的缓冲器数量和缓冲器行数方面，我们提出的算法表现最优，平均减少了98%和81%的缓冲器需求，显著优于其他两种方法。在时间开销方面，我们的算法也表现出色，平均加速比分别达到GA方法的81.82倍和ASAP方法的1.88倍，体现了其在提高布局效率方面的优势。

 

图5.面积功耗延迟对比

通过柱状图展示了在c3540测试例上，应用ASAP算法和本文提出的算法后，电路的延时增加百分比、功耗增加百分比和面积增加百分比的比较。结果显示，与ASAP算法相比，我们提出的算法的电路的延时、功耗和面积的增加百分比均显著降低，表明算法在优化电路性能方面具有显著优势。具体来说，延时增加百分比从34%降低到13%，功耗增加百分比从42%降低到15%，面积增加百分比从38%降低到19%，体现算法在提升电路效率方面的有效性。

结论:

本文提出了一种新颖的算法，旨在高效地布局AQFP超导逻辑电路，减少在AQFP电路中额外插入的缓冲器数量，以提升电路的功率、性能和面积效率。算法分为拓扑初始化和布局插入缓冲器两个阶段，拓扑初始化阶段通过引入最小化纠缠熵的概念来优化每行中单元的顺序，布局插入缓冲器阶段则通过迭代确定每个单元的具体坐标，并在必要时插入缓冲器以消除布线长度违规。实验结果表明，与现有的GA方法和ASAP算法相比，本文提出的算法在缓冲器需求和运行时间上均表现出显著优势，平均减少了98%和81%的缓冲器需求，以及81.82倍和1.88倍的加速比。此外，对c3540电路的测试结果显示，应用本文算法后的电路在延时、功耗和面积方面均有显著降低，表明该算法在工业应用中的巨大潜力。 

通讯作者简介:

金洲，副教授，中国石油大学（北京）计算机系副教授，入选北京市科协青年人才托举工程、中国石油大学（北京）青年拔尖人才。主要从事集成电路设计自动化（EDA）方面的研究工作。主持并参与国家自然科学基金青年项目、培育项目、重点项目，科技部重点研发微纳电子专项、高性能计算专项青年科学家项目，国家重点实验室开放课题、企业横向课题等二十余项。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要国际会议和期刊上发表60余篇高水平学术论文。是DAC、SC、TCAD、TPDS、TODAES等多个顶刊顶会程序委员会委员和审稿人。获SC23最佳论文奖、SC24最佳论文提名、EDA2青年科技奖、ISEDA23荣誉论文奖、IEEJ九州支部长奖等。 

联系方式：jinzhou@cup.edu.cn