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

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

005531882

Балашов Вадим Владимирович

РАЗРАБОТКА АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ СИНТЕЗА ТОПОЛОГИИ СПЕЦИАЛИЗИРОВАННЫХ БОЛЬШИХ ИНТЕГРАЛЬНЫХ СХЕМ

Специальность 05.13.12 — Системы автоматизации проектирования (промышленность)

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

-1 АВГ 2013

Санкт-Петербург 2013

005531882

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина)», кафедра систем автоматизированного проектирования

Научный руководитель:

доктор технических наук, старший научный сотрудник, Власов Сергей Евгеньевич, директор департамента развития научно-производственной базы ядерного оружейного комплекса государственной корпорации «Росатом»

Официальные оппоненты:

доктор технических наук, Лузин Сергей Юрьевич, технический директор и руководитель обособленного подразделения САПР Санкт-Петербургского филиала ООО «Эремекс»

кандидат технических наук, Исаков Александр Борисович, директор по производству ООО «Научно-производственная фирма «Модем»»

Ведущая организация:

Федеральное государственное унитарное предприятие «Всероссийский научно-исследовательский институт автоматики им. Н. Л. Духова»

Защита состоится « 23 » октя5ря 2013 года в У5:00часов на заседании диссертационного совета Д212.238.02 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В. И. Ульянова (Ленина) по адресу: 197376, г. Санкт-Петербург, ул. Профессора Попова, д. 5.

С диссертацией можно ознакомиться в библиотеке СПбГЭТУ.

Автореферат разослан « 05 » ииддя 2013 года

Учёный секретарь

Диссертационного совета Д212.238.С

к. т. н., доцент

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

Актуальность исследования. Процесс изготовления больших интегральных схем (БИС) состоит из нескольких сотен сложных операций, вследствие чего даже при высоком выходе годных на каждой стадии процесса общий процент выхода годных изделий остаётся довольно низким. Для аналоговой и аналого-цифровой техники (микросборки и пр.), функциональных устройств микроэлектроники, то есть устройств с существенно нерегулярной структурой и, в особенности, с однослойной коммутацией, существующие конструкторские САПР либо недостаточно эффективны, либо вообще не пригодны. Так ни один из модулей трассировки коммерческих современных САПР (в том числе и ведущих фирм Cadence Design Systems, Mentor Graphics, Synopsys) не позволяет осуществлять разводку соединений БИС на основе базовых матричных кристаллов (БМК) с однослойной коммутацией с поликремниевыми перемычками. Это связано с тем, что все современные САПР ориентированы на заказные схемы, выполняемые по технологии с несколькими слоями металлизации. Актуальность БИС на основе БМК с однослойной коммутацией до сих пор остаётся высокой. Одной из разработок последних лет являются структурированные БМК. Западные разработчики считают, что подобный тип ИС может вытеснить ПЛИС в качестве предварительного этапа отработки схем. В связи с вышесказанным, необходимо продолжать исследования новых методов и математических моделей, применяемых для решения оптимизационных задач размещения и трассировки связей устройств с нерегулярной структурой и однослойной коммутацией.

Работа выполнялась в рамках научной школы «Оптимизация в САПР» профессора Батищева Д. И.

Большой вклад в разработку методов и систем автоматизированного проектирования внесли работы учёных АбрайтисаЛ. Б., Анисимова В. И., БазилевичаР. П., Батищева Д. И., Вернадского А. М., Герасимова И. В., ДмитревичаГ. Д., КурейчикаВ. М., Львовича А. Я., Норенкова И. П. и других российских и зарубежных специалистов.

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

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

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

2. Исследование и разработка алгоритмов решения задачи размещения элементов;

3. Разработка алгоритма трассировки, основанного на новой модели коммутационного поля;

4. Разработка программной системы, позволяющей выполнять синтез

топологии однослойных БИС на основе БМК (в том числе обладающих нерегулярной структурой).

5. Разработка сквозного маршрута проектирования БИС на основе аналого-цифрового БМК с применением программной системы синтеза топологии.

Достоверность результатов

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

Достоверность разработанных алгоритмов и методов подтверждается работоспособными образцами трёх проектов БИС, разработанными с помощью программной системы «Синтез» в обеспечение опытно-конструкторской работы (ОКР) «Разработка аналого-цифрового БМК для применения в технических средствах защиты» (шифр «БИС-АБМК»), выполняемой во ФГУП «ФНПЦ НИИИС им. Ю. Е. Седакова» (далее НИИИС).

Новые научные результаты

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

2. Разработана гиперграфовая модель коммутационного пространства (КП) для задачи трассировки соединений, которая, в отличие от классических моделей, содержит не только информацию о топологических особенностях кристалла, но и информацию об «узких местах» КП;

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

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

5. Разработан алгоритм локальной трассировки, основанный на графовой модели КП, который осуществляет разводку трасс внутри макродискретов.

Основные положения, выносимые на защиту

¡.Математическая модель, алгоритм размещения элементов, основанный на декомпозиции задачи;

2. Математическая модель, алгоритмы трассировки, основанные на графовых моделях коммутационного пространства;

3. Программная система синтеза топологии (ПС «Синтез»);

4. Сквозной маршрут проектирования аналого-цифровых БИС на основе БМК с одним слоем коммутации.

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

Cadence Design Systems, образуя сквозной маршрут проектирования микроэлектронных устройств с однослойной коммутацией.

Внедрение результатов работы. Разработанная система проектирования топологии БИС на основе аналого-цифрового БМК внедрена в НИИИС (используется в сквозном маршруте проектирования аналого-цифровых БИС на основе БМК с одним слоем металлизации).

Результаты работы внедрены в учебный процесс факультета вычислительной математики и кибернетики при преподавании основного курса «Схемотехника, организация ЭВМ и систем» и специального курса «Автоматизация проектирования цифровых микроэлекгронных устройств» для студентов специальности 08.08.01 «Прикладная информатика» в ННГУ им. Н. И. Лобачевского [16,17].

