透過您的圖書館登入
IP:3.89.163.120
  • 學位論文

有障礙物限制下之效能導向 全域繞線

Performance Driven Global Routing in Present of Obstacles

指導教授 : 謝財明

摘要


製程技術一日千里,已逐步邁入奈米的時代,為積體電路相關領域帶來許多改變以及挑戰,其中最顯著的莫過於晶片訊號連線數的增加,所以在晶片設計整體效能上,繞線問題的影響比例也越來越高,因此如何在決定繞線路徑時能有效的降低繞線問題是很重要的研究課題。 因此擬提出一個在全域繞線階段同時考量障礙物以及改進餘裕時間(slack)的演算法,有效的提供完整繞線路徑選擇資訊給全域繞線器並減少細部繞線階段之後處理工作;另一方面也可改善繞線擁擠度以及串音問題。 本方法先以各組連線的連線範圍(Bounding Box)半周長以及餘裕時間來初步判斷路徑的選擇以及每組net有效繞線長度,而有效的繞線長度,可為傳統不考慮障礙物的半週長計算方式或考慮因須繞過障礙物的繞線長度。爾後根據連線的資訊來進行繞線擁擠度以及繞線串音分布的估計來調整以建構出避開障礙物之全域繞線路徑解(grid-to-grid path),最後以修正型Crosstalk-Driven Track Assignment 演算法[11]進一步分配每條線段在方格裡的位置。實驗結果顯示本方法對於在不同時間限制下的可繞度比一般全域繞線不考慮餘裕時間的情況平均多出4%~8%,顯示了在時間限制越嚴苛時,本方法的可繞度改善越加明顯。儘管可繞度較為改善的情況下而有更多的連線繞線成功,平均耦合長度仍有3%的改善。

並列摘要


In this paper, we proposed a new approach which simultaneously considers timing slack, congestion, crosstalk and the present of obstacles during global routing stage. First, we determine the net routing order by ascending slack evaluated by Elmore delay model. For each determined two-pin net, we compute the integrated cost including crosstalk and congestion of each grid assuming that the routing paths are L or Z-shaped. Then detour will be introduced when nets cross the obstacles. During the progress of the algorithm, we dynamically update the information of slack, congestion, and crosstalk. When a global routing path with a set of horizontal and vertical segments is found, a crosstalk-driven method is used to assign the segments to the proper tracks. Compared with results of previous methods, our algorithm can achieve 4~8% improvement on average of routability under various time constraints. Moreover, even more than 4~8% paths are routed successfully, there are still 3% of effective total coupling wire length are reduced.

並列關鍵字

obstacles coupling effect slack. global route

參考文獻


[16] J. Lou, S. Thakur, S. Krishnamoorthy and Henry S.Sheng, “Estimating Routing Congestion using Probabilistic Analysis,” Proc. ACM International Symposium on Physical Design, pp. 112-117, 2001.
[2] Shabbir Batterywala, Narendra Shenoy, William Nicholls and Hai Zhou, “Track Assignment:A Desirable Intermediate Step Between Global Routing and Detailed Routing,” Proc. IEEE International Conference on Computer Aided Design, pp. 59-66, 2002.
[6] S. Even, A. Itai and A. Shamir, “On the Complexity of Timetable and Multicommodity Flow Problems,” SIAM Journal of Comp. 1976.
[7] J. L. Ganley and J. P. Cohoon, “Routing a multi-terminal Critical net: Stiner Tree Construction in the present of obstacles,” In Proc. IEEE International Symposium Circuits and Systems, pp.113-116, 1994.
[8] T. Gao, C.L. Liu, “Minimum Crosstalk Switch-box Routing,” IEEE/ACM International Conference on Computer Aided Design, pp. 610-615, 1994.

延伸閱讀