考慮障礙物繞線及緩衝器插入之方法研究

Abstract

近來，由於導線延遲己凌駕於電晶體延遲的緣故，致使許多效能導向的繞線及插入緩衝器的演算法，相繼被提出，以降低導線的延遲。在我們的論文當中，我們提出了兩種有效率的方法，可以快速建構出效能導向的繞線及插入緩衝器，並考慮避開障礙物的限制。 第一個演算法，我們修改了[8]中使用的降溫演算法，以階層的方式建構繞線，並同時考量插入緩衝器的效應。第二個演算法，我們採用兩級最佳化的方式，來達成繞線和插入緩衝器的任務，首先建構出效能導向的繞線之後，再插入緩衝器，以降低導線的延遲效應。 最後，我們所提出的兩個方法，與過去所提出的演算法相比，能夠得到更好的效能，且所需要的運算時間大幅減少。

In recent years, many algorithms for buffered interconnect tree construction were proposed to minimize interconnect delay due to the interconnect delay becomes more critical than transistor delay. In this thesis, we proposed two efficient algorithms to construct buffered interconnect tree with blockages. Our first algorithm modifies the simulated annealing algorithm [8] to hierarchically construct buffered interconnect tree considering buffer insertion simultaneously. Our second algorithm adopts two-stage optimization techniques to construct buffered interconnect tree. First to construct a performance-driven routing and then insert buffers for it to minimize the interconnect delay. We will show our algorithms could obtain better performance and more efficient than pervious algorithms.