Результаты диссертационной работы использовались в госбюджетных НИР по теме «Математико-логические основы построения сред виртуальных инструментов» (шифр САПР-49 тем. плана СПбГЭТУ 2012 г.).

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

1. 7-ая Нижегородская сессия молодых учёных (Н. Новгород, 2002 г);

2. Всероссийская научно-техническая конференция «Информационные системы и технологии ИСТ-2004» и «ИСТ-2008» (Н. Новгород, 2004, 2008 г);

3. IV и VI международная научно-техническая конференция «Будущее технической науки» (Н. Новгород, 2005, 2007 г);

4. Всероссийская конференция «Технологии Microsoft в теории и практике программирования» (Н. Новгород, 2006 г);

5. Научно-техническая конференция «Высокие технологии атомной отрасли. Молодёжь в инновационном процессе» (Н. Новгород, 2011,2012 г);

6. Семинары кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (Н. Новгород, 2007 - 2012 гг).

7. XIX международная конференция «Современное образование: содержание, технологии, качество» (Санкт-Петербург, 2013 г).

Публикации

Основное теоретическое и практическое содержание диссертации опубликовано в 17 печатных работах [1-17], в том числе 5 работ — в изданиях, рекомендованных ВАК к опубликованию основных научных результатов диссертаций на соискание учёных степеней доктора и кандидата наук [1-5], 10 работ — в материалах конференций [6-15], 2 — учебно-методические пособия [16, 17].

Структура и объём работы. Работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Основное содержание изложено на 144 страницах машинописного теста и иллюстрировано 39 рисунками. Список литературы состоит из 122 наименований.

Благодарность

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

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

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

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

В работе рассматривается БМК, в котором наряду с цифровыми элементами присутствуют и аналоговые. Все соединения реализуются одним слоем металлизации. В качестве дополнительного слоя используют шины поликремния. Все трассы должны проводиться по ортогональной сетке трассировки, контактные окна к слою поликремния не программируются (постоянные). Общая структура рассматриваемого аналого-цифрового БМК представлена на рисунке 1. В левой части кристалла располагаются аналоговые элементы, в правой — расположенные вертикальными рядами посадочные места для цифровых элементов. Аналоговые элементы, в отличие от цифровых, уже сформированы на кристалле. Проводя между ними коммутационные соединения можно на их основе формировать различные схемы. Для формирования цифровых библиотечных элементов, на посадочные места в правой части кристалла необходимо разместить фрагменты коммутационных соединений, которые сформируют библиотечный элемент.

11111111111 Обозначения:

1 =|ГПЁ ¡' I— 1 - цифровые контактные площадки;

2 г Ц И ||| ИI — 5 2 - аналоговые контактные площадки;

' "СО- И |! [ I— 6 3 - аналоговые элементы;

4 =Л1йЛ _ 4 - цифровые контактные площадки;

3 II "Ее:: |Ем[_ 5 - посадочные места для цифровых элементов;

I I I I 111 I I I I I I I I С! 6 - аналоговые контактные площадки.

Рисунок 1. Структура аналого-цифрового БМК

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

II 1 II I N I II

...... I I I I I Г

Рисунок

Работа посвящена исследованию и разработке моделей, алгоритмов для решения задачи синтеза топологии специализированных БИС и созданию на их основе системы синтеза топологии специализированных БИС в автоматизированном режиме на базе ЭВМ типа ЮМ РС.

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

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

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

Задача компоновки элементов схемы по столбцам может быть представлена как задача ¿-разбиения гиперграфа Н = (УН, ЕН, м/), где УН — множество вершин (соответствуют компонентам схемы); ЕН — множество гиперрёбер (соответствуют электрическим цепям); м>\УН^>Ы— отображение, определяющее для каждой вершины гиперграфа натуральное число (вес вершины, соответствует числу посадочных мест компонента), на к подграфов; к — фиксированное число (число столбцов посадочных мест). Главной целью разбиения гиперграфа является минимизация веса сечений (под сечением понимается множество гиперрёбер, которые целиком не попали в один из подграфов разбиения). При этом используется критерий направленный на минимизацию веса сечений. Также предлагается использовать композитные критерии, направленные помимо минимизации веса сечений, например, на обеспечение равномерности разбиения, то есть сокращения разницы суммарных весов подграфов разбиений. Равномерность распределения элементов схемы по площади кристалла ведёт к более равномерному распределению нагрева по поверхности, что положительно сказывается на работоспособности БИС.

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

(VI,..., V/,) определяет, какие элементы схемы попадут в один и тот же вертикальный столбец из посадочных мест, а значение критерия соответствует нижней оценке числа «горизонтальных» связей в задаче компоновки. Для решения декомпозиционных задач на гиперграфах большой размерности был использован многоуровневый подход. Ключевая идея многоуровневого алгоритма декомпозиции заключается в следующем: вместо того, чтобы строить ¿-разбиение непосредственно для исходного гиперграфа, сначала строится ряд его приближений («загрублений»). Каждое приближение уменьшает размерность исходной задачи. Процесс редукции продолжается до тех пор, пока порядок «затрубленного» гиперграфа не снизится до сотен или даже десятков. На гиперграфе таких размерностей и отыскивается начальное разбиение. Полученное решение используется для построения решения исходной задачи. Это достигается путём выполнения серии переносов решения задачи меньшей размерности на задачу большей размерности с последующим улучшением перенесённого решения. Таким образом, работу многоуровневого алгоритма можно разделить на три фазы: первая — фаза «загрубления» когда производится ряд последовательных редукций размерности задачи, вторая — фаза поиска начального разбиения и третья — фаза восстановления решения, когда производится серия последовательных переносов решения задачи меньшей размерности на менее редуцированную задачу. При этом производится улучшение спроецированного решения на основе итерационного алгоритма Алгоритм обменивает вершины из разных подграфов. В основе лежит принцип переноса гиперрёбер из сечения в один из подграфов разбиения с целью минимизации критерия.

