skip to main content
research-article

Partitioning parameterized 45-degree polygons with constraint programming

Published: 25 July 2008 Publication History

Abstract

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 algorithm consists of the contour of a parameterized polygon to be partitioned and a set of constraints for parameters of the contour. The algorithm uses horizontal cuts only and generates a number of nonoverlapping trapezoids whose union is the original parameterized polygon. Processing of constraints and coordinates that contain first-order multiple-variable polynomials has been made possible by incorporating the JaCoP constraint programming library. The proposed algorithm has been implemented in Java programming language and can be used as the basis to build the trapezoidal corner stitching data structure for parameterized VLSI layout masks.

References

[1]
Agarwal, A., Sampath, H., Yelamanchili, V., and Vemuri, R. 2004. Fast and accurate parasitic capacitance models for layout-aware synthesis of analog circuits. In Proceedings of the ACM/IEEE Design Automation Conference (DAC), 145--150.
[2]
Badaoui, R. F., Sampath, H., Agarwal, A., and Vemuri, R. 2004. A high level language for pre-layout extraction in parasite-aware analog circuit synthesis. In Proceedings of the ACM Great Lakes Symposium on (GLSVLSI), 271--276.
[3]
Beckenbach, E. and Bellman, R. 1961. An Introduction to Inequalities. Random House, New York.
[4]
Berg, M. D., Kreveld, M. V., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications. Springer.
[5]
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms. MIT Press.
[6]
Dessouky, M., Louerat, M.-M., and Porte, J. 2000. Layout-Oriented synthesis of high performance analog circuits. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), 53--57.
[7]
Gajski, D. D. and Lin, Y.-L. S. 1988. Module generation and silicon compilation, In Physical Design Automation of VLSI Systems, B. T. Preas, and M. J. Lorenzetti, Eds. Benjamin/Cummings, Publishing, Chapter 7, 283--345.
[8]
Gourley, K. D. and Green, D. M. 1983. A polygon-to-rectangle conversion algorithm. IEEE Comput. Graph. Appli. 3, 1, 31--36.
[9]
Kuchcinski, K. 2003. Constraints-driven scheduling and resource assignment. ACM Trans. Des. Autom. Electron. Syst. 8, 3, 355--383.
[10]
Kuchcinski, K. and Wolinski, C. 2003. Global approach to assignment and scheduling of complex behaviors based on HCDG and constraint programming. J. Syst. Archi. 49, 489--503.
[11]
Kuhn, J. 1987. Analog module generators for silicon compilation. VLSI Syst. Des. 74--80.
[12]
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 (GLSVLSI), 183--188.
[13]
Lopez, M. A. and Mehta, D. P. 1996. Efficient decomposition of polygons into L-shapes with applications to VLSI layouts. ACM Trans. Des. Autom. Electron. Syst. 1, 3, 371--395.
[14]
Marple, D., Smulders, M., and Hegen, H. 1990. Tailor: A layout system based on trapezoidal corner stitching. IEEE Trans. Comput.-Aided Des. 9, 1, 66--90.
[15]
Marriott, K. and Stuckey, P. J. 1998. Programming with Constraints: An Introduction. The MIT Press.
[16]
Mead, C. and Conway, L. 1980. Introduction to VLSI Systems. Addison-Wesley.
[17]
Mehta, D. P. and Blust, G. 1997. Corner stitching for simple rectilinear shapes. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 16, 2, 186--198.
[18]
Nahar, S. and Sahni, S. 1988. Fast algorithm for polygon decomposition. IEEE Trans. Comput.-Aided Des. 7, 4, 473--483.
[19]
Newton, A. R. 1987. Symbolic layout and procedural design. In Design Systems for VLSI Circuits, G. D. Micheli, et al., eds. Martinus Nijhoff, 65--112.
[20]
Onodera, H., Kanbara, H., and Tamaru, K. 1990. Operational-Amplifier compilation with performance optimization. IEEE J. Solid-State Circuits 25, 2, 466--473.
[21]
Ottmann, T., Widmayer, P., and Wood, D. 1985. A fast algorithm for the Boolean masking problem. Comput. Vision, Graph. Image Proc. 30, 3, 249--268.
[22]
Ousterhout, J. K. 1984. Corner stitching: A data-structuring technique for VLSI layout tools. IEEE Trans. Comput.-Aided Des. 3, 1, 87--100.
[23]
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.
[24]
Rabaey, Y. M., Chandrakasan, A., and Nikolic, B. 2003. Digital Integrated Circuits: A Design Perspective (DAC), Prentice Hall.
[25]
Sampath, H. and Vemuri, R. 2003. MSL: A high-level language for parameterized analog and mixed-signal layout generators. In Proceedings of the IFIP 12th International Conference on Very Large Scale Integration of System-on-Chip, 416--421.
[26]
Scott, W. S. and Ousterhout, J. K. 1985. Magic's circuit extractor. In Proceedings of the Design Automation Conference (DAC), 286--292.
[27]
Tseng, I.-L. and Postula, A. 2004a. GBLD: A formal model for layout description and generation. In Proceedings of Forum on specification and Design Languages (FDL), 660--670.
[28]
Tseng, I.-L. and Postula, A. 2004b. A layout-aware circuit sizing model using parametric analysis. In Proceedings of the 12th Workshop on Synthesis and System Integration of Mixed Information Technologies (SASIMI), 235--240.
[29]
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 (GLSVLSI), 366--371.
[30]
Vancorenland, P., van der Plas, G., Steyaert, M., Gielen, G., and Sansen, W. 2001. A layout-aware synthesis methodology for RF circuits. In Proceedings of the International Conference on Computer Aided Design (ICCAD), 358--362.

