BENGALURU, India The time-consuming process of recompiling designs from scratch after every update in traditional CAD design is a function not only of the size of the update, but also of the new layout size. The updates may be local, affecting only small parts of the layout, but the entire layout must be recompiled, and incremental algorithms are needed to cut design cycle time. Now, a researcher here has outlined a method to ease the process, especially when larger VLSI layout sizes do not fit into the main memory.
The algorithms that search for parts of the layout affected by the update and that give the result of the updates are hampered when the layout is so large that it cannot fit into the available main memory. The main performance bottleneck here is the communication between fast internal memory and slow external memory. Hence the need for algorithms and data structures that can tap external memory management to reduce external memory access and, therefore, the I/Os between main and external memory.
To address the problem, Akash Agrawal of the Algorithms and Computation Theory Laboratory at the International Institute of Information Technology, Hyderabad, champions an I/O-efficient and output-sensitive external-memory algorithm for incremental connectivity extraction. The algorithm is based on a recursive tiling approach that Agrawal claims enables an easy-to-implement data structure for the aggregation of parts of the layout for fast search and updates.
"Traditionally, algorithms and data structures are designed assuming that there is a large amount of memory available, which requires constant time per access to any memory location. But this assumption may not be true in practice," Agrawal notes in a paper describing his approach. "While the memory hierarchy of a computer system can be divided into CPU registers, several levels of cache, RAM (main memory) and hard disk (external or secondary memory), there are many applications, including those of VLSI layout editing, that require such a large amount of data to be processed that it cannot fit into main memory.
"For processing data sets that cannot be fit into main memory, the bottleneck is the communication between the internal memory (RAM) and the external memory (disk), instead of the internal computation time, as accessing the data from secondary memory is a million times slower than that from main memory. To process such large amounts of data, we need algorithms and data structures that can reduce the amount of data accesses from the external memory and, hence, are I/O-efficient."
Main-memory size continues to rise, but at a far lower rate than the size and complexity of VLSI devices. Thus VLSI tools must consider external-memory management. "In the incremental setting, we have to search and update the parts of the layout [affected by] the incremental changes; but if the size of layout is so large that it cannot fit entirely into main memory, we have to search the secondary memory for the portions of the layout that have to be modified, and load those portions into main memory from secondary memory. So we need an external memory algorithm for incremental changes for large layouts," Agrawal argues in his paper.
"The problem of incremental connectivity extraction is to report on the changes in connectivity information due to incremental updates in the layout," he adds. "An incremental update can be either an insertion or a deletion of a polygon. The resultant change can be an instance of a short-circuit or an open circuit in the layout. More formally, the online connectivity extraction can be defined as follows: Preprocess the given layout such that on insertion or deletion of a polygon in the layout, the change in connectivity can be reported efficiently. A dynamic or incremental algorithm, which requires updating the connectivity in the presence of insertion and deletion, is very useful for layout editors.
"A net-list is associated with each design, and each net can be thought of as a signal and is associated with a unique net ID. Assuming that each polygon is attached with the net ID of the net to which it belongs, the notion of short-circuits and open circuits in the layout can be defined.
"If two polygons originally on different nets belong to the same connected component, the nets are electrically connectedan instance of a short-circuitand the two nets are said to be shorted. If two polygons originally on the same net belong to different connected components, it shows a break in electrical connectivity of that net and is an instance of an open circuit."
The electrical connection in the layout is made using the metal and via (or contact) layers. The polygons of the two metal layers are connected through a polygon via layer between the two metal layers. While Agrawal's paper considers only two metal layers and one via layer in between them, the same approach can be extended if there are more metal and via layers.
Agrawal uses a generalization of the recursive tiling method of partitioning that he says is easy to implement and update. It also provides for an efficient mechanism for extending the main-memory application to external memory, as any existing main memory can be used to process the tiles.
The method was implemented and tested against main memory on a line-connectivity-extraction algorithm. The implementation used the STXXL package, which provides an I/O-efficient extension to standard C++STL vectors, along with other data structures.
Binary search was used in the main-memory algorithm to implement incremental changes to find portions of the layout to be updated. The experiments were conducted on a 3-GHz Pentium IV processor with 512 Mbytes of RAM.