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

Введение.

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

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

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

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

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

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

Апробация.

Публикации.

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

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 Классический min - cut алгоритм.

2.1.2.3.1 Определения.

2.1.2.3.2 Описание алгоритма.

2.1.2.4 Отличие алгоритмов Федучи-Матеуса и Лина-Кернигана.

2.1.2.5 Преимущества min-cut разбиения.

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, VHDL или С. Синтез схемы, реализующей заданные функции, выполняется автоматически с использованием специального программного обеспечения, результатом работы которого является представление схемы в виде набора конкретных библиотечных элементов и списка соединений между ними.

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

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

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

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

Целью диссертационной работы являлось создание компонента САПР для визуализации электрических схем.

В соответствии с этим были определены следующие задачи:

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

• Разработка алгоритмического обеспечения для построения схем любого типа.

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

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

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, прежде всего, составляют:

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

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

• Метод укладки проводников в канале при трассировке связей

• Новое программное обеспечение для визуализации электрических схем, осуществляющее построение схемы по образцу и построение части схемы в интерактивном режиме.

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

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

В процессе проведения исследований получены следующие новые научные результаты:

• Разработаны алгоритмы и методы, обеспечивающие построение изображения электрических схем, заданных списком соединений, применимые для схем любого типа (аналоговых, цифровых, смешанных) и любого размера.

• Предложен новый метод построения изображения схем, у которых список соединений был изменён в процессе автоматизированного проектирования, - построение по образцу.

• Предложен новый метод работы со схемами большого размера, представленными списком соединений, - построение изображения части схемы в интерактивном режиме.

• Созданы компоненты САПР для визуализации электрических схем, представленных списком соединений.

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

Результаты исследований, выполненных по теме диссертации, нашли применение в разработанном программном комплексе редактора электрических схем (Schematic Editor) и в приложении cseExch для импорта проектов из сторонних систем в САПР Avant! Разработанное программное обеспечение используется на этапе логического проектирования в САПР Avant! и позволяет построить графическое изображение схемы по списку соединений её элементов.

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

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

Предложенные в диссертации методы использования алгоритмов размещения и трассировки для смешанных аналогово-цифровых схем разработаны лично автором. Программное обеспечение в течение ряда лет создавалось коллективом разработчиков (в Московском центре SPARC технологий) при личном участии автора. Объём кода, разработанного лично автором на языке программирования С++, составил более 15 тыс. строк.

Апробация.

Результаты диссертационной работы докладывались на всероссийских и вузовских научных конференциях и обсуждались на научно-технических семинарах:

1. Российская научная конференция "Экономические информационные системы на пороге 21 века" г. Москва, МЭСИ 1999г.

2. V всероссийская научная конференция студентов и аспирантов, г. Таганрог. 2000г. (Диплом за лучший доклад на подсекции "Интеллектуальных САПР" секции "Систем управления и информационных технологий").

3. Традиционная конференция МФТИ. 1999г. (Лучший доклад на подсекции "Вычислительной техники").

Кроме того, результаты работы докладывались и обсуждались на научных семинарах НИИ ВТ в 2001г.

Публикации.

По теме диссертации опубликованы 4 работы.

1. Уткин В.Ф., Ирбенек B.C., Жмурин A.B. «Схем-Конструктор -алгоритмическое и программное обеспечение для графического изображения схем».//. «Высокопроизводительные вычислительные системы и микропроцессоры». Труды ИВВС РАН, М., 1999, с. 31-40.

2. Уткин В.Ф., Ирбенек B.C., Жмурин A.B. «Алгоритмическое и программное обеспечение для графического изображения схем, представленных списком соединений».// В сб. докладов российской научной конференции 'Экономические информационные системы на пороге 21 века'. М., 1999, с. 338-344.

3. Жмурин A.B., Келенин К.В.,.Перекатов В.И, Уткин В.Ф. «Некоторые вопросы проектирования коммуникационных элементов микроэлектроники». // «Высокопроизводительные вычислительные системы и микропроцессоры». Выпуск 2. Труды ИМВС РАН, М., 2001, с. 119-124.

4. Уткин В.Ф. «Новые методы построения графического изображения схем, представленных списком соединений».// «Зарубежная радиоэлектроника. Успехи современной радиоэлектроники» №7, 2002, стр. 80-86.

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

Во введении описаны цель исследования, актуальность работы, её практическая ценность.

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

