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



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

РИХТЕР Маргарита Робертовна

ОПТИМИЗАЦИЯ ПРОЦЕССА РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ НА КРИСТАЛЛЕ ЦИФРОВОЙ ИНТЕГРАЛЬНОЙ СХЕМЫ ПРИ НАЛИЧИИ ТЕХНОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ

Специальность 05.13.01 Системпый анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

г з мдп ¿013

Уфа-2013

005059836

005059836

Работа выполнена в ФГБОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной математики и кибернетики

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

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

д-р техн. наук, профессор Валеева Аида Фаритовна

д-р техн. наук, профессор Ефанов Владимир Николаевич проф. каф. биомедицинских систем и электроники ФГБОУ ВПО «Уфимский государственный авиационный технический университет» в г. Уфа

д-р ф-м. наук, профессор Маликов Рамиль Фарукович

зав. каф. полиграфических и информационных систем и технологий ФГБОУ ВПО Башкирский государственный педагогический университет им. М. Акмуллы

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

Башкирский государственный университет

Защита диссертации состоится 14 июня 2013 в 10 часов на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа-центр, ул. К. Маркса, 12

С диссертацией можно ознакомиться в научной библиотеке университета

Автореферат разослан «13» мая 2013г.

Ученый секретарь диссертационного совета, д-р техн. наук, проф.

В.В. Миронов

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

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

Задача размещения элементов на кристалле состоит из двух этапов: планирование размещения элементов на кристалле и физическое соединение этих элементов (трассировка).

Задачи планирования, и трассировки рассматриваются в работах отечественных и зарубежных авторов (С. Zhuang, К. Sakanushi, L. Jin, Y. Kajitani, M. Burstein, D. Rautenbach, E. Aurts, K. Lenstra, S. Koranne, К. В. Корняков, В. В. Емельянов, В. М. Курсйчик, В. В. Курейчик, А. И. Ерзип, Л. А. Гладков, О. Б. Лебедев, И. Н. Ерошенко, Г. Г. Забудский, В. К. Попков, В. А. Шахнов, А. В. Назаров и другие).

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

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

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

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

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

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

2. Разработать математическую модель для задачи трассировки при наличии технологических ограничений.

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

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

5. Исследовать эффективность предложенного алгоритма с помощью численного эксперимента.

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

На защиту выносятся:

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

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

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

4. Алгоритм декодера, осуществляющий размещение и соединение элементов на кристалле при наличии технологических ограничений с учетом теплового критерия.

5. Программное обеспечение па основе предложенного алгоритма при наличии технологических ограничений на примере фрагмента схемы.

Научная новизна результатов диссертационного исследования:

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

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

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

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

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

Практическую значимость имеют следующие результаты:

1. Разработанный алгоритм для решения задачи трассировки при размещении элементов на кристалле цифровой интегральной схемы при наличии технологических ограничений с учетом теплового критерия принят в качестве методического обеспечения в ОАО «БПО «Прогресс» при создании системы автоматизированного размещения и соединения элементов на печатных платах. Применение предлагаемого алгоритма позволило понизить температуру внутри корпуса разрабатываемых изделий, а также снизить интенсивность отказов за счет создания зон с пониженной температурой среды вокруг элементов, критичных к повышенной температуре.

Связь исследования с научнымн проблемами

Исследование проводилось в рамках научного гранта Российского фонда фундаментальных исследований (РФФИ) № 13-07-00579.

Апробация работы и публикации

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

• VII Всероссийская зимняя школа-семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники», УГАТУ, Уфа 2012г.

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

• Международная конференция «Компьютерные науки и информационные технологии» (CSIT), Уфа, 2012г.

® Международная молодежная конференция «Интеллектуальные технологии обработки информации и управления», Уфа, 17-20 июля 2012г.

Публикации. По теме диссертации опубликовано 7 работ: 6 статей, в том числе 2 в рецензируемых журналах ВАК и в сборниках трудов конфе-

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

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 149 страницах машинописного текста, кроме того содержит 59 рисунков. Библиографический список включает 107 наименований и занимает 9 страниц.

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

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

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

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

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

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

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

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

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

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

