Title :
Space-efficient extraction algorithms
Author :
Van Der Meijs, N.P. ; van Genderen, A.J.
Author_Institution :
Dept. of Electr. Eng., Delft Univ. of Technol., Netherlands
Abstract :
A description is given of how the authors limited the space complexity of a layout to circuit extractor by: a combination of the scanline technique with the corner stitching technique; a region-based extraction algorithm; a judicious choice of netlist format; and a union-find data structure also supporting deletions of elements. The efficiency of the new algorithms and the resulting extractor is confirmed by experimental data. These results are important, since in practice the size of the largest design that can be handled is often hard-limited by available memory
Keywords :
VLSI; circuit layout CAD; computational complexity; computational geometry; data structures; circuit extractor; corner stitching technique; experimental data; netlist format; region-based extraction algorithm; scanline technique; space complexity; union-find data structure; Algorithm design and analysis; Circuits; Data mining; Data structures; Degradation; Environmental economics; Space technology; Tiles; Very large scale integration; Workstations;
Conference_Titel :
Design Automation, 1992. Proceedings., [3rd] European Conference on
Conference_Location :
Brussels
Print_ISBN :
0-8186-2645-3
DOI :
10.1109/EDAC.1992.205990
