在多核心平台上執行之多執行緒廣域佈線法

Abstract

隨著先進IC製程之設計複雜度的增加，其運算時間成為了許多電子設計自動化應用程式的主要問題；而平行計算的出現提供了我們一個可能改進此問題的方法。因為許多近年發表的廣域佈線器皆為循序處理，而使得它們無法充分利用多核心平台的優點，所以我們的工作將著重於如何將平行運算融入於廣域佈線器並加速之。 在這篇論文中，我們提出了一個有彈性的平行策略，它可以輕易融入任何的廣域佈線器進而使其加速，我們亦提出了數個方法來增強其繞線能力。這篇論文的主要貢獻為(1)一個可以使各執行緒達到負載平衡且使廣域佈線器加速之工作基礎平行策略，以及(2)在某些測試資料，我們的強化方法甚至可以讓強化後的廣域佈線器產生比原本的繞線結果更好的繞線結果。實驗數據顯示，我們的演算法在可以解決的測試資料上得到平均2.73倍的加速；此外，我們的演算法甚至在較難繞線的測試資料中得到了平均2.94倍的加速。

As the design complexity increasing in advanced IC technique, the computation effort becomes the major challenge for many EDA applications; the emergence of parallel computations provides us the potential to solve the problem. This work focuses on adopting parallel computation to speedup global router sine many modern global routers were proposed recently, but most of them are sequential routers and are not working well on multi-core platform. This paper presents a flexible concurrency strategy which can be easily embedded into any modern global routers and obtain acceleration, and we also propose several approaches to enhance the routability. The key contributions of this work include: (1) A task-based concurrency strategy which keeps load balance between threads and achieves high acceleration and (2) in some benchmarks, our enhanced approaches can even make the router produce better routing results than original one. Experimental results demonstrate that our algorithm obtains 2.73x average speedup in solvable benchmarks by using quad-core; furthermore, our algorithm even achieves 2.94x average speedup in hard-to-route benchmarks.