面向区域布线的层次式PB角勾链版图数据结构

Area Routing Oriented Hierarchical Corner Stitching with Partial Bin

无网格区域布线具有存储量小、布通率较高、易实现混合设计规则布线并可解决串扰问题等优点 .无网格区域布线算法中 ,找到路径后对底层版图数据库的修改时间在整个算法运行时间中占很大比例 .因此 ,操作简便、快捷的版图数据结构对于无网格区域布线算法非常重要 .目前在无网格区域布线算法中应用最广泛的版图数据结构是矩形角勾链 ,其点查找和模块插入操作的复杂度均为 O(N1 /2 ) .文中提出一种新型的结合了 Bin结构与梯形角勾链结构的层次式 PB角勾链版图数据结构 ,其点查找和模块插入操作的复杂度降低至 O(N1 /2 /r) ,其中 r2 为 Bin数 .同时 ,针对区域布线算法的特点 ,文中给出了层次式 PB角勾链结构的点查找、区域枚举、推移等操作的算法 .

Gridless routing now attracts more concerns for these advantages: it reduces the memory requirements; it can help to reach a higher connection rate; it enjoys more flexibility in accommodating complicated design rules; and it can handle the problem of crosstalk. For most of the proposed gridless routers, not only the path finding process but also the postprocessing of updating geometrical information for subsequent interconnection occupies a major portion of total processing time for interconnecting nets one after another. Therefore, a fast and convenient layout data structure is of great importance to a gridless area router. Nowadays, the rectangular corner stitching structure, whose point searching and tile insertion are O(N 1/2 /r ), is the most popular data structure used by gridless area routers. This paper discusses a novel database hierarchical corner stitching with partial bin, or hierarchical PB corner stitching, which combined the bin based structure and the trapezoidal corner stitching. Its point searching and tile insertion are both enhanced to O(N 1/2 /r ). It also derives the algorithms of the operations, such as point searching, area searching, plowing, etc., according to the specialties of area routers.