Введение к работе
.. г
Актуальность темы. Создание современной вычислительной техники невозможно без применения схем высокой и сверхвысокой степени интеграции, а проектирование таких схем в свою очередь требует принципиально новых подходов к разработке средств проектирования. Один из возможных подходов к созданию программных систем для проектирования сверхбольших интегральных схем был предложен в начале 80-х годов и получил название "кремниевый компилятор". Появление программных систем типа "кремниевый компилятор" можно сравнить с появлением языков высокого уровня в программировании. а само название "кремниевый компилятор" (в дальнейшем КК) отражает тот факт, что основной функцией системы типа КК является трансляция описания проектируемого устройства на поведенческом или структурном уровне в описание топологии фотошаблона подобно тому, как обычные трансляторы порождают машинные коды по тексту программы на языке высокого уровня.
( Одной из подсистем, входящих в состав КК. является подсистема синтеза топологии ИС. которая предназначена для генерации рисунка топологии ИС по описанию схемы проектируемого устройства на языке структурно-функционального уровня. Основными требованиями, предъявляемыми к подсистеме синтеза топологии в рамках системы типа КК, помимо обеспечения высокой скорости процесса разработки (нескольких недель вместо месяцев и годов) и повышения размерности решаемых задач (от нескольких сотен до нескольких тысяч и миллионов транзисторов), являются также гарантия бездефектности получаемого результата и настраиваемость подсистемы как на технологию, так и на конкретную архитектуру или стиль проектирования.
Цель работа.
В основу разработки подсистем топологического синтеза, удовлетворяющих вышеприведенным условиям, положены следующие две идеи:
1. В качестве базиса конструктора, из которого будет сгенерирована топология проектируемого устройства, использовать библиотеки элементов достаточно высокого уровня интеграции и
- 4 -тем самым дать возможность разработчику описывать проект не в терминах транзисторов и вентилей, а в терминах таких функциональных элементов., как ОЗУ, ПЗУ, регистры, дешифраторы, сдви-гатели, ПЛМ и т.д. При этом, по возможности, использовать параметризованные библиотеки элементов, причем в качестве параметров рассматривать не только разрядность (для элементов типа регистр), или прошивки (для элементов типа ПЗУ. ОЗУ или ПЛМ), но и технологические константы.
2. Задать такие правила сборки топологии кристалла из библиотечных элементов, чтобы на каждом шаге сборки гарантировалось бы соответствие получаемого результата схеме проектируемого устройства и конструкторско-технологическим ограничениям. Эти две идеи являются достаточно общими и существует широкий диапазон возможных способов их реализации. Целью данной работы было исследование возможных путей и научное обосновать методики построения систем синтеза топологии СБИС, реализующих принцип попарной сборки и позволяющих использовать библиотеки параметризованных элементов., При этом предполагалось зафиксировать входные и выходные форматы подсистемы топологического синтеза, а также небольшой набор основных структур данных и затем, используя эти структуры как каркас системы, написать такие прикладные программы для решения поставленной задачи, -чтобы впоследствии эти прикладные программы могли быть использованы в качестве конструктора для создания систем проектирования различных модификаций: т полностью заказных схем до схем на стандартных элементах и базовых матричных кристаллах.
Методы исследования. Было выделено несколько подзадач) решение которых в совокупности обеспечивает решение основной задачи. Более конкретно можно перечислить следующие подзадачи, которые решались в процессе создания подсистемы синтеза топологии ИС:
нахождение адекватных подходов к комплексному решению задач синтеза топологии и задачи кремниевой компиляции;
использование современных подходов системного программирования к выделению основных объектов обработки, созданию языков, форматов и структур для их описания,;
формализация базовых задач и разработка алгоритмов для их решения;
реализация разработанных подходов, методов и алгоритмов в виде программной системы;
экспериментальная апробация созданной системы, анализ экспериментальных результатов, оптимизация программ и алгоритмов.
Использовался типовый механизм языка программирования Поляр для спецификации оснозных входных и выходных языков (форматов) системы, а таете интерфейсов между отдельными прикладными программами системы.
Для описания семантики операций над основными объектами системы использовались графовые модели. Рассматривались трансформации деревьев для описания возможных путей отображения иерархического описания устройства в топологию кристалла.
Для решения прикладных проблем использовались известные алгоритмы, такие как алгоритмы поиска кратчайиего пути, минимального связующего дерева и минимального дерева Штейнера на графе. Для реализации планировщика кристалла были использованы методы вычислительной геометрии, в частности, метод сканирующей прямой. В тех случаях, когда не удавалось использовать известные алгоритмы для эффективного решения поставленных задач создавались Собственные алгоритмы, к таковым относится, например, алгоритм размещения, реализованный в данной системе. Были проанализированы также различные эвристики канальной трассировки и. с целью поиска наиболее эффективных вариантов решения задачи канальной трассировки, выполнены экспериментальные реализации некоторых алгоритмов, не реализовывавшихся ранее.
Совершенствование и оптимизация алгоритмов потребовало проведения большой экспериментальной работы на реальных и тестовых задачах- проектирования. Трудоемкость данной работы осталась за рамками текста диссертации равно как и конкретные выводы по оптимизации алгоритмов и параметров алгоритмов.
Научная новизна. Были получены следующие результаты:
сформирован комплексный системный подход к задачам синтеза топологии;
определены базовые структуры данных, форматы и языки описания основных объектов проектирования;
исследован и реализован подход к КК на основе параметризации описаний и библиотек элементов;
рассмотрены в комплексе задачи декомпозиции, планирования кристалла, размещения, глобальной и детальной трассировки;
созданы новые и предложены модификации известных алгоритмов решения основных задач топологического синтеза, проведен анализ и экспериментальное исследование предложенных алгоритмов, проведено сравнение используемых алгоритмов с наиболее хорошо зарекомендовавшими себя алгоритмами.
Практическая ценность. В рамках диссертационной работы разработана универсальная система автоматического синтеза топологии ИС, : функционирующая на ЭВМ типа PC AT и внедренная в эксплуатацию для различных архитектурных стилей - от полностью заказных схем до базовых матричных кристаллов различных типов.
Апробация работы. Основные результаты и положения диссертационной работы докладывались на школе-семинаре "Системные и прикладные аспекты диалога на персональных ЭВМ" (Гагра, 1985), Всесоюзной школе-семинаре "САПР ЭВМ и БИС" (Ереван, 1986), 3-ем Всесоюзном совещании "Высокопроизводительные вычислительные системы" (Таллинн. 1988). Всесоюзной-конференции "Интегрированные системы автоматизированного проектирования в гибких производственных системах" (Гурзуф. 1988), Всесоюзной школе "Актуальные проблемы создания интеллектуальных САПР РЭА и СБИС" (Крым, 1989), 1-ой международной научно-практической конференции САПР СВТ-89 (Ленинград, 1989), Всесоюзной школе-семинаре "Автоматизация проектирования СБИС и конструкций РЭА" (Львов.1990). Всесоюзной школе "Методы искусственного интеллекта в САПР"(Гурзуф, 1990). Международной школе молодых ученых "Новые информационные технологии в проектировании" "(Ялта 1991), Всесоюзной научно-технической конференции "Автоматизацій проектирования РЭА и ЭВА" (Пенза 1991).
Структура диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Основной текст диссертации включает 1 CjLстраниц и ДЧ" рисунков. Список литературы содержит С1 наименований. К диссертации имеются 2 приложения на .% страницах.
