CAD oriented database for integrated circuit layouts

Modern integrated circuit layouts are so complex that databases often have to deal with a million or more geometric objects. For circuit and layout designers to be able to cope with such complex circuits, we (tool designers) must provide more and more support in such areas as design rule checking, circuit extraction, compaction, and routing. To support these tools the database must provide fast geometric operations for region queries, neighbor finding, and location of empty space. Furthermore, in order to build practical interactive systems the database must also permit fast incremental modifications. This thesis describes the design of a database that satisfies the above requirements. The database, based on a data structure called corner stitching, consists of all data structure definitions and operations, the rule based system, hierarchical structures, database I/O, and interface for the CAD tool designer. The implementation techniques for a layout editor are also described. The most important feature of the database is that the complexity of key operations for neighbor finding, region queries, and location of empty space depend on local factors and are independent of overall layout size. The above mentioned features should make it possible to design tools that operate incrementally.