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

Введение к работе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   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 страниц.

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

         

         Оптимизация процесса раскроя промышленных материалов по критерию минимума материальных потерь при наличии технологических ограниченийФайзрахманов, Ришат Илшатович

         

         Алгоритмы глобальной оптимизации функций в пространстве непрерывных переменных при наличии ограничений-неравенствКузнецов Алексей Владимирович

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

         

         Методы минимаксного оценивания в многомерных линейных моделях наблюдения при наличии геометрических ограничений на моментные характеристикиСеменихин, Константин Владимирович

         Разработка математических моделей для оптимизации структур информационных сетей при ограничении на время доставки сообщенийХалдун, Мохаммад Абдель-Рахман Батиха

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

         

         Динамическая оптимизация процессов природопользованияАсанбаева, Людмила Токтобаевна

         Минимаксные методы оценивания и оптимизации процессов в неопределенно-стохастических системахПанков, Алексей Ростиславович

         

         Оптимизация процессов обработки заданий в дискретных многостадийных системах Мирецкий Игорь Юрьевич

         

         Оптимизация процессов отжига листового и сортового стекла Марголис Борис Иосифович