автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС

На правах рукописи

Сотников Михаил Анатольевич

Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС

Специальность: 05.13.12 - Системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2004

Работа выполнена в ЗАО "Моторола ЗАО'

Научный руководитель: доктор технических наук А.М Марченко

Официальные оппоненты: доктор технических наук, профессор,

Лауреат Государственной Премии СССР В.М. Щемелинин

кандидат технических наук СВ. Гаврил ов

Ведущая организация: ОАО "Институт электронных

управляющих машин"

Защита состоится 18 марта 2004 г. в 14 часов на заседании Диссертационного совета Д 002.078.01 в Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН) по адресу: 124681, г. Москва, ул.Советская, Д.З.

С диссертацией можно ознакомиться в библиотеке ИППМ РАН.

Автореферат разослан 17 февраля 2004 г.

Ученый секретарь диссертационного совета Д 002.078.01, Кандидат технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

В настоящее время современные субмикронные технологии достигли такой степени интеграции, что минимальный размер топологического объекта меньше длины волны, используемой при фотолитографии. Например, длина затвора транзистора равна 45 нм, а длина волны - 193 нм. Как следствие этого, к известным технологическим ограничениям на минимальное расстояние и размер объектов топологии добавились новые, более сложные правила. Данные правила зависят от конфигурации, геометрических размеров и взаимного расположения объектов топологии. Кроме того, для создания объектов меньше чем длина волны применяются специальные приемы, позволяющие улучшить разрешающую способность технологического оборудования. Одним из таких приемов является засветка противоположными фазами с разных сторон проводника. Это порождает ряд правил, гарантирующих отсутствие конфликтов противоположных фаз. Например, необходимо выдерживать специальное минимальное расстояние между проводами, если:

• они перпендикулярны и их ширина меньше длины волны;

• между ними расположен третий провод и их ширина меньше длины волны.

Технологические ограничения такого вида делают процесс разработки современных топологий более трудоемким, чем раньше.

Уменьшение размеров привело к тому, что проводники вносят существенный вклад в задержку распространения сигнала даже в топологии стандартной ячейки. Следовательно, необходимо учитывать данные схемотехнические проблемы при разработке топологии ячеек. Особенно сильно на задержку распространения сигнала в стандартной ячейке влияет расстояние между

диффузионная область имеет значительное сопротивление и емкость по сравнению с металлами.

Наряду с перечисленными ограничениями происходит быстрая смена технологий. Каждый год появляется новый технологический процесс, который в первую очередь требует разработки новой библиотеки стандартных ячеек. Это приводит к тому, что разработка библиотеки производится в сжатые сроки и часто параллельно с доводкой технологии.

Таким образом, сложные технологические ограничения и сжатые сроки проектирования делают невозможным разработку топологии стандартных ячеек без использования Систем Автоматизированного Проектирования (САПР). Одним из важных этапов автоматического синтеза топологии является сжатие. На этом этапе производится уменьшение площади топологии одновременно с контролем и выполнением всех ограничений, накладываемых технологическим процессом производства.

Параллельная разработка библиотеки и технологий требует коррекции уже разработанных ячеек после каждого изменения технологических норм. Задача коррекции технологических правил является родственной задаче сжатия и называется миграцией топологии. Однако, при миграции размер топологии может увеличиться для выполнения требований новых ограничений.

Известные методы сжатия не учитывают перечисленные выше технологические и схемотехнические ограничения. Следовательно, разработка новых эффективных методов сжатия и миграции топологии является актуальной.

Цель диссертационной работы состоит в разработке эффективных методов и алгоритмов сжатия топологии стандартных ячеек СБИС с учетом требований современных субмикронных технологий. Для

достижения данной цели в диссертационной работе решаются следующие задачи:

разработка эффективного алгоритма сжатия топологии стандартных ячеек субмикронных СБИС;

разработка алгоритмов для улучшения быстродействия, трассируемости и выхода годных на этапе сжатия; разработка модели топологии, позволяющей проводить эффективное сжатие и учитывать современные технологические ограничения;

разработка иерархических методов сжатия больших ячеек; исследование эффективности предложенного алгоритма, сравнение качества сжатия с существующими методами и выбор оптимальных параметров настройки алгоритмов.

Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем:

предложен алгоритм полуторамерного сжатия топологии стандартных ячеек субмикронных СБИС, который, в отличие от известных, учитывает современные технологические ограничения, позволяющие создавать объекты меньше длины волны, используемой при фотолитографии;

предложен алгоритм автоматического удаления положительных циклов в графе ограничений, который, в отличие от известных, использует полуторамерные реорганизации топологии. Это позволяет сжимать некорректную топологию с одновременным устранением технологических нарушений. Данный алгоритм используется как при сжатии, так и в различных методах оптимизации топологии;

разработан оригинальный метод поиска оптимального сечения

критического подграфа, который отличается от известных

5

одновременным применением различных способов минимизации длины критического пути (разбиение вершины и удаление ребра). Данный подход позволяет получать более компактную топологию; предложен алгоритм минимизации диффузионных областей с помощью полуторамерных реорганизаций топологии, который позволяет минимизировать задержки сигнала.

Реализация

На базе предложенных алгоритмов разработан комплекс программ сжатия и миграции топологии. Программа сжатия топологии стандартных ячеек используется в системе автоматического синтеза топологии стандартных ячеек. Программа миграции топологии успешно используется для коррекции топологии при незначительном изменении технологических ограничений и при переводе топологии на новые технологические процессы. Разработанные программы внедрены в ЗАО "Моторола ЗАО".

Практическая значимость работы

Алгоритмы и подходы, предложенные в данной работе, реализованы в виде программы сжатия топологии, которая используются при автоматическом синтезе топологии стандартных ячеек СБИС. Данные алгоритмы также используются при миграции существующих топологий на новые технологические процессы. Модель топологии, используемая для сжатия, позволяет выдерживать основные современные технологические ограничения. С использованием данных программ были проведены синтез и миграция нескольких библиотек стандартных ячеек для современных технологических процессов. Предложенный метод линейной декомпозиции задачи сжатия, позволяет применять данные алгоритмы для топологии больших размеров.

Апробация основных теоретических и практических результатов работы проводилась на конференциях:

• Международная научно-техническая конференция "Интеллектуальные САПР" (г. Геленджик, 1999-2003 г., 5 докладов)

• Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика-2003", (МИЭТ, 2003 г., 1 доклад)

Публикации

Результаты диссертации отражены в пяти статьях [2,3,6,7,12], шести тезисах научных докладов на конференциях [1,4,8-11] и одном патенте [5].

Структура и объем диссертационной работы. Диссертационная работа состоит, из введения, пяти глав, заключения и списка литературы. Работа содержит 119 страниц и 2 акта о внедрении.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулирована цель работы, показана научная новизна и практическая значимость полученных результатов, раскрыта структура диссертации.

В первой главе представлена постановка задачи сжатия топологии. Описаны основные типы технологических правил и отражены особенности современных технологий. Представлена модель топологии, используемая при сжатии в известных алгоритмах. Показаны основные недостатки данной модели, ограничивающие поддерживаемый при сжатии набор технологических ограничений.

Проведена классификация алгоритмов сжатия топологии и описаны основные методы для каждого класса. Перечислены преимущества и недостатки рассмотренных методов. Выделен класс методов, использующих граф ограничений. Данный класс является наиболее

перспективным, так как позволяет легко расширять множество выполняемых при сжатии технологических правил. Для поддержки нового технологического правила необходимо только реализовать способ его отражения в граф ограничений, т.е. построения эквивалентной системы неравенств. Далее задача сжатия трансформируется в задачу поиска длиннейших путей в графе ограничений и не зависит от конкретных технологических правил.

Выделен класс эвристических алгоритмов, использующих два графа ограничений. Для их обозначения используется термин "полуторамерное" сжатие. В данных алгоритмах сжатие происходит в одном (основном) направлении. Однако, в процессе сжатия возможно изменение координат объектов в ортогональном направлении для уменьшения размера топологии в основном. Такие локальные перемещения называются реорганизацией. Описан базовый алгоритм для проведения допустимых, т.е. не приводящих к нарушению технологических правил, реорганизаций топологии, которые уменьшают критический путь в графе ограничений для основного направления. Выявлены слабые места данного алгоритма, требующие улучшения.

Сформулированы проблемы, которые необходимо решать при сжатии топологии стандартной ячейки. К данным проблемам относятся:

• выполнение требований современных субмикронных технологий;

• увеличение плотности сжатой топологии;

• автоматическое разрешение конфликтных ситуаций в топологии;

• увеличение быстродействия, трассируемости и выхода годных;

• сжатие сравнительно больших фрагментов топологии.

Вторая глава посвящена разработке модели топологии, которая позволяет поддерживать требования современных субмикронных технологий при полуторамерном сжатии.

В известных алгоритмах одномерного сжатия используется контурное представление топологии, которое дает возможность поддерживать современные технологические правила. Однако, одномерное сжатие не позволяет достичь плотности топологии, необходимой для стандартных ячеек. Для улучшения плотности применяются алгоритмы полуторамерного сжатия. В известных алгоритмах полуторамерного сжатия используется, модель прямоугольников, которая отличается простотой, но не позволяет поддерживать все виды современных технологических ограничений. В данной главе предложены новые подходы, позволившие применять контурную модель при полуторамерном сжатии.