Решение задачи построения графического изображения схемы, требует в конечном итоге решения нескольких задач, часто встречающихся в других научно-технических проблемах, в том числе в САПР на этапе физического проектирования. Основные из них это размещение элементов и трассировка связей. В связи с этим раздел 2 содержит подробное исследование основных алгоритмических методов для решения этих задач, существующих на сегодняшний день. Так как при построении графического изображения схемы к результатам размещения и трассировки предъявляются особые требования, приведённые алгоритмы не могут быть использованы в чистом виде для построения схемы. По результатам анализа выбраны наиболее подходящие из них с учётом специфики решаемой задачи и осуществлена их доработка для достижения оптимального с пользовательской точки зрения результата. Так как при построении графического изображения схемы к результатам размещения и трассировки предъявляются особые требования, приведённые алгоритмы не могут быть использованы в чистом виде для построения схемы. По результатам анализа выбраны наиболее подходящие из них с учётом специфики решаемой задачи и в разделе 3 осуществлена их доработка для достижения оптимального с пользовательской точки зрения результата. Представлены новая модификация алгоритма построения минимального разреза для размещения элементов схемы и особый метод укладки проводников в канале при трассировке связей.

В разделе 3 также рассмотрены вопросы практического использования программного обеспечения для визуализации электрических схем. Предложен новый метод работы со схемами большого размера, представленных списком соединений, при котором осуществляется построение изображения части схемы в интерактивном режиме и новый метод построения изображения схем, у которых список соединений был изменён в процессе автоматизированного проектирования, - построение по образцу. Также в этом разделе дано краткое описание программных компонентов САПР, разработанных на основе алгоритмического обеспечения, предложенного в разделе 3, и реализованных в подсистемах промышленной САПР Avant!, и приведены результаты его использования для построения изображения различных электрических схем.

3.5 Выводы.

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

Эффективность решения задачи построения обеспечивается использованием самых современных алгоритмов визуализации и новых разработок, среди которых:

• Новый метод размещения, объединяющий ранжирование и разбиение;

• Новое понятие векторов ограничений и новый способ подсчёта оценки разбиения с учётом веса этих векторов;

• Модифицированный min-cut алгоритм;

• Динамическая последовательность min-cut разрезов;

• Комплексный параметрический алгоритм построения деревьев Штейнера в ортогональной метрике;

• Метод разблокирования сегментов;

• Набор сортировок для эффективной укладки проводников в канале.

Разработанное ПО применимо для схем любого типа (аналоговых, цифровых, смешанных). Для расширения области его применимости предложен новый метод работы со схемами большого размера, при котором осуществляется построение изображения части схемы в интерактивном режиме, и новый метод построения изображения схем, у которых список соединений был изменён в процессе автоматизированного проектирования, - построение по образцу.

Результаты тестирования показали высокую скорость работы предложенного ПО. Сравнение схем, построенных вручную и созданных автоматически, показало, что вторые уступают в качестве первым. Тем не менее, автоматически построенные схемы имеют неоспоримое преимущество перед списком соединений, так как дают возможность визуального контроля схемы с использованием средств графической оболочки, входящей в состав САПР.

Заключение.

В современных системах автоматизации проектирования для описания проекта широко используется формат списка соединений. Использование данного формата удобно для программ САПР, но лишает разработчика непосредственного визуального контроля схемы. В связи с этим возникает потребность в построении графического изображения электрических схем по списку соединений элементов, её составляющих, и включении программного обеспечения, осуществляющего визуализацию электрических схем, в состав САПР. Увеличение размеров проектов и появление нового программного обеспечения, работающего со списками соединений, требует расширения возможностей такого рода программ и актуальной становится задача разработки новых методов визуализации электрических схем и создание соответствующих компонентов САПР. В результате решения поставленных задач в рамках диссертационной работы получены следующие новые научные результаты:

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

2) Предложены новые методики построения изображения схем, а именно, построение по образцу для проектов, у которых список соединений был изменён в процессе автоматизированного проектирования, и интерактивное построение изображения схем большого размера

3) Разработано новое программное обеспечение. Созданы компоненты САПР для визуализации электрических схем, представленных списком соединений.

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

Предложенное ПО интегрировано в экспериментальную версию промышленной САПР фирмы Avant! - лидера в области создания средств разработки субмикронных устройств, и уже используются московским подразделением этой фирмы.

Благодарности.

Автор выражает искреннюю признательность всем сотрудникам московского подразделения фирмы Avant! за неоценимые знания, полученные за время обучения и работы, особенно Валентину Сергеевичу Ирбенеку за необходимое руководство и поддержку при написании данной работы. Большое спасибо Келенину Константину и Егорову Сергею за ценные замечания, учтенные в работе.

1. Уткин В.Ф., Ирбенек B.C., Жмурин А.В. «Схем конструктор -алгоритмическое и программное обеспечение для графического изображения схем». В сб. 'Высокопроизводительные вычислительные системы и микропроцессоры'. Труды ИМВС РАН, М., 1999, с. 31-40.

2. Ирбенек В.С «Алгоритмы построения минимальных связывающих деревьев и их применение в САПР электронной аппаратуры». В сб. 'Высокопроизводительные вычислительные системы и микропроцессоры'. Труды ИМВС РАН, М., 1999, с. 3-17

