透過標識障礙物邊界快速產生虛擬方塊以加速尼摩非點格式繞線器

Abstract

這份研究發展了一個以箱子基礎資料結構的多層隱性連通圖之非點格式繞線器。這個研究保留了前一個版本大部分的優點，如多層隱性連通圖、快速換層機制、以及虛擬磚瓦傳遞，並且加快了建構繞線圖以及萃取虛擬磚瓦的速度。在繞線區域外的障礙物所產生的多餘格線增加了繞線圖的複雜度，使得路徑搜尋變得緩慢。不同於之前的版本掃描在全域路徑中所有的格線，這個研究使用箱子基礎資料結構直接萃取在全域路徑中所有的障礙物來產生簡化的繞線圖。這個新的繞線圖建構方法比之前的方法快了一倍。為了加速傳遞速度，連續的空磚瓦被連結在一起形成虛擬最大水平條帶或最大垂直條帶磚瓦。藉由標識障礙物，合法性檢查在每一個空磚瓦上只需要比較一次，使得虛擬磚瓦萃取比在縱切樹和區間樹中搜尋障礙物快十倍。實驗數據顯示這個新的非點格式繞線器可以節省一半的繞線時間，一般性質繞線也比所有的多階層非點格式繞線器快了將近3.5倍至86.8倍。

This investigation develops a new multilayer implicit connection graph-based gridless router with bin system. This work retains all advantages of the previous version and improves the speed of graph construction and pseudo tile extraction. The grid-lines derived from the blockages which fall entirely outside the routing region increase the complexity of routing graph and decelerate path search. Unlike the previous work that scans all grid-lines inside the routing region for filtering out redundant grid-lines, this work generates a simplified routing graph by extracting blockages in the routing region explicitly. Furthermore, continuous space tiles are combined as a pseudo maximum horizontally or vertically stripped tile for accelerating path search. By tagging blockage on the routing graph, legality check on each tile needs little query overload such that pseudo tile extraction is about ten times faster than querying the well-known slit plus interval tree. Experimental results reveal that this new gridless router around two times faster than the previous version. General-purpose routing by this work also outperforms all multilevel gridless routers with runtimes that are approximately 3.5x to 86.8x faster.