高级检索

    一种基于带权有向图的印刷电路板群组布线算法

    A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards

    • 摘要: 布线是印刷电路板设计中的重要一环. 现有的印刷电路板设计多依赖于电子设计自动化工具的处理,而传统的自动布线研究多聚焦于总线布线,没有将布线时确定的群组作为研究对象. 由于未经总线分组,可能存在群组中线网较多的情况,这将导致群组所占据的线宽与线间距比原先总线布线中各总线组分别占据的线宽与线间距更大,从而给实际布线带来了新的挑战. 为此,提出一种基于带权有向图的群组布线算法. 首先构建仅含有合并边以及它们之间邻接关系的Hanan网格图. 接着,利用合并边信息构建带权有向图,完成对电路板上布线资源的表示. 然后,使用一种具有多线避让功能的启发式搜索算法来进行布线规划. 最后,通过将布线归类为数种可能的情况分别考虑,完成详细布线并得到群组布线的最终结果. 实验结果表明,算法在已经测试过的工业界复杂例子上均能达到100%的布通率,并且不会违反所有工业印刷电路板基准用例的设计规则约束.

       

      Abstract: Routing is considered an essential component in the design of printed circuit board (PCB). Current existing PCB designs mostly rely on the process results from electronic design automation tools, and traditional automatic routing research often focuses on only general bus routing without considering bus groups to be determined during the routing process. Due to the absence of general bus grouping, there may be situations where there are more nets in one group than in other groups, resulting in larger line width and line clearance occupied by this group when compared to other bus groups in the original bus routing, thereby posing new challenges to effective and efficient routing. To overcome this drawback, this paper focuses on studying PCB group routing. In this study, a group routing algorithm based on a weighted directed graph is proposed. A Hanan grid graph is constructed, containing only merged edges and their adjacent relationships. Following this, a weighted directed graph is developed using the merged edge information to represent the routing resources on the circuit board. For routing planning, a heuristic search algorithm equipped with multi-wire avoidance features is utilized. The routing situations are then classified into several potential scenarios, with each considered separately, to accomplish detailed routing and obtain a final result of group routing. Results from experiments demonstrate that a 100% routability is consistently achieved by using the algorithm on complex industrial examples that have been previously tested, and that the design rule constraints of all benchmark industrial PCB cases are not violated.

       

    /

    返回文章
    返回