Содержание к диссертации
Введение
Глава I. Обзор основных задач конструкторского проектирова ния ЗВМ 8
I. Некоторые оптимизационные задачи комбинаторного типа, возникающие на этапе конструкторского проектирования и методы их решения 8
2. Основные подходы, применяемые при решешш оп тимизационных задач проектирования II
3. Формальная постановка задачи компоновки, раз мещения, трассировки и распределения инвариант ных выводов 26
Глава II. Математические модели и алгоритмы решения задач проектирования узлов ЗВМ . 32
. I. Компоновка базовых элементов в модули 32
2. Размещение компонентов на монтажном поле ... 46.
3. Распределение внешних выводов узлов ЗВМ 54
Глава III. Формирование графической информации при проектировании печатных плат 61
I. Принципы подготовки управляющих программ для автоматизации изготовления узлов ЗВМ 61
2. Математическая модель и алгоритм решения одной задачи типа задачи коммивояжера 63
Глава ІV. Система автоматизированного проектирования цифровой аппаратуры ДИСИО 73
I. Назначение и структура системы. 73
2. Принципы функционирования системы ДИСИО 77
3. Входной язык системы ДИСИО - 82
Заключение 97
Литература 99
- Основные подходы, применяемые при решешш оп тимизационных задач проектирования
- Размещение компонентов на монтажном поле
- Математическая модель и алгоритм решения одной задачи типа задачи коммивояжера
- Принципы функционирования системы ДИСИО
Введение к работе
Широкое внедрение во многие сферы человеческой деятельности различных средств вычислительной техники потребовало ускоренных разработок вычислительных машин и систем, сложность которых непрерывно возрастает. Проектирование.ЭВМ, во время которого перерабатываются огромные массивы информации, немыслимо без автоматизации разработок ЭВМ.
Согласно [i] , проектирование ЭВМ разделяют на этапы: системное проектирование, проектирование математического обеспечения, логическое, конструкторское проектирование, проектирование электронных схем.
В настоящее время в разных организациях реализованы и используются ряд систем и подсистем автоматизированного проектирования (САПР), имеющие различное целевое назначение (см. например [l-27]). Большой вклад в развитие автоматизации конструкторского проектирования внесли различные коллективы под руководством Абрайтиса Л.Б., Глушкова В.М., Ландау И.Я., Майорова С.А., Матюхина Н.Я., Пескова М.И., Петренко А.И., Рябова Г.Г., Рябова Л.П., Селютина В.А. и ряда других советских ученых,
В диссертационной работе рассматриваются вопросы, связанные с автоматизацией конструкторского проектирования узлов ЭВМ. На конструкторском этапе проектирования узлов ЭВМ предполагается автоматизация решения следующих задач: обработка входной информации для выбранной САПР и преобразование ее во внутренний формат данных; решение комбинаторных задач оптимизации, возникающих на этом этапе, таких как: компоновка базовых элементов в модули; распределение инвариантных выводов модулей; размещение радиоэлементов на поверхности печатной платы; распределение инвариантных контактов разъема; трассировка печатных проводников; выпуск полного комплекта конструкторской документации; подготовка данных на машинных носителях информации для автоматизации изготовления печатных плат.
Исходной информацией при проектировании узлов ЭВМ являются техническое задание на конструкцию, электрическая схема и перечень элементов. В техническом задании указаны требования, предъявляемые к конструкции, различные технические ограничения, Перечень элементов содержит описание типов элементов, которые входят в электрическую схему, их обозначения по ГОСТу, электрические параметры.
Электрическую схему можно представить в виде графа G[l9j, в котором различают несколько типов ребер и вершин. Введем вер шины трех типов v^lV*,:., *ty}, %=i ^i, ",хп У/ ^~(-7/,..., Тс J.Вершины IX соответствуют элементам схемы, ft - их количест во, вершиныX -выводам элементов,включая внешние выводы схемы,П-их количество, а вершины Т - цепям схемы, С - количество цепей. Среди ребер графа G различают элементные ребра г и сигнальные W , Элементные ребра определяют принадлежность выво дов из множества X элементам из множества v и задаются па рами вершин [%х) L=t,&J=i/i, Сигнальные ребра определяют вхождение выводов из X в отдельные цепи и описываются парами вершин /^ 7}'rJ~ lnj t,- і, С e jjpH подготовке информации электри- ческую схему задают в виде списка цепей. Граф G также задают и в виде матрицы А-11aijlltts » гДе ~ количество модулей, S - максимальное количество выводов модуля -го типа, а элемент /номеру цепи в схеме, если вывод модуля I -%; = j го типа входит в данную цепь, Lo в противном случае.
Результатами проектирования являются конструкторская документация и массивы информации на машинных носителях, выполняющих роль управляющих программ при автоматизации изготовления узлов ЭВМ.
Существующие САПР имеют ряд недостатков. Например, в [5-8, 12-13,15-18,21-22]отсутствует автоматизированный этап: компоновки базовых элементов в модули. САПР [5,8,13,18,21 ] не обеспечивает автоматизацию размещения разногабаритных элементов. В большинстве САПР реализован один алгоритм для решения задач определенного класса, причем, как правило, выбор оптимального решения производится по одному критерию, т.е. оптимизируется скалярная целевая функция. Так как целевая функция в задачах проектирования является не скалярной, а векторной, то результаты решения, полученные при помощи такого алгоритма, не всегда удовлетворяют технологическим и конструкторским требованиям. Часто на производстве используют несколько САПР, которые отличаются кругом решаетлых задач, но их совместная эксплуатация и передача информации между ними затруднены из-за различия во входных языках. На эффективное использование САПР в большой мере влияют и технические средства, выбранные разработчиком при проектировании системы.
При проектировании многих САПР недостаточное внимание уделено проблеме подготовки и ввода в ЗВМ исходной информации. Входные данные для многих САПР подготавливают ручным способом, который состоит из нескольких этапов: подготовка электрической схемы к описанию, занесение данных о схеме на специальный бланк, набивка входных данных на машинные носители информации. Как известно, количество допускаемых ошибок возрастает с увеличением этапов ручной подготовки информации, а это приводит к повышению трудоемкости при эксплуатации САПР.
Отсюда следует, что вопросы, связанные с созданием САПР, а также разработка математических моделей, которые позволяют более точно описЕвать практические задачи оптимизации, возникающие при проектировании, и применять к их решению существующие подходы, являются весьма актуальными.
Работа состоит из четырех глав.
Основные подходы, применяемые при решешш оп тимизационных задач проектирования
Для итерационных алгоритмов необходимо задавать некоторое начальное размещение. В процессе их разработок используются различные методы и подходы
Последовательные алгоритмы размещения не требуют начального размещения. Особенность их в том, что вводится многошаговый процесс принятия решений, на каждом шаге которого выбирается один из неразмещенных элементов и помещается в одну из незанятых позиций. Выбор очередного элемента и позиции для его установки опреде ляются заданными правилами .
В качестве целевой функции в большинстве алгоритмов размещения используется минимизация суммарной длины соединений. Учет этого критерия при решении большинства задач проектирования позволяет создавать благоприятные условия для трассировки соединений электрической схемы. Но в некоторых случаях учет только одного критерия не всегда приводит к качественному решению задачи. Оно зависит от конструкции печатных плат, расположения выводов на корпусе модуля, расположения посадочных мест на поверхности, ориентации модулей и степени свободы их размещения на плоскости. При решении задачи проектирования полученное решение должно удовлетворять ряду заданных ограничений (некоторые модули необходимо установить в заданных позициях, суммарная длина заданных цепей не должна превышать установленную величину и т.д.). В этом случае, для достижения желаемого результата оптимизацию необходимо производить по нескольким критериям.
Для вычисления целевой функции в алгоритмах размещения важно определить вспомогательные критерии, поскольку от их выбора зависит точность решения задачи. В дальнейшем такие вспомогательные критерии будем называть оценкой качества решения задачи. Так, напршлер, для определения минимальной длины цепи строят дерево, применяют косвенную оценку по числу прямолинейных связей между модулями и т.д.
Суммарная длина связей, вычисляемая при размещении модулей, отличается от реальной длины проводников после их трассировки. Поэтому исследована зависимость предполагаемых и реальных длин в зависимости от оценки качества решения задачи, выбранной для построения целевой функции. Так, напршлер, предсказываемая длина цепей, вычисленная путем построения дерева Штейнера в ортогональной мет рике, короче действительной на 6-7$. Если функция цели вычисляется не путем построения деревьев, а подсчитывается на основе матрицы связности и матрицы расстояний, то ошибка оценки суммарной длины составляет 1-2% [S2j .
Точность решения задачи размещения модулей зависит от выбора математической модели при создании алгоритма. Используются следующие типы моделей. 1. Размещаемые модули и позиции для установки приборов интерпретируются точками. 2. Модель учитывает приближенно геометрические размеры модулей и расположение контактов на плоскости. 3. Размещаемые приборы и позиции интерпретируются точками, но указывается принадлежность модулей электрическим цепям схемы и учитывается расположение контактов выводов на поверхности. 4. В качестве точек рассматриваются отдельные контакты модуля.
Считается, что математические модели 3 и 4 позволяют более точно вычислять расположение контактов модулей в узлах координатной сетки. Модели I и 2 находят широкое применение благодаря своей простоте, но при этом теряется часть информации о геометрии контактов выводов [ 34 ]
К настоящему времени строгих математических доказательств влияния выбора математических моделей и критериев качества на точность решения задач проектирования еще нет, поэтому мы произвели анализ ручной трассировки по результатагл автоматического размещения модулей, полученных с применением разных алгоритмов.
Размещение компонентов на монтажном поле
Как видно из анализа алгоритмов размещения, приведенного в главе I, этой задаче в литературе уделено много внимания. Здесь подробнее рассмотрим задачу размещения разногабаритных элементов на поверхности печатной платы. Для ее решения в литературе описано несколько вычислительных схем, которые относятся, как правило, к двум классам алгоритмов: методы силовых функций [46] и алго ритмы последовательного размещения [I0I-I05]
Метод силовых функций, как отмечено выше, с вычислительной точки зрения весьма трудоемок и требует подбора коэффициентов опытным путем. Поэтому на практике большее распространение нашли алгоритмы последовательного размещения. Их применение, в свою очередь, вызывает трудности, связанные с предварительными расчетами, равномерного заполнения платы. Кроме того, они не позволяют улучшать результаты решения данной задачи.
Рассмотрим некоторые из известных подходов. К алгоритмам последовательного размещения можно отнести такие как волновой алгоритм размещения модулей произвольной формы [ 12 ] , алгоритм размещения с учетом трасс соединений [95] , алгоритмы, использующие годограф вектор-функции плотного размещения [101] и ряд других [102-107]
Алгоритм размещения разногабаритных элементов в кратные позиции описан в [Юб},В начале работы алгоритма размещаемые элементы разбиваются на несколько групп с одинаковыми или близкими кратными размерами. Для них строят набор целочисленных кратных позиций. На следующем шаге производится привязка этих позиций к плате. При этом площадь поверхности, на которой размещаются модули, рассматривается как некоторое множество взаимно перекрывающихся целочисленных кратных позиций. Размещение элементов на вычисленном поле позиций производится последовательным алгоритмом.
Решение задачи размещения элементов, имеющих форму прямоугольников с одинаковой шириной CL И разной высотой [107J , производим в несколько этапов: монтажное поле разбивают на прямоугольные площадки (позиции) шириной CL и фиксированной высотой; получают допустимую упаковку модулей в заданные позиции (ширина каждого модуля - CL , а высота - кратная (X ); осуществляют перестановку групп модулей на поле платы с мини-мизациБЙ качества размещения.
В работе [105J предлагается дифференциальный подход к размещению элементов разных габаритов. Для определения оптимальных мест установки микросхем используется алгоритм волнового расширения габаритов микросхем. Размещение дискретных элементов производится после того, как буде.т определена загруженность отдельных участков печатной платы. В зависимости от соотношения полезной площади печатной платы и площади радиоэлементов, количества микросхем и дискретных элементов, а также от ресурса времени выбирается та или иная стратегия размещения.
В алгоритмах [106 - 107} предварительно фиксируется система кратных по .размерам позиций, размеры и состав которых соответствуют размещаемым элементам. После этого решается задача размещения заданного множества модулей в эти фиксированные позиции. Естественно, что при таком подходе уменьшается время, требующееся для решения этой задачи, но вместе с тем существенно сужается область просматриваемых вариантов размещения, что влечет за собой возможность потери оптимальных решений исходной задачи размещения.
Предложенный автором подход к решению задачи размещения разногабаритных элементов заключается в проведении последовательных шагов, на каждом из которых осуществляется разбиение элементов на подмножества - блоки разбиения. На сформированном в процессе работы алгоритма регулярном поле позиций одним из методов дискретной оптимизации производится последующее размещение этих блоковl08J . Задача разбиения элементов решается многокритериальным алгоритмом
Гюо] который благодаря введению оценок, учитывающих прямую и косвенную связь элементов, формирует блоки разбиения с учетом их последующего размещения. При таком подходе уменьшается время, требующееся для решения последующей задачи размещения. К тому же в отличие от болылинства известных подходов в предлагаемом алгоритме для более точного учета выбранного критерия оптимизации при формировании вариантов размещения принимаются во внимание не только группы модулей но и отдельные приборы. Это достигается за счет построения на каждой шаге алгоритма новой системы позиций для размещения. Также имеется возможность улучшать результат размещения в рамках выделенных ресурсов машинного времени. Перейдем к рассмотрению формальных постановок.
Математическая модель и алгоритм решения одной задачи типа задачи коммивояжера
Пусть имеется печатный слой с расположенным на нем печатным монтажом. На плоскость слоя нанесена координатная сетка с заданньм шагом. В качестве нулевой координаты примем нижний левый угол сетки. Линии, параллельные оси X , пронумеруем от / до а , линии, параллельные оси у - от і до Ь , узлы координатной сетки - от 1 до о- & .
Рассмотрим k, объектов, которые являются элементами печатно-го монтажа (контактными площадками, отверстиями, проводниками). Полагаем, что точки, соответствующие концам проводников, отверстия, контактные площадки расположены на поверхности так, что их центры совпадают с узлами координатной сетки. При этом положение объектов зададим упорядоченной парой 0 = /// 1Р ) t гДе ///у Функ» ция, задающая номер узла координатной сетки, в котором находится начало Р -го объекта, о(р) - функция, задающая номер узла, в котором находится конец р -го объекта; р=А& . Пусть (%s/pj,!/flpj)i (X &fp) rj/dtPM координаты начала и конца Р -го объекта. Если такой упорядоченной паре U-p соответствует контактная площадка или отверстие, то tf(P) $(Р) t Р с A ..., fej .
Утверждение 2. Принадлежащие множеству Иц_ два маршрута, один из которых - инверсия другого, имеют одинаковую длину. Доказательство очевидно. Следствие I. Количество маршрутов, подлежащих исследованию на длину при минимизации функции (3.1), равно
Отсюда видно, что найти оптимальный результат полным перебором безперспективно даже при малых значениях k , поэтому для решения задачи применен последовательно-итерационный алгоритм, основанный на идеях метода вектора спада [48,-- 57J ,
В процессе работы алгоритма на каждом шаге итерации (т.е. при фиксированных перестановках ь=С ,)находим такой булевый вектор tr , для которого f(L 11 )- пгіп. (В[ЯВ, І. it,)] L ijliJ, ijJ JhU (Ц),ЭЦ. (3.4) С этой целью применен способ, являющийся некотором модификацией известного метода Гаусса-Зайделя (метода поочередного изменения элементов) [Іш] . Он заключается в поиске тіл F(XtJs XJ, у lTtt)rlt) х Є)) , — где Л -( / / %т І І t ittb - некоторые векторы, имеющие размерность соответственно ,4.,...,0. &р - область определения вектора Ар , L=fn .
Для фиксированных значений X % Х/ Х/ ...,К найдем минимум функции одной векторной переменной rtx J&,- ,Xi,Xe Xe+x - XJ- (3 -5) Затем выбираем другое значение X/ , и для него (при остальных а фиксированных) минимизируем функцию (3.5), и т.д.
Суть предлагаемой модификации метода в следующем. Поскольку для вычисления значения ,/ как видно из выражения (3.4), необходимо определить Ч- f то переменные, по которым минимизируется функция цели, выбираются не произвольно, а в заданном порядке; t+i , t j, k . К тому же каждая булева переменная входит в два слагаеглых целевой функции, поэтому рассматриваем группы слагаемых по два и вместо задачи.(3.4) решаем следующие подзадачи:
Полагаем aS/iCC) = Ла » ш +- ftt 4 ) A0 Тогда рассматрива ло 0/ 1#4/ емую задачу записываем в общем виде: Фії, ijj-mln (вр ф/МЩЫ /rJl (3.6) Представим вычислительную схему алгоритма в следующем виде. По)с с с J , & ;f) Шаг I. Выбираем начальное приближение Ьс 1ъ л/с -1 t Шаг 2. Определяем значение //L , J для перестановки , решая задачу (3,6). Шаг 3. Находим вариант перестановки L f - , используя метод вектора спада и для него, решая задачу (3.6), вычисляем значение f( ,L J . Шаг 4. Переходим к шагу 5, бели ffi 5, г% (іг х шМ) , В противном случае в качестве начального значения выбираем тот вариант перестановки, для которого целевая функция принимает минимальное значение. Переходім к шагу 3. Шаг 5. Вычисления прекращаем. Решением задачи (3.4) прини-маем значение ffi ; ь /,
В случае минимизации частоты изменения направления движения значение I находил последовательно с использованием метода приближенной декомпозиции [і18J . Такой подход применим и при решении задач с большими значениями К- .
В качестве к. объектов рассмотрим упорядоченные пары, которым соответствуют отрезки проводников, расположенные на горизонтальных, вертикальных линиях координатной сетки или под углом 45 к осям координат, а также контактные площадки и отверстия.
В дальнейшем под горизонтальными линиями будем подразумевать строки, а под вертикальными - столбцы матрицы С , отображающей печатный слой с нанесенной на него сеткой.
Принципы функционирования системы ДИСИО
На этапе ввода система воспринимает управляющие директивы, которые определяют выполняемый шаг задания, задают внешние устройства для чтения описательных операторов1, устройства для вывода результатов, номера файлов и т. д. Каждый оператор проходит синтаксический контроль. Правильные операторы запоминаются системой, а неправильные корректируются в диалоговом или пакетном режимах -при этом осуществляется вывод соответствующих диагностических сообщений. Если исходная информация закодирована на устройстве планшетного типа, транслятор преобразует ее во внутренний формат данных без: предварительного синтаксического контроля. Неправильные операторы игнорируются.
Информация, вводимая с перфокарт проходит синтаксический контроль и исправляется в пакетном или диалоговом режимах. Затем данные преобразуются во внутреннюю форму.
На этапе семантического контроля контролируются наиболее часто допускаемые ошибки, такие например, как ошибочное количество модулей, базовых элементов, цепей электрической схемы, ошибочный номер радиоэлемента или вывода модуля в списке цепей. Подсчет количества цепей электрической схемы для сравнения с закодированным списком производится так: где Л/ - количество цепей; t количество связей, идущих с разъема печатной платы на входа радиоэлементов; л - количество базовых элементов в электрической схеме; о- - количест-во выходных контактов в базовых элементах t - го типа.
Оптимизационные задачи проектирования решаются алгоритмом, заданным пользователем или выбранным соответствующим программным модулем. Результаты запоминаются в архиве данных. Входной информацией для решения очередного этапа служат результаты решения, полученные автоматическим способом на предыдущем шаге,либо заданные пользователем. Служебными программами системы имеется возможность корректировать как входную информацию так и результаты вычислений на отдельных этапах. Ручная доработка результатов, проектирования (размещения, трассировки) производится в диалоговом режиме, информация вносится в текстовом виде с дисплея. Предусмотрена коррекция информации и с перфокарт. Система позволяет одновременно обрабатывать несколько заданий. Результаты решения очередной задачи хранятся в указанном пользователем файле.
По результатам трассировки комплекс программ формирования выходной информации готовит управляющие данные для устройств с программным управлением, С целью устранения "узких мест" на печатном слое при формировании управляющих программ предусматривается локальное изменение топологии печатных проводников. Управление вычислительным процессом на каждом этапе производится управляющей программой.
По желанию пользователя система формирует массив информации в формате, предназначенном для некоторых других САПР и подсистем. В процессе вычислений для считывания необходимой информации в комплексах программ предусмотрено обращение к архиву данных и библиотеки элементов и конструктивов. Архив данных состоит из файлов прямого доступа и содержит результаты вычислений.
Библиотека элементов и конструктивов состоит из двух файлов; в первом находится исходная информация, во втором- данные, представленные во внутреннем формате. Исходная информация готовится на входном языке, символы которого практически не отличаются от привычных для пользователя обозначений. Библиотека элементов и конструктивов содержит необходимую для решения задач проектирования и изготовления конструкторской документации,информацию о радиоэлементах. Служебные программы библиотеки корректируют содержащиеся в этих библиотеках данные, они же производят поиск и чтение параметров элементов, необходимых для проектирования (габаритные размеры, электрические параметры и др.), осуществляют вывод их графического изображения. В библиотеке содержатся используемые на практике типоразмеры печатных плат.