3. В. W. Kernighan, S. Lin. An efficient heuristic procedure to partition graphs. Bell System, Technical Journal, 49 (2), pp. 297-307, February, 1970.

4. С. M. Feduccia,, R. W. Mattheyses. A linear-time heuristic for improving network partitions. Proc. 19th. Design Automation Conference, pp. 175-181, 1982.

5. S. M. Sadiq, H. Youssef, VLSI Physical Design Automation. Theory and Practice. IEEE Press, New York, 1995.

6. Э. Рейнгольд, Ю. Нивергельт, H. Део. Комбинаторные алгоритмы. Теория и практика, МИР, Москва, 1980.

7. М. Брейер "Теория и методы автоматизации проектирования вычислительных систем. ", "МИР", Москва 1977.

8. Tim Barrera, Jeff Griffith, Gabriel Robins, Tongtong Zhang "Closing the Gap: Near-Optimal Steiner Trees in Polynominal Time" 1993

9. M.E. Штейн, Б.Е. Штейн "Методы машинного проектирования цифровой аппаратуры" Москва 1973

10. М. Hanan. "On Steiner's problem with rectilinear distance" SIAM J. Applied Math, 1966

11. Y.Y. Yang, O.Wing "Optimal and subottimal solution algorithms for the wiring problem" Proc IEEE Int. Symp. on Circuit Theory, 1972

12. J.L. Ganley, J.P. Cohoon "A faster dynamic programming algorithm for exact rctilinear Steiner minimal trees" Proc. Fourth Great Lakes Symp. on VLSI 1994

13. F.K. Hwang "On Steiner minimal trees with rectilinear distance" SIAN J. Applied Math, 30, 1976

14. F.K. Hwang, D.S. Richards, P. Winter "The Steiner tree problem" North Holland, 1992

15. D.M. Warme "A new exact algorithm for rectilinear Steiner trees"

16. J.S. Salowe, D.M. Warme "An exact rectilinear Steiner tree algorithm"

17. J.P. Cohoon, D.S. Richards, J.S. Salowe "An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of a rectangle" 1990

18. J. Ho, G. Vijayan, C.K. Wong "New algorithms for the rectilinear Steiner tree problem" 1992

19. Tim Barrera, Jeff Griffith, Sally A. McKee, Gabriel Robins, Tongtong Zhang "Toward a Steiner Engine: Enhanced and Parallel Implementations of the Iterated 1-Steiner MRST Heuristic" 1992

20. R. J. Brennan "An algorithm for automatic line routing on schematic diagrams". 12th Design automation conference, pp.324-330, June 1975.

21. M. J. Irwin, R. Owens, S. P. Levitan "Selected topics in architecture, logic and physical synthesis". Technical report, Department of Electrical Engineering, University of Pittsburgh, November 1988.

22. R. K. Chung, K. Chang, L. P. McNamee "VISION: VHDL induced schematic imaging on netlists". 24th Design automation conference, pp. 436-442, 1987.

23. M. L. Ahkstrom, G. D. Hadden G. R. Stroick "HAL: A heuristic approach to schematic generation". IEEE international conference on Computer Aided Design, pp.83-86, 1983.

24. V. V. Venkataraman C. D. Wilcox "GEMS: An automatic layout tool for MIMOLA schematics". 23rd Design Automation conference, pp. 131-137, 1986.

25. M. May "Computer generated multi row schematic". IEEE transaction on Computer Aided Design, Vol. 17 No. 1, pp. 25-29, January 1985.

26. M. May, A. Iwainsky, P. Mennecke "Placement and routing for logic schematic". IEEE transaction on Computer Aided Design, Vol. 15 No. 3, pp. 89-101, January 1983.

27. J. Sigl, K. Doll, F. M. Johannes "Analitical placement: A linear or a quadratic objective function?" 28th Design Automation Conference, pp. 427-432, 1991.

28. S.-L. Ou, M. Pedram "Timing-driven placement with dynamic cut-net control". 37th Design Automation Conference, pp.472-477, 2000.

29. M. C. Yildiz, P. H. Madden "Improved cut sequence for partitioning based placement" 21st Design Automaton Conference, pp. 776-781 ,2001.

30. P.R. Sauris, G. Kedem "An algorithm for quadrisection and its application to standard cell placement" IEEE transactions on circuits and systems, 35(3), pp, 394-403, 1988.

31. M. A. Breuer " A class of min-cut placement algorithms". In proceedings of Design Automation conference, pp. 530-533, 1997.

32. E. A. Caldwell, A. B. Khang I. L. Markov "Can recursive bisection alone produce routable placements?" 37th Design Automation Conference, pp.477-482,2000.

33. Архив публикаций ACM SIGDA (Special Interest Group on Design Automation) http://jamaica.ee.pitt.edu/