Предлагаемая модель топологии представлена: множеством фигур, множеством слоев и гиперграфом связности. Фигуры можно разделить на два класса: внутренние и внешние. В общем случае внешняя фигура представлена многосвязным контуром. Контуры, принадлежащие одному слою, не могут пересекаться. Данное ограничение позволяет избежать основного недостатка модели прямоугольников - изменения внешних границ в процессе сжатия. Внутренние фигуры представлены прямоугольниками и описывают составные части приборов: транзисторов, межслойных переходов, диодов и т.д. Каждая такая фигура расположена внутри некоторого внешнего контура и не может его покинуть в процессе сжатия. Геометрия фигуры описана множеством взаимно ортогональных сторон, которые характеризуются типом (левая, правая, верхняя или нижняя) и координатой. Кроме того, каждая фигура принадлежит некоторому слою.

Гиперграф связности описывает взаимосвязь объектов топологии. Каждая вершина соответствует объекту топологии, а ребро описывает отношения между множеством объектов топологии. Ребро представляет прибор (межслойный переход, диод, транзистор и т.д.), пару связности,

9

соответствие между внешней и внутренней фигурами, цепь или дополнительное внешнее ограничение.

Обычно граф ограничений для задачи сжатия - это направленный, взвешенный граф. Каждая вершина представляет одну сторону контура и характеризуется координатой, которая равна координате стороны. Также граф содержит две дополнительные вершины Source и Sink. Source - это вершина, которая не имеет входящих ребер, a Sink - выходящих. Вершины Source и Sink представляют воображаемые границы топологии. Для них не существует сторон контура. Ребро графа описывает множество ограничений между соответствующими сторонами контуров. Вес ребра равен длине максимального ограничения.

Кроме ограничений, определяемых технологией, топология должна удовлетворять ограничениям, которые являются внешними. Данные ограничения необходимы для обеспечения стыковки ячеек или обеспечения корректной работы схемы (например, возникающие из ограничений на задержку сигнала).

Множество вершин и ребер основного графа, принадлежащих длиннейшему пути между вершинами Source и Sink, называется критическим подграфом, а его ребра и вершины — критическими. Длина критического пути определяет размер топологии в соответствующем направлении и может быть уменьшена с помощью следующих операций:

• разбиения критической вершины на несколько новых вершин;

• удаления критического ребра из графа ограничений.

Для использования контурной модели в алгоритме полуторамерного сжатия разработаны методы преобразования (реорганизации) контурной топологии, приводящие к разбиению вершины графа или удалению его ребра.

Разбиение критической вершины приводит к разрыву критических путей, проходящих через данную вершину. Преобразования топологии, которые приводят к разбиению вершины графа ограничений, следующие:

10

• разрыв связи между объектами топологии (удаление пары связности);

• оптимизация формы контура, которую можно представить в виде разделения некоторой стороны контура на две или более частей.

Удаление критического ребра приводит к разрыву критических путей, проходящих через данное ребро. Если ребро невозможно удалить, то уменьшение его длины, также позволяет сократить длину критического пути. Алгоритм удаления (уменьшения длины) критического ребра состоит из трех шагов:

1. удаления критического ребра из основного графа ограничений;

2. добавления новых ребер в основной или ортогональный граф ограничений;

3. удаления сторон контура (если это необходимо).

Удаление некоторого ребра в графе является следствием реорганизации контуров, между сторонами которых было построено ребро. Для удаления критических ребер предложены следующие способы реорганизации контуров:

• сдвиг стороны контура;

• удаление стороны контура;

• изменение типа стороны;

• слияние двух контуров одной и той же цепи;

• изменение формы контура при сохранении его площади.

Таким образом, разработанные способы реорганизации контурной модели топологии позволяют выполнять ее полуторамерное сжатие с учетом требований современных субмикронных технологий.

Третья глава посвящена разработке метода полуторамерного сжатия топологии стандартных ячеек.

Так как при полуторамерном сжатии минимизируется размер

топологии только в основном направлении, то необходимо

11

последовательно применять данный алгоритм для вертикального (У) и горизонтального (X) направлений. Указанный порядок применения определяется тем, что топология стандартной ячейки должна иметь фиксированную высоту, поэтому У сжатие выполняется первым. Если при этом не удалось достичь заданной высоты, то такая топология считается некорректной и дальнейшее сжатие не выполняется.

Основой полуторамерного сжатия является одномерное сжатие, где минимизируется размер топологии в основном направлении. Если целевой размер достигнут, то сжатие останавливается. Целевой размер - это высота стандартной ячейки или ее оценка. Далее выполняется полуторамерная минимизация длины критического пути. Если критический путь минимизирован, то возвращаемся к одномерному сжатию.

Для одномерного сжатия обычно используется поиск длиннейших путей в графе ограничений. На данном этапе вычисляются минимально возможные координаты вершин, которые определяют координаты объектов топологии. Однако, в топологии стандартной ячейки существуют объекты (внешние порты и граница ячейки), координаты которых должны быть кратны некоторой сетке. Для решения данной проблемы разработан алгоритм поиска длиннейших путей, позволяющий вычислять координаты таких объектов с учетом сетки.

Ограничения на задержку сигнала и современные технологические правила порождают ограничения связности. Данные ограничения приводят к возникновению циклов в графе ограничений. Если длина цикла больше нуля, то такой цикл называется положительным. Если в графе существует положительный цикл, то невозможно вычислить длины путей, проходящих через данный цикл. Следовательно, такая топология не может быть сжата. Для решения данной проблемы традиционно используются следующие подходы:

1. удаляется ограничение связности, породившее цикл;

2. объекты, образующие цикл, "замораживаются", т.е. не сдвигаются относительно друг друга в процессе сжатия;

3. делается попытка разбить одну из вершин, входящую в цикл. Первый и второй подходы приводят к нарушению технологических ограничений или ограничений на задержку, что требует доработки топологии человеком. Последний подход позволяет решить проблему, но не всегда применим, так как часто нет возможности разбить вершины цикла.

Для решения данной проблемы предложен новый подход, позволяющий автоматически разрешать данные конфликты. Предлагается разорвать положительный цикл в одной из вершин, создав дополнительную вершину, и рассматривать этот цикл как путь. Затем к полученному пути применяются разработанные методы полуторамерной минимизации длины пути. Уменьшение длины пути на величину цикла или большую приводит к удалению положительного цикла. В отличие от известных методов данный подход позволяет как разбивать вершины цикла, так и удалять ребра. Это дает возможность сжимать топологию, которая не может быть сжата существующими алгоритмами.

В известных алгоритмах полуторамерного сжатия уменьшение длины критического пути (размера топологии), производится за счет удаления ребер или разбиения вершин. Данные преобразования не могут выполняться одновременно, что существенно ухудшает плотность топологии. Для решения данной проблемы предложен новый алгоритм поиска сечения критического подграфа. Для поиска множества ребер и вершин, которые необходимо удалить для минимизации длины критического пути, строится специальный граф критических путей, который можно представить в виде:

CPG = (I_N0DE\J0_N0DE,S\JJ) (1)