Задача размещения элементов на кристалле цифровой интегральной схемы сводится к JVP-трудной квадратичной задаче о назначениях.

Имеются:

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

Нагревающие элементы - это активные элементы, выделяющие тепло в большом количестве. К ним относятся транзисторы, диоды, лампы.

Пассивные элементы - это элементы, которые почти не выделяют тепло. К ним относятся резисторы, конденсаторы, катушки индуктивности.

б) Структурная схема, отражающая взаимное расположение элементов и соединения между ними.

Требуется получить такое размещение элементов на кристалле, при котором:

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

2) расположение элементов и соединения между ними удовлетворяли бы следующим технологическим ограничениям (задача трассировки):

1. Ребра всех элементов (блоков) параллельны сторонам кристалла;

2. Каждый элемент не перекрывается с любым другим элементом;

3. Каждый элемент не пересекается со сторонами кристалла, т.е. не выходит за его границы;

4. Соединения не должны пересекаться и накладываться друг на друга;

5. Допустимое расстояние между проводниками: 3-4 мкм;

6. Минимально допустимая длина проводника 4 мкм;

7. Минимально допустимая ширина проводника 3 мкм;

8. Нагревающие (тепловыделяющие) элементы должны располагаться ближе к теплоотводящим краям кристалла;

9. Пассивные элементы должны располагаться ближе к центру кристалла.

На рисунке 1 показаны основные этапы процесса размещения элементов на кристалле цифровой интегральной схемы.

Первый этап подразумевает разбиение функциональной схемы на элементы (рисунок 1а).

Второй этап - планирование размещения элементов на кристалле (рисунок 16). Под планированием понимается разбиение кристалла на п прямоугольников (комнат), каждая из которых содержит по одному элементу (рисунок 16). Область, в которую помещается элемент, называется комнатой. Совокупность комнат, полученных при разбиении, называется планом {floor-plan) (план не включает размещаемые элементы) (С. Zhuang, К. Sakanushi, L. Jin, Y. Kajitani, 2002 г.). При этом требуется найти размещение элементов

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

Третий этап размещения - физическое соединение элементов на кристалле (трассировка) (рисунок 1в).

Рисунок 1 — Этапы процесса размещения элементов на кристалле интегральной схемы

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

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

п - общее количество прямоугольников (элементов);

