應用熱斥力模型處理自動繪圖和晶片布局問題之研究

裴慶興 ； 黎靖

《東方學報》 30期 (2009/12) Pp. 99-109

https://doi.org/10.29421/JTDU.200912_(30).0009

摘要

繪圖問題是組合最佳化問題中之一環，其目的不外乎是繪製圖形滿足：小面積、最小化邊相交的次數、邊的分隔情形、節點均勻分布及角度的解析度等。在不同的領域中有許多重要的問題都可以描述成繪圖問題，例如平行電腦架構下的網路最佳化問題、積體電路布局設計問題、資訊視覺化問題及圖形理論等。由於大部分重要的問題屬於NP-hard，近似解或啟發式的解法是常用的解法。我們合併熱斥力模型與連接力模型成為混成力模型，並使用混成力模型類比二維自動繪圖問題。

關鍵字

自動繪圖 ； 晶片布局 ； 熱斥力法

參考文獻

Md. S. Rahman, T. Nishizeki, and S. Ghosh, “Rectangular Drawings of Planar Graphs,” Journal of Algorithms, Vol. 50, pp. 62-78, 2004.

M. Kaufmann and D. Wagner (Eds), Drawing Graphs: Methods and Models, New York: Springer, 2001.

J. Lee, “Thermal placement algorithm based on heat conduction analogy,” IEEE Trans. On Components and Packaging Technologies, Vol. 26, No. 2, pp. 473-482, 2003.

J. Lee, “Reliability and wireability optimizations for chip placement on multichip modules,” IEEE Trans. on Electronics Packaging Manufacturing, Vol. 28, No. 2, pp.133-141, 2005.

J. Lee, “General thermal force model with experimental studies,” IEEE Trans. On Components and Packaging Technologies, Vol. 29, No. 1, pp.20-29, 2006