Целью второго этапа алгоритма является определение такого положения столбцов относительно друг друга, при котором общая длина транзитных связей минимальна. Транзитной называется связь между элементами не смежных столбцов (например, между столбцами 1 и 3, 1 и 4,2 и 4, и т. п.). Для реализации транзитных связей приходится задействовать поликремниевые перемычки, расположенные между элементами в столбце, что негативно сказывается на электрофизических характеристиках схемы и усложняет трассировку в целом. Предлагается эвристический конструктивный алгоритм, состоящий из двух процедур — определение положения столбцов в круговом размещении и поиск оптимального места разрыва для перехода к линейному размещению (рисунок 2). Процедура определения кругового положения столбцов заключается в последовательном выборе вершин (из числа не размещённых) и нахождении для неё такой позиции, которая обеспечивает минимальную длину транзитных связей. Выбираются вершины по степени убывания числа связей с вершинами, размещёнными относительно друг друга.

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

связей. Во второй главе приведён пошаговый пример работы конструктивного алгоритма для графа связей столбцов. 8

На третьем этапе алгоритма выполняется размещение элементов внутри каждого столбца. Цель третьего этапа — размещение элементов внутри столбцов так, чтобы создать благоприятные условия для дальнейшей трассировки соединений в рамках столбца. При размещении элементов и последовательной трассировке соединений коммутационные свойства монтажного пространства изменяются. Предлагается методика оценки качества размещения, которая учитывает ряд ключевых показателей, оказывающих сильное влияние на эти свойства. Для оценки качества размещения элементов в пределах одного столбца предлагается три критерия: /Г1 — количество конфликтующих цепей (конфликтующие цепи реализуются, как правило, с помощью поликремниевых перемычек), Ь\ — «толщина» связей, — общая длина трасс. Под «толщиной» связей понимается максимальное количество параллельно идущих участков трасс, которые требуется реализовать в одном трассировочном канале (рисунок 3). Фактически, функцию можно считать нижней оценкой числа поликремниевых перемычек, которые пришлось бы задействовать для реализации цепей одного столбца

элементов внутри одного канала. _ - ■— - . .

Главное - обеспечить возможность Рисунок 3. Конфликтующие цепи (а) трассируемости, поэтому критерий и «толщина» связей (б)

имеет смысл использовать только в случае идентичности двух вариантов размещения с точки зрения двух других критериев. С другой стороны, как правило, уменьшение числа конфликтующих связей ^ напрямую влияет на толщину связей 7*2, поэтому сравнивать различные варианты размещения необходимо главным образом по первому критерию Т7!.

Для решения поставленной задачи (с заданным порядком критериев ^з) размещения элементов внутри отдельно взятого столбца предлагается гибридный алгоритм, в основе которого лежит эволюционно-генетическая адаптация в пространстве параметров задачи и итерационный улучшающий алгоритм, используемый в качестве процедуры локальной адаптации новых решений. Перестановка л = ..., к,„) кодирует относительное размещение т элементов в столбце. Оператор формирования начальной популяции генерирует N различных перестановок. Для перестановок применяются операторы ОХ-порядкового кроссовера и одноточечного обмена в качестве мутации. Оператор отбора — ранговая селекция. Алгоритм останавливается, когда популяция вырождается, то есть разнообразие популяции падает до одной особи. В качестве приспособленности особи выбрана функция вида:

|Д.(71) = М2-/м(л) + М-Р2(п) + 1<\(п), где М= |Щ[ — число цепей схемы.

Фактически, указанная свёртка ранжирует критерии по степени важности. В основе оператора локальной адаптации новых найденных решений в процессе генетического поиска лежит итерационный алгоритм, улучшающий решения. Он пытается улучшить качество решения, используя гибридную технику, основанную на принципах силовой укладки и метода «подъёма на холм». В работе показано, как описанный выше алгоритм может быть применён при проектировании БИС на основе БМК, обладающей

Й

а)

учасаж с максимальным ■ числом иараллип.пых учаспс»« трасс

б)

неравномерной структурой. Если БМК содержит аналоговые элементы, суть алгоритма остаётся прежней. Для аналоговых элементов предлагается использовать функцию приспособленности вида |л.(л) = /^(я), поскольку аналоговые элементы расположены нерегулярно. Число посадочных мест для аналоговых элементов пренебрежимо мало по сравнению с цифровыми, следовательно аналоговые элементы не оказывают существенного влияния на решение задачи размещения описанным алгоритмом.

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

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

подмножеств С] с V, / = 1,к , где СпС> = 0, у , ¿, \ .

Обозначим через Е, = (еД ..., е„) систему рёбер исходного графа С, где е'у е Е, 7 = 1, т . Обозначим через V, = (VI1,..., у„') множество вершин исходного графа С, на котором определена система рёбер Еи Будем говорить, что система рёбер реализует множество Су (или Е, — реализация множества С]) и обозначать £'/(Q), если С, п V, =С,. Будем называть Е1 трассой множества С] и обозначать Г,(С,), если граф С,( V,, Е,) является компонентой связности. Под решением задачи трассировки будем понимать систему трасс Т, = (Т,(С[),..., Т,(Ск)). Целью трассировки является построение непересекающейся системы трасс минимальной длины.

Сформулируем задачу как бикритериальную к

X ЦУАС^ПУ^С^тт

Т, 1 = 1

РАТ^тпт^У^С^тт

Т, 1=1 Т'

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

т' > (1)

где Ж— большая константа (например, число узлов на всём КП).

В дальнейшем под задачей трассировки будем понимать задачу поиска такой системы трасс, которая обеспечивает минимум критерия (1).

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

гибкой трассировке. КП разбивается на макродискреты и осуществляется глобальная трассировка на гиперграфовой модели. На последнем этапе выполняется трассировка внутри каждого макродискрета с использованием сеточной модели. Рассмотрим эти три этапа подробнее.