= (м>1, ...,м>ь где м>1 - ширина г-го прямоугольника (откладывает-

ся на оси ОХ);

к = (к1, ...,ИЬ ...,кп), где Л, — высота г-го прямоугольника (откладывается на оси ОУ);

г — признак направления прямоугольников (элементов): 1, если прямоугольники можно поворачивать на 90°

0, иначе

Решение задачи можно представить в виде следующего набора данных: Б=<Х; У; Т>, где

Х=(х!,...,хи ...,х„), где х,-- координата г-го прямоугольника по оси ОХ, 1 У=(уь -,уи —,Уп), где у, - координата г-го прямоугольника по оси ОУ, 1

где Н =

1, если г'-й прямоугольник повернут на 90°

1 =1 ,п

О, иначе

Если г=О, то Т=0.

Задача трассировки.

Дано: кристалл с размещенными на нём элементами (прямоугольниками) (рисунок 2); структурная схема 5, на которой заданы взаимное расположение элементов и соединения между ними (рисунок 3).

Рисунок 2 - Кристалл с размещенными на нём элементами (прямоугольниками)

Рисунок 3 - Структурная схема, на которой заданы взаимное расположение элементов и соединения между ними

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

Математическая модель задачи трассировки. Структурную схему интерпретируем плоским неориентированным графом 0=(У,Е) (рисунок 4), где V - число вершин графа, Е - число ребер графа. Вершинами в графе С являются элементы, ребрами — соединения между элементами.

Дано: неорграф й = (У,Е), где У={у,,..,ут} - множество вершин (элементов для размещения на кристалле), Е - {е;,...,е„} - множество ребер (соединений между элементами), V - подмножество помеченных вершин, соответствующих нагревающим (тепловыделяющим) элементам, УСУ (на рис.4 V = {4;8}).

Требуется найти плоское изображение графа О = (У,Е) (т.е. должно выполняться: п - т +/= 2, где и - число вершин, т - число ребер, /- число граней графа) при следующих технологических ограничениях:

1. Ребра не должны пересекаться и накладываться друг на друга (е,Пе/=0, Ш

2. Допустимое расстояние между ребрами: 3-4 мкм (й?(еье,)<4);

3. Минимально допустимая длина 1(е,) ребра 4 мкм (/(е,)= 4 мкм);

4. Минимально допустимая толщина м>(е,) ребра 3 мкм (и>(е,)= 3 мкм).

5. Нагревающие (тепловыделяющие) элементы должны располагаться ближе к теплоотводящим краям кристалла: пусть М, = {1,...,£} - множество тепловыделяющих элементов, а, - нижняя теплоотводящая граница кристалла, Ь, - правая теплоотводящая граница кристалла. Если текущий элемент

1 1 ь 7

г;

8

А

I ' 3 ' 1 ^ Тт] щ

7 :;б 1; 1 -31!=!.

i e Mn т. e. t.—>max, где — температура элемента, то необходимо разместить этот элемент ближе к теплоотводящим краям кристалла а, или bh т. е. г—>• at или I—» b

6. Пассивные элементы должны располагаться ближе к центру кристалла: пусть Mj ={1,...,/} - множество пассивных элементов, ZKp - центр кристалла, Если текущий элемент izMJ: т. е. i,—>min, где f; - температура элемента, то необходимо разместить этот элемент ближе к центру поля размещения кристалла, т. е. i—* ZKp

рованным графом 0(У,Е)

Общая схема алгоритма решения задачи трассировки при размещении элементов на кристалле цифровой интегральной схемы

Вход: план Р с размещёнными по «комнатам» элементами (прямоугольниками), полученный на базе алгоритма локального спуска. Среди элементов имеются нагревающие (тепловыделяющие) М1 = {1 ,...,£} и пассивные

Ц={\,...,!};

структурная схема 5 соединений элементов.

Выход: план Р с соединенными проводниками элементами в соответствии со структурной схемой удовлетворяющий ограничениям (1-9) (с. 9).

Шаг 1. Соединение элементов плана Р проводниками в соответствии со структурной схемой

Шаг 2. Построение графа О = (У,Е'), соответствующего схеме 5, в котором вершины V - это элементы, а ребра Е - проводники, соединяющие элементы, V а V, где V - подмножество нагревающих (тепловыделяющих) элементов М,-.

Шаг 3. Если имеются пересечения проводников, то применяем алгоритм проверки планарности графа на базе проъ^едур генетического алгоритма (В. В. Емельянов, В. М. Курейчик, В. В. Курейчик, 2002 г.), который строит базис циклов Вр, где р—т-п+2, т - число ребер графа, п - число вершин графа.

Если граф С=(У,Е) - планарный (1Ч^=2т), где /у,- - число ребер, принадлежащих первым р циклам, т - число ребер графа, то сформировать приоритетный список ребер (соединений) по базису циклов, соответствующему плоской укладке графа, и перейти к шагу 4.

Если граф С=(У,Е) - непланарный (У)П2т), то сформировать приоритетный список ребер (соединений) РЬр по базису циклов, соответствующему

укладке максимальной планарной части графа, и перейти к шагу 4 (для многослойной разводки проводников).

Шаг 4. Расчет температур элементов, которые необходимо разместить на кристалле, по формуле Т3 =ТК *{1ъ!2Хкр+Иш!\л) (М. Ф. Пономарев, Б. Г. Коноплев, 1986г.),

где Тк — температура основания корпуса под кристаллом, °С; Тэ — температура элемента, °С;

д, = /5Э/5'Э - плотность мощности элемента, мВт/мм2; где Ръ - мощность элемента, мВт; - площадь элементов, мм2

4 - линейный размер элемента, мкм;

- коэффициент теплопроводности кристалла (кремния), мВт/мм*град;

К - толщина клея (припоя), мм;

^кл - коэффициент теплопроводности клея (припоя), мВт/мм*град.

Шаг 5. Выполнение процедуры «декодер», осуществляющей размещение элементов по полученному приоритетному списку РЬр и их соединение с учётом условий 1-7 (с. 9) и одновременной проверкой условия:

Если текущий элемент г е Мп то разместить этот элемент ближе к теп-лоотводящим краям кристалла;

Если текущий элемент г е М,, то разместить этот элемент ближе к центру поля размещения кристалла.

Шаг 6. Конец алгоритма трассировки.

В таблице 1 приведены результаты расчета тепла элементов, а на рисунке 5 — результат работы алгоритма трассировки.

Таблица 1. Расчет температуры элементов, расположенных на кристалле

Наименование параметра Наименование олока

Блок Х°1 Блок №2 Клок №3 Блок Хг4

Температура корпуса, Тк (град) 80 80 80 80

Мощность элемента, Р (мВт) 8 12 9 22

Длина элемена (мкм) 27,5 15,5 14.5 34,5

Ширина элемена (мкм) 13 27 25,5 17,5

Площадь элементов, в (мм.кв) 0.000358 0.000419 0,000370 0,000604

Линейный размер элемента, 1э ср. (101) 0.028 0,016 0,015 0,035

Коэф. тепло-ти кристалла, >л;р (мВт/мм*трад) 50 50 50 50

Толщина клея (припоя), Ькл (>ш) 0.005 0.005 0,005 0,005

Коэф. тепло-ти клея (припоя), лкл (мВт.'мм*град) 400 400 400 400

Плотность мощности элемента, qэ (мВт/мм кв.) 22377,62 28673,84 24340,77 36438,92

Температура элемента, град. 86.43 84.80 83.83 93,03

Продолжение таблицы 1.

Наименование параметра Наименование блока

Блок №5 Блок №6 Блок №7 Блок Л'28

Температура коипуса, Тх (град) 80 80 80 80

Мощность элемента, Р (мВт) 14 16 15 25

Длина злемена (мкм) 17,5 33,5 17,5 33,5

Ширина злемена (мкм) 30 25,5 30,5 25,5

Площадь элементов. Б (мм.кв) 0,000525 0.000854 0,000534 0.000854

Линейный размер элемента, 1э ср. (мм) 0.018 0,034 0,018 0,034

Коэф. тепло-ти кристалла, /,кр (мВт/мм*град) 50 50 50 50

Толщина клея (припоя), Ькл (мм) 0,005 0.005 0.005 0,005

Коэф. тепло-ти клея (припоя), ?лсл (мВт/мм*трад) 400 400 400 400

Плотность мощности элемента, дэ (мВт/мм кв.) 26666,67 18729,88 28103,04 29265,44

Температура элемента, град. 85.00 86.51 85.27 90.17

ле

В третьей главе приведен алгоритм декодера и пример работы алгоритма. Рассмотрен пример многослойной разводки проводников на примере 4 слоев.

Процедура «декодер» позволяет получить плотное размещение элементов на кристалле с учетом технологических ограничений (стр.9) для выполнения последующего соединения элементов (трассировки).

и

Декодер. Алгоритм декодера

Декодер - специализированная процедура, осуществляющая получение упаковки на основе исходных данных задачи и закодированного представления решения.

Алгоритм работы декодера:

Шаг 1. Формирование плана размещения.

Шаг 1.1. Инициализация пустого плана с двумя псевдо-комнатами, расположенными друг над другом.

Шаг 1.2. Добавление комнат, соответствующих элементам первого блока ребер из приоритетного списка ребер РЬр, в псевдо-комнаты плана.

Шаг 1.3. Последовательно выбираем блоки ребер из приоритетного списка ребер РЬр, начиная со второго, i =2.

Шаг 1.4. Если рассмотрены все блоки ребер, то выйти из алгоритма.

Шаг 1.5. Поочередное добавление комнат, соответствующих элементам г'-го блока ребер из приоритетного списка. Критерий выбора местоположения добавляемой комнаты - непосредственное соприкосновение с комнатами, с элементами которых соединен ребрами текущий элемент.

Шаг 1.6. Положим г= г+1. Перейдем на шаг 1.4.

Шаг 2. Размещение элементов по комнатам плана.

Шаг 3. Соединение элементов согласно структурной схеме.

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

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

Шаг 4. Уплотнение полученного размещения.

Шаг 4.1. Итерационный процесс проверки возможности сдвига узловых точек соединений вверх/вправо. Если такая возможность есть, то узловые точки смещают вверх/вправо до предела (до краев элемента или до ближайшего параллельного соединения, в которое «упирается» смещаемое соединение). При этом учитываются технологические ограничения для недопущения соприкосновения соединений между собой или с элементами. Если после просмотра всех соединений не произошло ни одного изменения, то переходим на шаг 4.2.

Шаг 4.2. Итерационный процесс проверки текущего элемента на возможность сдвига вверх/вправо. Если сдвиг возможен, то дополнительно проверяется два условия:

а) сдвиг не должен приводить к увеличению площади ограничивающего размещение прямоугольника;

б) сдвиг не должен приводить к увеличению суммарной длины соединений.

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

