於異質平行化平台之現代廣域繞線設計

Abstract

近年來因積體電路製程技術的快速發展，在越來越複雜的設計需求和加速構思新產品上市的緊迫壓力下，繞線的計算速度更加地受到重視。本論文實現於由CPU和GPU處理器組成之異質平行平台。我們使用以處理速度為導向的CPU進行軟體的串行部分，以吞吐量為導向的GPU處理軟體的平行部分。 當多條連線同時取用相同的繞線資源時就會發生資源競爭的問題，並導致平行繞線產生不可預期的溢出。本論文提出一個於GPU上針對個別連線的繞線資源成本評估演算法，使在平行繞線下的連線能夠有較佳廣域觀點並改善上述所提之資源競爭現象。我們提出在GPU平台上進行的平行化拓撲結構重建方法。經實驗顯示本拓鋪結構重建法在多次完成重建後能夠有效幫助設計改善擁擠區域，其執行時間僅佔整體時間的 0.09%~1.81%。

As integrated circuit technology rapidly advanced, the runtime of routing gains much more attention due to the elaborate design requirements and time-to-market pressure. This thesis is implemented on the heterogeneous parallel platform, which is build up by hybrid CPU and GPU processors. We use the latency oriented CPU to compute the sequential part of the program and the throughput oriented GPU to execute the parallel part. When more than one net queries the same routing resource, the race condition occurs and leads to unexpected overflow after the parallel routing. In this thesis, a GPU-based algorithm is proposed to evaluate the cost of routing resources for each net separately with a good global view and the algorithm can efficiently relieve the phenomenon mentioned above. The GPU-based topology reconstruction is proposed to reconstruct the topology of a multi-pin net in parallel and fix the overflow edges. Experimental result shows that the proposed algorithm can iteratively relieve the over-congested areas efficiently in 0.09% to 1.81% of the total runtime.