Проектирование сверхбольших интегральных схем
(СБИС) – чрезвычайно сложный многостадийный процесс, с трудом
поддающийся эффективной автоматизации. Трудности автоматизации обусловлены
сложностью задач, возникающих на каждой стадии. Во многих случаях эти задачи
являются многокритериальными. Так, например, на стадии размещения элементов на
схеме инженеры стремятся одновременно минимизировать длину соединений, площадь,
уровень энергопотребления, обеспечив при этом хорошие временные характеристики
интегральной схемы. Очевидно, некоторые из критериев оптимальности являются
противоречивыми, и улучшение одного из них зачастую приводит к ухудшению
другого, что затрудняет решение задачи.
Исследования в
области оптимального проектирования СБИС ведутся во многих научных центрах и
лабораториях по всему миру. При этом рассматриваются как отдельные этапы
процесса проектирования, так и их сочетание. В реальных условиях строгое
поочередное выполнение этапов не всегда является эффективным. Так, например,
использование буферизации (вставки буферных элементов) после процесса размещения
теоретически может улучшить временные характеристики, но на практике связано с
большими сложностями ввиду малого количества свободного места на схеме по
окончании процесса размещения. В данной ситуации инженерам приходится выполнять
цикл размещение-буферизация-размещение несколько раз, что, очевидно, является
крайне затратным по времени и не гарантирует улучшения результатов.
Целью проекта VLSI design, выполняемого при поддержке
компании Intel в
лаборатории ITLab,
является выработка подходов к так называемой совместной оптимизации СБИС,
выполняющей буферизацию непосредственно в ходе процесса размещения. В настоящий
момент в рамках данного проекта в качестве целевого функционала рассматривается
свертка, моделирующая временные характеристики интегральной схемы.
Необходимо
отметить, что задача размещения элементов на схеме в реальных условиях может
решаться для миллионов переменных, что делает ее особенно сложной. Для решения
этой задачи научным сообществом предложены различные варианты многоуровневых
подходов, использующих как аналитические, так и эвристические методы и
алгоритмы.
В
2005-2007 г.г. коллективом проекта
была разработана программная система для осуществления процесса размещения. В
основу созданной реализации был положен известный в литературе подход Dragon с некоторыми
модификациями, которые позволили улучшить оригинальную реализацию по качеству
получаемого решения (длине проводов). По данным на 2007 год на популярном
тестовом наборе ISPD’04, повсеместно используемом для
сравнения академических инструментов размещения, созданная в ITLab реализация удерживала второе место
по качеству финального размещения.
В
конце 2007 – начале 2008 года коллектив проекта перешел к решению
задачи совместной оптимизации и буферизации. Для этого была разработана
исследовательская инфраструктура, включающая чтение форматов lef/def и bookshelf, аналитическое размещение
(реализован опубликованный в литературе подход APlace), буферизация с последующей
легализацией результатов и возможностью возврата на стадию размещения, оценка
временных характеристик итогового размещения.
Цель
следующего этапа – выработка и апробация подходов к совместной
оптимизации.
В составе
нашего коллектива 1 преподаватель, 1 аспирант, 3
магистранта и 1 студент факультета ВМК ННГУ.
Ранее в проекте участвовали:
| Гагаринова Светлана Александровна |
 |
| Курина Нина Владиславовна |
 |
| Бадер Алексей Алексеевич |
 |
Команда обсуждает план работы на ближайший год:
Результаты проекта неоднократно докладывались на
конференциях. Опубликовано 8 научных работ, из них 6 статей.
1.
Гагаринова С.А., Живодеров А.В., Корняков К.В., Курина Н.В.,
Мееров И.Б. Об одном подходе к решению задачи о размещении // Технологии
Microsoft в теории и практике программирования. Материалы конференции / Под ред.
проф. Р.Г. Стронгина. – Нижний
Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 215-219.
2. Гагаринова
С.А., Живодеров А.В., Корняков К.В., Курина Н.В., Мееров И.Б. Использование
метода имитации отжига для решения задачи размещения элементов на схеме //
Технологии Microsoft в теории и практике программирования. Материалы конференции
/ Под ред. проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского
госуниверситета, 2006. – С. 220-225.
3. Гагаринова
С.А., Живодеров А.В., Корняков К.В., Курина Н.В., Мееров И.Б.
Вычислительная схема алгоритма Dragon для решения задачи о размещении элементов
на схеме // XI нижегородская сессия молодых ученых. Математические науки.
Материалы докладов. Н. Новгород, 2006.– С.24-25.
4. Корняков
К.В., Курина Н.В., Мееров И.Б. Параллельная реализация метода имитации
отжига в алгоритме размещения элементов сверхбольших интегральных схем //
Высокопроизводительные параллельные вычисления на кластерных системах. Материалы
шестого Международного научно-практического семинара / Под ред. проф. Р.Г.
Стронгина. Санкт-Петербург: Изд-во Санкт-Петербургского госуниверситета, 2007,
С. 225-230
5.
Корняков К.В., Курина Н.В., Мееров И.Б. Анализ сложности
алгоритма размещения элементов СБИС инструмента itlDragon // Технологии
Microsoft в теории и практике программирования. Материалы конференции / Под ред.
проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского госуниверситета,
2007. – С. 125-129.
6.
Корняков К.В., Живодеров А.В., Мееров И.Б. Алгоритмы
размещения элементов смешанных размеров при проектировании СБИС // Технологии
Microsoft в теории и практике программирования. Материалы конференции / Под ред.
проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского госуниверситета,
2007. – С. 95-98.
7. Живодеров
А.В., Корняков К.В., Курина Н.В., Мееров И.Б. Улучшение метода
моделирования отжига в алгоритме размещения элементов СБИС // Труды 50-й научной конференции
МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть I.
Радиотехника и кибернетика. - М.: МФТИ, 2007. - С. 87
8.
Kirill Kornyakov, Nina Kurina,
Iosif
Meyerov, Artem Zhivoderov. An Improved Implementation of
the Simulated Annealing Based Standard Cell Placement Algorithm Dragon // 5th
IEEE East-West Design & Test International Symposium, Yerevan,
2007.
Презентация
Исследования
