Исследование алгоритмических методов визуализации электрических схем

• Автор: Уткин, Виталий Фёдорович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 120 с. : ил

Содержание.
Введение .

Актуальность работы

Цель исследования

Научная новизна работы.

Результаты работы, выносимые на защиту.

Практическая ценность

Личный вклад автора.

Апробация.
Публикации

Содержание работы.

1 Анализ места списка соединений и
графического изображения схем в САПР
1.1 Проектирование сложных ИС
1.1.1 Системное проектирование
1.1.2 Логическое проектирование.
1.1.3 Физическое проектирование.
1.2 ПО используемое при проектировании ИС.
1.2.1 Роль графического представления схемы
1.2.2 Предыдущие работы.
1.3 Задача построения изображения
1.3.1 Постановка задачи
1.3.2 Пример описания.
1.3.3 Требования к построенной схеме
1.3.4 Оценка качества изображения
1.3.4.1 Оценочная модель.
1.4 Выводы.
2 Исследование и сравнительный анализ алгоритмических методов визуализации
2.1 Задача размещения
2.1.1 Глобальное размещение
2.1.1.1 Линейная и квадратичная целевые функции
2.1.1.2 Метод собственных значений.
2.1.1.3 Недостатки размещения, полученного минимизацией целевой функции.
2.1.2 Итеративное разбиение
2.1.2.1 Задача разбиения.
2.1.2.2 Алгоритм ЛннаКернигана
2.1.2.2.1 Оценка разбиения
2.1.2.2.2 Улучшение разбиения
2.1.2.2.3 Итеративное улучшение
2.1.2.2.4 Временная сложность алгоритма.
2.1.2.3 Классический i алгоритм.
2.1.2.3.1 Определения
2.1.2.3.2 Описание алгоритма.
2.1.2.4 Отличие алгоритмов ФедучнМатеуса и ЛннаКерннгана
2.1.2.5 Преимущества i разбиения
2.2 Трассировка
2.2.1 Общая трассировка
2.2.1.1 Манхеттеново расстояние.
2.2.1.2 Построение минимального связывающего дерева.
2.2.1.2.1 Построение кратчайшего остова графа
2.2.1.2.2 Построение дерева Штейнера.
2.2.2 Задача Штейнера в ортогональной метрике
2.2.2.1 Точные алгоритмы
2.2.2.2 Точные алгоритмы для задач малой размерности
2.2.2.3 Алгоритмы преобразования деревьев к дереву Штейнера.
2.3 Выводы.
3 Разработка ПО для построения изображения схем.
3.1 Схем конструктор.
3.1.1 Основные характеристики.
3.1.1.1 Чтение списка соединений и запись изображения ИС
3.1.1.2 Построение иерархии.
3.1.1.3 Шины и векторные элементы
3.1.1.4 Символы элементов
3.1.1.5 Способы соединения.
3.1.2 Размещение
3.1.2.1 Логические связи.
3.1.2.2 Логическая сетка элементов.
3.1.2.3 Г орнзонтальное распределение
3.1.2.4 Вертикальное распределение.
3.1.2.5 Модифицированный гтнпсш алгоритм
3.1.2.5.1 Критерий балансировки.
3.1.2.5.2 Последовательность разрезов.
3.1.2.5.3 Распространение границы.
3.1.2.5.4 Вектора ограничений.
3.1.2.5.5 Вертикальные ограничения
3.1.2.6 Размещение аналоговых элементов
3.1.2.7 Размещение смешанных схем
3.1.2.7.1 Горизонтальные ограничения
3.1.2.7.2 Балансировка схемы и последовательность разрезов
3.1.3 Оптимизация ориентации модулей
3.1.4 Трассировка связен
3.1.4.1 Распределение трасс по каналам.
3.1.4.1.1 Комплексный параметрический алгоритм
3.1.4.1.2 Трассировка сетей с большим числом подключений
3.1.4.2 .Подсоединение трасс к выводам элементов.
3.1.4.2.1 Блокировка сегментов
3.1.4.3 Укладка проводников в каналах
3.1.4.3.1 Определение порядка трассировки.
3.1.4.3.2 Определение номера трека
3.2 Применение Схем конструктора.
3.2.1 Построение схем
3.2.2 Построение схемы по образцу
3.2.3 Построение части схемы
3.3 Сравнение изображений схем
3.4 Сравнение с конкурирующими программами
3.4.1 Скорость работы.
3.4.2 Интеграция в среду проектирования.
3.4.3 Функциональность
3.4.4 Качество результатов
3.5 Выводы
Заключение
Благодарности.
Литература