где I_NODE=fi_nodeJ, 0_NODE=(o_nodeJ - множество вершин графа; S, J - множества ребер типа "Shearing" и "Jogging" соответственно. Данный граф строится на основании критического подграфа графа ограничений. Каждому ребру критического подграфа ставятся в соответствие две вершины(1_по<1е и o_node) и одно ребро (типа "Shearing") в новом графе. Критической вершине соответствует множество ребер типа "Jogging" между каждой парой соответствующих i_node u o_node. После построения графа критических путей вычисляются веса его ребер, необходимые для поиска оптимального сечения. Присутствие в сечение ребра типа "Shearing" означает удаление критического ребра из графа ограничений, а ребра типа "Jogging" -разбиение соответствующей вершины. Таким образом, представление критических вершин в виде множества ребер позволяет находить сечение критического подграфа, состоящее из ребер и вершин одновременно.

При использовании итерационных алгоритмов хороший критерий остановки позволяет существенно ускорить сходимость и избежать зацикливания. Для сжатия топологии стандартных ячеек предлагаются следующие критерии: целевой размер, плотность и "память" объектов топологии.

Целевой размер является нижней оценкой возможного размера топологии в направлении сжатия, которую предложено вычислять, исходя из следующих характеристик топологии:

• Количество входных и выходных портов.

• Минимально возможная длина цепочки N или Р транзисторов.

Если плотность топологии больше некоторой предельной величины,

то сжатие завершается. Предельная плотность определяется экспериментальным путем и зависит от технологических ограничений и

шаблона (ограничений пользователя) ячейки.

14

В работе вводится понятие "памяти" объекта топологии. Это целое число, определяющее количество итераций без улучшения целевой функции, в которых может участвовать объект. Если в процессе минимизации критического пути объект участвует в трансформациях топологии, то значение его память уменьшается на единицу после каждой трансформации. За счет этого значимость реорганизации объекта ослабевает по мере уменьшения значения памяти. Объект исключается из рассмотрения, если его памяти равна нулю. При каждом уменьшении размера топологии память объектов восстанавливается. Такой подход позволяет избежать зацикливания.

Известные алгоритмы полуторамерного сжатия являются итерационными и выполняют итерации до тех пор, пока размер топологии уменьшается. Одним из недостатков такого подхода является попадание в. локальные минимумы. Для решения данной проблемы предложены специальные эвристические методы, которые позволяют выходить из локальных минимумов с временным увеличением размера топологии или нарушением некоторых технологических правил. Для этого предлагается несколько способов модификации топологии:

• Выпрямление меандров: Меандр, принадлежащий критическому пути, значительно увеличивают его длину. Для его удаления из критического пути в топологию добавляются ограничения, которые при сжатии будут выпрямлять меандр и выталкивать посторонние объекты за его пределы.

• Локальная перетрассировка: В качестве локальной перетрассировки предлагается упрощать сложную форму топологических объектов, изменять их порядок или переносить в другой слой.

• Удаление критических правил: Некоторые технологические правила имеют большую (в несколько раз, чем остальные) величину.

15

Удаление таких правил из критического пути производится путем полуторамерного сдвига в ортогональном направлении объектов топологии, между которыми применяется данное правило. Если при этом увеличивается размер топологии, то при последующем сжатии делается попытка восстановить его за счет других ресурсов.

Таким образом, предложенные методы выхода из локального минимума позволяют получать более компактную топологию, по сравнению с известными подходами.

Как уже отмечалось ранее, при сжатии топологий необходимо учитывать ограничения на задержку распространения сигнала. Если, минимизация задержек более приоритетна, чем уменьшение размера топологии, то необходимо проводить сжатие с учетом данных ограничений. В противном случае, минимизацию задержек можно выполнять после сжатия, но при этом необходимо сохранять полученный размер топологии. Существенное влияние на задержку распространения сигнала при современных субмикронных технологиях оказывает расстояние между затворами транзисторов, так как диффузионная область имеет значительное сопротивление и емкость по сравнению с металлами. Для уменьшения расстояния между транзисторами предлагается алгоритм минимизации попарного расстояния между объектами топологии. Выбираются пары соседних транзисторов, которые расположены на большом расстоянии. Затем между каждой парой затворов создается ограничение связности для минимизации расстояния между ними. Создание таких ограничений приводит к положительным циклам, т. к. вся минимизация диффузионной области в пределах допустимой подвижности была выполнена на этапе минимизации длин проводников. Для удаления таких циклов необходимы достаточно сложные топологические преобразования, такие как сдвиг объектов топологии и

добавление изломов проводников. Данные преобразования выполняются предложенным в работе алгоритмом удаления положительных циклов.

Топология стандартных ячеек многократно используется при синтезе различных блоков более высокого уровня. На верхнем уровне программа трассировки выполняет разводку цепей, соединяя внешние выводы ячеек, так называемые порты. Хорошая верхнеуровневая трассируемость определяется размещением портов и их количеством в цепи. Вставка дополнительных портов там, где существует место (не надо увеличивать площадь топологии) позволяет существенно улучшить трассируемость за счет того, что трассировщик имеет альтернативные позиции для подключения. Для добавления дополнительных портов предлагается универсальный алгоритм; позволяющий добавлять в топологию, как дополнительные порты, так и другие объекты, (диоды, контакты к подложке, дополнительные межслойные переходы и т.д.). Тип объекта определяет способ его создания, вставки в топологию, поиска возможных позиций и их сортировку. Для вставки портов создается как сам порт, так и некоторое множество дополнительных фигур, гарантирующих доступ к данному порту из верхних слоев. Множество позиций определяется множеством координат, кратных сетке трассировщика и расположенных в пределах данной цепи (для обеспечения связности). Сортировка позиций проводится по критерию наилучшего расположения портов, определяемому пользователем. После вставки новых объектов в топологию некоторые технологические правила могут быть нарушены, что приводит к возникновению положительных циклов. Алгоритм удаления положительных циклов позволяет решить данные проблемы, используя полуторамерные реорганизации топологии. Если все положительные циклы удалены и выполнены дополнительные условия, определяемые пользователем (например, сохранен исходный размер), то можно считать, что объект добавлен успешно, иначе выполняется возврат

назад и выбор следующей по приоритету позиции. Цикл повторяется до тех пор, пока есть вакантные позиции.

Для увеличения выхода годных предложены следующие алгоритмы:

• уменьшение числа "изломов" проводников;

• вставка дополнительных контактных окон к истокам/стокам транзисторов, уменьшающих вероятность их выгорания.

В четвертой главе предложен метод линейной декомпозиции топологии при полуторамерном сжатии, который позволяет сократить временные и машинные ресурсы необходимые для обработки больших фрагментов топологии.

Известные методы декомпозиции разбивают входную топологию на К непересекающихся частей, сжимают каждую часть независимо, а затем склеивают их. Разбиение производится сечениями, проходящими от одного края топологии до другого, перпендикулярно направлению сжатия, а полученные блоки оказываются линейно упорядоченными в направлении сжатия. Такой подход имеет следующие недостатки:

• Сечение не может пересекать межслойные переходы и транзисторы.

• Необходим лучевой алгоритм для поиска сечения.

• Результирующее сечение с изломами.

• Запрещенные для сжатия регионы на изломах сечения.

• Только одномерные методы сжатия.

Для решения перечисленных проблем и применения эффективного полуторамерного сжатия предлагается новый метод разбиения топологии и обработки граничных объектов. Данный метод имеет следующие особенности:

• Используется прямолинейное сечение, которое может пересекать любые объекты топологии: терминалы, транзисторы, межслойные переходы и т.д.

• Объекты, пересекаемые сечением, не разрезаются, а целиком переносятся в локальную топологию, и их положение фиксируется относительно сечения.

• При сжатии учитываются объекты, расположенные за пределами рассматриваемого фрагмента топологии, расстояние до которых меньше, чем величина максимального технологического правила. Это позволяет при сжатии сдвигать объекты топологии вплотную к линии сечения.

• Внешние части объектов фиксируются относительно линии сечения.

Предложенный способ обработки объектов топологии в области сечения позволяет избежать потерь площади, обусловленных запрещенными регионами и краевыми ситуациями, возникающими в известных алгоритмах. Учет объектов окружения дает возможность применить полуторамерные методы сжатия, что существенно увеличивает плотность топологии. В отличие от ранее предложенного подхода всегда гарантируется построение допустимого сечения. Данный метод позволяет применять рассмотренные алгоритмы сжатия для больших топологий стандартных ячеек. Предлагается два способа применения данного подхода:

• сжимать отдельные рыхлые фрагменты топологии;

• сжимать очень большие ячейки, используя сканирующее окно.

Обычно рыхлая топология возникает на месте стыковки отдельно

синтезированных фрагментов и может быть выделена автоматически. Такой подход позволяет не применять сжатие к плотным фрагментам топологии, что существенно экономит время. В случае, если топология собрана из нескольких одинаковых фрагментов (например, топология сдвигового регистра), данный подход позволяет сохранить ее регулярность.

Для сжатия всей топологии большого блока предлагается применять сканирующее окно. При данном подходе окно постепенно сдвигается в направлении сжатия от одного края топологии до другого. Размер окна определяет компромисс между качеством и временем сжатия. Чем шире окно и больше область перекрытия соседних окон, тем лучше качество сжатия, но больше время.

В пятой главе проведено исследование предложенных алгоритмов сжатия, которые были реализованы в виде программы на языке

Построена зависимость времени сжатия от размера задачи, которая подтверждает теоретически полученную оценку О(^), где N - количество затворов транзисторов. Показано, что алгоритмы оптимизации качества топологии на практике имеют меньшую сложность, чем было оценено. На Рис. 1 показана зависимость времени сжатия от размера топологии и кривая Л/У*.

13 14 • 13 • ♦ ■

12 • 11 •

10 . ♦ •'

X . /

X » ■

I 1.

1 7

& •< ■ я _ У*1

4 • *

1 •

2 • 1 • ♦

) 10 20 30 40 50

количество транзисторов

Рис. 1 Зависимость времени сжатия от размера топологии

Проведено сравнение с известными алгоритмами по качеству сжатия. Основными критериями при сравнении являются плотность топологии и количество нарушений технологических правил (DRC ошибок). Ячейки, имеющие DRC ошибки, не могут быть произведены на кристалле и нуждаются в ручной доработке, которая требует временных затрат. Кроме

этого, для исправления ошибки иногда необходимо увеличить размер топологии. Проведенные эксперименты показали, что плотность топологии в среднем увеличилась на 10%, а на некоторых ячейках до 30% по сравнению с известными методами. Сравнение ширины ячеек приведено на Рис. 2.

Проведенное сравнение показало, что предложенная контурная модель топологии позволяет полностью избежать DRC нарушений. Анализ нарушений, полученных при использовании модели прямоугольников, показал, что все они обусловлены недостатками данной модели. На Рис. 3 приведено сравнение двух алгоритмов по количеству нарушений технологических правил.

Кроме того, при сравнении использовались следующие дополнительные критерии:

• степень минимизации размеров диффузионных областей, которые определяют задержку распространения сигнала;

• количество вставки дополнительных портов (мест для подключения трассировщика);

• количество дополнительных контактов к диффузионным областям транзисторов.

Проведенное сравнение показало, что наличие специализированных алгоритмов для поддержки данных требований позволяет существенно улучшить данные характеристики. Среднее превышение минимального расстояния между затворами сократилось в 2 раз. Среднее количество портов в цепи выросло примерно в 2.5 раза. Количество контактов к транзисторам также возросло.

Для сравнения качества минимизации использовался следующий критерий:

где О^ЦуЬеп&Ь/ _ расстояние между 1-ой парой соседних затворов транзисторов; - минимально возможное расстояние между

