Investigations on Alliance Rectangle Data Structure for VLSI/CAD Algorithms
A. Greiner, L. Jacomme, F. Pétrot, F. Wajsbürt
IBP-Masi
1994/16:
Rapport de Recherche Masi /
Masi research reports
17 pages - Avril/April 1994 -
Document en anglais.
Titre / Title: Investigations on Alliance Rectangle Data Structure for VLSI/CAD Algorithms
Résumé : Ce rapport décrit une nouvelle structure de données permettant une recherche efficace pour le dessin des masques VLSI rectilinéaires. Cette structure offre d'excellentes performances dès lors qu'il y a suffisement de mémoire interne disponible. Elle peut néanmoins être ajustée afin d'économiser de la mémoire, au détriment de la vitesse de la procédure de recherche. Ces hautes performances sont atteintes par le découpage du dessin en fenêtres carrées, permettant ainsi à tous les rectangles d'une aire donnée d'être accessible en une complexité temporelle de O(1). Le rapport vitesse sur mémoire est dépendant de la surface choisie pour les fenêtres. La structure offre des temps d'exécution presque linéaire en fonction du nombre de rectangles. Elle tient compte des exigences réelles d'implémentation: structuration nécessaire au déroulement d'algorithmes hiérarchiques et prise en compte des niveaux technologiques pour la représentation efficace des masques.
Un ensemble d'outils a éte réalisé sur cette structure: leurs performances sur des circuits réels sont exposés, discutés et comparés aux outils équivalents existants. Les tests ont été effectué sur 22 blocs de taille et densitévariable, representant un total de plus de 6000000 de rectangles. Les temps obtenus sur ces circuits sont excellents comparés aux outils industriels. Environ 60000 lignes de C ont été écrites sur cette structure. Elles sont disponibles sur ftp.
Abstract : A new data structure for efficient search in rectilinear VLSI layouts is described in this report. This structure offers very high performances when memory is available. It can be tuned for preserving memory, at the cost of slowing down the search procedure. The high performances are achieved in partitioning the layout in set of rectangles belonging to square windows, thus making available the rectangles belonging to a given area in O(1) time. The memory versus speed adjustment is done in chosing the window area. This ensures a pseudo-linear run time versus the number of rectangles. This structure takes into account the actual implementation problems: structuring to handle hierarchical algorithms, multiple layers to efficiently represent the layouts.
Several CAD tools have been implemented on this structure: their performances on real VLSI circuits are presented, discussed, and compared to existing tools. The benchmarks involve 22 blocks with various sizes and densities, with a total of over 6,000,000 rectangles. The run times on these VLSI layouts are really good compared to existing industrial tools. Over 60,000 lines of C code have been written using this data structure and the resulting code is available on anonymous ftp
Publications
internes Masi 1994 /
Masi research reports
1994