Cited By

View all
  • (2013)A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygonsACM Transactions on Design Automation of Electronic Systems10.1145/250501518:4(1-18)Online publication date: 25-Oct-2013
  • (2013)Procedural module generation for parameterized layoutsIEEE 2013 Tencon - Spring10.1109/TENCONSpring.2013.6584505(548-551)Online publication date: Apr-2013
  • (2013)Fast partitioning of parameterized 45-degree polygons into parameterized trapezoids2013 IEEE 11th International New Circuits and Systems Conference (NEWCAS)10.1109/NEWCAS.2013.6573570(1-4)Online publication date: Jun-2013
  • Show More Cited By

Index Terms

  1. Partitioning parameterized 45-degree polygons with constraint programming

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Design Automation of Electronic Systems
    ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 3
    July 2008
    370 pages
    ISSN:1084-4309
    EISSN:1557-7309
    DOI:10.1145/1367045
    Issue’s Table of Contents
    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 ACM 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 July 2008
    Accepted: 01 February 2008
    Revised: 01 November 2007
    Received: 01 June 2007
    Published in TODAES Volume 13, Issue 3

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Parameterized polygons
    2. analog and mixed-signal design
    3. parameterized layouts
    4. polygon decomposition
    5. trapezoidal corner stitching

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2013)A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygonsACM Transactions on Design Automation of Electronic Systems10.1145/250501518:4(1-18)Online publication date: 25-Oct-2013
    • (2013)Procedural module generation for parameterized layoutsIEEE 2013 Tencon - Spring10.1109/TENCONSpring.2013.6584505(548-551)Online publication date: Apr-2013
    • (2013)Fast partitioning of parameterized 45-degree polygons into parameterized trapezoids2013 IEEE 11th International New Circuits and Systems Conference (NEWCAS)10.1109/NEWCAS.2013.6573570(1-4)Online publication date: Jun-2013
    • (2013)Boolean mask operations on parameterized 45-degree polygons2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS)10.1109/MWSCAS.2013.6674683(453-456)Online publication date: Aug-2013
    • (2013)Design and representation of parameterized layouts for octagonal spiral inductors2013 International Symposium on Next-Generation Electronics10.1109/ISNE.2013.6512359(333-336)Online publication date: Feb-2013
    • (2010)Efficient partitioning of parameterized 45-degree polygons with mixed ILPTENCON 2010 - 2010 IEEE Region 10 Conference10.1109/TENCON.2010.5686151(1531-1534)Online publication date: Nov-2010

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media