Современные методы проектирования, как правило, начинаются с построения модели схемы на поведенческом уровне с использованием языков описания аппаратуры высокого уровня (RTL HDL) типа Verilog, VIIDL или С. Синтез схемы, реализующей заданные функции, выполняется автоматически с использованием специального программного обеспечения, результатом работы которого является представление схемы в виде набора конкретных библиотечных элементов и списка соединений между ними. Анализ существующих САПР показывает широкое применение списка соединений для описания схемы в процессе разработки. В состав современных САПР входит большое число компонентов, использующих в качестве входных или выходных данных формат списка соединений. Одни из них осуществляют преобразование списка соединений, выполняя различные оптимизационные задачи. Другие используют этот формат для анализа и моделирования схемы. Кроме того, именно этот формат является исходным для размещения и трассировки элементов схемы. Обмен схемами между различными САПР также выполняется на уровне списков соединений. Формат списка соединений удобен для программ автоматического проектирования, но он лишает разработчика возможности непосредственного визуального контроля схемы. Существует необходимость проанализировать результат работы автоматизированных программ или внести в них изменения в ручном режиме. Для этого требуется решить задачу построения изображения схемы по набору элементов, ее составляющим, и списку соединений между ними. Таким образом, графическое представление схемы служит не только и не столько для ввода начальных данных в процессе разработки, а для вывода полученных данных, с целью их удобной интерпретации. И актуальной становится разработка эффективных методов визуализации электрических схем и реализация на их основе соответствующих средств САПР. Цель исследования. Целью диссертационной работы являлось создание компонента САПР для визуализации электрических схем. Исследование существующих методов построения графического изображения схем, заданных списками соединений, и анализ эффективности их применения для цифровых, аналоговых и смешанных схем. Разработка алгоритмического обеспечения для построения схем любого типа. Разработка новых программных средств визуализации электрических схем с расширенной областью применимости. Создание дружественной программной среды для удобного использования данных программных продуктов. Научная новизна работы. Разработка алгоритмов и методов построения изображения аналоговых, цифровых и смешанных электрических схем, заданных списком соединений. Новая модификация алгоритма построения минимального разреза для размещения элементов схемы. Новое программное обеспечение для визуализации электрических схем, осуществляющее построение схемы по образцу и построение части схемы в интерактивном режиме. Результаты работы, выносимые на защиту. В данной работе рассматриваются проблемы повышения эффективности работы со схемами, заданных списками соединений, для чего используются различные методы визуализации. Разработаны алгоритмы и . Предложен новый метод построения изображения схем, у которых список соединений был изменён в процессе автоматизированного проектирования, - построение по образцу. Предложен новый метод работы со схемами большого размера, представленными списком соединений, - построение изображения части схемы в интерактивном режиме. Созданы компоненты САПР для визуализации электрических схем, представленных списком соединений. Практическая ценность. Результаты исследований, выполненных по теме диссертации, нашли применение в разработанном программном комплексе редактора электрических схем (Schematic Editor) и в приложении cseExch для импорта проектов из сторонних систем в САПР Avant! Разработанное программное обеспечение используется на этапе логического проектирования в САПР Avant! Практическая ценность предложенного программного обеспечения достигается за счёт реализации нескольких специализированных приложений на общей алгоритмической базе. Во-первых, разработчик имеет возможность получить изображение любой иерархической схемы целиком или частично.