用于提供回转约束最小代价缓冲的方法和系统

摘要

缓冲器插入技术针对回转约束的同时最小化缓冲器代价。该方法构造用于汇点的初始解决方案，其各自具有关联的代价、回转和容量。当解决方案朝向源点传播时，将导线容量和导线回转添加到该解决方案。当选择缓冲器用于可能的插入时，将该解决方案的回转设置为0，同时基于所选缓冲器而使现有的解决方案的代价递增，并将容量设置为所选缓冲器的固有容量。通过添加分支容量和代价、并选择最高的分支回转，而合并两个相交的导线分支的解决方案。通过忽略具有比回转约束大的回转分量的解决方案，而更新候选解决方案集合，并且，去除被其它解决方案胜过的任何解决方案。选择具有最小的代价的解决方案作为最终解决方案。

主权项

一种提供用于集成电路设计的网络的缓冲器树的方法，包括：根据用于网络的汇点的初始解决方案构造用于缓冲器树的初始解决方案集合，其中，解决方案具有关联的代价、关联的回转和关联的容量作为分量；为源自汇点、并朝向网络的源点延伸的网络导线分支生成候选解决方案的集合，其中所述生成候选解决方案的步骤包括，通过相加导线分支的容量和相加导线分支的代价、并选择最高的分支回转，而合并两个相交的导线分支的解决方案，以及其中，所述候选解决方案具有通过下述操作得出的关联的代价、关联的回转和关联的容量：选择用于在沿着该导线分支的缓冲器位置上插入的缓冲器；将用于该导线分支的现有解决方案的回转设置为0；基于所选缓冲器而使现有的解决方案的代价递增；以及将现有的解决方案的容量设置为所选缓冲器的固有容量通过添加新的导线部分的导线容量，而增大用于导线分支的现有的解决方案的容量；以及通过添加新的导线部分的导线回转，而增大现有的解决方案的回转；通过忽略具有比回转约束大的回转分量的任何候选解决方案，而更新候选解决方案的集合；以及从更新的候选解决方案的集合中选择具有最小代价的最终解决方案。