Предлагается новый принцип разбиения КП на прямоугольные макродискреты. Предлагаемая модель КП наряду с использованием макродискретов прямоугольной формы позволяет добиться линейной зависимости числа макродискретов от числа особых зон КП. В классической модели аналогового рабочего поля, любое внутреннее ребро является общим только для двух граней. В предлагаемой модели КП ребро может быть общим для большего числа граней. Построим разбиение КП с учётом «узких мест» КП. Разбиение предлагается строить в два этапа. На первом этапе из прямоугольной области КП исключаются прямоугольные участки особых зон — получаем непрямоугольный сегмент КП, границу которого можно представить как множество точек, соединённых отрезками. Полученный сегмент моделируем неориентированным помеченным графом Со, в котором вершины соответствуют точкам, рёбра - отрезкам. Каждой вершине приписываем метки, описывающие координаты расположения соответствующей точки в КП. Каждому ребру, отрезок которого граничит с контактной площадкой, приписываем метку, соответствующую данной контактной площадке. Всем остальным рёбрам приписываем метки, указывающие на нулевую пропускную способность. На рисунке 4а показан пример КП, соответствующий ему граф С0 — на рисунке 46. Для построения множества прямоугольных макродискретов выполняется последовательное разрезание непрямоугольных сегментов КП отрезками минимальной длины. На каждой итерации выделяется множество вершин графа Со со степенью два — данные вершины соответствуют точкам, где происходит излом границы непрямоугольных сегментов. Из каждой такой точки оцениваются длины вертикального и горизонтального разрезов (перпендикуляр, опускаемый до пересечения с особой зоной или до границы КП) некоторого сегмента. Выбирается разрез минимальной длины и моделируется введением в граф Со вершины (или пары вершин) и ребра. Алгоритм заканчивает свою работу, когда в графе Со не останется ни одной вершины со степенью два. Полученный граф С будем называть графом сетки макротрассировки (рисунок 4в). В процессе работы алгоритма каждому ребру, введённому в граф сетки макротрассировки, приписывается метка, описывающая пропускную способность соответствующего разреза — это максимальное число трасс, способных пересечь разрез без нарушения ограничений.

Разбиение КП будем моделировать гиперграфом Я, в котором вершины уе. НУ соответствуют рёбрам графа С сетки макротрассировки (или разрезам КП), а гиперрёбра ее НЕ - граням графа б (или макродискретам). Пример графа Сг и соответствующего ему гиперграфа Н приведён на рисунках 4в, г.

Предлагаемый подход позволяет перейти от сеточной модели КП к гиперграфовой модели КП меньшей размерности. Размерность гиперграфовой модели линейно зависит от числа особых зон. Эксперименты показали, что гиперграфовая модель КП цифровой части аналого-цифрового БМК имеет размерность приблизительно в 4 раза меньше, чем размерность

аналогичной модели графа-сетки. Подобная редукция размерности даёт существенный выигрыш в скорости работы алгоритмов.

о о

О - о О

3" з-

О О О 9' о ___о * О -

9'

О 8 О

д) е)

Рисунок 4

а — КП с двумя контактами (чёрные прямоугольники) и двумя зонами запрета трассировки (серые прямоугольники); б — соответствующий

граф Со; в — граф С? сетки макротрассировки; г — гиперграф Я, моделирующий КП; д,е — модификация структуры гиперграфа при прокладывании трассы на КП

Для данной гиперграфовой модели КП предлагается алгоритм трассировки, состоящий из двух этапов — макротрассировка на гиперграфовой модели и фиксации трасс внутри макродискретов.

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

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

2) с учётом пропускных способностей вершин находится кратчайший маршрут от начальной вершины до некоторого элемента гиперграфа, который соответствует фрагменту трассируемой цепи;

3) модифицируется структура гиперграфовой пересчитываются пропускные способности вершин.

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

модели КП и

последовательно, порядке убывания

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

На финальном этапе трассировки устраняются пересечения и производится окончательная фиксация трасс внутри областей. Порядок трассировки предлагается определять с помощью

эволюционно-генетического алгоритма (ГА). Участки трасс нумеруются. Решения кодируются перестановками из номеров участков трасс конфликтной области КП. Классический алгоритм последовательной трассировки Ли используется в качестве декодера, который по перестановке однозначно строит трассы внутри области. Для решения задачи трассировки соединений БИС все описанные выше подходы можно применять совместно друг с другом, организуя при этом многопроходные схемы. Основные этапы многопроходных схем: начальная трассировка соединений, анализ текущей ситуации на КП, дотрассировка не разведённых соединений, оптимизация трасс, интерактивность автоматический подбор алгоритмов на разных этапах трассировки. Многопроходные схемы могут быть применены к трассировке БИС на основе аналого-цифрового БМК с одним слоем металлизации.

В четвёртой главе рассмотрены особенности программной реализации разработанных алгоритмов в системе синтеза топологии «Синтез». Разработанная ПС «Синтез» предназначена для выполнения автоматизированного синтеза топологии аналого-цифровых и цифровых БИС

13

на основе БМК с одним слоем металлизации (КМОП, КМОП-КНС-технология с поликремниевыми вставками). ПС «Синтез» позволяет выполнять размещение элементов проекта и трассировку соединений в автоматизированном и ручном режимах. При трассировке соединений не делается различия между аналоговыми и цифровыми элементами, то есть разводка трасс осуществляется для всего проекта в целом. ПС «Синтез» обладает графическим интерфейсом, с помощью которого можно управлять процессами и настраивать необходимые значения, а также осуществлять корректировку топологии в ручном режиме.

При разработке ПС «Синтез» учитывались принципы создания САПР (принципы включения, системного единства, развития, комплексности, информационного единства, совместимости, стандартизации).