Дано: структурная схема 8 соединений элементов (рисунок б), план с размещенными элементами (модулями) (рисунок 7).

Рисунок 6 - Структурная схема Рисунок 7 - План Р с размещен-соединений элементов (модулей) ными элементами

Необходимо осуществить такое размещение элементов по «комнатам» плана, чтобы проводники, расположенные в одном слое, не пересекались. Это задача трассировки. Решение задачи трассировки.

Шаг 1. Соединение элементов плана (рисунок 8) в соответствии со структурной схемой (рисунок 6).

Рисунок 8 - План с размещенными и соединенными проводниками элементами в соответствии со структурной схемой (рисунок 6)

Рисунок 9 - Граф Сг=(К,£), соответствующий структурной схеме (рисунок 6)

Шаг 2. Построение графа 0={УД) (рисунок 9), соответствующего схеме 5, в котором вершины V- это элементы, ребра Е- проводники, соединяющие эти элементы.

Т.к. имеются пересечения проводников, применяем алгоритм проверки планарности графа на базе процедур генетического алгоритма (В. В. Емельянов, В. М. Курейчик, В. В. Курейчик, 2002 г.).

Результат работы алгоритма проверки планарности графа на базе процедур генетического алгоритма представлен на рисунке 10.

г

тами в соответствии со структурной схемой (рисунок 6)

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