соседними затворами, вычисляемое из технологических правил и конфигурации диффузионной области.

Данная величина показывает относительное превышение минимально возможной длины диффузии. Сравнение данных величин для одномерного и полуторамерного алгоритмов приведено на Рис. 4

Для оценки эффективности предложенного алгоритма линейной декомпозиции проведено сравнение с сжатием целой топологии. Сравнение проведено по критериям плотности и времени. Показано, что сжатие только рыхлых фрагментов топологии позволяет сократить время сжатия больше чем в 100 раз при уменьшении плотности на 5-7%. Использование сканирующего окна сокращает время сжатия примерно в 20 раз при увеличении площади всего на 0.6%.

Для линейной декомпозиции с использованием сканирующего окна предложен способ выбора его оптимального размера, который обеспечивает компромисс между временем и качеством сжатия. На основании проведенного эксперимента предлагается выбирать ширину окна примерно в 2-2.5 раза больше высоты ячейки. Для выбора оптимальной величины пересечения окон был проведен ряд сжатий топологий с оптимальным размером окна и различной величиной перекрытия. Оптимальным размером перекрытия можно считать ширины окна.

В заключении сформулированы основные результаты, полученные в рамках диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложен алгоритм полуторамерного сжатия топологии стандартных

ячеек, который отличается от известных методов тем, что в него

добавлены новые функциональные возможности, а именно:

• Разработан алгоритм удаления положительных циклов, позволяющий автоматически устранять конфликты между технологическими правилами и ограничениями на задержку сигнала. Предложенный подход позволяет сжимать топологию, которая не может быть сжата известными методами.

• Минимизация критического пути улучшена за счет специального метода поиска сечения критического подграфа. Предложенный подход позволяет находить сечение, состоящее из ребер и вершин одновременно, что приводит к увеличению плотности топологии по сравнению с известными алгоритмами. Предложенный метод запатентован.

• Для постановки некоторых объектов топологии в сетку трассировщика предложен алгоритм вычисления длиннейших путей графа ограничений, учитывающий данные требования.

• Критерии остановки позволяют уменьшить время работы алгоритма сжатия. Предложен ряд критериев: целевой размер, плотность и память объектов топологии.

• Алгоритм выхода из локального минимума и методы реорганизации топологии существенно повышают эффективность итерационных алгоритмов сжатия, что позволяет получать более компактную топологию. Предложено несколько вариантов реорганизаций топологии: выпрямление меандров, локальная перетрассировка и удаление критических правил.

• Предлагаются алгоритмы оптимизации топологии по критериям быстродействия, трассируемости и выхода годных.

2. Предложено использовать контурную модель топологии при полуторамерном сжатии, которая, в отличие от широко применяемой модели прямоугольников, позволяет учитывать более широкий набор технологических правил. Для этого предложены методы реорганизации контуров, позволяющие минимизировать длину критического пути.

3. Для сжатия больших стандартных ячеек преложен алгоритм линейной декомпозиции топологии, который отличается от известных способом обработки объектов топологии в области сечения. Такой подход позволяет уменьшать размер топологии для сжатия, избегая потерь площади, обусловленных запрещенными регионами и граничными ситуациями, возникающими в известных подходах. Учет объектов окружения дает возможность применять более эффективные полуторамерные методы сжатия, что существенно увеличивает плотность топологии. В отличие от ранее предложенного подхода, всегда гарантируется построение допустимого сечения. Разработанный .. метод позволяет сократить временные и машинные ресурсы, необходимые для сжатия больших фрагментов топологии.

4. Проведено исследование разработанных алгоритмов сжатия, а именно:

• Проанализирована зависимость времени работы программы сжатия от размерности задачи и подтверждены теоретические оценки, полученные в предыдущих главах. Показана что алгоритм имеет сложность

• Проведено сравнение предложенных алгоритмов сжатия с известными методами по различным критериям: время сжатия, плотность топологии, количество DRC ошибок и т.д. Показано

преимущество разработанного метода. Плотность топологии, увеличилась на 10-30%. • Выполнена оценка эффективности метода линейной декомпозиции и оптимизированы параметры запуска данного алгоритма. Предложен способ выбора оптимальной ширины окна сжатия и величины перекрытия соседних окон. Использование данного подхода сокращает время сжатия в 20-100 раз при незначительном увеличении размера топологии.

5. Предложенные алгоритмы реализованы в виде программы сжатия: топологии стандартных ячеек, написанной на языке C++. Данная программа интегрирована в систему автоматического синтеза топологии стандартных ячеек СБИС и внедрена в ЗАО "Моторола ЗАО". Кроме того, в МИЭТе результаты диссертации внедрены в учебный процесс в курсе "Автоматизация топологического проектирования БИС".

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

[1] Марченко A.M., Плис А.П., Сотников МА Контурная модель топологии для задачи сжатия на основе графа ограничений // Известия ТРТУ, тезисы докладов. -1999. - С. 353-354.

[2] Марченко A.M., Плис А.П., Сотников М.А. Контурная модель топологии ячейки СБИС для задачи сжатия // Труды НИИР. — 2000. -С. 73-75.

[3] Марченко A.M., Сотников М.А. Сжатие с одновременным использованием сдвига и разбиения // Труды НИИР. - 2001. - С. 74 -76.

[4] Марченко A.M., Сотников МА Методы реорганизации контуров при сжатии топологии // Известия ТРТУ, тезисы докладов. - 2001. -С. 205-206.

[5] ' ChiluvuriV.K. Rf MarchenkoAM., SotnikovMA Method and

Apparatus for Constraint Graph Based Layout Compaction for Integrated Circuits // United States Patent, № 6,434,721 Bl,Aug. 13,2002,

[6] Марченко A.M., Сотников МА Методы реорганизации контурной топологии при сжатии ячеек СБИС // Труды НИИР.- 2002. -С.105-107.

[7] Сотников МА. Алгоритм сжатия топологии стандартных ячеек субмикронных СБИС// Труды НИИР. - 2002. - С. 108112.

[8] Марченко A.M., Сотников М.А. Метод линейной декомпозиции топологии СБИС в задаче сжатия // Международная научно-технической конференции "Интеллектуальные САПР', Труды конференций. - 2002. -С. 346-347.

[9] Марченко A.M., Сотников МА Методы выхода из локального минимума в итерационных алгоритмах сжатия топологии // Международная научно-техническойконференции "Интеллектуальные САПР", Труды конференций. - 2002. - С. 323-326.

[ю] Сотников М.А., Сухов М.А Сравнительный анализ методов построения графа ограничений для одномерного сжатия // "Микроэлектроника и информатика-2003", Десятая всероссийская межвузовская научно-техническая конференция студентов и аспирантов, апрель 2003. - С, 282.

[и] Марченко A.M., Сотников М.А. Метод линейной декомпозиции ячеек СБИС при сжатии топологии // Труды НИИР. - 2003, -С. 117-121.

[12] Марченко A.M., Сотников М.А Критерии остановки в итеративных алгоритмах сжатия топологии стандартных ячеек СБИС. // Международная научно-технической конференции "Интеллектуальные САПР", Труды конференций. - 2003, -Т. 2, -С. 96-99.

» -mi

Введение,

Оглавление

Глава 1. Обзор методов сжатия топологии.

1.1. Постановка задачи сжатия.

1.2. Классификация алгоритмов сжатия.

1.3. Одномерное сжатие.

1.4. Алгоритмы, использующие два графа ограничений.

1.5. Двумерное сжатие.

1.6. Иерархическое сжатие.

1.7. Оптимизация топологии.

Выводы.

Глава 2. Представление топологии и построение графа ограничений.

2.1. Контурное представление топологии.

2.2. Представление технологических правил.

2.3. Построение графа ограничений.

2.4. Способы минимизации длины критического пути в графе ограничений

2.5. Выводы.

Глава 3. Методы сжатия топологии стандартных ячеек.

3.1. Алгоритм 1.5 мерного сжатия.

3.2. Анализ графа ограничений.

3.3. Критерий остановки и анализ дальнейшей сжимаемости топологии.

3.4. Выход из локальных минимумов.

3.5. Заключительная оптимизация топологии.

3.6. Сложность алгоритма сжатия.

3.7. Выводы.

Глава 4. Снижение размерности задачи сжатия.

4.1. Метод линейной декомпозиции.

4.2. Способы применения линейной декомпозиции.

4.3. Выводы.

Глава 5. Исследование эффективности методов сжатия.

5.1. Выбор характеристики размера топологии стандартной ячейки.

5.2. Зависимость времени сжатия от размеров топологии.

5.3. Сравнение качества сжатия топологии.

5.4. Минимизация задачи сжатия.

5.5. Выводы.

Актуальность работы.

В настоящее время современные субмикронные технологии достигли такой степени интеграции, что минимальный размер топологического объекта меньше длины волны, используемой при фотолитографии. Например, длина затвора транзистора равна 45 нм, а длина волны - 193 нм. (Для сравнения размер вируса гриппа равен 60 нм.) Как следствие этого, к известным технологическим ограничениям на минимальное расстояние и размер объектов топологии добавились новые, более сложные правила. Данные правила зависят от конфигурации, геометрических размеров и взаимного расположения объектов топологии. Кроме того, для создания объектов меньше чем длина волны применяются специальные приемы, позволяющие улучшить разрешающую способность технологического оборудования. Одним из таких приемов является засветка противоположными фазами с разных сторон проводника. Это порождает ряд правил, гарантирующих отсутствие конфликтов противоположных фаз. Например, необходимо выдерживать специальное минимальное расстояние между проводами, если:

• они перпендикулярны и их ширина меньше длины волны;

• между ними расположен третий провод и их ширина меньше длины волны. Технологические ограничения такого вида делают процесс разработки современных топологий более трудоемким, чем раньше.

Уменьшение размеров привело к тому, что проводники вносят существенный вклад в задержку распространения сигнала даже в топологии стандартной ячейки. Следовательно, необходимо учитывать данные схемотехнические проблемы при разработке топологии ячеек. Особенно сильно на задержку распространения сигнала в стандартной ячейке влияет расстояние между затворами транзисторов, так как диффузионная область имеет значительное сопротивление и емкость по сравнению с металлами.

Наряду с перечисленными ограничениями происходит быстрая смена технологий. Каждый год появляется новый технологический процесс, который в первую очередь требует разработки новой библиотеки стандартных ячеек. Это приводит к тому, что разработка библиотеки производится в сжатые сроки и часто параллельно с доводкой технологии.

Таким образом, сложные технологические ограничения и сжатые сроки проектирования делают невозможным разработку топологии стандартных ячеек без использования Систем Автоматизированного Проектирования (САПР). Одним из важных этапов автоматического синтеза топологии является сжатие. На этом этапе производится уменьшение площади топологии одновременно с контролем и выполнением всех ограничений, накладываемых технологическим процессом производства.

Параллельная разработка библиотеки и технологий требует коррекции уже разработанных ячеек после каждого изменения технологических норм. Задача коррекции технологических правил является родственной задаче сжатия и называется миграцией топологии. Однако, при миграции размер топологии может увеличиться для выполнения требований новых ограничений.

Известные методы сжатия не учитывают перечисленные выше технологические и схемотехнические ограничения. Следовательно, разработка новых эффективных методов сжатия и миграции топологии является актуальной.

Цель диссертационной работы состоит в разработке эффективных методов и алгоритмов сжатия топологии стандартных ячеек СБИС с учетом требований современных субмикронных технологий. Для достижения данной цели в диссертационной работе решаются следующие задачи: разработка эффективного алгоритма сжатия топологии стандартных ячеек субмикронных СБИС;

- разработка алгоритмов для улучшения быстродействия, трассируемости и выхода годных на этапе сжатия;

- разработка модели топологии, позволяющей проводить эффективное сжатие и учитывать современные технологические ограничения;

- разработка иерархических методов сжатия больших ячеек;

- исследование эффективности предложенного алгоритма, сравнение качества сжатия с существующими методами и выбор оптимальных параметров настройки алгоритмов.

Научная новизна результатов, представленных в данной диссертационной работе, заключается в следующем: предложена новая модель топологии и методы ее реорганизации для проведения полуторамерного сжатия, основной особенностью которой является использование непересекающихся многосвязных контуров;

- предложен алгоритм полуторамерного сжатая топологии стандартных ячеек субмикронных СБИС, который, в отличие от известных, учитывает современные технологические ограничения, позволяющие создавать объекты меньше длины волны, используемой при фотолитографии;

- предложен алгоритм автоматического удаления положительных циклов в графе ограничений, который, в отличие от известных, использует полуторамерные реорганизации топологии. Это позволяет сжимать некорректную топологию с одновременным устранением технологических нарушений. Данный алгоритм используется как при сжатии, так и в различных методах оптимизации топологии;

- разработан оригинальный метод поиска оптимального сечения критического подграфа, который отличается от известных одновременным применением различных способов минимизации длины критического пути (разбиение вершины и удаление ребра). Данный подход позволяет получать более компактную топологию;

- предложен алгоритм минимизации диффузионных областей с помощью полуторамерных реорганизаций топологии, который позволяет минимизировать задержки сигнала.

Реализация.

На базе предложенных алгоритмов разработан комплекс программ сжатия и миграции топологии. Программа сжатия топологии стандартных ячеек используется в системе автоматического синтеза топологии стандартных ячеек. Программа миграции топологии успешно используется для коррекции топологии при незначительном изменении технологических ограничений и при переводе топологии на новые технологические процессы. Разработанные программы внедрены в ЗАО "Моторола ЗАО".

Практическая значимость работы.

Алгоритмы и подходы, предложенные в данной работе, реализованы в виде программы сжатия топологии, которая используются при автоматическом синтезе топологии стандартных ячеек СБИС. Данные алгоритмы также используются при миграции существующих топологий на новые технологические процессы. Модель топологии, используемая для сжатия, позволяет выдерживать основные современные технологические ограничения. С использованием данных программ были проведены синтез и миграция нескольких библиотек стандартных ячеек для современных технологических процессов. Предложенный метод линейной декомпозиции задачи сжатия, позволяет применять данные алгоритмы для топологии больших размеров.

Апробация основных теоретических и практических результатов работы проводилась на конференциях:

• Международная научно-техническая конференция "Интеллектуальные САПР" (г. Геленджик, 1999-2003 г., 5 докладов)

• Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика-2003", (МИЭТ, 2003 г., 1 доклад)

Публикации. Результаты диссертации отражены в пяти статьях [2,3,6,7,12], шести тезисах научных докладов на конференциях [1,4,8-11] и одном патенте [5].

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 119 страницы и 2 акта о внедрении.

5.5. Выводы.

В данной главе проведено исследование предложенных ранее алгоритмов сжатия, а именно:

• Проанализирована зависимость времени работы программы сжатия от размерности задачи и подтверждены теоретические оценки, полученные в предыдущих главах.

• Проведено сравнение предложенных алгоритмов сжатия с известными методами по различным критериям: время сжатия, плотность топологии, количество DRC ошибок и т.д.

• Оценена эффективность метода линейной декомпозиции задачи сжатия.

• Предложен способ выбора оптимальной ширины окна сжатия и величины перекрытия соседних окон при линейной декомпозиции.

Заключение.

Настоящая диссертационная работа была посвящена исследованию проблем сжатия топологии стандартных ячеек СБИС при соблюдении современных технологических ограничений.

1. Предложен алгоритм полуторамерного сжатия топологии стандартных ячеек, который отличается от известных методов тем, что в него добавлены новые функциональные возможности, а именно:

• Разработан алгоритм удаления положительных циклов, позволяющий автоматически устранять конфликты между технологическими правилами и ограничениями на задержку сигнала. Предложенный подход позволяет сжимать топологию, которая не может быть сжата известными методами.

• Минимизация критического пути улучшена за счет специального метода поиска сечения критического подграфа. Предложенный подход позволяет находить сечение, состоящее из ребер и вершин одновременно, что приводит к увеличению плотности топологии по сравнению с известными алгоритмами. Предложенный метод запатентован.

• Для постановки некоторых объектов топологии в сетку трассировщика предложен алгоритм вычисления длиннейших путей графа ограничений, учитывающий данные требования.

• Критерии остановки позволяют уменьшить время работы алгоритма сжатия. Предложен ряд критериев: целевой размер, плотность и память объектов топологии.

• Алгоритм выхода из локального минимума и методы реорганизации топологии существенно повышают эффективность итерационных алгоритмов сжатия, что позволяет получать более компактную топологию. Предложено несколько вариантов реорганизаций топологии: выпрямление меандров, локальная перетрассировка и удаление критических правил.

• Предлагаются алгоритмы оптимизации топологии по критериям быстродействия, трассируемости и выхода годных.

2. Предложено использовать контурную модель топологии при /ф полуторамерном сжатии, которая, в отличие от широко применяемой модели прямоугольников, позволяет учитывать более широкий набор технологических правил. Для этого предложены методы реорганизации контуров, позволяющие минимизировать длину критического пути.

3. Для сжатия больших стандартных ячеек преложен алгоритм линейной декомпозиции топологии, который отличается от известных способом обработки объектов топологии в области сечения. Такой подход позволяет уменьшать размер топологии для сжатия, избегая потерь площади, обусловленных запрещенными регионами и граничными ситуациями, возникающими в известных подходах. Учет объектов окружения дает возможность применять более эффективные полуторамерные методы сжатия, что существенно увеличивает плотность топологии. В отличие от ранее предложенного подхода, всегда гарантируется построение допустимого сечения. Разработанный метод позволяет сократить временные и машинные ресурсы, необходимые для сжатия больших фрагментов топологии.

4. Проведено исследование разработанных алгоритмов сжатия, а именно:

• Проанализирована зависимость времени работы программы сжатия от размерности задачи и подтверждены теоретические оценки, полученные в предыдущих главах.

• Проведено сравнение предложенных алгоритмов сжатия с известными методами по различным критериям: время сжатия, плотность топологии, количество DRC ошибок и т.д. Показано преимущество разработанного метода.

• Выполнена оценка эффективности метода линейной декомпозиции и оптимизированы параметры запуска данного алгоритма. Предложен способ выбора оптимальной ширины окна сжатия и величины перекрытия соседних окон.

5. Предложенные алгоритмы реализованы в виде программы сжатия топологии стандартных ячеек, написанной на языке С++. Данная программа интегрирована в систему автоматического синтеза топологии стандартных ячеек СБИС и внедрена в ЗАО "Моторола ЗАО". Кроме того, в МИЭТе результаты диссертации внедрены в учебный процесс в курсе "Автоматизация топологического проектирования БИС".

4Г 4