Вся исходная информация для решения задачи синтеза топологии передаётся в файлах в форматах LEF, DEF, PEF. Форматы LEF (Library Exchange Format) и DEF (Design Exchange Format) — известные форматы обмена библиотеками и проектами соответственно, которые используются САПР различных фирм (в том числе Cadence Design Systems, Synopsys). Для описания постоянных фрагментов поликремниевых перемычек был разработан собственный текстовый формат PEF. После завершения работы проект сохраняется в файл формата DEF.

Программная система «Синтез» состоит из 17 подсистем, приведены назначение каждой из них и их функции. Все компоненты системы реализованы на объектно-ориентированном языке С#.

В пятой главе описано применение разработанной системы синтеза топологии в сквозном маршруте проектирования БИС на основе аналого-цифрового БМК, основанном на модулях фирмы Cadence Design Systems (рисунок 5).

Маршрут состоит из 7 этапов (подготовительный, разработка структурной схемы, схемотехническое проектирование, синтез топологии, верификация топологии, подготовка конструкторской документации, формирование архива проекта). ПС «Синтез» используется на четвёртом этапе (синтез топологии). При этом ПС «Синтез» может функционировать и отдельно (обеспечивая размещение элементов БИС и трассировку соединений), при условии наличия входной информации о кристалле в формате LEF и floorplan (планировка кристалла) и информации о проекте в формате DEF. ПС «Синтез» обеспечивает работу в двух режимах — размещение элементов осуществляется средствами САПР фирмы Cadence Design Systems (модуль SoC Encounter), ПС «Синтез» при этом используется для трассировки соединений (левая ветвь на рисунке 5); размещение элементов и трассировка осуществляются в ПС «Синтез» (правая ветвь на рисунке 5). Описываются все этапы сквозного маршрута проектирования и необходимые технические и программные средства, информационное обеспечение (ИО). Также описывается процесс создания необходимого ИО для функционирования ПС «Синтез».

Для описания библиотечной информации о кристалле и стандартных элементах используется файл формата LEF. Описан процесс создания LEF-файла, в том числе определение координат элементов, описание их посадочных мест и расположения контактов. Приведены примеры описаний 14

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

Техническое задание-Нподготовительный| дтоп і

^ ^Программные средства

| Разработка 'лруктурной схемы | Этап 2

Схема электрическая структурная

Рисунок 5. Маршрут проектирования БИС

Средства описания постоянных фрагментов поликремниевых перемычек в модуле SoC Encounter отсутствуют. В связи с этим был разработан собственный формат описания поликремниевых перемычек — формат PEF. Описан синтаксис файла PEF и показан пример указания координат и типов поликремниевых перемычек. Для получения списка связей (netlist) проекта в формате Verilog из базы данных DFII используется программа Virtuoso NC Verilog, входящая в состав САПР Cadence. Эта среда может быть вызвана непосредственно из схемотехнического редактора (Virtuoso Schematic Editor). Показан принцип формирования списка связей в формате Verilog. Решение задачи синтеза топологии осуществляется с помощью графического интерфейса пользователя ПС «Синтез». После

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

С помощью ПС «Синтез» был выполнен синтез топологии для трёх проектов БИС, разрабатываемых в рамках ОКР «БИС-АБМК». Краткая характеристика третьего проекта: число цепей — 530, число элементов проекта — 499 (процент заполнения 95%), длина трасс по металлу — 3236 мкм, длина трасс по поликремнию — 224 мкм.

Для подтверждения корректности проекта в САПР Cadence была выполнена верификация топологии: выполнена проверка выполнения норм КТО, осуществлено сравнение схемы, извлечённой из топологии с исходной схемой. Полученные положительные результаты позволяют сделать вывод о корректности выполнения синтеза топологии БИС на основе аналого-цифрового БМК в ПС «Синтез».

Основные результаты работы

В работе поставлены, формализованы и типизированы проектные процедуры размещения элементов и трассировки связей специализированных БИС на основе аналого-цифрового БМК, имеющих нерегулярную структуру и изготавливаемых по технологии с одним слоем коммутации и с фиксированными вставками поликремния в качестве второго слоя трассировки.

В результате были решены следующие задачи:

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

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

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

4. Разработана программная система, позволяющая выполнять синтез топологии (автоматизированное размещение элементов и автоматизированную трассировку связей) однослойных БИС на основе БМК, в том числе обладающих нерегулярной структурой. Помимо автоматизированного режима система позволяет осуществлять ручную корректировку топологии разрабатываемого проекта. Система работает на этапе синтеза топологии в сквозном маршруте проектирования, построенном на модулях фирмы Cadence Design Systems. Совместимость системы с модулями Cadence достигается за счёт использования входных и выходных файлов в форматах LEF и DEF. Поскольку данные файлы имеют текстовый формат, это позволяет осуществлять настройку на любую конфигурацию 16

кристалла и любой библиотечный базис. Разработанная ПС «Синтез» может использоваться как на этапе трассировки соединений, так и полностью выполнять синтез топологии, решая задачи размещения элементов проекта и прокладки трасс.

5. Разработан сквозной маршрут проектирования аналого-цифровых БИС на основе БМК с одним слоем коммутации. Для обеспечения этапа синтеза топологии был разработан комплект информационного обеспечения САПР, описывающий аналого-цифровой БМК. В дополнение к существующим форматам был разработан собственный формат представления данных о поликремниевых перемычках — текстовый формат PEF.

Выполнена апробация системы на трёх проектах БИС на основе аналого-цифрового БМК (КМОП-технология на объёмном кремнии с проектными нормами 2,6 мкм), разработанных в рамках ОКР «БИС-АБМК». Полученные положительные результаты позволяют сделать вывод о корректности разработанных алгоритмов и работы системы в целом.

Список опубликованных работ по теме диссертации

Публикации в изданиях, рекомендованных ВАК РФ:

1. Балашов В. В. Исследование методов автоматизированной трассировки однослойных структур [Текст] / БатищевД. И., Власов С. Е., Балашов В. В. // Известия Государственного электротехнического универститета. Сер. Информатика, управление и компьютерные технологии. 2005. Вып. 1. С. 40-44.

2. Балашов В. В. Разработка алгоритмов распространения волны по макродискретам для однослойных структур [Текст] / БатищевД. И., Власов С. Е., Балашов В. В. // Известия Государственного электротехнического универститета. Сер. Информатика, управление и компьютерные технологии. 2006. Вып. 1. С. 17-21.

3. Балашов В. В. Использование гиперграфов для решения задачи ортогональной трассировки БИС с нерегулярной структурой [Текст] / Старостин Н. В., Балашов В. В. // Радиотехника и электроника. 2008. Т. 53, №5. С. 618-623.

4. Балашов В. В. Эволюционно-генетический алгоритм линейного размещения цифровых элементов интегральных схем [Текст] / Старостин Н. В., Филимонов А. В., Балашов В. В. // Системы управления и информационные технологии, 2009. №1 (35). С. 64-68.

5. Балашов В. В. Решение задачи размещения элементов специализированных БИС на основе БМК [Текст] / Старостин Н. В., Филимонов А. В., Балашов В. В. // Системы управления и информационные технологии. 2009. 2.1 (36) С. 189-194.

Другие статьи, материалы конференций:

6. Балашов В. В. Разработка и внедрение современных методов проектирования БИС [Текст] / Балашов В. В. // Материалы VII Нижегородской сессии молодых учёных. Техническое направление. Н. Новгород, 2002. С. 86-88.

7. Балашов В. В. Разработка информационного обеспечения сквозного маршрута проектирования микроэлектронной аппаратуры [Текст]

17

/ Балашов В. В., Власов С. Е. // Материалы всеросийской науч.-технич. конференции «Информационные системы и технологии ИСТ-2004». Н. Новгород, 2004. С. 90-91.

8. Балашов В. В. Алгоритмы распространения волны по макродискретам [Текст] / Балашов В. В. // Материалы IV междунар. науч.-технич. конф. «Будущее технической науки». Н. Новгород, 2005. С. 37.

9. Балашов В. В. Алгоритм разбиения коммутационного поля минимальными разрезами [Текст] / Балашов В. В., Старостин Н. В. // Материалы всероссийской конф. «Технологии Microsoft в теории и практике программирования». Н. Новгород, 2006. С. 28-29.

10. Балашов В. В. Использование гиперграфовой модели для гибкой трассировки соединений специализированных БИС [Текст] / Старостин Н. В., Балашов В. В. // Вестник Нижегородского университета им. Н. И. Лобачевского. Математическое моделирование и оптимальное управление. 2007. №6. С. 134-139.

11. Балашов В. В. Разработка алгоритма автоматизированного размещения элементов для БМК с нерегулярной структурой [Текст] / Балашов В. В. // Материалы VI междунар. молодёжной науч.-технич. конф. «Будущее технической науки». Н. Новгород, 2007. С. 67-68.

12. Балашов В. В. Применение генетических алгоритмов для решения задачи размещения элементов БИС [Текст] / Балашов В. В. // Материалы междунар. науч.-технич. конф. «Информационные системы и технологии ИСТ-2008» Н. Новгород, 2008. С. 182.

13. Балашов В. В. Прокладка соединений специализированных БИС на основе псевдотрассировки и эволюционно-генетического поиска [Текст] / Батищев Д. И., Власов С. Е., Старостин Н. В., Балашов В. В. // Материалы отраслевой науч.-технич. конф. «Высокие технологии атомной отрасли. Молодёжь в инновационном процессе». Н. Новгород, 2011. С. 192-195.

14. Балашов В. В. Разработка маршрута аналого-цифрового моделирования [Текст] / СорокинА. Н., Михайлов А. С., Балашов В. В. // Материалы отраслевой науч.-технич. конф. «Высокие технологии атомной отрасли. Молодёжь в инновационном процессе». Н. Новгород, 2012. С. 120-123.

15. Балашов В. В. Применение автоматизированной системы проектирования специализированных БИС в образовательном процессе [Текст] / Балашов В. В. // Материалы XIX международной конференции «Современное образование: содержание, технологии, качество». Том 1. СПб., СПбГЭТУ, 2013. С. 144-145.

16. Балашов В. В. Автоматизация проектирования цифровых микроэлектронных устройств [Текст] / Костюков В. Е., Власов С. Е., Балашов В. В. // Методическое пособие. Н. Новгород: ННГУ, 2004. 32 с.

17. Балашов В. В. Математические модели, задачи и алгоритмы синтеза топологии специализированных интегральных схем [Текст] / Батищев Д. И., Власов С. Е., Старостин Н. В., Филимонов А. В., Балашов В. В. // Учебно-методическое пособие. Н. Новгород: ННГУ, 2010. 72 с.

Подписано в печать 01.07.13. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 2,0. Тираж 100 экз. Заказ 67.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В. И. УЛЬЯНОВА (ЛЕНИНА)

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

04201362649 Балашов Вадим Владимирович

РАЗРАБОТКА АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ СИНТЕЗА ТОПОЛОГИИ СПЕЦИАЛИЗИРОВАННЫХ БОЛЬШИХ

ИНТЕГРАЛЬНЫХ СХЕМ

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

(промышленность)

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель — доктор технических наук, С. Е. Власов

Санкт-Петербург 2013 год

стр.

Оглавление

ВВЕДЕНИЕ.............................................................................................................6

ГЛАВА 1. Синтез топологии специализированных БИС на основе БМК.........13

1.1 Специализированные типы интегральных схем в радиоэлектронной аппаратуре..........................................................................................................13

1.2 Особенности конструкции аналого-цифрового БМК с одним слоем металлизации.....................................................................................................19

1.3 Математические модели и методы решения задачи размещения элементов...........................................................................................................22

1.4 Математические модели и методы решения задачи трассировки соединений........................................................................................................28

