A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks

Yokohama January 23-January 26

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ASPDAC.2007.357997

2007 Asia and South Pacific Design Au ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by null Tan Yan Articles by null Shuting Li Articles by Y. Takashima Articles by H. Murata

	ASCII Text	x
	null Tan Yan, null Shuting Li, Y. Takashima, H. Murata, "A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks," Asia and South Pacific Design Automation Conference, pp. 268-273, 2007 Asia and South Pacific Design Automation Conference, 2007.

	BibTex	x
	@article{ 10.1109/ASPDAC.2007.357997, author = {null Tan Yan and null Shuting Li and Y. Takashima and H. Murata}, title = {A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks}, journal ={Asia and South Pacific Design Automation Conference}, volume = {0}, year = {2007}, isbn = {1-4244-0629-3}, pages = {268-273}, doi = {http://doi.ieeecomputersociety.org/10.1109/ASPDAC.2007.357997}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Asia and South Pacific Design Automation Conference TI - A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks SN - 1-4244-0629-3 SP268 EP273 A1 - null Tan Yan, A1 - null Shuting Li, A1 - Y. Takashima, A1 - H. Murata, PY - 2007 KW - shortest obstacle-avoiding routing length KW - wire length estimation algorithms KW - shortest routing length KW - routing obstacles KW - block placement KW - computational geometry KW - VLSI CAD VL - 0 JA - Asia and South Pacific Design Automation Conference ER -

null Tan Yan, Graduate Sch. of Environ. Eng., Kitakyushu Univ., Fukuoka

null Shuting Li, Graduate Sch. of Environ. Eng., Kitakyushu Univ., Fukuoka

Y. Takashima, Graduate Sch. of Environ. Eng., Kitakyushu Univ., Fukuoka

H. Murata, Graduate Sch. of Environ. Eng., Kitakyushu Univ., Fukuoka

How to estimate the shortest routing length when certain blocks are considered as routing obstacles is becoming an essential problem for block placement because HPWL, is no longer valid in this case. Although this problem is well studied in computational geometry (Mitchell, 2000), the research results are neither well-known to the CAD community nor presented in a way easy for CAD researchers to ultilize their establishment. With the help of some recent notions in block placement, this paper interprets the research result in Atallah and Chen (1991) and de Rezende et al. (1985), which gives the best algorithm for this problem as we know, in a way more concise and more friendly to CAD researchers. Besides, we also tailor its algorithm to VLSI CAD application. As the result, we present a method that estimates the shortest obstacle-avoiding routing length in 0(M² + N) time for a placement with M blocks and N 2-pin nets.

Index Terms:

shortest obstacle-avoiding routing length, wire length estimation algorithms, shortest routing length, routing obstacles, block placement, computational geometry, VLSI CAD

Citation:

null Tan Yan, null Shuting Li, Y. Takashima, H. Murata, "A Theoretical Study on Wire Length Estimation Algorithms for Placement with Opaque Blocks," asp-dac, pp.268-273, 2007 Asia and South Pacific Design Automation Conference, 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.