應用於超大型積體電路實體設計之繞線延遲界限產生器

Interconnect Delay Bound Generator for VLSI Physical Design Synthesis

洪旗徽(Chy-Hui Hong)

指導教授 ： 林榮彬

元智大學/資訊學院/資訊工程學系/碩士(2000年)

摘要

儘管網路長度界限取向的置放(net-length bound driven placement)長久以來被很多設計者質疑其可行性，但如能在置放的過程中適當的調整網路長度界限，這個方法仍是值得探討。為了支援本實驗室一位同仁發展一個繞線長度取向的標準元件置放器（ILDPer），本篇論文將發展一個網路延遲(長度)界限的產生器。過去的研究比較注重在不考慮false path影響的情況下，針對每一個網路產生一個界限。為了考量繞線上之RC effect，我們的界限產生器將在排除static false path的狀況下，針對每一個source-sink pair產生一個延遲界限。幾個網路權重分配的策略以及最大最小的延遲界限的限制使得網路延遲界限更加合理。這個網路延遲界限產生器將被整合至ILDPer中，同時在ILDPer的要求之下根據目前部份置放(partial placement)的結果來動態的產生一組新的延遲界限。隨著時間的演進，部份置放將會提供更精準的元件位置以致使每一個網路更易滿足新的延遲界限。一些MCNC測試電路用來測試界限產生器的效能與正確性，實驗的結果顯示出透過網路界限延遲來影響元件的移動是可行的，當和Cadence Silicon Ensemble所產生出來最長路徑延遲做比較，我們的最長路徑延遲的改進達百分之三十二。

關鍵字

延遲界限

並列摘要

Though the net-length bound driven placement has long been questioned by many designers about its feasibility, it is worth revisiting this approach given that net length bounds can be adapted for the progress of the placement process. In response to an attempt to develop an interconnect length driven standard cell placer (ILDPer) by a colleague in our laboratory, this thesis proposes to develop a net delay (length) bound generator to support its development. The past research has been focused more on generating bound for each net without considering the influence of false paths. To consider the interconnect RC effect, our bound generator will compute for each source-sink pair a delay bound with exclusion of static false paths. Several strategies of net weight assignment and the limitation of the maximum and minimum delay bounds are employed to make the delay bound more reasonable. The bound generator which is integrated into the ILDPer can dynamically generate, upon a request by the ILDPer, a new set of delay bound based on current partial placement. As time goes by, the partial placement will provide more accurate cell position such that the new set of net delay bounds is easier to satisfy. Some MCNC benchmark circuits are used to evaluate the efficiency and correctness. The experimental results show the employment of using delay bounds to influence the movement of cells is viable. The longest path delays are improved up to 32% when compared to those obtained by Cadence Silicon Ensemble.

並列關鍵字

delay bound ； false path ； bound generation

參考文獻

[2]R. Iris Bahar, Hyunwoo Cho, Gray D.Hatchtel, Enrico Macii, and Fabio Somenzi, ”Symbolic timing analysis and resynthesis for low power of combinational circuits containing false paths,” IEEE Trans. on Computer-Aided Design, Vol. 16, Oct. 1997, pp.1101-1115.

[5]Wing K. Luk, “A fast physical constraint generator for timing driven layout,” Proc. 28th ACM/IEEE Design Automat. Conf., 1991, pp.626-631.

[7]H. C. Chen and H. C. Du, “Path sensitization in critical path problem,” IEEE Trans. Computer- Aided Design, vol. 12, Feb. 1993, pp. 196-207.

[10]L. P. Roth, “Diagnosis of automata failures: A calculus and a new method,” IBM J. Res. Develop. , Oct. 1966, pp. 278-281.

[11]P. Mcgeer and R. Brayton, “ Efficient algorithms for computing the longest viable path in a combination network,” Proc. of the 26th Design Automation Conf., 1989, pp. 561-567.