1.5 Содержательное описание задачи синтеза топологии специализированных БИС................................................................................35

1.6 Выводы.........................................................................................................37

ГЛАВА 2. Математическая модель, постановка оптимизационной задачи размещения элементов, алгоритмы решения.......................................................38

2.1 Общая математическая модель и постановка оптимизационной задачи размещения элементов при проектировании БИС на основе БМК................38

2.1.1 Исходные параметры математической модели..................................39

2.1.1 Задача минимизации суммарной длины соединений.........................42

2.2 Алгоритм решения задачи размещения элементов при проектировании БИС на основе БМК..........................................................................................42

2.2.1 Поэтапная схема решения задачи размещения...................................43

2.2.2 Компоновка элементов схемы по столбцам........................................44

2.2.3 Размещение столбцов с минимизацией транзитных связей...............47

2.2.4 Методика оценки качества линейного размещения............................52

2.2.5 Многокритериальная задача линейного размещения.........................57

2.2.6 Гибридный метод решения задачи.......................................................57

2.2.7 Особенности генетического алгоритма...............................................58

2.2.7 Итерационный алгоритм улучшения решений...................................58

2.3 Выводы.........................................................................................................60

ГЛАВА 3 Математическая модель, постановка оптимизационной задачи трассировки, алгоритмы решения........................................................................61

3.1 Общая математическая модель и постановка оптимизационной задачи трассировки элементов при проектировании БИС на основе БМК...............61

3.2 Графовая модель коммутационного пространства и алгоритм трассировки соединений БИС..........................................................................63

3.3 Декомпозиция КП и его гиперграфовая модель........................................64

3.4 Алгоритм трассировки соединений на гиперграфовой модели................68

3.4.1 Выбор контактной площадки...............................................................68

3.4.2 Поиск маршрута на гиперграфовой модели........................................69

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

3.4.4 Микротрассировка................................................................................74

3.5 Многопроходные схемы трассировки........................................................81

3.6 Выводы.........................................................................................................82

ГЛАВА 4 Диалоговая программная система «Синтез» решения задачи синтеза топологии специализированных БИС..................................................................83

4.1. Архитектура программной системы решения задачи синтеза топологии ............................................................................................................................86

4.2. Типовые сценарии работы программной системы «Синтез»..................90

4.3. Выводы......................................................................................................104

ГЛАВА 5 Практическое применение программной системы «Синтез» в сквозном маршруте проектирования..................................................................105

5.1 Взаимодействие ПС «Синтез» с САПР Cadence......................................105

5.2 Подготовка исходных данных для работы программной системы «Синтез»...........................................................................................................114

5.3 Решение задачи проектирования специализированной БИС с использованием программной системы «Синтез»........................................122

5.4 Выводы.......................................................................................................126

Выводы и заключение.........................................................................................127

Список литературы..............................................................................................129

ПРИЛОЖЕНИЕ 1................................................................................................142

ПРИЛОЖЕНИЕ 2................................................................................................144

Перечень условных сокращений

DEF — Design Exchange Format, известный формат обмена проектами,

который используется САПР различных фирм (в том числе

Cadence Design Systems, Synopsys)

GDSII — двоичный промышленный формат, представляющий данные о

топологической информации в иерархическом виде LEF — Library Exchange Format — известный формат обмена

библиотеками, который используется САПР различных фирм

(в том числе Cadence Design Systems, Synopsys)

PEF — текстовый формат собственной разработки, содержащий

информацию о поликремниевых перемычках на кристалле Verilog — язык описания аппаратуры

АРП — аналоговое рабочее поле

БИС — большая интегральная схема

БМК — базовый матричный кристалл

ВКП — внешняя контактная площадка

ДРП — дискретное рабочее поле

ИО — информационное обеспечение

КП — коммутационное поле

КТО — конструкторско-технологические ограничения

НЖМД — накопитель на жёстком магнитном диске

ОС — операционная система

ПЛМ — программируемая логическая матрица

ПО — программное обеспечение

ПС — программная система

САПР — система автоматизированного проектирования

СБИС — сверхбольшая интегральная схема

ТЗ — техническое задание

ВВЕДЕНИЕ

Актуальность

Процесс изготовления больших интегральных схем (БИС) состоит из нескольких сотен сложных операций, вследствие чего даже при высоком выходе годных на каждой стадии процесса общий процент выхода годных изделий (от стадии обработки сырья до стадии готового изделия) остаётся довольно низким [47,70].

Для аналоговой и аналого-цифровой техники (микросборки и пр.), функциональных устройств микроэлектроники, то есть устройств с существенно нерегулярной структурой и, в особенности, с однослойной коммутацией, существующие конструкторские САПР либо недостаточно эффективны, либо вообще не пригодны. Так ни один из модулей трассировки коммерческих современных САПР (в том числе и ведущих фирм Cadence Design Systems, Mentor Graphics, Synopsys) не позволяет осуществлять разводку соединений БИС на БМК с однослойной коммутацией с поликремниевыми перемычками. Это связано с тем, что все современные САПР ориентированы на заказные схемы, выполняемые по технологии с несколькими слоями металлизации. В частности, современный программный модуль автоматизированной трассировки SoC Encounter одной из ведущих западных фирм Cadence Design Systems может учитывать различные антенные эффекты в проводниках, возникающие наводки на соседних трассах, и ряд других физических эффектов, появляющихся при использовании субмикронных технологий, но не рассчитан на однослойную трассировку.

Актуальность БИС на основе БМК с однослойной коммутацией до сих пор остаётся высокой. Это обуславливается тем, что для разработки проекта БИС на основе такого БМК достаточно спроектировать и изготовить только один фотошаблон переменного слоя металлизации (при условии что сам БМК уже сформирован). Это повышает качество и уменьшает стоимость разработки.

Одной из разработок последних лет являются структурированные БМК [107, 108, 110, 111]. В отличие от классического БМК, структурированный БМК состоит из предопределённых логических ячеек и

