探討B*-tree在非點格式軌道繞線中的應用

Abstract

在傳統的兩接段繞線流程中，電路線軌指派演算法扮演一個愈來 愈重要的角色且將其整併於全域繞線和精細繞線之中。其不僅分擔了 精細繞線的工作負荷並考量了內部互連性與空間利用率的最佳化。電 路線軌指派使用於非點格式繞線器中的非點格式軌道繞線是用來提 供更多的資訊在完成全域繞線之後，雖然已有許多關於點格式軌道繞 線的研究，但有關非點格式環境的研究就相對少了許多。這份論文將 一種樹狀資料結構B*-tree 應用到非點格式軌道繞線中並且基於模 擬退火演算法提出一個可行的流程。另外，這個非點格式電路線軌指 派的流程將可使用一些方法去改善它的結果。這份論文也比較了另一 個樹狀資料結構O-tree 和B*-tree 應用於非點格式電路線軌指派之 中的某些操作過程。B*-tree 的高效率將會是一個可以把O-tree 自 非點格式電路線軌指派取代的良好選擇就如同在大多數的平面規劃 和電路擺置策略一樣。

Track assignment plays a growing role of incorporating between global routing and detailed routing in the traditional two-stage routing flow. It shares the burden of detailed routing and considers optimizing interconnectivity and utilization. Gridless track routing is exploiting in gridless routers for providing more information after global routing. There is much research on grid track routing but little on gridless environment. This study applies B*-tree structure to the gridless track routing and propose a feasible flow based on simulated annealing. The flow of gridless track assignment may probably improve the result by using some techniques. We also compare some operations between the O-tree and B*-tree on gridless track assignment. The efficient B*-tree would be another option replacing O-tree on the gridless track assignment such as the substitution in most floorplans and placements.