Численный эксперимент основан на сравнительном анализе полученных результатов с известными рекордными решениями, полученными другими эвристическими алгоритмами. Он проведен на различных наборах тестовых примеров из международной библиотеки OR-Library (http:// people, brunel.ac. uk/"mast jjb/jeb/info.html): ami33, ami49, rplOO, pcbl46 для задач размещения элементов (модулей) по «комнатам» плана на кристалле. В качестве формального критерия оценки качества решения выступает площадь кристалла. Работа известных методов и алгоритмов для решения задачи планирования размещения элементов (модулей) на кристалле проводилась на каждом рассмотренном примере: ami33, ami49, rplOO, рсЫ4б. Результаты эксперимента приведены в таблице 2.

Таблица 2. Данные по классам задач

Задача D Общая площадь QS-LS QS-TS QS-SA Enhance d O-tree B*-tree CBL

P = 1 P = 0.5 P = 0.1 P= 1 P = 0.5 P = 0.1

ami33 33 1.156 1.773 1.804 1.549 1.614 1.891 2.036 1.594 1.55 1.57 1.60

ami49 49 35,433 52.565 51.117 38.476 52.338 53.969 41.229 38.75 38.73 38.80 38.58

rplOO 100 205.069 278.290 272.510 309.400 268.685 270.130 269.535 - - - -

pcb146 146 78.560 181.192 173.408 144.183 181.192 172.288 147.222 - - - -

Заключение по эксперименту: Как видно из результатов численного эксперимента при размерности и=33, п=49 и Р= 0,1 алгоритм рБ-ЬБ показывает лучшие результаты по сравнению с другими известными подходами.

Работа известных методов и алгоритмов для решения задачи трассировки на кристалле также проводилась на каждом рассмотренном примере: аггпЗЗ, агш49, грЮО, рсЫ46. Результаты эксперимента приведены в таблице 3.

Таблица 3. Данные по классам задач

Задача п Алгоритм проверки планарности графа С помощью деревьев Штейнера Имитация отжига Муравьиный алгоритм Генетический алгоритм

алнЗЗ 33 1,853 1,870 1,915 1,850 1,855

агш49 49 53,2 54,2 54,1 53,6 53,7

грЮО 100 206,01 207,16 207,02 206,15 206,23

рсЫ46 146 215,03 218,3 216,45 215,03 216,58

Заключение по эксперименту: Как видно из результатов численного эксперимента при размерности я=49, п= 100 алгоритм проверки планарности графа на базе процедур генетического алгоритма показывает лучшие результаты по сравнению с другими известными подходами.

Разработанный алгоритм для решения задачи трассировки был сравнен с известным пакетом Р-САО для автоматизированного размещения и соединения элементов. Как видно по рисунку 6, в окне программы Р-САД нагревающий (тепловыделяющий) элемент 8 оказался в центре кристалла, что ведет к отказу в работе микросхемы;

Р-САГ> произвел разводку проводников, соединяющих элементы, на двух слоях, в то время как разработанный алгоритм для решения задачи трассировки разводи:' эти же про^щию-пэ^^ слое.

вз

В1 Ё=

В6 Ц

В2

В8

В7 1

В 4

!Ы

В5

Рисунок 6 - Результат работы программы Р-САТ)

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

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

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ОПУБЛИКОВАНЫ В РАБОТАХ

