考慮存在電壓島的緩衝器繞線樹架構的一個有效率的演算法

Abstract

由於低功率的方法論在超大型積體電路(VLSI)和系統單晶片(SoC)的需求，電壓島(voltage island)越來越吸引設計者的注意。然而，相對應在電子自動化設計(EDA)工具方面，考慮到電壓島的繞線樹建構仍然非常稀少。[7] 是第一個深入研究應用兩種不同Vdd電壓的緩衝器在繞線樹的建構上，並且藉由限制緩衝器的擺放順序而忽略電壓轉換器(level converter)需求的考量。然而，因為有這些限制，所以這個方法並不能應用到具有電壓島的設計上面。 本篇論文提出一個演算法以解決具有電壓島的低功率設計上緩衝器以及電壓轉換器放置的問題。既然[7](使用[9]中的技巧)無法應用在電壓島的設計上，我們改進[9]中RMP的方法以適用在此種設計上。我們更進一步的發展我們的方法來做比較。藉由一些貪婪探索(greedy heuristic)的技巧，我們的方法不僅非常有效率，而且能維持解的品質。 實驗結果顯示相較於改良的RMP方法，我們的方法是非常有效率，甚至於會有較低的功率和延遲(delay)。再者，當汲點(sink)的個數增加，改良的RMP方法無法在一合理的時間內找到一組解答，我們的方法可以更有效率的找到一組適當的解。

Due to the need of low power methodology in VLSI and SoC designs, voltage island architecture is attracting attentions in design community. However, the corresponding EDA tools development regarding routing tree construction is still very few. [7] is the first in-depth study on applying dual □□□□buffers in routing tree construction, with the restriction on the ordering of buffers and the lack of level converter consideration. However this approach cannot be applied on a design with voltage islands due to these restrictions. This paper presents an algorithm to solve the buffer insertion and level converter assignment problem in the presence of voltage island in a low-power design. Since [7] (use techniques in [9]) cannot be performed on voltage island designs, we have modified RMP approach in [9] to perform on those designs. We then develop our approach for comparison. With some greedy heuristics and prune techniques, our approach is very efficient and it still keeps the quality of solutions. The experimental results show that we can obtain massive speedup over modified RMP approach, and even with lower power and delay. Furthermore, as number of sink increases, modified RMP cannot find solutions within a reasonable CPU time, while our approach can efficiently find feasible solutions.