Введение к работе
Актуальность работы. Проектирование БИС - сложный, занимающий много времени процесс; сроки разработки
электронного устройства, содержащего БИС в качестве
компонентов, могут превышать период, в течение которого изделие пользуется спросом и затраты на проектирование могут не окупиться до того, как прибор устареет. Учитывая эти обстоятельства, разработка СБИС должна осуществляться в кратчайшие сроки, с наименьшими затратами; устройства, выполненные по этим проектам, должны обладать заданными функциональными свойствами и отвечать поставленным требованиям. Проектирование БИС высокой степени интеграции требует создания эффективных систем автоматизированного проектирования (САПР) для организации сквозного цикла проектирования БИС за приемлемое с точки зрения пользователя время.
Удовлетворить в полной мере этим требованиям могут только вычислительные системы, имеющие структуру отличную от классической. К такого рода системам относятся параллельные вычислительные системы. Ясно, что использование этих систем в комплексе технических средств (КТС) САПР должно расширить возможности системы. При этом, положительный эффект при решении задач автоматизированного проектирования БИС на КТС, в состав которых входят параллельные вычислительные системы (ПВС), может быть достигнут, в основном, за счет их распараллеливания.
Цель работы и задачи исследования. Целью диссертационной
работы является исследование и разработка отдельных компонент
этапа проектирования БИС - построение связывающих деревьев,
расслоение, синтез топологии; разработка алгоритмического и
прикладного программного обеспечений систем
автоматизированного проектирования на базе параллельных вычислительных систем, в основу построения которых положены созданные или создающиеся высокопроизводительные многопроцессорные вычислительные комплексы.
Для достижения поставленной цели были решены следующие задачи:
исследование существующих алгоритмов построения связывающих деревьев, для оценки ускорения их выполнения на ПВС, на основе выделения в них максимальных параллельных процессов;
разработка нового алгоритма параллельного построения ортогональных связывающих деревьев и оценка ускорения его
выполнения на ПВС;
исследование существующих алгоритмов распределения фрагментов цепей по слоям для оценки ускорения их выполнения на ПВС на основе выделения в них максимальных параллельных процессов;
разработка алгоритма определения клик графа для выполнения на ПВС и оценка эффективности его выполнения;
исследование существующих алгоритмов трассировки соединений для оценки ускорения их выполнения на ПВС на основе выделения в них максимальных параллельных процессов;
- разработка нового алгоритма параллельной трассировки
соединений и оценка ускорения его выполнения на ПВС;
- разработка организации вычислительного процесса и синтез
базового набора макроопераций, необходимых для реализации
задачи параллельной трассировки на ПВС;
- разработка аппаратно-программного комплекса, для работы САПР
СБИС, на основе разработанных алгоритмов и многопроцессорной
вычислительной системы со структурно процедурной организацией
вычислений (МВС СПРВ), в качестве аппаратного ускорителя
выполнения задач САПР;
- исследование параметров вычислительного процесса при
реализации задачи параллельной трассировки на МВС СПРВ:
ускорение, доли накладного времени, коэффициента использования
оборудования и коэффициента качества программирования.
Методика исследований базируется на теории множеств, теории графов, теории оптимизации, теории алгоритмов, теории вычислительных систем и принципах параллельной обработки информации с учетом специфики алгоритмов и процессов, порождаемых при решении задач САПР.
Научная новизна диссертационной работы заключается в следующем:
разработан новый алгоритм параллельного построения ортогональных связывающих деревьев;
- разработаны новые алгоритмы для узловых процессоров
процессорного поля ПВС, позволяющие организовать процесс
одновременного построения всех ортогональных связывающих
деревьев, получена оценка ускорения выполнения построения
ортогонального связывающего дерева на ПВС;
- разработаны алгоритмы для узловых процессоров, позволяющие
организовать эффективный процесс выделения клик графа на ПВС,
процессоры которой соединены по полному графу, получена оценка
ускорения выполнения выделения на ПВС;
-разработаны алгоритмы для узловых процессоров, позволяющие
организовать процесс одновременного построения всех трасс на ПВС, процессорное поле которой имеет структуру типа "решетки",
получена оценка ускорения выполнения алгоритма на ПВС;
получены оценки ускорения выполнения на ПВС ряда существующих алгоритмов: построения ортогональных связывающих деревьев, разнесения связей по слоям, прокладки трасс, на основе исследования вариантов их вычислительных процессов;
- разработаны принципы организации вычислительного процесса и
синтезирован базовый набор макроопераций для выполнения
параллельной трассировки на МВС СПРВ.
Практическая ценность работы. На основе теоретических исследований предложена методика, позволяющая производить оценки эффективности выполнения алгоритмов проектирования на ПВС. Создан ряд алгоритмов этапа трассировки. На их основе разработаны алгоритмы для узловых процессоров процессорного поля ПВС, позволяющие организовать вычислительные процессы: одновременного построения всех связей деревьев, разнесения фрагментов цепей по слоям с минимальными временными затратами, прокладки одновременно всех трасс на коммутационном поле БИС. Адаптация алгоритма параллельной трассировки в условиях МВС СПРВ позволила выявить закономерности и ограничения, налагаемые на алгоритмы при проектировании на многопроцессорных системах.
Апробация основных результатов диссертационной работы докладывались и обсуждались на:
- всероссийской XXXIX научно-технической конференции, ТРТУ,
г.Таганрог, 1993г.;
всероссийской научно-технической конференции "Актуальные проблемы твердотельной электроники и микроэлектроники", г. Таганрог, 1994г.;
всероссийской научно-технической конференции "Интеллектуальные САПР-96", г. Геленджик, 1997г.;
научно-технических и научно-методических конференциях профессорско-преподовательского состава, аспирантов и сотрудников Таганрогского государственного радиотехнического университета в 1986-1997 г.
Публикации. Материалы, содержащие основные научные результаты, опубликованы в 10 печатных работах, кроме того, во ВНТИЦ зарегистрировано 5 отчетов по хоздоговорным и научно -исследовательским работам в области автоматизации и
проектирования РЭА и БИС, выполненных при непосредственном участии автора.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложения. Работа содержит 190 стр. машинописного текста, включая 37 стр. рисунков и таблиц, список литературы из 90 наименований, 3 стр. актов об использовании.
