平行運算電子設計自動化技術研究-子計畫三：在圖形處理單元平台上針對繞線演算法的平行化最佳化研究( I )

Abstract

在常規的時序修正型工程變更指令技術(Timing ECO)中，多接腳網路(Multi-pin Net)的緩衝器嵌入方法僅考慮縮短該網路關鍵點(Critical Sink)的到達時間(Arrival Times)。受到忽略障礙物和繞線線路的拓撲結構(Topology)的影響，該方法將延遲其他點的到達時間，使後續進行的修正負擔變重。本計畫主旨為在圖形處理單元平台上研究大量平行化繞線演算法在更短的執行時間內搜尋更多種解的組合，藉以改善時序型ECO並最佳化其品質。建立一個考慮拓撲結構的時序修正型工程變更指令技術最佳化方法(Topology-aware ECO Timing Optimization, TOPO)，其流程包含三個階段：(1)緩衝器對評分(Buffering Pair Scoring)、(2)去除邊和緩衝器連接(Edge Breaking and Buffer Connection)，和(3)拓撲結構重建法(Topology Restructuring)。TOPO能有效率地改善違反點(Violation Sinks)的到達時間且不會延遲其他的點。實驗結果顯示，TOPO演算法在各試驗基準(Benchmarks)下能改善最大違反時序(Worst Negative Slack, WNS)和總違反時序(Total Negative Slack, TNS)平均達79.2%和84.3%。相對於使用常規雙接腳網路型(Two-pin Net-based)緩衝器嵌入方法能改善40.4%的到達時間，使用19倍的執行時間。為加速繞線並改善各點的時序，本研究提出一個建立在圖形處理器(GPU)平台上高度可擴展的大量平行化迷宮繞線方法(Maze Routing)，使本流程能夠找尋更多可能的候選解。實驗結果顯示本研究提出的GPU-based平行化迷宮繞線方法可加速雙點繞線過程處理時間接近12倍，可解決4/5的WNS錯誤。

Conventional buffer insertion in timing ECO involves only minimizing the arrival time of the most critical sink in one multi-pin net and neglects the obstacles and the topology of routed wire segments, which may worsen the arrival times of other sinks and burden subsequent timing ECO. This work develops a topology-aware ECO timing optimization (TOPO) flow that comprises three phases - buffering pair scoring, edge breaking and buffer connection, and topology restructuring. TOPO effectively improves the arrival times of violation sinks without worsening those of other sinks. Experimental results indicate that TOPO improves the worst negative slack (WNS) and total negative slack (TNS) of benchmarks by an average of 79.2% and 84.3%, respectively. The proposed algorithm improves the arrival time that is achieved using conventional two-pin net-based buffer insertion by an average of 40.4%, at the cost of consuming 19× runtime. To speed up routing and further improve sink slack, a highly scalable massively parallel maze routing on Graphics Processing Unit (GPU) platform is also developed to enable the proposed flow to explore more solution candidates. High scalability and parallelism are realized by block partitioning and staggering. Experiments reveal that the proposed GPU-based parallel maze routing can achieve near 12× runtime speedup for two-pin routings. With parallelized maze routing, WNS violations in four out of five cases can be resolved.