尼摩: 一個新的以隱性連通圖為基礎並使用虛擬瓦磚傳播的多層非格子繞線器

Abstract

這個研究提出一個新的以隱性連通圖為基礎的多層非格子繞線器尼摩，它不像之前第一個以隱性連通圖為基礎的繞線器埋置所有層到一個繞線平面，尼摩一個繞線層就建構一個繞線平面。此外，尼摩的每一個繞線平面都是由瓦磚組成，而不是由格子點與它們之間的連接線所組成的陣列，因此繞線問題的複雜度將可以獲得減少。尼摩的每一個格子點精確地表示一個瓦磚(在瓦磚的左下角)，而格子點尋路將變成瓦磚傳播，並且為了更進一步地提升路徑搜尋的速度，連續的空白瓦磚將會被結合成虛擬的最大水平條帶或最大垂直條帶。實驗的結果指出尼摩在連通點對點的路徑搜尋會比之前第一個以隱性連通圖為基礎的繞線器快大約十倍，而由尼摩完成的全晶片繞線也勝過所有的多層級非格子繞線快大約二到五倍。

This study presents a new multilayer implicit connection graph-based gridless router called NEMO. Unlike the first implicit connection graph-based router that embeds all routing layers onto a routing plane, NEMO constructs a routing plane for each routing layer. Furthermore, each routing plane is composed of tiles, not an array of grid points as well as their connecting edges, and, consequently, the complexity of routing problem decreases. Each grid then exactly represents one tile (its left bottom corner), and grid maze becomes tile propagation; moreover, to further speedup in path searching, continuous space tiles are combined as a pseudo maximum horizontally or vertically stripped tile. Experimental results indicate that NEMO conducts point-to-point path searching on about 10 times faster than the implicit connection graph-based router. Full-chip routing by NEMO also outperforms all multi-level gridless routing with about twofold to fivefold speedup.