Title :
Implementation of an efficient algorithm for VLSI design rule checking on a 2-D mesh of transputers
Author :
Caviglia, Daniele D. ; Paganini, Maurizio ; Chirico, Marco ; Curatelli, Francesco ; Barzaghi, Marco ; Bisio, Giacomo M.
Author_Institution :
DIBE, Genoa Univ., Italy
Abstract :
A design rule checking program for VLSI circuit layouts with Manhattan geometries is presented. The layout model is described along with the way the authors implemented the check through few and simple primitives for describing parameteric rules. A single main function for the geometrical test is outlined and how the authors succeeded in limiting the checking time through an algorithm characterized by a linear computational complexity is given. How it was mapped on a mesh of transputers is also discussed
Keywords :
VLSI; circuit layout CAD; computational complexity; multiprocessor interconnection networks; 2-D mesh; Manhattan geometries; VLSI circuit layouts; checking time; design rule checking program; linear computational complexity; parameteric rules; transputers; Algorithm design and analysis; Circuit testing; Computational complexity; Concurrent computing; Shape; Solid modeling; Very large scale integration;
Conference_Titel :
CompEuro '91. Advanced Computer Technology, Reliable Systems and Applications. 5th Annual European Computer Conference. Proceedings.
Conference_Location :
Bologna
Print_ISBN :
0-8186-2141-9
DOI :
10.1109/CMPEUR.1991.257429