以B*樹處理含定位及效能導向的擺置問題

Abstract

為了促進循序電路的傳輸以及減少關鍵線路(bounded net)所造成的延遲效應(delay)並同時的降低線路的總合(total wire length)，目前需要將電路區塊(circuit block)一個接著一個的擺放(abut one by one)以及將一些電路區塊放在一個特定大小的區域之中。在這篇論文中，我們使用 B*-tree 的表示法處理依序排列以及效能導向的電路擺放問題(placement)。我們首先探討依序排列(alignment)以及效能導向(performance)的可行性，並提出一個演算法，該演算法保證在每個階段都可以找到符合依序排列以及效能導向的電路擺法。對於所提出的問題，我們的演算法是第一個達到理論上最佳化的演算法，時間複雜度僅僅只有線性時間(linear time)。以 MCNC 為主的實驗數據，說明了我們的方法比起之前的方法有很明顯的進步。

To facilitate sequential data transfer and reduce bounded net delay (as well as total wirelength), it is desired to align circuit blocks one by one and constrain the blocks within a certain bounding box. In this paper, we handle the placement with alignment and performance (delay) constraints using the B*-tree representation. We first explore the feasibility conditions with the alignment and performance constraints, and then propose algorithms that can guarantee a feasible placement with alignment and performance constraints during each operation. In particular, our method is the first algorithm to achieve the theoretically optimal linear-time complexity for evaluating a placement with the alignment and performance constraints. Experimental results based on the MCNC benchmark with the constraints show that our method significantly outperforms the previous work.