Cited By
View all- Xing SWang RHuang G(2020)Area Decomposition Algorithm for Large Region Maritime SearchIEEE Access10.1109/ACCESS.2020.30376798(205788-205797)Online publication date: 2020
A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygons
Article No.: 59, Pages 1 - 18
Abstract
In order to use rectangular corner stitching data structures in storing parameterized orthogonal layouts, parameterized polygons in the layouts must be partitioned into rectangles. Likewise, in order to use trapezoidal corner stitching data structures in storing parameterized 45-degree layouts, parameterized polygons in the layouts have to be partitioned into trapezoids. In this article, a parallel polygon partitioning algorithm is proposed; the algorithm is capable of partitioning parameterized orthogonal polygons into parameterized rectangles as well as partitioning parameterized 45-degree polygons into parameterized trapezoids. Additionally, the algorithm can be used to partition fixed-coordinate polygons. By adopting the dual-scanline technique, which involves using two scanlines to concurrently sweep an input polygon, the parallel partitioning algorithm can process vertices and edges of the input polygon efficiently. The parallel polygon partitioning algorithm has been implemented in C++ with the use of OpenMP. Compared with a sequential partitioning program which uses a single scanline, our parallel partitioning program can achieve 20% to 30% speedup while partitioning large parameterized polygons or partitioning parameterized polygons with complex constraints.
References
[1]
Adler, T. and Scheible, J. 1998. An interactive router for analog IC design. In Proceedings of the Conference on Design, Automation and Test in Europe. 414--420.
[2]
Arai, K. and Kikuchi, H. 2005. Basic cell of gate array semiconductor device, gate array semiconductor device, and layout method for gate array semiconductor device. United States Patent No. US 6842886 B2.
[3]
Baker, R. J. 2010. CMOS Circuit Design, Layout, and Simulation, Wiley-IEEE Press.
[4]
Bell, P. J., Hoivik, N. D., Saravanan, R. A., Ehsan, N., Bright, V. M., and Popovic, Z. 2007. Flip-chip-assembled air-suspended inductors. IEEE Trans. Adv. Packag. 30, 1, 148--154.
[5]
Bentley, J. L. and Ottmann, T. A. 1979. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28, 9, 643--647.
[6]
Berg, M. D., Kreveld, M. V., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications. Springer.
[7]
Blaschke, V. and Victory, J. 2006. A scalable model methodology for octagonal differential and single-ended inductors. In Proceedings of IEEE Custom Integrated Circuits Conference. 717--720.
[8]
Castro-López, R., Guerra, O., Roca, E., and Fernández, F. V. 2008. An integrated layout-synthesis approach for analog ICs. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27, 7, 1179--1189.
[9]
Chapman, B., Jost, G., and van der Pas, R. 2007. Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press.
[10]
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2009. Introduction to Algorithms, Third Edition. MIT Press.
[11]
Feng, W. S., Yang, W. T., and Hsieh, M. Y. 1993. Computer-aided design on the VLSI 45○-mask compaction. In Proceedings of the IEEE Region 10 Conference. 750--753.
[12]
Fortune, S. 1986. A sweepline algorithm for Voronoi diagrams. In Proceedings of the Annual Symposium on Computational Geometry. 313--322.
[13]
Gourley, K. D. and Green, D. M. 1983. A polygon-to-rectangle conversion algorithm. IEEE Comput. Graphics Appl. 3, 1, 31--36.
[14]
Hamachi, G. T. and Ousterhout, J. K. 1984. A switchbox router with obstacle avoidance. In Proceedings of the Design Automation Conference. 173--179.
[15]
Kumar, S., Carothers, J. D., Newbould, R. D., and Krishnan, B. V. 2003. Candidate generation for 45 degree routing for mixed-signal layout. In Proceedings of the IEEE Southwest Symposium on Mixed-Signal Design. 233--236.
[16]
Li, Q. and Kang, S.-M. 2000. Efficient algorithms for polygon to trapezoid decomposition and trapezoid corner stitching. In Proceedings of the Great Lakes Symposium on VLSI. 183--188
[17]
Marple, D., Smulders, M., and Hegen, H. 1990. Tailor: a layout system based on trapezoidal corner stitching. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 9, 1, 66--90.
[18]
McKenney, M. and McGuire, T. 2009. A parallel plane sweep algorithm for multi-core systems. In Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 392--395.
[19]
Mohan, S. S., Hershenson, M. D. M., Boyd, S. P., and Lee, T. H. 1999. Simple accurate expressions for planar spiral inductances. IEEE J. Solid-State Circuits. 1419--1424.
[20]
Nahar, S. and Sahni, S. 1988. Fast algorithm for polygon decomposition. IEEE Trans. CAD 7, 4, 473--483.
[21]
Onodera, H., Kanbara, H., and Tamaru, K. 1990. Operational-amplifier compilation with performance optimization. IEEE J. Solid-State Circuits 25, 2, 466--473.
[22]
Ottmann, T., Widmayer, P., and Wood, D. 1985. A fast algorithm for the Boolean masking problem. Comput. Vision Graphics Image Process. 30, 3, 249--268.
[23]
Ou, H.-C., Chang Chien, H.-C., and Chang, Y.-W. 2012. Non-uniform multilevel analog routing with matching constraints. In Proceedings of the Design Automation Conference. 549--554.
[24]
Ousterhout, J. K. 1984. Corner stitching: a data-structuring technique for VLSI layout tools. IEEE Trans. CAD 3, 1, 87--100.
[25]
Ousterhout, J. K., Hamachi, G. T., Mayo, R. N., Scott, W. S., and Taylor, G. S. 1984. Magic: a VLSI layout system. In Proceedings of the Design Automation Conference. 152--159.
[26]
Scott, W. S. and Ousterhout, J. K. 1984. Plowing: interactive stretching and compaction in Magic. In Proceedings of the Design Automation Conference. 166--172.
[27]
Scott, W. S. and Ousterhout, J. K. 1985. Magic's circuit extractor. In Proceedings of the Design Automation Conference. 286--292.
[28]
Stan, M. R., Hamzaoglu, F., and Garrett, D. 2004. Non-Manhattan maze routing. In Proceedings of the IEEE Symposium on Integrated Circuits and Systems Design. 260--265.
[29]
Taylor, G. S. and John, K. O. 1984. Magic's incremental design-rule checker. In Proceedings of the Design Automation Conference. 160--165.
[30]
Tseng, I.-L., Lee, C.-I., and Chen, H.-W. 2010. Efficient partitioning of parameterized 45-degree polygons with mixed ILP. In Proceedings of the IEEE Region 10 Conference. 1531--1534.
[31]
Tseng, I.-L. and Postula, A. 2006. An efficient algorithm for partitioning parameterized polygons into rectangles. In Proceedings of the Great Lakes Symposium on VLSI. 366--371.
[32]
Tseng, I.-L. and Postula, A. 2008. Partitioning parameterized 45-degree polygons with constraint programming. ACM Trans. Des. Autom. Electron. Syst. 13, 3, 52:1--52:29.
[33]
Wang, Z.-W., Tseng, I.-L., and Postula, A. 2013. Design and representation of parameterized layouts for octagonal spiral inductors. In Proceedings of the IEEE International Symposium on Next-Generation Electronics. 333--336.
Index Terms
- A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygons
Recommendations
An efficient algorithm for partitioning parameterized polygons into rectangles
GLSVLSI '06: Proceedings of the 16th ACM Great Lakes symposium on VLSIIn this paper, we propose an algorithm for partitioning parameterized orthogonal polygons into rectangles. The algorithm is based on the plane-sweep technique and can be used for partitioning polygons which contain holes. The input to the algorithm ...
Partitioning parameterized 45-degree polygons with constraint programming
An algorithm for partitioning parameterized 45-degree polygons into parameterized trapezoids is proposed in this article. The algorithm is based on the plane-sweep technique and can handle polygons with complicated constraints. The input to the ...
On partitioning rectilinear polygons into star-shaped polygons
AbstractWe present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2013 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 25 October 2013
Revised: 01 August 2013
Accepted: 01 June 2013
Received: 01 April 2012
Published in TODAES Volume 18, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 116Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
Cited By
View all- Xing SWang RHuang G(2020)Area Decomposition Algorithm for Large Region Maritime SearchIEEE Access10.1109/ACCESS.2020.30376798(205788-205797)Online publication date: 2020
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in