конфигурируемых ячеек памяти в форме массивов. Каждая из логических ячеек содержит комбинационную логику, управляемую пользователем, для создания сумматоров, мультиплексоров, триггеров и так далее. Структурированные БМК могут включать цепи синхронизации, встроенные IP-компоненты и тому подобное. Фактически, структурированные БМК содержат уже реализованные функциональные элементы более высокого уровня сложности, чем классический БМК [102, 116, 118, 119, 121, 122].

Таким образом, структурированные БМК предлагают производительность, потребление энергии и цену конечного продукта БИС наряду с короткими сроками разработки ПЛИС. Западные разработчики считают, что подобный тип ИС может вытеснить ПЛИС в качестве предварительного этапа отработки схем [105, 106, 109].

Слои, в которых реализованы данные функциональные элементы, являются фиксированными для БМК. Неопределёнными остаются несколько верхних слоев (от одного до трёх). С их помощью определяются межсоединения проекта. Таким образом, современный структурированный БМК может выполняться по технологии с одним слоем металлизации, используя фиксированные участки первого слоя для реализации пересечений.

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

Большой вклад в разработку методов и систем автоматизированного проектирования внесли работы учёных Абрайтиса Л. Б., Анисимова В. И., Базилевича Р. П., Батищева Д. И., Бершадского А. М., Герасимова И. В., Дмитревича Г. Д., Курейчика В. М., Львовича А. Я., Норенкова И. П. и других российских и зарубежных специалистов.

Цель и задачи исследований

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

специализированных БИС на основе аналого-цифрового БМК, имеющих нерегулярную структуру и изготавливаемых по технологии с одним слоем коммутации и с фиксированными вставками поликремния в качестве второго слоя трассировки.

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

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

2. Исследование и разработка алгоритмов решения задачи размещения элементов;

3. Разработка алгоритма трассировки, основанного на новой модели коммутационного поля;

4. Разработка программной системы, позволяющей выполнять синтез топологии однослойных БИС на основе БМК (в том числе обладающих нерегулярной структурой).

5. Разработка маршрута проектирования БИС на основе аналого-цифрового БМК с применением программной системы синтеза топологии.

Научная новизна работы

Научная новизна работы заключается в следующем:

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

2. Разработана гиперграфовая модель коммутационного пространства (КП) для задачи трассировки соединений, которая, в отличие от классических моделей, содержит не только информацию о топологических особенностях кристалла, но и информацию об «узких местах» КП;

3. Разработан многоэтапный алгоритм размещения элементов,

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

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

5 Разработан алгоритм локальной трассировки, основанный на графовой модели КП, который осуществляет разводку трасс внутри макродискретов.

Основные положения, выносимые на защиту

1. Математическая модель, алгоритм размещения, основанный на декомпозиции задачи;

2. Математическая модель, алгоритмы трассировки, основанные на графовых моделях коммутационного пространства;

3. Программная система синтеза топологии (ПС «Синтез»);

4. Сквозной маршрут проектирования аналого-цифровых БИС на основе БМК с одним слоем коммутации.

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

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

Достоверность результатов

Диссертация подготовлена на кафедре систем автоматизированного проектирования в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Санкт-Петербургский

государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина)» в обеспечение опытно-конструкторской работы «Разработка аналого-цифрового БМК для применения в технических средствах защиты» (шифр «БИС-АБМК»), выполняемой во ФГУП «ФНПЦ НИИИС им. Ю. Е. Седакова». Достоверность разработанных алгоритмов и методов подтверждается работоспособными образцами трёх проектов, разработанными с помощью ПС «Синтез».

Апробация работы

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

1. 7-ая Нижегородская сессия молодых учёных (Н. Новгород, 2002 г);

2. Всероссийская научно-техническая конференция «Информационные системы и технологии ИСТ-2004» и «ИСТ-2008» (Н. Новгород, 2004, 2008 г);

3. IV и VI международная научно-техническая конференция «Будущее технической науки» (Н. Новгород, 2005, 2007 г);

4. Всероссийская конференция «Технологии Microsoft в теории и практике программирования» (Н. Новгород, 2006 г);

5. Научно-техническая конференция «Высокие технологии атомной отрасли. Молодёжь в инновационном процессе» (Н. Новгород, 2011, 2012 г);

6. Семинары кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (Н. Новгород, 2007 - 2012 гг).

7. XIX международная конференция «Современное образование: содержание, технологии, качество» (Санкт-Петербург, 2013 г).

Внедрение результатов работы

Разработанная система проектирования топологии БИС на основе аналого-цифрового БМК внедрена во ФГУП «ФНПЦ НИИИС им. Ю. Е. Седакова» (см. приложение 1 — акт внедрения разработанной системы).

Результаты работы внедрены в учебный процесс факультета

вычислительной математики и кибернетики при преподавании специального курса «Автоматизация проектирования цифровых микроэлектронных устройств» в ННГУ им. Н. И. Лобачевского [69] (см. приложение 2 — акт внедрения в учебный процесс).

Основные результаты диссертации отражены в 17 печатных работах [13, 14, 15, 16, 17, 18, 19, 20, 26, 27, 36, 69, 88,91,92, 95, 96], в том числе 5 работ— в изданиях, рекомендованных ВАК к опубликованию основных научных результатов диссертаций на соискание учёных степеней доктора и кандидата наук [26, 36, 91, 95, 96], 10 работ — в материалах конференций [13, 14, 15, 16, 17, 18, 19, 20, 88, 92], 2 — учебно-методические пособия [27, 69].

Структура и объём работы

Работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Основное содержание изложено на 144 страницах машинописного теста и иллюстрировано 39 рисунками. Список литературы состоит из 122 наименований.

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

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

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

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

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

В четвёртой главе рассмотрены особенности программной реализации системы синтеза топологии. Описана архитектура системы, рассмо