基于SAT算法的时钟树布线方法

摘要

本发明实施例公开一种基于SAT算法的时钟树布线方法，该方法包括：从用户设计中获取时钟线、复位线和使能线，并保存该时钟线、该复位线和该使能线的约束；从芯片模型中获取第一时钟树网络图，并保存该第一时钟网络图中的节点和该第一时钟树网络图包括的多路选择器约束、多路选择器间配置约束和多路选择器间连接关系约束；根据该时钟线、该复位线和该使能线的约束以及该第一时钟树网络图包括的约束，生成WFF格式的子句；对该子句调用可满足性SAT算法，得到满足该约束的至少一个解；将该至少一个解中的任一解对应的数学解标记到该时钟线、该复位线和该使能线上，从而完成时钟树的布线。

说明书

技术领域

本发明涉及微电子领域中的集成电路设计技术领域，尤其涉及一种基于SAT算法的时钟树布线方法。

背景技术

现场可编程门阵列(Field Programmable Gate Array，简称“FPGA”)，是一种逻辑器件，它具有丰富的硬件资源、强大的并行处理能力和灵活的可重配置能力。因此，FPGA在数据处理、通信、网络等领域的应用越来越多广泛。

FPGA的设计流程包括：设计输入、调试、功能仿真、综合、布局布线、时序仿真、配置下载等步骤。其中，布局就是指将逻辑网表中的硬件原语或者底层单元合理地适配到FPGA内部的固有硬件结构上，布局的优劣对设计的最终结果(在速度和面积两个方面)影响很大。布线则是指根据布局的拓扑结构，利用FPGA内部的各种连线资源，合理正确连接各个元件的过程。

然而，现有的FPGA的时钟树布线方法采用一般的布线算法，很难从全局的角度考虑并对时钟树进行规划，所以不能得到所有满足约束的布线方式。

发明内容

本发明实施例的目的是提供一种基于SAT算法的时钟树布线方法，通过调用SAT算法，得到满足用户设计和芯片模型中的约束的解，并将解对应的数学解标记到从用户设计中获取的时钟线、复位线和使能线上，从而完成时钟树的布线。

为实现上述目的，本发明提供了一种基于SAT算法的时钟树布线方法，该方法包括：

从用户设计中获取时钟线、复位线和使能线，并保存该时钟线、该复位线和该使能线的约束；

从芯片模型中获取第一时钟树网络图，并保存该第一时钟网络图中的节点和该第一时钟树网络图包括的多路选择器约束、多路选择器间配置约束和多路选择器间连接关系约束；

根据该时钟线、该复位线和该使能线的约束以及该第一时钟树网络图包括的约束，生成WFF格式的子句；

对该子句调用可满足性SAT算法，得到满足该约束的至少一个解；

将该至少一个解中的任一解对应的数学解标记到该时钟线、该复位线和该使能线上。

优选的，根据该时钟线、该复位线和该使能线的约束以及该第一时钟树网络图包括的约束，生成WFF格式的子句，具体为：

对该时钟线、该复位线和该使能线的约束以及该第一时钟树网络图包括的约束进行合取范式；

将该合取范式的结果转换为WFF格式的子句。

优选的，该从用户设计中获取时钟线、复位线和使能线之后，该方法还包括：为该时钟线、该复位线和该使能线添加平衡约束和/或分支约束。

进一步优选的，至少一个解为满足该约束的所有解，将该至少一个解中的任一解对应的数学解标记到该时钟线、该复位线和该使能线上，具体为：

通过评估的方式确定该所有解中的优选解；

将该优选解对应的数学解标记到该时钟线、该复位线和该使能线上。

优选的，该从芯片模型中获取第一时钟树网络图之后，该方法还包括：

当该用户设计发生变化时，根据该用户设计中变化的线更新该第一时钟网络图中与该用户设计中变化的线相对应的部分，得到第二时钟网络图。

进一步优选的，从用户设计中获取时钟线、复位线和使能线，具体为：

标识连接到该用户设计中的寄存器中的时钟线、复位线和使能线。

基于上述技术方案，本发明实施例提供的基于SAT算法的时钟树布线方法，通过获取用户设计和芯片模型中的约束，并对由约束转化生成的WFF格式的子句调用SAT算法，得到满足约束的至少一个解，将至少一个解中的任一解对应的数学解标记到从用户设计中获取的线上，从而完成时钟树的布线。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例中所需要使用的附图作简单地介绍，显而易见地，下面所描述的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为根据本发明实施例的基于SAT算法的时钟树布线方法的示意性流程图；

图2为根据本发明实施例的基于SAT算法的时钟树布线方法的另一示意性流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都应属于本发明保护的范围。

图1为根据本发明实施例的基于SAT算法的时钟树布线方法100的示意性流程图。如图1所示的方法100包括：

110，从用户设计中获取时钟线、复位线和使能线，并保存该时钟线、该复位线和该使能线的约束。

120，从芯片模型中获取第一时钟树网络图，并保存该第一时钟网络图中的节点和该第一时钟树网络图包括的多路选择器约束、多路选择器间配置约束和多路选择器间连接关系约束。

130，根据该时钟线、该复位线和该使能线的约束以及该第一时钟树网络图包括的约束，生成WFF格式的子句。

140，对该子句调用可满足性SAT算法，得到满足约束的至少一个解。

150，将该至少一个解中的任一解对应的数学解标记到该时钟线、该复位线和该使能线上。

具体的，在本发明实施例中，在110中，可以通过标识连接到该用户设计中的寄存器中的时钟线、复位线和使能线的方式，获取用户设计中的时钟线、复位线和使能线。同时，可以保存获取的时钟线、复位线和使能线的约束。应理解，在本发明实施例中，用户设计中的一条线可能同时作为时钟线，复位线和使能线，还可能连接了其它的逻辑，因此，需要将用户设计中的每一线进行标识，从而有利于确定最后的布线规则。

在120中，可以从芯片模型中提取第一时钟树网络图，并保存第一时钟网络图中的节点和该第一时钟树网络图包括的多路选择器约束、多路选择器间配置约束和多路选择器间连接关系约束。应理解，在本发明实施例中，第一时钟网络图中的节点可以包括多路选择器的输入、输出，则多路选择器约束可以为多路选择器的输入、输出之间的逻辑关系，多路选择器间配置约束可以为不同的多路选择器之间的逻辑配置关系，多路选择器间连接关系约束可以为不同的多路选择器之间的逻辑连接关系。

在130中，将从用户设计中获取的时钟线、复位线和使能线的约束，以及从芯片模型中获取的第一时钟树网络图包括的约束，转化生成WFF格式的子句，以便在140中对这些WFF格式的子句调用SAT算法，得到满足这些约束的至少一个解。也就是说，得到满足这些约束的，能使得多路选择器的输出为真的所有的布线方式。应理解，在本发明实施例中，对WFF格式的子 句调用SAT算法，得到满足这些约束的至少一个解，就是基于SAT算法，得到多路选择器的输出为真的至少一种布线方式，其中，满足约束的每一个解对应一种布线方式。

在150中，将至少一个解中的任一解对应的数学解标记到时钟线、复位线和使能线上。当得到的满足约束的至少一个解为一个解时，例如：这个解可以为得到的第一个满足约束的解，为了加快计算速度，可以将这个解对应的数学解标记到从用户设计中获取的时钟线、复位线和使能线上，从而完成时钟树的布线。当得到的满足约束的至少一个解为多个解时，可以选择这多个解中任一个解对应的数学解标记到从用户设计中获取的时钟线、复位线和使能线上，从而完成时钟树的布线。

因此，本发明实施例提供的基于SAT算法的时钟树布线方法，通过获取用户设计和芯片模型中的约束，并对由约束转化生成的WFF格式的子句调用SAT算法，得到满足约束的至少一个解，将至少一个解中的任一解对应的数学解标记到从用户设计中获取的线上，从而完成时钟树的布线。

需要说明的，在本发明实施例中，在对从用户设计和芯片模型中获取的约束转化成的WFF格式的子句调用SAT算法后，可能出现不能得到满足约束的至少一个解的情况，例如：在约束不可满足、调用算法超时、内部存在不可知的问题、调用过程中出错或内存不足等情况下，是无法得到满足约束的解的，此时，就不能完成对时钟树的布线。

优选的，作为本发明的一个实施例，在130中，根据时钟线、复位线和使能线的约束以及第一时钟树网络图包括的约束，生成WFF格式的子句，具体为：

对时钟线、复位线和使能线的约束以及第一时钟树网络图包括的约束进行合取范式；

将合取范式的结果转换为WFF格式的子句。

具体的，在本发明实施例中，可以对在110中从用户设计中获取并保存 的时钟线的约束、复位线的约束和使能线的约束，以及在120中从芯片模型中获取的第一时钟树网线包括的多路选择器约束、多路选择器间配置约束和多路选择器间连接关系约束进行合取，应理解，我们可以将所有要处理的线用连续的整数表示，将线经过多路选择器的事实表示为将多路选择器的节点赋值为线对应的整数。将合取范式的结果转换为WFF格式的子句。

应理解，在本发明实施例中，WFF格式的子句可以为一个INT类型的数组。例如：对节点A、B、C之间的约束进行合取为：(A＝＝5)&&(B＝＝1)&&(B＝＝C)，则用A[0]，A[1]等表示A、B、C对应的二进制的比特位，则合取范式为A[0]&&！A[1]&&A[2]&&！B[0]&&！B[1]&&B[2]&&(B[0]||！C[0])&&(！B[0]||C[0])&&(B[1]||！C[1])&&(！B[1]||C[1])&&(B[2]||！C[2])&&(！B[2]||C[2]))的则可以使用1代表A[0]，使用-1代表！A[0]，同理2代表A[1]，使用-2代表！A[1]等等，使用0代表符号&&，那么，这个合取范式的结果可以表达为：10-2030-40-50604-70-4705-80-5806-90-690，这就是一个WFF格式的子句。其中，“！”表示：逻辑非，“&&”表示：逻辑与，“||”表示：逻辑或。

对节点A、B、C之间的约束进行合取范式为：A[0]&&！A[1]&&A[2]&&！B[0]&&！B[1]&&B[2]&&(B[0]||！C[0])&&(！B[0]||C[0])&&(B[1]||！C[1])&&(！B[1]||C[1])&&(B[2]||！C[2])&&(！B[2]||C[2]))，要得到满足约束的至少一个解，就是要得到使得A[0]&&！A[1]&&A[2]&&！B[0]&&！B[1]&&B[2]&&(B[0]||！C[0])&&(！B[0]||C[0])&&(B[1]||！C[1])&&(！B[1]||C[1])&&(B[2]||！C[2])&&(！B[2]||C[2]))为1时，节点A、B、C是否为真的解。例如，A[0]，A[2]，B[2]，C[2]为真，其余为假，这样可以满足合取范式为1，从而得到了一个解，再将解标记回十进制的值中，可知A为5，B和C均为1。进一步可知，节点A被线5使用，节点B和C被线1使用。需要说明的上，这仅是本发明实施例的一个例子，并不对本发明实施例构成任何限定。

优选的，作为本发明的另一个实施例，在150中，至少一个解为满足约 束的所有解，将该至少一个解中的任一解对应的数学解标记到时钟线、复位线和使能线上，具体为：

通过评估的方式确定该所有解中的优选解；

将该优选解对应的数学解标记到时钟线、复位线和使能线上。

具体的，在本发明实施例中，分析评估满足约束的所有解中不需要满足条件的解，或者需要满足条件但计算量大的解，将这些解从所有解中去除，从而确定该所有解中的一个优选解，并将从所有解中确定的一个优选解对应的数学解标记到该时钟线、该复位线和该使能线上。优选解对应一种较佳的布线方式，也就是说，将优选解对应的数学解标记到从用户设计中获取的时钟线、复位线和使能线上，完成的时钟树的布线是一种较佳的布线方式。

因此，本发明实施例提供的基于SAT算法的时钟树布线方法，通过获取用户设计和芯片模型中的约束，并对由约束转化生成的WFF格式的子句调用SAT算法，得到满足约束的所有解，将所有解中的优选解对应的数学解标记到从用户设计中获取的线上，从而完成时钟树的布线。

优选的，作为本发明的另一个实施例，如图2所示，在110之后，该方法100还包括：

160，为时钟线、复位线和使能线添加平衡约束和/或分支约束。

具体的，在本发明实施例中，可以对从用户设计中获取的时钟线、复位线和使能线额外的添加一些约束，可以添加平衡约束和/或分支约束，从而大大的减少不合理解的数目。其中，平衡约束可以使得线网中的源点相同的线到各个目的点的时延相同或相近。可以将线网中的目的点分组，分支约束可以使得每组目的点到其它线的某一组或多组中每一组目的点的时延相同或相近。

因此，本发明实施例提供的基于SAT算法的时钟树布线方法，通过获取用户设计和芯片模型中的约束，并对由约束转化生成的WFF格式的子句调用SAT算法，得到满足约束的至少一个解，将至少一个解中的任一解对应的数 学解标记到从用户设计中获取的线上，从而完成时钟树的布线。

应理解，在本发明实施例中，在130中，根据时钟线、复位线和使能线的约束以及第一时钟树网络图包括的约束，生成WFF格式的子句。其中，时钟线、复位线和使能线的约束包括从用户设计中获取的约束和额外为这些线添加的约束，因此，要根据这所有的约束，生成WFF格式的子句。

优选的，作为本发明的另一个实施例，如图2所示，在120之后，该方法100还包括：

170，当该用户设计发生变化时，根据该用户设计中变化的线更新该第一时钟网络图中与该用户设计中变化的线相对应的部分，得到第二时钟网络图。

具体的，在本发明实施例中，当用户设计发生变化时，从用户设计中获取的时钟线、复位线和使能线中的某些线发生了变化，这时需要更新第一时钟网络图中与该用户设计中变化的线相对应的部分，得到第二时钟树网络图。也就是说，根据用户设计中变化的部分仅更改第一时钟树网络图中的局部，而无需重新建立一个时钟树网络图，从而可以加快建立时钟树网络图的速度。

应理解，在本发明实施例中，在130中，根据时钟线、复位线和使能线的约束以及第一时钟树网络图包括的约束，生成WFF格式的子句。其中，第一时钟树网络图为更新后的时钟树网络图，即：第二时钟树网络图，因此，可以根据时钟线、复位线和使能线的约束以及第二时钟树网络图包括的约束，生成WFF格式的子句。

另外，本文中术语“和/或”，仅仅是一种描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。另外，本文中字符“/”，一般表示前后关联对象是一种“或”的关系。

应理解，在本发明各实施例中，上述各过程的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本发明实施例的实施过程构成任何限定。

本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为。