1. Марченко A.M., Плис А.П., Сотников М.А. Контурная модель топологии для задачи сжатия на основе графа ограничений // Известия ТРТУ, тезисы докладов. 1999. - С. 353-354.

2. Марченко A.M., Плис А.П., Сотников М.А. Контурная модель топологии ячейки СБИС для задачи сжатия // Труды НИИР. 2000. - С. 73-75.

3. Марченко A.M., Сотников М.А. Сжатие с одновременным использованием сдвига и разбиения // Труды НИИР. 2001. - С. 74 - 76.

4. Марченко A.M., Сотников М.А. Методы реорганизации контуров при сжатии топологии // Известия ТРТУ, тезисы докладов. 2001. — С. 205206.

5. Chiluvuri V. К. R., Marchenko A.M., Sotnikov М.А. Method and Apparatus for Constraint Graph Based Layout Compaction for Integrated Circuits // United States Patent, № 6,434,721 Bl, Aug. 13, 2002.

6. Марченко A.M., Сотников М.А. Методы реорганизации контурной топологии при сжатии ячеек СБИС // Труды НИИР. 2002. - С. 105-107.

7. Сотников М.А. Алгоритм сжатия топологии стандартных ячеек субмикронных СБИС // Труды НИИР. 2002. - С. 108-112.

8. Марченко A.M., Сотников М.А. Метод линейной декомпозиции топологии СБИС в задаче сжатия // Международная научно-технической конференции "Интеллектуальные САПР", Труды конференций. 2002. -С. 346-347.

9. Марченко A.M., Сотников М.А. Методы выхода из локального минимума в итерационных алгоритмах сжатия топологии // Международная научно-технической конференции "Интеллектуальные САПР", Труды конференций. 2002. - С. 323-326.

10. Марченко A.M., Сотников М.А. Метод линейной декомпозиции ячеек СБИС при сжатии топологии // Труды НИИР. 2003. - С. 117-121.

11. Марченко A.M., Сотников М.А. Критерии остановки в итеративных алгоритмах сжатия топологии стандартных ячеек СБИС. // Международная научно-технической конференции "Интеллектуальные САПР", Труды конференций. 2003. - Т. 2. - С. 96-99.

12. Wayne Н. Wolf, Robert G. Mathews, Jon A Newkirk, and Robert W.Dutton. Algorithm for Optimizing Two-Dimensional Symbolic Layout Compaction, IEEE Transactions On Computer-aided Design, Vol.7, April* 1988, pp. 451-466

13. Hyunchul Shin and Chi-Yuan Lo, An Efficient Two-Dimensional Layout Compaction Algorithm, Proceedings of the 26th ACM/IEEE Design Automation Conference, pp. 290-295, ACM Press, June 1989

14. N.Sherwani. Algorithm for the VLSI Physical Design Automation, Second Edition, Kluwer Academic Publishers, 1995

15. F.-L.Heng, Z.Chen, G.E.Telfez. A VLSI Artwork Legalization Technique Based on a New Criterion of Minimum Layout Perturbation, ISPD'97, 1997, pages 116-121

16. F.-L.Heng, L.Liebmann, J. Lund. Application of Automated Design Migration to Alternating Phase Shift Mask Design, ISPD'01, April, 2001

17. L.-Y. Wang, Y.-T. Lai, Graph-Theory-Based Simplex Algorithm for VLSI Layout Spacing Problem with Multiple Variable Constraints, IEEE Transaction on Computer-Aided Design of Integrated Circuits an Systems, vol. 20, no 8, pp. 967-979, August 2001

18. Reinhardt, Michael, Automatic Layout Modification, Kluwer Academic Publishers Group, 2002

19. R.Sedgewick, Algorithms in С++, Addison-Wesley Publishing Company, 1992

20. Thomas Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, 1990

21. Ralf Seepold, Amo Kunzmann, Breuse Technique for VLSI Design, Kluwer Academic Publishers 1999

22. H.Veendrick, Deep-Submicron ICs, Kluwer Academic Publisher,s 2000

23. D.J.Eaglesham 0.18um CMOS and beyond, // DAC-99, pp703-707, 1999

24. M.A.Breuer, M. Sarrafzadeh and F. Somenzi, Fundamental CAD Algorithms, // IEEE Transaction on Computer-Aided Design, vol. 19, No 12, pp. 1449-1475, December 2000

25. R.W.Dutton, and A.J.Strojwas, Perspectives on Technology and Technology-Driven CAD, // IEEE Transaction on Computer-Aided Design, vol. 19, No 12, pp. 1544-1560, December 2000

26. Abdul A. Malik, An Efficient Algorithm for Generation of Constraint Graph for Compaction, 1С CAD, pp. 130-133, 1987

27. W.H.Crocher, C.Y.Lo and R Varadarajan, MACS: a Module Assembly and Compaction System, Proc. Of the IEEE International Conference on Computer Design, pp205-208, Oct. 1987

28. X.M Xiong and E.S.Kuh, An Efficient and Intelligent Channel Spacer, Proc. ACM/IEEE Design Automation Conference, pp298-304,1986

29. Y.E.Cho, A Subjective Review of Compaction, Proc. of the ACM/IEEE 22nd Design Automation Conference, pp 396-404, June 1985.

30. S.B.Akers, J.M.Geyer and D.L.Roberts 1С Mask Layout with a Single Conductor Layer //Proceedings of 7th Design Automation Workshop, pages 716,1970

31. M.Y. Hsueh and D.O.Pederson Computer-Aided Layout of LSI Circuit Building-Block // PhD. thesis, University of California at Berkeley, December 1979

32. S.Kirpatrick, C.D.Gelatt, MP.Vecchi, Optimization by Simulated Annealing, Science, vol. 20, pp. 671-680, May 1983.

33. H.Shin, A.L.Sangiovanni-Vinncentelli, C.H.Sequin Two-Dimensional Compaction by 'Zone Refining', Proc of the 23rd IEEE Design Automation Conference, pp. 115-122, June 1986

34. H.Shin, A.L.Sangiovanni-Vinncentelli, C.H.Sequin Two-Dimensional Module Compactor Based on 'Zone Refining', Proc of the IEEE International Conference, on Computer Design, pp. 201-204, October 1987

35. H.Shin, A.L.Sangiovanni-Vinncentelli, C.H.Sequin 'Zone Refining' Techniques for 1С Layout Compaction, IEEE Transaction on Computer-Aided Design, vol. 9, No 2, pp. 167-179, February 1990

36. W.L. Schiele, Automatic Design Rule Adaptation of Leaf Cell Layouts, // INTEGRA TION, the VLSIjournal (3), 1985, pages 93-112

37. W.L. Schiele, Compaction with Internal Over-Constraints Resolution, ACM/IEEE 27th Design Automation Conference, pages 390-395, 1988

38. J.Burns and A.R.Newton. SPARCS: A new constraint-based 1С symbolic layout £ spacer, Proc. of the IEEE Custom Integrated Circuits Conference, pages 534539, May 1986

39. J.Burns and A.R.Newton, Efficient Constraint Generation for Hierarchical Compaction, Proc. of the IEEE Custom Integrated Circuits Conference, pages 197-200, October 1987

40. B.G.Boyer and N.Weste. Virtual Grid Compaction Using the Most Resent Layers Algorithm, Proc. of the IEEE International Conference on Computer-Aided Design, pages 92-93, September 1983

41. D. G. Boyer, Split Grid Compaction for a Virtual Grid Symbolic Design System, Proc. of the IEEE International Conference on Computer-Aided Design, pp. 134-137, November 1987

42. D. G. Boyer, Symbolic Layout Compaction Benchmarks Introduction and Ground Rules, Proc. of the IEEE International Conference on Computer Design, pp. 186-191, October 1987

43. D. G. Boyer, Symbolic Layout Compaction Benchmarks Results, Proc. of the IEEE International Conference on Computer Design, pp. 209-217, October 1987

44. D. G. Boyer, Symbolic Layout Compaction Renew, Proceedings of the 25th ACM/IEEE Design Automation Conference, pp. 383-389, IEEE Computer Society Press, June 1988

45. D.N.Deutsch. Compacted channel routing, Proc. of the IEEE International Conference on Computer-Aided Design, pages 223-225, November 1985

46. W.W. Dai and E.S. Kuh, Global Spacing of Building Block Layout, in С. H. Sequin, editor, VLSI'87. Elsevier Science Publisher В. V., Amsterdam, The Netherlands, 1987.

47. T. Lengauer, On the Solution of Inequality System Relevant to IC-Layout. Journal of Algorithms, 5:408-421,1984

48. Jurgen Doenhardt and Thomas Lengauer, Algorithmic Aspects of One-Dimensional Layout Compaction, IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-6, No.5, pp863-878, September 1987

49. Y.-Z. Liao and C.K. Wong An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints, IEEE Transaction on Computer-Aided Design of Integrated Circuits an Systems, vol. CAD-2, No 2, pp. 62-69, April 1983

50. M. Schlag, Y.-Z. Liao and С. K. Wong, An algorithm for optimal two-dimensional compaction of VLSI layouts, INTEGRATION, the VLSI journal, Elsevier Science Publisher В. V., Amsterdam, The Netherlands, 1983, pp. 179209

51. T.Yoshimura, A Graph Theoretical Compaction Algorithm, Proc. of the International Symposium on Circuits and Systems, June 1985, pages 1455-1458

