R*-TREE CONSTRUCTION BASED ON GEOMETRIC DATA FROM GDSII FILE
R*-TREE CONSTRUCTION BASED ON GEOMETRIC DATA FROM GDSII FILE
Abstract
Nowadays, topologies of integrated circuits are becoming more and more complex: the size of elements is decreasing, the number of elements and connections between them is increasing. The number of elements in IC topologies can reach billions, which makes it difficult to analyse them at the design and development stages. Special attention is paid to the problem of performance of IC topology navigation operations. This article presents an algorithm for transforming geometric data from a GDSII file into an R*-tree. This type of tree is well established in indexing multidimensional information such as rectangles, geographic coordinates or polygons. It allows to perform various navigational tasks simply and quickly and to retrieve the necessary information about elements.
1. Введение
При проектировании интегральных схем наиболее популярным форматом является GDSII, разработанный Calma Company (США). В течение многих лет GDSII был единственным в своем роде форматом для хранения и передачи данных по интегральным схемам и их топологиям. Вследствие этого многие производители стали активно использовать его в своих системах. Хотя Calma обновляла формат по мере развития своих систем САПР, они сохранили обратную совместимость, так что ни один файл GDSII не устарел.
Основной недостаток формата GDSII заключается в отсутствии оптимизации для уменьшения размера файла, вследствие чего проекты часто превышают размер в 20 гигабайт. Более подробную информацию о проблеме оптимизации файла, размерах и других недостатках GDSII можно найти в статье .
Серьезные недостатки формата GDSII стали основной причиной возникновения альтернативного формата для хранения топологий ИС – Open Artwork System Interchange Standard (OASIS), который более подробно рассмотрен в статье . Основным преимуществом формата является то, что при использовании OASIS появляется возможность уменьшения размера файлов, вследствие чего время их обработки и загрузки сокращается. Данное преимущество основывается на том, что в OASIS существует множество различных опций для представления одних и тех же данных, однако количество возможных ошибок в файле OASIS резко возрастает по сравнению с GDSII (как минимум в 4 раза).
Некоторые компании начинают переходить на формат OASIS, однако большинство продолжает использовать GDSII. Проблема размера файлов GDSII в таких компаниях обычно решается с помощью увеличения емкости диска и оперативной памяти. Это считается более выгодной мерой по сравнению с заменой квалифицированного потока, основанного на GDSII, на новый, основанный на OASIS.
Файлы GDSII хранят данные в бинарном виде, эти данные содержат информацию о плоских геометрических фигурах (полигонах), различных текстовых метках и других данных касательно топологии интегральных схем в иерархической форме. Эти данные также можно использовать для изменения всей архитектуры интегральной схемы или какой-то ее конкретной части, которая может быть использована для обмена данными между макетами или при конструировании фотошаблонов (фотомасок).
Файлы GDSII представляют из себя набор ячеек, которые содержат различные данные о полигонах. Также из-за того, что данные в GDSII могут быть представлены в иерархической форме, ячейки могут содержать ссылки на другие ячейки. Ячейки в GDSII представляют собой записи STRUCTURE и имеют буквенно-цифровые имена до 32 символов, которые однозначно их определяют.
Файл начинается с библиотеки этих структур, где запись заголовка библиотеки (BGNLIB) определяет начало, а запись конца библиотеки (ENDLIB) определяет конец файла. Между записями начала и конца библиотеки располагается последовательность структур, где каждая структура сама состоит из записи заголовка структуры (BGNSTR), последовательности элементов и записи конца структуры (ENDSTR).
Элементы в GDSII файлах разделяются на семь видов , :
1) граница представляет собой заполненный многоугольник. Начинается с записи BOUNDARY и имеет обязательные атрибуты LAYER, DATATYPE и XY;
2) путь представляет собой незамкнутую фигуру с ненулевой шириной, которая обычно используется для размещения проводов. Этот элемент инициируется записью PATH и имеет обязательные атрибуты LAYER, DATATYPE и XY;
3) ссылка (SREF) на структуру представляет собой иерархический элемент, который вызывает все элементы из структуры, на которую он ссылается, с измененными координатами в зависимости от атрибутов;
4) ссылка на массив структур (AREF) представляет собой иерархический элемент, который вызывает массив структур и все элементы внутри каждой структуры с измененными координатами в зависимости от атрибутов;
5) текст (TEXT) предназначен для документации и имеет обязательные атрибуты LAYER, TEXTTYPE и XY;
6) узел (NODE) определяет электрический путь (сеть) и имеет обязательные атрибуты LAYER, NODETYPE и XY;
7) прямоугольник (BOX) представляет собой прямоугольную геометрию и имеет обязательные атрибуты LAYER, BOXTYPE и XY.
Как упоминалось ранее, данные топологий ИС содержат ячейки, сигналы, порты и другие элементы схемы в виде геометрических объектов, чаще всего полигонов. Увеличение сложности ИС увеличивает объем информации о топологии, из-за чего точность и скорость навигации для поиска целевого объекта становится серьезной проблемой.
Таким образом, навигация по макету проявляется как проблема пространственного поиска, которую можно решить с помощью доступных методов геометрических запросов. В вычислительной геометрии существует множество алгоритмов, которые имеют большое значение, особенно в автоматизированном проектировании. Так, в работе
задача эффективного вычисления пересечения нескольких наложенных друг на друга фигур решается с помощью двух алгоритмов плоской прогонки. Многие другие подходы предлагают методы доступа на основе индексов для быстрого извлечения элементов данных в соответствии с их пространственным расположением.Наиболее популярным методом доступа является метод R-дерева Гутмана , основанный на оптимизации площади объемлющих прямоугольников в каждом внутреннем узле. Несколько других вариантов классического R-дерева также предложены для оптимизации алгоритмов R-дерева Гутмана. Упакованные R-деревья , , R*-дерево , R-дерево Грина относятся к числу этих вариантов, предлагающих различные подходы к оптимизации загрузки дерева. Среди них наиболее примечательным является R*-дерево, в котором введены новые параметры настройки для устранения проблем, существующих в классических R-деревьях.
2. Алгоритм построения R*-дерева на основе геометрических данных из GDSII файла
Благодаря тому, что данные GDSII имеют иерархическую структуру, можно описывать миллионы или миллиарды полигонов в ИС. Иерархия очень важна, потому что в дизайне ИС, как правило, повторно используются одни и те же геометрические фигуры. Благодаря этому можно создавать компактные файлы для очень больших конструкций .
Однако не существует эмпирических правил структурных организаций топологий интегральных схем. В связи с отсутствием точных правил проектирования, для извлечения иерархической информации из файла GDSII и построения сбалансированного дерева необходимо привести иерархическую топологию GDSII файлов в плоский вид.
3. Вычисление новых координат геометрических элементов GDSII
В формате GDSII иерархию определяют два элемента: SREF (элемент ссылки на структуру) для ссылки или размещения структуры и AREF (элемент ссылки на массив структуры) для ссылки на массив структур. Обязательными атрибутами данных элементов являются: SNAME, который хранит информацию структуры, на которую ссылается данный элемент, и XY, который хранит координаты в плоскости для смещения структуры. Для AREF также обязателен элемент COLROW, который хранит информацию про сетку ссылок на структуру. Необязательными атрибутами данных элементов являются STRANS, MAG, ANGLE, которые определяют следующие преобразования:
- Отражение: если флаг отражения установлен в атрибуте STRANS, структура отражается относительно оси x. Отражение осуществляется перед угловым поворотом. Отражение может быть достигнуто путем умножения матрицы отражения в (1),
где r равно −1 в случае отражения. Значение r по умолчанию равно 1.
- Увеличение: если установлен атрибут MAG, структура увеличивается в соответствии с коэффициентом увеличения (значением данного атрибута). Это достигается умножением координат на матрицу увеличения, заданную в (2),
где К — коэффициент увеличения. Значение К по умолчанию равно 1.
- Вращение: если установлен атрибут ANGLE, структура поворачивается в соответствии с углом поворота (значением данного атрибута). Это достигается предварительным умножением точек на матрицу вращения, заданную в (3),
где, α угол поворота. Его значение по умолчанию равно 0.
- Перемещение: Это самый важный шаг из всех наборов преобразований, именно поэтому атрибут XY является обязательным. Здесь каждая из точек перемещается с использованием значения атрибута XY. Перемещение может быть достигнуто добавлением вектором перемещения, указанного в (4),
где, tx,y является перемещением в плоскости. Значение по умолчанию — 0.
Все преобразования выполняются в определенной последовательности: отражение, увеличение, вращение и перемещение. Матрица преобразований, которая объединяет все модификации изменения местоположения точек на плоскости представлена в (5),
Итоговые координаты точек на плоскости можно найти по (6),
Применяя к координатам выражение (6), можно вычислить новые координаты геометрических объектов, которые были вызваны элементом SREF. Однако для вычисления новых координат геометрических элементов, которые были вызваны элементом AREF, необходимо помимо умножения точек на (6) добавлять трансляционный вектор решетки AREF согласно (7). Вектор смещения рассчитывается с использованием вектора строки и столбца, которые вычисляются с использованием трех опорных точек и количества строк и столбцов, информация которых храниться в атрибуте COLROW элемента AREF в файле GDSII.
Благодаря (6) и (7) можно рассчитать новые координаты геометрических объектов, вызванных с помощью SREF и AREF соответственно.
4. Организация R*-дерева с геометрическими элементами GSDII
R-дерево состоит из узлов, которые классифицируются как листовые и внутренние узлы. Конечные узлы соответствуют узлам нижнего уровня, которые содержат объекты пространственных данных. Эти объекты представляют собой геометрические объекты в многомерном пространстве, к которым будет применяться запрос. Каждый узел определен минимальным ограничивающим прямоугольником (MBR), который является минимальным охватывающим прямоугольником для пространственного объекта со сторонами, параллельными осям координат. MBR учитывается как в листовых узлах, так и во внутренних.
Минимальный ограничивающий прямоугольник в листовых узлах заключает в себе геометрические объекты, а во внутренних узлах охватывает все MBR листов, на которые он ссылается. Структура дерева разработана с целю того, чтобы для пространственного поиска требовалось минимального количества посещений узлов.
В геометрических элементах GDSII необходимо помимо базовой информации, такой как номер слоя, координаты объекта, дополнительные атрибуты, хранить данные о вложенности объекта в иерархическую структуру в виде списка. Данная информация необходима для корректного определения данных в GDSII файле, так как в нем не используются уникальные идентификаторы элементов.
Если резюмировать все вышеописанные условия, то каждый листовой узел дерева будет состоять из элементов, имеющих вид (ObjectGDSII, MBR), где ObjectGDSII - это ссылка/указатель на геометрический элемент GDSII, который дополнительно хранит и данные о вложенности. Внутренние узлы дерева содержат элементы, имеющие похожую структуру: (MBR, ChildPointer), где ChildPointer ссылка/указатель на элемент последующего нижнего уровня. Минимальный ограничивающий прямоугольник внутреннего узла включает все MBR нижнего уровня, на который он указывает.
Блок-схема алгоритма построения R*-древа по данным GDSII файла представлена на рисунке 1.
Рисунок 1 - Алгоритм построения R*-древа по данным GDSII файла
Рисунок 2 - Пример топологии ИС с MBR
Рисунок 3 - Структура R*-древа построенная по топологии ИС на рисунке 2
5. Заключение
В связи с усложнением топологий интегральных схем в данной статье был предложен способ преобразования информации из файлов формата GDSII в структуру R*-дерева. Данная древовидная структура является более усовершенствованной, чем стандартное R-дерево. R*-дерево вводит новые концепции, основанные на уменьшении площади, отступов и перекрытий минимальных ограничивающих прямоугольников. Сложность поиска элементов в заданной траектории в соответствии со структурой R*-дерева составляет O(log n) в среднем и O(n) в худшем случае. Однако для практических целей производительность все еще является недостаточной, и здесь открыт простор для дальнейших исследований. Одним из возможных путей исследования является организация фильтра избыточных данных и извлечение только тех элементов, которые содержат ценную для данного запроса информацию.