Проектирование топологии СБИС методом иерархической декомпозиции в среде распределенных вычислений

• Автор: Селиверстов, Михаил Николаевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Пенза
• Количество страниц: 181 с. : ил

ОГЛАВЛЕНИЕ
Введение.

1. Обзор и анализ методов повышения производительности САПР.

1.1. Темпы роста размерности задач проектирования СБИС

1.2. Аппаратные ускорители решения задач проектирования.

1.3. Параллельные вычисления как метод повышения производительности.

1.4. Системы распределенных вычислений

1.5. роблсмы выбора конфигурации кластерной системы.

2. росктированне параллельных алгоритмов.

2.1. Декомпозиция задач.

2.2. Организация взаимодействия задач.

2.3. Укрупнение зернистости задач.
2.4. Отображение множества задач на множество процессоров.
2.5. Иерархическая декомпозиция как унифицированный метод организации параллельного процесса решения
3. Параллельное решение задачи глобальной трассировки СБИС
3.1. Линейчатые топологии.
3.2. Существующие алгори гмы глобальной трассировки.
3.3. Модель глобальной трассировки
3.4. Стратегии максимального и миниматьного определения границ.
3.5. Параллельный алгоритм и его вычислительная сложность
3.6. Программная реализация и результаты тестирования
Выводы.
4. Совместное решение задач размещения и глобальной трассировки
4.1. Существующие алгоритмы размещения ячеек и глобальной трассировки
42. Параллельный алгоритм размещения и глобальной трассировки.
4.3. Параллелизм и вычислительная сложность алгоритма
4.4. Программная реализация и результаты тестирования
Выводы.
Заключение.
Список литературы


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