52. J.F.Lee and C.K.Wong A Performance-Aimed Cell Compactor with Automatic Jogs, IEEE Transaction on Computer-Aided Design, Vol.11, No. 12, December 1992, pages 1495-1507

53. S.K.Dong, P.Pan, C.Y.Lo and C.L.Liu, Constraint Relaxation in Graph-Based Compaction, Proc of the 5th ACM/SIGMA Physical Design Workshop, April 1996, pages 256-261

54. Sching L. Lin and Jonathan Allen, Minplex A Compactor that Minimizes the Bounding Rectangle and Individual Rectangles in a Layout, 23rd Design Automation Conference, 1986, pp. 123-129

55. W.L.Schiele, Improved Compaction by Minimized Length of Wires, Proceedings of the 20th ACM/IEEE Design Automation Conference, pp. 121127, 1983

56. R.E.Tarian, Data structures and network algorithms, SIAM, 1983

57. А. С. Плеханов, Метод минимизации задержек сигналов при сжатии топологии с учетом технологической сетки // Автоматизация и новые технологии, №1,2001

58. Э. Рейнгольд, Ю. Нивергельт, Н. Део, Комбинаторные алгоритмы теория и практика, издательство "Мир", Москва, 1980

59. В.Липский, Комбинаторика для программистов, издательство "Мир", Москва, 1988

60. W.Kim, J. Lee, Н. Shin, A New Hierarchical Layout Compactor Using Simplified Graph Models, 29th ACM/IEEE Design Automation Conference, 1992

61. David Marple, M.Smulders, H Hegen, An Efficient Compactor for 45° Layout, Proc. of the 25th ACM/IEEE Design Automation Conference, pages 396-402, June 1988

62. D.Marple, A Hierarchy Preserving Hierarchical Compactor, ACM/IEEE 27th Design Automation Conference, pages 134-140, 1990

63. David Marple, M.Smulders and H Hegen, Tailor: A Layot System Based on Trapezoidal Corner Stitching, IEEE Transaction on Computer Aided Design, Vol.9, No. J, January 1990

64. Jin-fuw Lee, Donald T. Tang, HIMALAYAS- A Hierarchical Compaction System with a Minimized Constraint Set, IEEE Transaction on Computer-Aided Design of Integrated Circuits an Systems, 1992

65. So-Zen Yao, Chung-Kung Cheng, Debaprosat Dutt, Surendra Nahar and Chi-Yuan Lo, Cell-Based Hierarchical Pitch-Matching Compaction Using Minimal LP, ACM/IEEE 30th Design Automation Conference, pages 395-400, 1993

66. C. S. Bamji and R. Varadarajan, Hierarchical Pitchmatching Compaction Using Minimum Design, Proceedings of the 29th Conference on Design Automation, pp. 311-317, IEEE Computer Society Press, June 1992.

67. C.Bamji and R.Varadarajan, MSTC: A Method for Identifying Overconstraints during Hierarchical Compaction, ACM/IEEE 30th Design Automation Conference, pages 389-394, 1993

68. W.Crocker, R. Varadarajan, C.Y. Lo, MACS: A Module Assemble and Compaction System, Proc. of the IEEE International Conference on Computer Design, pages 205-208, October 1987

69. P. Eichenberger, Fast Symbolic Layout Translation for Custom VLSI Integrated Circuit, PhD thesis, Stanford University, April 1986

70. P. Eichenberger and M.Horowitz, Topological Compaction of Symbolic Layouts for rectangular structures, IEEE International Conference on Computer-Aided Design, pages 142-145, November 1987

71. G. Entenman, S. Daniel, A Fully Automatic Hierarchical Compactor, Proceeding of the 22nd Design Automation Conference, pages 69-75, June 1985

72. С Kingsley, A Hierarchical Error-Tolerant Compactor, Proc. of the 21s' Design Automation Conference, pages 126-132, June 1984

73. M Reichelt, W. Wolf, A Improved Cell Model for Hierarchical Constraint-Graph Compaction, Proc of the IEEE International Conference on Computer-AidedDesign, pages 482-485,1986

74. Дж. Данцинг, Линейное программирование его применения и обобщения, издательство "Прогресс ", Москва 1966

75. J. Dao, N. Matsumoto, Т. Hamai, С. Ogawa and S. Mori, A Compaction Method for Full Chip VLSI Layouts, 30th ACM/IEEE Design Automation Conference, 1993, pp. 407-412

76. H. Kitazawa and K. Ueda, A look-ahead line search algorithm with high wireability for custom VLSI design, Proc. ISCAS, pp.1035-1038, 1985

77. D. Dutt and C. Y. Lo, On minimal closure constraint generation for symbolic cell assembly, Proc. 28th ACM/IEEE Design Automation Conf, 1991, pp.736739

78. Peichen Pan, Sai-keung Dong, and C.L. Liu, Optimal Graph Constraint Reduction for Symbolic Layout Compaction, ACM/IEEE 30th Design Automation Conference, pages 401-406,1993

79. D.E.Goodman A.Y.Tetelbaum and V.M.Kureichik, A Genetic Algorithm Approach to Compaction, Bin Packing and Nesting Problems, Technical Report #940702, Case Center for Computer-Aided Engineering and Manufacturing Michigan State University, 1994

80. E.Papadopoulou, Critical Area Computation for Missing Material Deffects in VLSI Circuits, IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No 5, May 2000

81. C.-K.Cheng, X.Deng, Y.-Z.Liao and S.-Z.Yao, Symbolic Layout Compaction Uder Conditional Design Rules, IEEE Transaction on Computer-Aided Design, Vol. 11, No 4, April 1992

82. P.Dood, J.Wawrzynek, E.Liu, R.Suaya, A Two-Dimensional Topological Compactor with Octagonal Geometry, 28th ACM/IEEE Design Automation Conference, pages 727-731,1991

83. J.Valainis, S.Kaptanoglu, E.Liu, R.Suaya, Two Dimensional 1С Layout Compaction Based on Topological Design Rule Checking, IEEE Transactions on CAD oflCs and Systems, 9(3), March 1990

84. А.В.Бондалетов, Двумерная упаковка со связями, Известия ТРТУ, Материалы Международной конференции "Интеллектуальные САПР", 1999

85. W.Dai. B.Eschermann, E.Skuh and M.Pedram, Hierarchical Placement and Floorplaning in BEAR, IEEE Transaction on Computer-Aided Design, Vol. 8, No. 12,1989, pages 1335-1348

86. A. V. Aho, M. R. Garey and J. D. Ullman, The transitive reduction of a directed graph, in SIAMJ. Comput., Vol.2, No. 2, pp. 131-137,1972

87. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland, New York, 1976.

88. Andrew J. Harrison, VLSI Layout Compaction Using Radix Priority Search Trees, Proceedings of the 28th ACM/IEEE Design Automation Conference, pp. 732-735, ACM Press, June 1991.

89. M.Barzaghi, F.Curatelli, D.D.Caviglia, G.M.Bisio, Symbolic Compaction of Digital CMOS Cells, IEEE, pages 222-225, vol. 1, May 1991

90. C.Y.Lo and R Varadarajan, An 0(nl 5logn) 1-d Compaction Algorithm, ACM/IEEE 27th Design Automation Conference, pages 382-386, 1990

