Incremental analysis of large VLSI Layouts

The verification of VLSI layouts is an important and expensive step in physical design process and has significant contribution in overall design cycle time. Design rule checking, connectivity extraction and device extraction are important steps in layout analysis. Efficient incremental algorithms for these steps are crucial for fast development as well as small time-to-market of the design. If the size of layout is so large that it cannot fit entirely into available main memory, the main performance bottleneck is communication between internal memory and the external memory due to the slow access speed of external memory.In this paper, incremental solutions for problems of layout analysis are presented considering the external memory management. The main component of these algorithms is the proposed “recursive tiling” approach, which provides an easy to implement data structure for the aggregation of parts of layout for fast search and updates. Experimental results show that the recursive tiling approach proposed in this paper has reduced the time required for incremental processing on the workstations with limited amount of physical memory.