В рецензируемых журналах из списка ВАК

1. Алгоритм трассировки при проектировании СБИС / М. Р. Рихтер // Научно-технические ведомости СПбПУ: науч. журн. С.-Петербургск. гос. политехн. ун-та. 2011. № 5 (133). С. 111-118.

2. Разработка декодера для решения задачи размещения и трассировки СБИС / М. Р. Рихтер // Современные проблемы науки и образования. 2012. № 5. URL: http://www.science-education.ru/105-7315.

В других изданиях

3. Решение задачи проектирования СБИС / М. Р. Рихтер // Микроэлектроника и информатика - 2012: 19-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов (18-20 апреля 2012): тезисы докладов. М., Зеленоград: МИЭТ, 2012. С, 83.

4. Разработка алгоритмов для решения задачи трассировки и планирования СБИС / М.Р. Рихтер // Интеллектуальные технологии обработки информации и управления: сб. тр. Междунар. молодёжи, конф. Уфа: УГАТУ,

2012. Т. 2. С. 48-53.

5. Решение задачи трассировки и планирования при проектировании СБИС: численный эксперимент / М.Р. Рихтер // Компьютерные науки и информационные технологии CSrr'2012. Уфа: УГАТУ, 2012. Т. 3. С. 14-17. (Статья на англ. яз).

6. Решение задачи планирования СБИС на основе метода локального спуска. Реализация окрестности решения / М.Р. Рихтер // Отраслевые аспекты технических наук: науч.-практ. журнал. 2012. № 7 (19). С. 29-32.

7. Решение задачи проектирования СБИС: свид. о гос. per. программы для ЭВМ № 2012617363 / М. Р. Рихтер. Зарегистрирована 15 августа 2012.

ß J.

Диссертант . aU11*'*1^' М'РнХТер

РИХТЕР Маргарита Робертовна

ОПТИМИЗАЦИЯ ПРОЦЕССА РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ НА КРИСТАЛЛЕ ЦИФРОВОЙ ИНТЕГРАЛЬНОЙ СХЕМЫ ПРИ НАЛИЧИИ ТЕХНОЛОГИЧЕСКИХ ОГРАНИЧЕНИЙ

Специальность 05.13.01 Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 08.05.2013 г. Формат 60x84 1/16.0 Бумага офсетная. Печать плоская. Гарнитура Times New Roman. Усл. печ. л. 1,0. Усл. кр,- отт. 1,0. Уч. - изд. л. 0,9. Тираж 100 экз. Заказ №295

ФГБОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12