91. G. Kedem, H. Watanabe, Graph Optimization Techniques for 1С Layout and Compaction, 2(fh Design Automation Conference, pages 113-120,1983

92. G. Kedem, H. Watanabe, Graph Optimization Techniques for 1С Layout and Compaction, IEEE Trans. On CAD oflCs, Vol3, Nol, January 1984

93. H.Watanabe, 1С Layout Generation and Compaction Using Mathematical Optimization, PhD Thesis, University of Rochester, 1984

94. S.Gao, M.Kaufmann and F.M.Maley, Advances in Homotopic Layout Compaction, Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 273-282, ACM Press, June 1989.

95. F.M.Maley, Compaction with automatic jog introduction, Chapel Hill Conference on VLSI, pages 261-283, May 1985

96. C. W. Carpenter and M. Horowitz, Generating Incremental VLSI Compaction Spacing Constraints, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 291-297, IEEE Computer Society Press, June 1987.

97. W.S.Scott, J.K.Ousterhout, Plowing: Interactive Stretching and Compaction in Magic, ACM/IEEE 21st Design Automation Conference, pp. 166-172, IEEE Computer Society Press, June 1984.

98. J.K.Ousterhout, G.T.Hamachi, R.N.Mayo, W.S.Scott and G.S.Taylor, Magic: A VLSI Layout System, ACM/IEEE 21st Design Automation Conference, pp. 152159, June 1984

99. T. Hedges, W. Dawson and Y.E. Cho, Bitmap Graph Build Algorithm for Compaction, Proc. of the IEEE International Conference on Computer-Aided Design, pages 340-342, November 1985

100. J. Do and W. Dawson, SPACER II: Well-Behaved 1С Layout Compactor, Proc of VLSI 85, pages 283-291

101. K.Mehlhorn and S.Naher, A Faster Compaction Algorithm with Automatic Jog Insertion, IEEE Transaction on Computer-Aided Design, vol. 9, No 2, February 1990

102. Akira Onozawa, Layout Compaction With Attractive and Repulsive Constraints, Proceedings of the 27th ACM/IEEE Design Automation Conference, pp. 369-374, ACM Press, June 1990.

103. A.Onozawa, K.Chaudhary, E.S.Kuh, Performance-Driven Spacing Algorithm using Attractive and Repulsive Constraints for Submicron LSIs, IEEE Transaction on Computer-Aided Design, Vol. 14, June 1995, pages 707-719

104. P.-Y. Hsiao and W.-S. Feng, An Edge-Oriented Compaction Scheme Based on Multiple Storage Quad Tree, Proc. of the IEEE International Symposium on Circuits and Systems, June 1988

105. A.E. Dunlon, SLIM The translation of Symbolic Layouts into Mask Data, Proc. of the 17th Design Automation Conference, pages 595-602, Junel980

106. Z.V. Apanovich and A.G. Marchuk Top-Down Approach to Technology Migration for Full-Custom Mask Layouts, Proceedings of the Eleventh International Conference on VLSI Design: VLSI for Signal Processing, 1998

107. R.C.Mosteller, A.H.Frey and R.Suaya 2-D Compaction a Monte Carlo Method, Proc. of the Stanford Conference on Advanced Research in VLSI, 1987, pages 173-197

108. Wayne H. Wolf, Robert G.Mathews, Jon A Newkirk, and Robert W.Dutton. Two-dimensional Compaction Strategies, Proc of the IEEE International Conference on Computer-Aided Design, pp. 90-91, September 1983

109. W. Wolf, An Experimental Comparison of 1-D Compaction Algorithms, Chapel Hill VLSI Conference, pp. 165-180, 1985

110. W. Wolf, Sticks Compaction and Assembly, IEEE Design & Test of Computers, pp. 57-63, June 1986

111. T.M.Hsieh, H.W.Leong, C.L.Liu, Two-Dimensional Layout Compaction by Simulated Annealing, Proc. of the IEEE International Symposium on Circuits and Systems, June 1988

112. E.G.Goffman and P.W.Shor, Average-case analysis of cutting and packing in two dimensions, Europenian Journal of Operational Research, Elsevier Science Publisher В. V., Amsterdam, The Netherlands, 1983, pp. 134-144

113. J. Lee, A New Framework of Design Rules for Compaction of VLSI Layouts, IEEE trans, on CAD, vol.7, No 11, pages 1195-1204, November 1988

114. W. Kim, J. Lee, and H. Shin, A New Hierarchical Layout Compactor Using Simplified Graph Models, Proceedings of the 29th Conference on Design Automation, pp. 323-326, IEEE Computer Society Press, June 1992

115. L.-Y. Wang, Y.-T. Lai, B.-D. Liu and T.-C. Chang, Layout Compaction with Minimized Delay Bound on Timing Critical Path, Proc. of the International Symposium on Circuits and Systems, June 1993, pages 1849-1852

116. L.-Y. Wang, Y.-T. Lai, B.-D. Liu and T.-C. Chang, A Graph-Based Simplex Algorithm for Minimizing the Layout Size and the Delay on Timing Critical Path, Proc. of the IEEE International Conference on Computer-Aided Design, November 1993, pages 703-708

117. L.-Y. Wang, Y.-T. Lai, B.-D. Liu and T.-C. Chang, Performance-Directed Compaction for VLSI Symbolic Layouts, Computer-aided Design, 27(1), pp. 65-74, Elsevier Science, 1995

118. Awashima, Sato and Ohtsuki, Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced Plane-Sweep Method TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1993.

119. Ishima, Tsukiyama, On an Algorithm to Detect Positive Cycles in a Constraint Graph for Layout Compaction, T1EICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1991.

120. S. E. Hambrusch, Y. Tu, New Algorithms and Approaches for 1—Dimensional Layout Compaction, Proceedings of New Results and New Trends in Computer Science, LNCS, Vol. 555, pp. 152-171, Springer, June 1991.

121. D. G. Boyer, Process Independent Constraint Graph Compaction, Proceedings of the 29th Conference on Design Automation, pp. 318-322, IEEE Computer Society Press, June 1992

122. Sai-Keung Dong, Graph-Based Algorithms for Floorplanning, Routing and Compaction, Technical Report, University of Illinois at Urbana-Champaign, Number UIUCDCS-R-94-1845, January 1994.

123. Matthias, F.M.Stallmann, T.A.Hughes, Fast Algorithms for One-Dimensional Compaction with Jog Insertion, Algorithms and Data Structures, Third Workshop, Lecture Notes in Computer Science, Vol. 709, pp. 589-600, Springer, 11-13 August 1993

124. Klau, and Mutzel, Optimal Compaction of Orthogonal Grid Drawings, IPCO: 7th Integer Programming and Combinatorial Optimization Conference, 1999.

125. Klau, and Mutzel, Combining Graph Labeling and Compaction, GDRAWING: Conference on Graph Drawing (GD), 1999.

126. Narayan Vikas, Computational Complexity of Compaction to Cycles, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 977-978, ACM-SIAM, January 17-19 1999.

127. N.G.Sullivan and J.B.Rosenberg, Parallel Incremental Compaction Technical Report, Department of Computer Science, Duke University, Number Technical report DUKE-TR--1988--18,1988.

128. Chen, and Lee, A Faster One-dimensional Topological Compaction Algorithm, ISAAC: 8th International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms), 1997.

129. R. Andersonl, S. Kahan and M. Schlag, An 0(n log n) Algorithm for 1-D Tile Compaction, Graph-Theoretic Concepts in Computer Science, pp. 287-301, Springer, June 1990.

130. A. A. J. de Lange, J. S. J. de Lange and J. F. Vink, A Hierarchical Constraint Graph Generation and Compaction System for Symbolic Layout, International

131. Conference on Computer Design, VLSI in Computers and Processors, pp. 532535, IEEE Computer Society Press, October 1989.

132. A. Herrigel, J. Kamm and W. Fichtner, Macrocell-Level Compaction with Automatic Jog Introduction, International Conference on Computer Design, VLSI in Computers and Processors, pp. 536-541, IEEE Computer Society Press, October 1989.

133. F.M.Maley, A Generic Algorithm for One-Dimensional Homotopic Compaction, Algorithmica, Vol. 6, pp. 103-128,1991.

134. S.E.Hambrusch and H.-Y. Tu, New Algorithms for Minimizing the Longest Wire Length During Circuit Compaction, Algorithmica, 17(4), pp. 426-448, April 1997.

135. Awashima, Sato and Ohtsuki, Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced Plane-Sweep Method, TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1993.

136. R.Okuda, T.Sato, H.Onodera, and K.Tamaru, An efficient algorithm for layout compaction problem with symmetry constraints, in Digest int'l. Conf. on Computer-Aided Design, 1989, pp. 148-153

137. J.Royle, M.Palczewski, H.VerHeyen, N.Naccache, J.Soukrup, Geometrical Compaction in One Dimension for Channel Routing, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 140-145, IEEE Computer Society Press, June 1987.

138. L.S.Nyland, S.W.Daniel, D.Rogers, Improving Virtual-Grid Compaction Through Grouping, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 305-310, IEEE Computer Society Press, June 1987.

139. P.C.Shah, H.N.Mahabala, A New Compaction Scheme Based on Compression Ridges, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 645-648, IEEE Computer Society Press, June 1987.

140. G.Lakhani, R.Varadajan, A Wire-Length Minimization Algorithm for Circuit Layout Compaction, Proc. of the IEEE International Symposium on Circuits and System, 1987, pages 276-279

141. Y.Shigehiro, T.Nagata, I.Shirakawa, I.Arungsrisangchai, H.Takahashi, Automatic Layout Recycling Based on Layout Description and Linear Programming, IEEE Transaction on Computer Design of Integrated Circuits and Systems, vol. 15, No. 8, August 1996.

142. M.C.Utesch, A New Approach to Hierarchical Adaptation Using Sequence-Control Based on Cell Interactions, In 28th ACM/IEEE Design Automation Conference, 1991

143. А.М.Марченко, М.А.Сотннков, Приближенный метод решения задачи коммивояжера//Труды НИИР, 1995, сс. 102-105.

144. А.М.Марченко, В.П.Розенфельд, М.А.Сотннков Модифицированный силовой алгоритм планировки кристалла СБИС // Технология и конструирование в электронной аппаратуре. №2, 1995, сс. 6-8.

145. А.М.Марченко, А.П.Плис, М.А.Сотннков, И.Г. Топузов, Е.Г.Широ. Алгоритм уменьшения максимальной локальной плотности канала // Труды НИИР, 1998, сс. 55-59

146. Е.Г.Березин, А.М.Марченко, А.С.Плеханов, В.П.Розенфельд, М.А.Сотннков, Е.Г.Широ, Гибридная модель трассировки соединений в ультра-БИС //Труды НИИР, 1998, сс. 49-54.

147. A.Marchenko, A.Plis, E.Shiro, M.Sotnikov, I.Topouzov, P.McGuinness, Method and Apparatus for Channel-Routing of an Electronic Device // United States Patent, No: 6,477,692 Bl, Nov.5,2002

148. A.Marchenko, A.Plis, M. Sotnikov, P.McGuinness, Method for channel routing and apparatus // United States Patent, No: 6,564,366 Bl, May.13,2003

149. S.Even, Graph Algorithms, IIComputer Science Press, 1979

150. В. А. Сынгаевский Е. Г. Широ1. Акт внедрениярезультатов диссертационной работы Сотникова Михаила

151. Анатольевича "Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС", представленной на соискание ученой степени кандидата технических наук по специальности 05.13.12 "Системы автоматизации проектирования".

152. Декан ЭКТ факультета Члены комиссии: