修复电路中的保持时间违例的方法和装置的制造方法

修复电路中的保持时间违例的方法和装置的制造方法
【技术领域】
[0001] 本发明涉及电路设计领域，更具体地涉及一种修复电路中的保持时间违例的方法 和装置。
【背景技术】
[0002] 在设计电路(例如集成电路等）时，在完成了该电路的各种元件(例如各种口电路 和各种标准单元）的放置和布线之后，对该电路进行时序分析，W检查该电路是否存在时 序违例。所述时序违例包括建立时间违例（setuptimeviolation)、保持时间违例（hold timeviolation)等。建立时间是指在时钟沿到达口电路之前，该口电路的输入端口处的数 据应当保持稳定的时间。如果该口电路的输入端口处的数据保持稳定的时间小于要求的建 立时间，则发生建立时间违例，该将导致当时钟沿到达该口电路时，所述数据不能正确地输 入该口电路。如本领域公知的，可W利用建立时间余量（setupslack)来判断是否发生建立 时间违例。具体地，当建立时间余量小于0时，可W确定发生建立时间违例。保持时间是指 在时钟沿到达口电路之后，该口电路的输入端口处的数据应当保持稳定的时间。如果在时 钟沿到达口电路之后该口电路的输入端口处的数据保持稳定的时间小于要求的保持时间， 则发生保持时间违例，该也将导致所述数据不能正确地输入该口电路。如本领域公知的，可 W利用保持时间余量（holdslack)来判断是否发生保持时间违例。具体地，当保持时间余 量小于0时，可W确定发生保持时间违例。当发生上述任一种时序违例时，需要修复该时序 违例，W使得电路能够正常工作。
[0003]通常，在电路设计的最后阶段，即，在放置并固定了所有元件及其输入/输出管 脚，并且修复了建立时间违例和其他时序违例之后，修复保持时间违例。在传统的保持时间 违例修复方法中，找出电路中发生保持时间违例的元件，并且在该元件处插入延迟元件，W 修复该保持时间违例。然而，传统的保持时间违例修复方法存在若干问题。首先，随着电 路的规模和复杂度增大，电路包含大量元件，使得电路中的某些区域的元件密度非常大，而 且，在该样的区域中，制造工艺导致的元件特性变化（variation)的影响也比较大，因此可 能出现大量的保持时间违例。如果为了修复保持时间违例而在该些区域中插入延迟元件， 会导致该些区域的元件密度进一步增大，并且使电路元件的布线发生拥塞。此外，传统的保 持时间修复方法往往需要移动已经放置好的元件和/或其输入/输出管脚，使得容易产生 新的时序违例。

【发明内容】

[0004]为了解决上述问题，本发明的一个目的是提供一种修复电路中的保持时间违例的 方法和装置，其能够修复电路中的保持时间违例，同时避免出现新的时序违例，并且避免由 于修复保持时间违例而使电路过于拥挤。
[0005]根据本发明的一个方面，提供了一种修复电路中的保持时间违例的方法，包括：创 建所述电路的拓扑图，该拓扑图中的支路表示所述电路中发生保持时间违例的信号路径， 所述支路上的节点表示所述信号路径上发生保持时间违例的元件的端口；将所述电路划分 为多个区域；根据所述拓扑图中的所述节点对应的区域的电路元件密度，选择性地在所述 节点对应的区域中放置保持时间校正元件W修复其保持时间违例。
[0006] 根据本发明的另一个方面，提供了一种修复电路中的保持时间违例的装置，包括： 拓扑图创建设备，被配置为创建所述电路的拓扑图，该拓扑图中的支路表示所述电路中发 生保持时间违例的信号路径，所述支路上的节点表示所述信号路径上发生保持时间违例的 元件的端口；电路划分设备，被配置为将所述电路划分为多个区域；违例修复设备，被配置 为根据所述拓扑图中的节点对应的区域的电路元件密度，选择性地在所述节点对应的区域 中放置保持时间校正元件W修复其保持时间违例。
[0007] 在根据本发明上述方面的方法和装置中，可W根据电路中发生保持时间违例的元 件所在的区域的电路元件密度，确定是否在该元件处插入保持时间校正元件(例如延迟元 件）W修复该保持时间违例。该样，可W避免在电路元件密度过大的区域插入新的元件，并 且避免布线拥塞。而且，根据本发明上述方面的方法和装置不需要移动已经放置在电路中 的元件及其输入/输出管脚，从而避免因为元件/管脚的移动而产生新的时序违例。
【附图说明】
[0008] 通过结合附图对本公开示例性实施方式进行更详细的描述，本公开的上述W及其 它目的、特征和优势将变得更加明显，其中，在本公开示例性实施方式中，相同的参考标号 通常代表相同部件。
[0009] 图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12的框 图。
[0010] 图2示出了根据本发明实施例的修复电路中的保持时间违例的方法的流程图。
[0011] 图3示例性地示出了根据本发明实施例的电路的有向无环图（DAG)。
[0012] 图4示出了根据本发明实施例的通过将电路划分为H个区域产生的瓦片图的示 例。
[0013] 图5A和5B示意性地示出了根据本发明实施例的两种类型的保持时间校正元件 链。
[0014] 图6示出了根据本发明实施例的修复电路中的保持时间违例的方法的框图。
[0015] 图7示意性地示出了图6所示的违例修复设备的结构。
【具体实施方式】
[0016] 下面将参照附图更详细地描述本公开的优选实施方式。虽然附图中显示了本公开 的优选实施方式，然而应该理解，可WW各种形式实现本公开而不应被该里阐述的实施方 式所限制。相反，提供该些实施方式是为了使本公开更加透彻和完整，并且能够将本公开的 范围完整地传达给本领域的技术人员。
[0017] 图1示出了适于用来实现本发明实施方式的示例性计算机系统/服务器12的框 图。图1显示的计算机系统/服务器12仅仅是一个示例，不应对本发明实施例的功能和使 用范围带来任何限制。
[0018] 如图1所示，计算机系统/服务器12W通用计算设备的形式表现。计算机系统 /服务器12的组件可W包括但不限于；一个或者多个处理器或者处理单元16,系统存储器 28,连接不同系统组件(包括系统存储器28和处理单元16)的总线18。
[0019] 总线18表示几类总线结构中的一种或多种，包括存储器总线或者存储器控制器， 外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总线结构的局域总线。举 例来说，该些体系结构包括但不限于工业标准体系结构（ISA)总线，微通道体系结构（MAC) 总线，增强型ISA总线、视频电子标准协会（VESA)局域总线W及外围组件互连（PCI)总线。
[0020] 计算机系统/服务器12典型地包括多种计算机系统可读介质。该些介质可W是 任何能够被计算机系统/服务器12访问的可用介质，包括易失性和非易失性介质，可移动 的和不可移动的介质。
[0021] 系统存储器28可W包括易失性存储器形式的计算机系统可读介质，例如随机存 取存储器（RAM)30和/或高速缓存存储器32。计算机系统/服务器12可W进一步包括其 它可移动/不可移动的、易失性/非易失性计算机系统存储介质。仅作为举例，存储系统34 可W用于读写不可移动的、非易失性磁介质（图1未显示，通常称为"硬盘驱动器")。尽管图 1中未示出，可W提供用于对可移动非易失性磁盘(例如"软盘")读写的磁盘驱动器，W及对 可移动非易失性光盘(例如CD-ROM,DVD-ROM或者其它光介质）读写的光盘驱动器。在该些 情况下，每个驱动器可W通过一个或者多个数据介质接口与总线18相连。存储器28可W 包括至少一个程序产品，该程序产品具有一组(例如至少一个）程序模块，该些程序模块被 配置W执行本发明各实施例的功能。
[0022] 具有一组(至少一个）程序模块42的程序/实用工具40,可W存储在例如存储器 28中，该样的程序模块42包括一但不限于一操作系统、一个或者多个应用程序、其它 程序模块W及程序数据，该些示例中的每一个或某种组合中可能包括网络环境的实现。程 序模块42通常执行本发明所描述的实施例中的功能和/或方法。
[0023] 计算机系统/服务器12也可W与一个或多个外部设备14 (例如键盘、指向设备、 显示器24等)通信，还可与一个或者多个使得用户能与该计算机系统/服务器12交互的设 备通信，和/或与使得该计算机系统/服务器12能与一个或多个其它计算设备进行通信的 任何设备(例如网卡，调制解调器等等）通信。该种通信可W通过输入/输出（I/O)接口 22 进行。并且，计算机系统/服务器12还可W通过网络适配器20与一个或者多个网络(例如 局域网（LAN),广域网（WAN)和/或公共网络，例如因特网）通信。如图所示，网络适配器20 通过总线18与计算机系统/服务器12的其它模块通信。应当明白，尽管图中未示出，可W 结合计算机系统/服务器12使用其它硬件和/或软件模块，包括但不限于；微代码、设备驱 动器、兀余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器W及数据备份存储系统等。
[0024] 下面，将参照附图来描述根据本发明实施例 的修复电路中的保持时间违例的方法 和装置。
[0025] 首先，参照图2来描述根据本发明实施例的修复电路中的保持时间违例的方法。
[0026] 如图2所示，在步骤S201中，创建所述电路的拓扑图，该拓扑图中的支路表示所述 电路中发生保持时间违例的信号路径，所述支路上的节点表示所述信号路径上发生保持时 间违例的元件的端口（例如输入端口或输出端口）。
[0027] 通常，设计人员使用各种元件来设计电路(例如集成电路)。所述元件可W包括各 种时序单元(例如知识产权（IP)核、寄存器等）W及各种组合单元(例如与口、非n等)。在 时序单元之间可w形成一条或多条信号路径。例如，当一个时序单元的输出端口（在本说明 书中，与输出管脚可互换地使用）直接地或者经由一个或多个组合单元连接到另一个时序 单元的输入端口（在本说明书中，与输入管脚可互换地使用）时，在该两个时序单元之间形 成信号路径。当电路工作时，信号从时序电路的输出端口沿着信号路径流到另一个时序电 路的输入端口，从而实现设计的功能。当对电路进行分析时，可W根据电路的拓扑，找出电 路中的所有信号路径W及该些信号路径上的所有元件。
[0028] 此外，如上文所述，在电路设计后期，可W针对电路的每个信号路径，计算该信号 路径上的各个元件的输入端口和输出端口处的保持时间余量，从而根据该保持时间余量来 确定在所述信号路径上是否发生保持时间违例。在信号路径上发生保持时间违例意味着在 该信号路径上的所有元件处(即，其输入端口和输出端口处)都发生保持时间违例。该样，可 W找出电路中所有发生保持时间违例的信号路径W及该信号路径上的所有元件（即发生保 持时间违例的元件)。应当注意，当多条发生时间违例的信号路径经过一个输入端口或输出 端口，并且针对所述多条路径分别计算的该端口处的保持时间余量存在多个不同的值时， 可W将绝对值最大的值(其对应于最严重的保持时间违例）作为该端口处的保持时间余量。
[0029] 然后，可W根据电路中发生保持时间违例的各条信号路径、W及该些信号路径上 发生保持时间违例的元件，创建该电路的拓扑图。在本发明的实施例中，所述拓扑图可W是 有向无环图（DAG)，并且在下文中，WDAG为例来进行描述。DAG中的支路表示电路中发生 保持时间违例的信号路径，所述支路上的节点表示所述信号路径上发生保持时间违例的元 件的输入端口或输出端口。创建电路的DAG的方法是本领域公知的，在该里不再费述。图3 示例性地示出了根据本发明实施例的电路的DAG。在该示例中，电路包括时序电路（IP核和 寄存器）W及组合电路(非口和与口），该IP核的输出端口分别经由不同的组合电路与各个 寄存器的输入端口连接，从而形成多条信号路径，在该些信号路径上(其各个元件处）发生 了保持时间违例。在图3中，为了便于描述，将该DAG中的各个节点命名为A、B、C、…、X、 Y、Z，并且在各个节点旁边标注的数字表示该节点处的保持时间余量(例如W毫砂为单位)， 如上文所述，保持时间余量为负表示该节点对应的端口处发生了保持时间违例。应当认识 至IJ，所述拓扑图不限于DAG，在其他实施例中，可W使用其他形式的拓扑图。此外，在其他实 施例中，除了发生保持时间违例的信号路径及其元件W外，所建立的拓扑图也可W包括电 路中的没有发生保持时间违例的信号路径及其元件。
[0030] 应当注意，当在电路的某个元件的输入端口或输出端口处发生保持时间违例时， 出于某些原因，可能不允许修复该输入端口或输出端口处的保持时间违例。例如，如果对该 输入端口或输出端口处的保持时间违例的修复操作会使得在电路中发生新的时序违例(尤 其是建立时间违例)，则不允许在该输入端口或输出端口处修复保持时间违例。在本发明的 实施例中，对于DAG中的每个节点(其对应于发生保持时间违例的元件的输入端口或输出 端口），可W根据该节点处的建立时间余量細常为正值)和保持时间余量(负值)来确定是否 允许在该节点处修复保持时间违例。例如，可W设置参数Se化pSlack+Vi地oldSlack，其中 Se化pSlack是该节点处的建立时间余量，Vi是经验值(例如3)，化IdSlack是该节点处的保 持时间余量，所述建立时间余量和保持时间余量可W使用本领域公知的方法获得。当该参 数小于0时，该意味着该节点处的建立时间余量不够大，在该种情况下，如果在该节点处修 复保持时间违例，则可能导致出现新的建立时间违例，因此不应当在该节点处修复保持时 间违例，反之，如果该参数不小于0,则说明建立时间余量足够大，可W在该节点处修复保持 时间违例。可W对DAG中的所有节点计算上述参数，W确定不允许修复保持时间违例的节 点（为便于描述，W下称为不可修复节点)，并且在DAG图中将不可修复节点标识出。在图3 所示的DAG示例中，假设节点B、U、V、Z为不可修复节点，因此例如用"X0"标识出。
[0031] 返回图2,在步骤S202中，将所述电路划分为多个区域。
[0032] 具体地，可W按照任何适当的方式将所述电路划分为多个区域(或称为瓦片 (tile))，从而产生所述电路的瓦片图。图4示意性地示出了根据本发明实施例的通过将电 路划分为H个区域(瓦片）而产生的瓦片图的示例。为简单起见，在图4中没有画出具体的 电路元件。应当注意，所述区域的形状不限于矩形，而是可W是任意形状，并且每个区域的 大小也可W根据需要灵活地选择。通过划分电路，可W确定在步骤S201中创建的DAG中的 各个节点所在的电路区域。
[0033] 然后，可W计算每个区域(瓦片)的电路元件密度。例如，可W计算在每个区域内放 置的所有电路元件占据的面积（即，所有电路元件映射到该区域所在平面上的面积）与该区 域的总面积之比，作为该区域的电路元件密度。该样，可W确定该电路的DAG中的各个节点 对应的区域的电路元件密度。应当注意，如果某个区域(瓦片）由于某些限制而不能放置任 何元件或者不能增加任何元件时，则可W将该区域的电路元件密度设置为无穷大，W避免 在随后的修复操作中在该区域插入新的元件。
[0034] 返回图2,在步骤S203中，根据所述DAG中的节点对应的区域的电路元件密度，选 择性地在所述节点对应的区域中放置保持时间校正元件W修复其保持时间违例。例如，可 W将所述节点对应的区域的电路元件密度与密度阔值进行比较，并且响应于所述节点对应 的区域的电路元件密度没有超过该密度阔值，在所述节点对应的区域中放置保持时间校正 元件W修复其保持时间违例。
[003引具体地，首先，可W建立节点列表，该节点列表包括所述DAG中可修复其保持时间 违例的所有节点（为便于描述，W下称为可修复节点)，其中，可W根据节点列表中的各个可 修复节点的输入路径数量（即，从DAG的各个支路的起始节点到达该可修复节点的不同路 径数量）数量和输出路径数量（即，从该可修复节点到DAG的各个支路的最后的节点的不同 路径数量）W及保持时间余量，对节点列表中的各个节点进行排序。例如，可W计算各个可 修复节点的输入路径数量和输出路径数量的乘积，并且按照乘积从大到小的顺序将各个可 修复节点排序，其中，如果两个或多个可修复节点的输入路径数量和输出路径数量的乘积 相等，则可W按照所述两个或多个可修复节点的保持时间余量的绝对值从大到小（即，从保 持时间违例程度严重到保持时间违例轻微）的顺序将该些节点排序，如果两个可修复节点 的保持时间余量相同，则可W任意地将它们排序。在图3所示的示例中，节点A的输入路径 (即从IP核的输出管脚到节点A的路径）只有一条，节点A的输出路径（即，从节点A到各 个寄存器的输入管脚的路径）有8条，即，路径A-C-D-E-F-G、A-C-D-E-F-H、A-I-X-J-K-L、 A-I-X-J-K-M、A-N-0-P-Q-K-L、A-N-0-P-Q-K-M、A-N-S-Y-T-Z-U和A-N-S-Y-T-Z-V，因此节 点A的输入路径数量和输出路径数量的乘积为8。类似地，可W确定其他节点的输入路径数 量和输出路径数量的乘积，并且按照上文所述的方式，根据所述乘积W及保持时间余量将 各个节点排序。在本发明的实施例中，所述节点列表还可W包括DAG中的不可修复节点，在 该种情况下，可W将不可修复节点排在所有可修复节点之后，也可W不将其与可修复节点 一起排序，并且在所述不可修复节点之间，可w按照上文所述的方式排序，也可w不进行排 序。在其他实施例中，所述节点列表可W不包括所述不可修复节点。
[0036] 所建立的节点列表可W根据实际需要而采用任何适当的形式。例如，对于图3所 示的DAG，可W按照上文所述的方式，建立如下表1所示的节点列表，其中，斜体字母表示的 节点是对应的区域的电路元件密度超过密度阔值的节点：
[0037]
[0038]表1
[0039]在表1中，使用各个节点的输入路径数量与输出路径数量的乘积作为各个节点的 序号，其中序号大的节点在后续操作中将先被处理。对于序号相同的两个或多个节点，按照 保持时间余量的绝对值的大小从左向右排列该些节点，使用节点的位置表示其顺序，其中 左侧的节点在后续操作中将先被处理。此外，在表1中，不可修复节点位于与可修复 节点不 同的栏中，W表示排序在可修复节点之后。应当认识到，表1只是示例性的，也可W采用其 他形式的节点表。例如，可W按照上述排序方式，简单地建立W下节点队列；4-3-1(-0斗-9-N-W-S-Y-TA-M-C-D-E-F-I-X-J-G-H-B-Z-U-V。
[0040] 在建立节点列表之后，可W按照节点列表中的各个节点的顺序，根据所述各个节 点对应的区域的电路元件密度，选择性地在所述各个节点对应的区域中处放置保持时间校 正元件W修复其保持时间违例。
[0041] 具体地，可W按照节点列表中的每个节点的顺序，将每个节点对应的区域的电路 元件密度与密度阔值进行比较。所述密度阔值可W是根据设计需要和/或其他因素灵活选 择的值。当节点列表中的某个节点对应的区域的电路元件密度超过所述密度阔值时，该意 味着该节点对应的区域的元件密度过大，因此不在该区域中插入新的元件W修复该节点处 的保持时间违例。反之，当节点列表中的某个节点对应的区域的电路元件密度不超过所述 密度阔值时，该意味着该节点对应的区域存在较大的空闲空间，因此可W在该区域中插入 保持时间校正元件W修复该节点处的保持时间违例。所述保持时间校正元件可W是能够引 入时间延迟的任何种类的元件，例如本领域公知的缓冲器或延迟元件。由于每种保持时间 校正元件能够引入的时间延迟量是已知的，因此，可W根据该节点处的保持时间余量与每 种时延元件能够引入的时间延迟量，确定最终插入的保持时间校正元件的种类和数量，然 后，将该保持时间校正元件插入到该节点对应的区域中，从而修复该节点处的保持时间违 例。使用保持时间校正元件校正节点处的保持时间违例的具体方式是本领域公知的，在该 里省略其详细描述。在对该节点执行了所述修复操作之后，可W从节点列表中删除该节点 (即修复了保持时间违例的节点）W及与该节点处于相同信号路径上的所有节点。进行该删 除操作的原因是：当在所述节点对应的区域中通过插入保持时间校正元件而修复了保持时 间违例时，与所述节点处于相同信号路径上的所有节点的保持时间余量都会发生变化，因 此不应当基于原来的保持时间余量对该些节点进行保持时间违例修复。
[0042] 下面结合图3所示的例子来描述该修复操作。在图3所示的例子中，按照各个节点 的顺序，首先确定节点A对应的区域的电路元件密度是否超过密度阔值，得到肯定的结果， 因此不在节点A对应的区域中放置保持时间校正元件W修复其保持时间违例。接下来，检 查节点R对应的区域的电路元件密度是否超过密度阔值，得到肯定的结果，因此不在节点R 对应的区域中放置保持时间校正元件W修复其保持时间违例。接下来，由于节点K对应的 区域的电路元件密度没有超过密度阔值，因此，在节点K对应的区域中插入保持时间校正 元件来修复其保持时间违例。然后，可W从节点列表中删除节点KW及与节点K处于相同 信号路径上的节点，即节点A、I、X、J、L、M、N、0、P、Q、B、W。通过该删除操作获得表2所示 的节点列表。
[0043]
[0044]表 2
[0045] 然后，对于表2所示的节点列表中的节点K之后的其他可修复节点，重复上述操 作，直到检查了节点列表中的所有可修复节点为止。对于图3所示的例子，在对于节点列表 中的所有可修复节点执行了上述操作之后，可W获得下表3所示的节点列表。
[0046]
[0047]
[0048] 表 3
[0049] 可W看到，表3中的节点均为不可修复节点或者对应的区域的元件密度超过密度 阔值的可修复节点。
[0050] 在完成上述操作之后，对于节点列表中剩余的每个可修复节点(其为对应的区域 的电路元件密度超过所述密度阔值的可修复节点)，可W找出在该节点对应的区域周围的、 电路元件密度没有超过所述密度阔值的区域(为便于描述，W下称为替代区域)，并且通过 在该替代区域中，而不是该节点对应的区域中，插入如下所述的保持时间校正元件链来修 复该节点处的保持时间违例。
[0051] 具体地，可W在与所述剩余的可修复节点对应的区域的距离不超过预设的距离阔 值的区域中，找出电路元件密度不超过所述密度阔值的一个区域作为所述替代区域。所述 距离阔值可W根据电路的实际情况灵活地设定，使得所述替代区域与所述剩余的可修复节 点对应的区域直接相邻或者间隔一个或多个区域。
[0052] 然后，可W在所选择的替代区域中插入至少一个保持时间校正元件(例如延迟元 件）来修复该节点处的保持时间违例。由于所插入的保持时间校正元件与该节点之间存在 的一定的距离，因此，除了保持时间校正元件W外，还需要在该节点和保持时间校正元件之 间插入至少一个驱动元件(例如缓冲元件)，用于将所述至少一个保持时间校正元件连接到 所述节点，并且驱动所述至少一个保持时间校正元件W使其能够工作。该样，所述至少一个 保持时间校正元件和至少一个驱动元件形成保持时间校正元件链。
[0053] 在本发明的实施例中，可W使用两种类型的保持时间校正元件链，即图5A所示的 大延迟型保持时间校正元件链W及图5B所示的低变化型保持时间校正元件链。如图5A和 5B所示，该两种类型的保持时间校正元件链包括具有至少一个保持时间校正元件的保持时 间校正元件组W及具有至少一个驱动元件的驱动元件组。图5A所示的大延迟型保持时间 校正元件链中的每个保持时间校正元件能够引入的时间延迟大，因此只需要较少的保持时 间校正元件来引入所需的时间延迟量，从而占据的空间小，然而，由于制造工艺等导致的保 持时间校正元件的特性变化对电路的影响较大，因此容易引起新的时序违例(例如建立时 间违例)。图5B所示的低变化型保持时间校正元件链中的每个保持时间校正元件能够引入 的时间延迟小，因此需要较多的保持时间校正元件来引入所需的时间延迟量，从而占据的 空间大，然而，由于制造工艺等导致的保持时间校正元件的特性变化对电路的影响较小，因 此不容易引起新的时序违例。
[0054]当要插入保持时间校正元件链W修复某个剩余的可修复节点的保持时间违例时， 可W根据该节点处的建立时间余量和保持时间余量，选择要插入的保持时间校正元件链的 类型。例如，可W设置参数Se化pSlack+V2地oldSlack，其中V2是大于Vi的经验值，例如5。 对于该可修复节点，可W计算该参数的值，如果该参数大于0,该意味着建立时间余量足够 大，即使保持时间校正元件的特性变化对电路的影响较大，也不容易引起新的时序违例，因 此可W选择大延迟型保持时间校正元件链W减小占据的空间，反之，如果该参数小于0,该 意味建立时间余量不够大，因此可W选择低变化型保持时间校正元件链W避免引起新的时 序违例。然后，可W根据该可修复节点处的保持时间余量W及所述替代区域与该可修复节 点对应的区域之间的距离，确定保持时间校正元件链中的保持时间校正元件的数量和驱动 元件的数量，并且将由此确定的保持时间校正元件链插入所述替代区域，W修复所述可修 复节点处的保持时间违例。然后，同样，从节点列表中删除与修复了保持时间违例的该可修 复节点W及与其处于相同的信号路径上的所有节点，并且对于节点列表中的剩余可修复节 点重复上述操作，直到对于节点列表中的所有可修复节点都执行了上述操作为止。
[00巧]该样，利用根据本发明实施例的上述方法，可W修复电路中的保持时间违例，而不 会在电路元件密度过大的区域插入新的元件，也不会导致布线的拥塞。此外，上述方法不需 要移动已经放置在电路中的元件及其输入/输出管脚，从而避免因为元件/管脚的移动而 产生新的时序违例。
[0056] 应当注意，由于在上述方法中删除了某些节点而没有对其执行保持时间违例的修 复，因此即使经过上述操作，在电路中可能仍然存在保持时间违例。在该种情况下，可W对 电路重新进行时序分析，并且在确定发生保持时间违例时再次利用上述方法修复所述保持 时间违例。然而，相对于传统方法，只需要将根据本发明实施例的方法重复较少的次数。
[0057] 前面已经参考附图描述了实现本发明的方法的各个实施例。本领域技术人员可W 理解的是，上述方法既可WW软件方式实现，也可WW硬件方式实现，或者通过软件与硬件 相结合的方式实现。并且，本领域技术人员可W理解，通过W软件、硬件或者软硬件相结合 的方式实现上述方法中的各个步骤，可W提供一种基于相同发明构思的修复电路中的保持 时间违例的装置。即使该装置在硬件结构上与通用处理设备相同，由于其中所包含的软件 的作用，使得该装置表现出区别于通用处理设备的特性，从而形成本发明的实施例的装置。 本发明中所述装置包括若干单元或模块，所述单元或模块被配置为执行相应步骤。本领域 的所述技术人员通过阅读本说明书可W理解如何编写程序实现所述单元或模块执行的动 作。
[0058] 下面将参考附图6具体描述根据本发明的实施例的修复电路中的保持时间违例 的装置。由于所述装置与方法基于相同的发明构思，因此其中相同或相应的实现细节同样 适用于与上述方法对应的装置，由于其在上文中已经进行了详细和完整的描述，因此在下 文中可能不再进行费述。
[0059] 如图6所示，根据本发明的实施例的修复电路中的保持时间违例的装置60 0可W 包括拓扑图创建设备601、电路划分设备602和违例修复设备603。
[0060] 拓扑图创建设备601可W创建所述电路的拓扑图，该拓扑图中的支路表示所述电 路中发生保持时间违例的信号路径，所述支路上的节点表示所述信号路径上的所有元件 (即，发生保持时间违例的元件)的端口（例如输入端口或输出端口）。如上文所述，在本发明 的实施例中，所述拓扑图可W是DAG。在其他实施例中，所述拓扑图也可W是其他类型的拓 扑图。拓扑图创建设备601可W按照上文所述的方式创建所述电路的拓扑图，在该里不再 费述。在其他实施例中，除了发生保持时间违例的信号路径及其元件W外，所建立的拓扑图 也可W包括电路中的没有发生保持时间违例的信号路径及其元件。
[0061] 电路划分设备602可W将所述电路划分为多个区域。具体地，电路划分设备602可 W按照任何适当的方式将所述电路划分为多个区域(瓦片)，从而产生所述电路的瓦片图。 所述区域可W是任意形状，并且每个区域的大小也可W根据需要灵活地选择。由此，可W 确定拓扑图创建设备601创建的DAG中的各个节点所在的电路区域。此外，电路划分设备 602还可W计算每个区域(瓦片）的电路元件密度。例如，电路划分设备602可W计算在每 个区域内放置的所有电路元件占据的面积与该区域的总面积之比，作为该区域的电路元件 密度。该样，电路划分设备602可W确定该电路的DAG中的各个节点对应的区域的电路元 件密度。应当注意，如果某个区域(瓦片）由于某些限制而不能放置任何元件或者不能增加 任何元件时，则电路划分设备602可W将该区域的电路元件密度设置为无穷大。
[0062] 违例修复设备603可W根据所述DAG中的节点对应的区域的电路元件密度，选择 性地在所述节点对应的区域中放置保持时间校正元件W修复其保持时间违例。例如，违例 修复设备603可W将所述节点对应的区域的电路元件密度与密度阔值进行比较，并且响应 于所述每个节点对应的区域的电路元件密度没有超过该密度阔值，在所述节点对应的区域 中放置保持时间校正元件W修复其保持时间违例。
[0063] 下面，将参照图7具体描述违例设备603。如图7所示，违例修复设备603可W包 括列表建立单元6031和修复单元6032。
[0064] 列表建立单元6031可W建立节点列表，该节点列表包括所述DAG中可修复其保持 时间违例的所有节点（为便于描述，W下称为可修复节点)，其中，可W根据节点列表中的各 个可修复节点的输入路径数量和输出路径数量W及保持时间余量，对节点列表中的各个节 点进行排序。列表建立单元6031可W按照上文所述的方式来执行该一排序操作，在该里省 略其详细描述。所建立的节点列表可W根据实际需要而采用任何适当的形式。
[0065] 在建立节点列表之后，修复单元6032可W按照节点列表中的各个节点的顺序，根 据所述各个节点对应的区域的电路元件密度，选择性地在所述各个节点对应的区域中放置 保持时间校正元件W修复其保持时间违例。具体地，修复单元6032可W按照节点列表中 的每个节点的顺序，将每个节点对应的区域的电路元件密度与上文所述的密度阔值进行比 较。当节点列表中的某个节点对应的区域的电路元件密度超过所述密度阔值时，修复单元 6032不在该区域中插入新的元件W修复该节点处的保持时间违例。反之，当节点列表中的 某个节点对应的区域的电路元件密度不超过所述密度阔值时，修复单元6032可W在该区 域中插入保持时间校正元件W修复该节点处的保持时间违例。所述保持时间校正元件可W 是能够引入时间延迟的任何种类的元件，例如本领域公知的缓冲器或延迟元件。由于每种 保持时间校正元件能够引入的时间延迟量是已知的，因此，违例修复设备603可W根据该 节点处的保持时间余量与每种时延元件能够引入的时间延迟量，确定最终插入的保持时间 校正元件的种类和数量，然后，将该保持时间校正元件插入到该节点对应的区域中，从而修 复该节点处的保持时间违例。修复单元6032使用保持时间校正元件校正节点处的保持时 间违例的具体方式是本领域公知的，在该里省略其详细描述。在对该节点执行了所述修复 操作之后，修复单元6032可W从节点列表中删除该节点（即修复了保持时间违例的节点）W 及与该节点处于相同信号路径上的所有节点。
[0066] 在完成上述操作之后，对于节点列表中剩余的每个可修复节点(其为对应的区域 的电路元件密度超过所述密度阔值的可修复节点)，修复单元6032可W找出在该可修复节 点对应的区域周围的、电路元件密度没有超过所述密度阔值的区域（即上述替代区域)，并 且通过在该替代区域中，而不是该可修复节点对应的区域中，插入保持时间校正元件链来 修复该可修复节点处的保持时间违例。如上文所述，所述保持时间校正元件链包括放置在 所述替代区域中的至少一个保持时间校正元件W及将所述至少一个保持时间校正元件连 接到所述可修复节点的至少一个驱动元件。具体地，修复单元6032可W根据该可修复节点 处的建立时间余量和保持时间余量，选择要插入的保持时间校正元件链的类型。例如，修复 单元6032可W在参数Se化pSlack+V2地oldSlack大于0时选择上文所述的大延迟型保持 时间校正元件链W减小占据的空间，而在该参数小于0选择低变化型保持时间校正元件链 W避免引起新的时序违例。然后，修复单元6032可W确定保持时间校正元件链中的保持时 间校正元件的数量和驱动元件的数量，并且将所确定的保持时间校正元件链插入所述替代 区域。接下来，修复单元6032可W从节点列表中删除与修复了保持时间违例的该可修复节 点W及与其处于相同的信号路径上的所有节点，并且对于节点列表中的剩余可修复节点重 复上述操作，直到对于节点列表中的所有可修复节点都执行了上述操作为止。
[0067] 该样，利用根据本发明实施例的上述装置，可W修复电路中的保持时间违例，同时 避免在电路元件密度过大的区域插入更多的元件W及避免布线的拥塞。此外，上述装置不 需要移动已经放置在电路中的元件及其输入/输出管脚，从而可W避免因为元件/管脚的 移动而产生新的时序违例。
[0068] 在利用上述装置对电路进行了一次保持时间违例修复操作之后，如上文所述，可 W对电路重新进行时序分析，并且在确定发生保持时间违例时再次利用上述装置修复所述 保持时间违例，直到电路中不再发生保持时间违例为止。
[0069] 应当认识到，上文所述的根据本发明实施例的方法和装置只是说明性的，而非限 制性的，本领域技术人员可W对其进行适当的修改和改变，而不背离本发明的范围。例如， 尽管在上文中先执行步骤S201，然后执行步骤S202,但该不是限制性的，也可W先执行步 骤S202,再执行步骤S201。
[0070] 本发明可W是系统、方法和/或计算机程序产品。计算机程序产品可W包括计算 机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机可读程序指令。
[0071] 计算机可读存储介质可W是可W保持和存储由指令执行设备使用的指令的有形 设备。计算机可读存储介质例如可W是一-但不限于一-电存储设备、磁存储设备、光存储 设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的 更具体的例子(非穷举的列表)包括；便携式计算机盘、硬盘、随机存取存储器（RAM)、只读存 储器（ROM)、可擦式可编程只读存储器（EPROM或闪存)、静态随机存取存储器（SRAM)、便携 式压缩盘只读存储器（CD-ROM)、数字多功能盘（DVD)、记忆棒、软盘、机械编码设备、例如其 上存储有指令的打孔卡或凹槽内凸起结构、W及上述的任意合适的组合。该里所使用的计 算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、 通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传 输的电信号。
[0072] 该里所描述的计算机可读程序指令可W从计算机可读存储介质下载到各个计算/ 处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或 外部存储设备。网络可W包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网 关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接 收计算机可读程序指令，并转发该计算机可读程序指令，W供存储在各个计算/处理设备 中的计算机可读存储介质中。
[0073]用于执行本发明操作的计算机程序指令可W是汇编指令、指令集架构（ISA)指 令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、或者W-种或多种编程语 言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言一诸如 Smallta化、C++等，W及常规的过程式编程语言一诸如"C"语言或类似的编程语言。计算机 可读程序指令可W完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独 立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机 或服务器上执行。在涉及远程计算机的情形中，远程计算机可W通过任意种类的网络一包 括局域网（LAN)或广域网（WAN)-连接到用户计算 机，或者，可W连接到外部计算机(例如 利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指 令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程口阵列（FPGA)或 可编程逻辑阵列（PLA)，该电子电路可W执行计算机可读程序指令，从而实现本发明的各个 方面。
[0074] 该里参照根据本发明实施例的方法、装置(系统）和计算机程序产品的流程图和/ 或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框W及流程图和 /或框图中各方框的组合，都可W由计算机可读程序指令实现。
[0075] 该些计算机可读程序指令可W提供给通用计算机、专用计算机或其它可编程数据 处理装置的处理器，从而生产出一种机器，使得该些指令在通过计算机或其它可编程数据 处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功 能/动作的装置。也可W把该些计算机可读程序指令存储在计算机可读存储介质中，该些 指令使得计算机、可编程数据处理装置和/或其他设备W特定方式工作，从而，存储有指令 的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框 中规定的功能/动作的各个方面的指令。
[0076] 也可W把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它 设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，W产 生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的 指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。
[0077] 附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程 序产品的可能实现的体系架构、功能和操作。在该点上，流程图或框图中的每个方框可w代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个 用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能 也可不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可W基本并行地 执行，它们有时也可W按相反的顺序执行，该依所涉及的功能而定。也要注意的是，框图和 /或流程图中的每个方框、W及框图和/或流程图中的方框的组合，可W用执行规定的功 能或动作的专用的基于硬件的系统来实现，或者可W用专用硬件与计算机指令的组合来实 现。
[0078]W上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也 不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技 术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨 在最好地解释各实施例的原理、实际应用或对市场中的技术的技术改进，或者使本技术领 域的其它普通技术人员能理解本文披露的各实施例。
【主权项】
1. 一种修复电路中的保持时间违例的方法，包括： 创建所述电路的拓扑图，该拓扑图中的支路表示所述电路中发生保持时间违例的信号 路径，所述支路上的节点表示所述信号路径上发生保持时间违例的元件的端口； 将所述电路划分为多个区域； 根据所述拓扑图中的所述节点对应的区域的电路元件密度，选择性地在所述节点对应 的区域中放置保持时间校正元件以修复其保持时间违例。2. 如权利要求1所述的方法，其中，所述根据所述拓扑图中的各个所述节点对应的区 域的电路元件密度，选择性地在所述各个节点对应的区域中放置保持时间校正元件以修复 其保持时间违例包括： 将所述节点对应的区域的电路元件密度与密度阈值进行比较；以及 响应于所述节点对应的区域的电路元件密度没有超过该密度阈值，在所述节点对应的 区域中放置保持时间校正元件以修复其保持时间违例。3. 如权利要求1或2所述的方法，其中，所述根据所述拓扑图中的所述节点对应的区域 的电路元件密度，选择性地在所述节点对应的区域中放置保持时间校正元件以修复其保持 时间违例包括： 建立节点列表，该节点列表包括所述拓扑图中可修复其保持时间违例的所有节点，其 中，根据节点列表中的各个节点的输入路径和输出路径的数量以及保持时间余量，对节点 列表中的各个节点进行排序； 按照节点列表中的各个节点的顺序，根据节点列表中的各个节点对应的区域的电路元 件密度，选择性地在所述各个节点对应的区域中放置保持时间校正元件以修复其保持时间 违例。4. 如权利要求3所述的方法，其中，所述根据所述拓扑图中的所述节点对应的区域的 电路元件密度，选择性地在所述节点对应的区域中放置保持时间校正元件以修复其保持时 间违例还包括： 从节点列表中删除修复了保持时间违例的节点以及与该节点处于相同信号路径上的 节点。5. 如权利要求4所述的方法，其中，所述根据所述拓扑图中的所述节点对应的区域的 电路元件密度，选择性地在所述节点对应的区域中放置保持时间校正元件以修复其保持时 间违例还包括： 对于节点列表中的可修复其保持时间违例的剩余节点，选择在该剩余节点对应的区域 周围的、电路元件密度没有超过所述密度阈值的区域； 在所选择的区域中放置保持时间校正元件链以修复所述剩余节点处的保持时间违例， 所述保持时间校正元件链包括放置在所选择的区域中的至少一个保持时间校正元件以及 将所述至少一个保持时间校正元件连接到所述剩余节点的至少一个驱动元件。6. 如权利要求5所述的方法，其中，所述在所选择的区域中放置保持时间校正元件链 以修复所述剩余节点处的保持时间违例包括： 根据所述剩余节点处的建立时间余量和保持时间余量，选择所述保持时间校正元件链 的类型，以及 在所选择的区域中放置具有所选择的类型的保持时间校正元件链以修复所述剩余节 点处的保持时间违例。7. -种修复电路中的保持时间违例的装置，包括： 拓扑图创建设备，被配置为创建所述电路的拓扑图，该拓扑图中的支路表示所述电路 中发生保持时间违例的信号路径，所述支路上的节点表示所述信号路径上发生保持时间违 例的元件的端口； 电路划分设备，被配置为将所述电路划分为多个区域； 违例修复设备，被配置为根据所述拓扑图中的节点对应的区域的电路元件密度，选择 性地在所述节点对应的区域中放置保持时间校正元件以修复其保持时间违例。8. 如权利要求7所述的装置，其中，所述违例修复设备被配置为将所述节点对应的区 域的电路元件密度与密度阈值进行比较，并且响应于所述节点对应的区域的电路元件密度 没有超过该密度阈值，在所述节点对应的区域中放置保持时间校正元件以修复其保持时间 违例。9. 如权利要求7或8所述的装置，其中，所述违例修复设备包括： 列表建立单元，被配置为建立节点列表，该节点列表包括所述拓扑图中可修复其保持 时间违例的所有节点，其中，根据节点列表中的各个节点的输入路径和输出路径的数量以 及保持时间余量，对节点列表中的各个节点进行排序； 修复单元，被配置为按照节点列表中的各个节点的顺序，根据节点列表中的各个节点 对应的区域的电路元件密度，选择性地在所述各个节点对应的区域中放置保持时间校正元 件以修复其保持时间违例。10. 如权利要求9所述的装置，其中，所述修复单元还被配置为从节点列表中删除修复 了保持时间违例的节点以及与该节点处于相同信号路径上的节点。11. 如权利要求10所述的装置，其中，所述修复单元还被配置为对于节点列表中的可 修复其保持时间违例的剩余节点，选择在该剩余节点对应的区域周围的、电路元件密度没 有超过所述密度阈值的区域，并且在所选择的区域中放置保持时间校正元件链以修复所述 剩余节点处的保持时间违例，所述保持时间校正元件链包括放置在所选择的区域中的至少 一个保持时间校正元件以及将所述至少一个保持时间校正元件连接到所述剩余节点的至 少一个驱动元件。12. 如权利要求11所述的装置，其中，所述修复单元被配置为按照以下方式在所选择 的区域中放置保持时间校正元件链以修复所述每个节点处的保持时间违例：根据所述剩余 节点处的建立时间余量和保持时间余量，选择所述保持时间校正元件链的类型，以及在所 选择的区域中放置具有所选择的类型的保持时间校正元件链以修复所述剩余节点处的保 持时间违例。
【专利摘要】本发明公开了一种修复电路中的保持时间违例的方法和装置。所述方法包括：创建所述电路的拓扑图，该拓扑图中的支路表示所述电路中发生保持时间违例的信号路径，所述支路上的节点表示所述信号路径上发生保持时间违例的元件的端口；将所述电路划分为多个区域；根据所述拓扑图中的所述节点对应的区域的电路元件密度，选择性地在所述节点对应的区域中放置保持时间校正元件以修复其保持时间违例。通过所述方法和装置，可以避免在电路元件密度过大的区域插入新的元件，并且不需要移动已经布置在电路中的元件及其输入/输出管脚，从而避免因为元件/管脚的移动而产生新的时序违例。
【IPC分类】G06F17/50
【公开号】CN104881507
【申请号】CN201410072528
【发明人】牛佳, 李继峰, 戴红卫, 宋羽芸
【申请人】国际商业机器公司
【公开日】2015年9月2日
【申请日】2014年2月28日
【公告号】US20150248520