Содержание к диссертации
Введение
1. Современное состояние проблемы размещения элементов 9
1.1. Анализ критериев размещения 9
1.2. Классификация алгоритмов размещения 13
1.2.1. Класс точных алгоритмов 14
1.2.2. Класс приближенных алгоритмов 18
І.2.3І Интерактивные алгоритмы 28
1.3. Анализ алгоритмов размещения разногабаритных элементов 30
1.4. Анализ методов оценки эффективности алгоритмов размещения 40
1.5. Постановка задачи 43
Выводы 46
2. Макроэлементшй принцип размещения разногабаритнбк элементов 47
2.1. Макроэлементный метод и его этапы 47
2.2. Методика выбора габаритных размеров макроэлементов 49
2.3. Последовательное распределение посадочных мест и назначение в них компонентов в макроэлементах 55
2.4. Размещение макроэлементов в регулярном монтажном поле 70
2.5. Алгоритм размещения компонентов, основанный
на макроэлементном принципе размещения 74
Выводы 75
3. Последовательное размещение разногабаритных компонентов методом сканирования в дискретном пространстве 76
3.1. Унифицированное посадочное место и способ его представления в дискретном поле 76
3.2. Выбор и обоснование применяемого критерия качества размещения 80
3.3. Стратегия выбора компонентов для размещения 84
3.4. Методика поиска посадочных мест в дискретном пространстве 90
3.5. Алгоритм размещения разногабаритных компонентов 98
Выводы 102
4. Исследование эффективности алгоритмов размещения разногабаритных компонентов 103
4.1. Организация программных комплексов для размещения разногабаритных компонентов 103
4.2. Экспериментальная оценка эффективности алгоритмов размещения 107
4.3. Рекомендации по применению алгоритмов раз мещения 116
Выводы 120
Заключение 122
Литература
- Классификация алгоритмов размещения
- Методика выбора габаритных размеров макроэлементов
- Унифицированное посадочное место и способ его представления в дискретном поле
- Организация программных комплексов для размещения разногабаритных компонентов
Введение к работе
В настоящее время системы автоматизированного проектирования (САПР) нашли применение во многих отраслях промышленности, но особенно прочное место они заняли в области создания устройств электронно-вычислительной техники, чему во многом способствовало то, что современные электронно-вычислительные машины (ЭВМ) и устройства электронно-вычислительной аппаратуры (ЭВА) строятся по модульному многбуровнему иерархическому принципу [74], что во многом облегчает автоматизацию процесса проектирования.
Преимущества САПР хорошо известны [72J , поэтому в решениях ХХУІ съезда КПСС было указано о необходимости дальнейшего расширения автоматизации проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники.
В последние годы большие работы ведутся по созданию ЭВМ четвертого поколения, элементную базу которых составляют боль -шие интегральные схемы (БЙСы) и гибридные большие интегральные схемы (ГБИСы). ШСы и ГЕЙСы характеризуются разнообразием размеров и форм составляющих их компонентов. Алгоритмическая база большинства действующих САПР ЭВМ и ЭВА рассчитана на проектирование модулей с регулярной топологией. Разногабаритность компонентов ШС и ГЕЙС не позволяет использовать эти методы проектирования и, прежде всего, методы решения задачи размещения компонентов схем.
Следовательно, актуальной является проблема создания новых эффективных методов и алгоритмов, способных обеспечить размещение разногабаритных компонентов.
В ходе решения поставленной проблемы предстоит выбрать математическую модель, описывающую топологию ГЕЙС и БИС, разработать эффективную алгоритмическую базу для решения задачи размещения разногабаритных компонентов, включить разработанную подсистему размещения разногабаритных компонентов в состав действующей системы автоматизированного проектирования топологии конструктивно-функциональных узлов (САПР КФУ) ЭВА.
Целью работы являются анализ существующих методов и алгоритмов размещения компонентов, разработка новых алгоритмов для подсистемы размещения разногабаритных компонентов с использованием ЭВМ третьего поколения.
Предмет и методы исследования. Предметом исследования являются алгоритмические методы решения задачи размещения разногабаритных компонентов ГБИС, БИС и многослойных печатных плат (МПП) и созданные на их основе машинные алгоритмы.
Методы исследования базируются на анализе содержательных аспектов проблемы, использовании методов теории множеств,теории графов, прикладного программирования и на экспериментах с программной реализацией предложенных алгоритмов.
Научная новизна работы заключается в получении следующих результатов:
- разработан макроэлементный метод размещения разногабаритных компонентов и на его основе алгоритм размещения компонентов ГБИС и БИС;
- исследована матричная модель монтажного поля, введено понятие унифицированного посадочного места и разработан способ его представления в матричной модели;
- разработан алгоритм размещения разногабаритных компонентов, использующий в качестве критерия оптимизации функцию, обеспечивающую равномерное распределение соединений по всей площади коммутационного поля и сокращающую число слоев коммутации на этапе трассировки;
- разработан единый методологический подход, объединяющий ряд частных методик, предназначенных для оценки эффективности алгоритмов размещения в зависимости от класса проектируемых схем.
Практическая ценность. Применение алгоритмов, разработанных в работе, позволяет включить их в качестве подсистемы в систему автоматизированного проектирования КФУ ЭВА. Практическая эксплуатация разработанной подсистемы показала, что использование предложенных алгоритмов позволяет повысить плотность упаковки размещенных компонентов, повысить процент автоматически разведенных соединений, уменьшить число слоев коммутации и улучшить технологичность изделия.
На основании данных экспериментальных исследований выработаны рекомендации по применению алгоритмов размещения и исполь -зованию режимов их работы.
Реализация работы. Результаты диссертационной работы использовались для создания подсистемы размещения разногабаритных компонентов, входящей в состав системы автоматизированного проектирования топологии КФУ ЭВА в рамках операционной системы ЭВМ третьего поколения (ОС ЕС). Разработанная система внедрена на ряде предприятий. Суммарный экономический эффект от внедрения составил 25,8 тыс.рублей.
Апробация работы. Основные научные положения диссертации опубликованы в 6 печатных работах и докладывались автором на:
- семинаре "Автоматизация проектирования электронно-вычислительной аппаратуры" ДЗЩТП, Ленинград, май 1980;
- ЮЛУ юбилейной научно-технической конференции профеесорско преподавательского состава Ленинградского института точной механики и оптики, Ленинград, октябрь 1980;
- семинаре "Машинные методы проектирования электронно-вычислительной аппаратуры" ДДН Ш, Ленинград, июнь 1981.
Работа состоит из введения, четырех глав, заключения и списка литературы.
В первой главе рассмотрены целевые функции, с помощью которых осуществляется один из этапов проектирования - этап размещения элементов, приведена классификация применяемых критериев. Анализируются методы, используемые для решения задач размещения. Особое место уделено алгоритмам размещения разногабаритных элементов, дана их классификация. Рассмотрены способы, оценивающие эффективность алгоритмов размещения, проведен их анализ. Приведена постановка задачи диссертационной работы.
Вторая глава посвящена разработке метода размещения разногабаритных компонентов в непрерывном монтажном поле. Сформули -рован макро элементный принцип размещения компонентов. Предложен способ для определения площади посадочных мест для разногабаритных компонентов. Разработан алгоритм, использующий идею макроэлементного метода, позволяющий успешно размещать разногабаритные компоненты.
В третьей главе рассматривается матричная модель монтажного поля, вводится понятие унифицированного посадочного места. Обосновывается критерий, применяемый для выбора посадочных мест размещаемых компонентов ГШС и МПП. Формулируются правила последовательного выбора компонентов для размещения. Описан метод сканирования, осуществляющий поиск посадочных мест в модифицированной матричной модели поля. Приведено описание разработанного алгоритма размещения разногабаритных компонентов.
Четвертая глава отведена вопросам организации разработанных программ в виде функциональных программных модулей, включенных в действующую систему автоматизированного проектирования топологии конструктивно-функциональных узлов, и проведению экспериментальных исследований разработанных алгоритмов. Приводятся данные сравнения разработанных алгоритмов с известными алгоритмами согласно предложенной методике оценки эффективности. Даются рекомендации по использованию предложенных алгоритмов.
Классификация алгоритмов размещения
В настоящее время нет устоявшейся классификационной системы алгоритмов размещения. В работах [Ъ,20,32,51,84,87,92,97,104J авторами приводятся различные варианты классификации алгоритмов,предназначенных для решения задач размещения. Каждая из предложенных классификационных систем построена на основе определенного признака, в качестве которого в одной системе служит тип модели, в другой - способ организации вычислительного процесса и т.п. Но каждый из этих признаков не позволяет получить единую стройную систему классификации. Любой из алгоритмов размещения направлен на отыскание оптимального решения задачи размещения, но не каждый алгоритм в состоянии найти глобальный оптимум. Думается, что способность того или иного алгоритма отыскать глобальный оптимум в задаче размещения и должна быть принята в качестве признака построения классификационной системы. С учетом предложенного признака классификации все алгоритмы размещения могут быть разделены на два класса: алгоритмы, гарантирующие глобальный оптимум,условно назовем их точными алгоритмами и алгоритмы, не гарантирующие получение глобального оптимума, последние назовем приближенными алгоритмами. Данное разделение справедливо для алгоритмов, в кото рых вычислительный процесс осуществляется без вмешательства человека, но в последнее время широкое распространение получают интерактивные способы проектирования. Хотя они не являются предметом исследования данной работы, тем не менее они должны быть учтены в системе классификации. Поэтому предлагается выделить интерактивные алгоритмы в самостоятельный класс. Классификация алгоритмов размещения приведена на рис.1.2.
Анализ алгоритмов данного класса начнем с группы алгоритмов, получивших название силовых. Силовые алгоритмы основаны на механической модели, с помощью которой размещаемые элементы заменяются материальными точками, на каждую из которых действуют силы притяжения от соседних точек [бз]. Если известен способ получения начального расположения точек [б2], то можно составить дифференци -альные уравнения движения этих точек под действием сил. Но решение для системы, в которой действуют лишь силы притяжения, может получиться неудовлетворительным, т.к. возможно слияние точек.Чтобы избежать неравномерности в размещении точек, вводятся силы отталкивания между точками и от краев области размещения,чтобы точки не вышли за границы области. Для того, чтобы система точек не совершала незатухающих колебаний, вводятся силы трения, направленные в сторону, противоположную скорости движения точек и прямо пропорциональные ей [62,63]. Но все равно полученное размещение не всегда получается равномерным, поэтому в [85] предлагается производить сдвиг материальных точек в фиксированные места с малым изменением их взаимного расположения.
В работе [79 ] рассматривается иной подход по представлению схемы механической аналогией. Элементы схемы и их соединения за меняются графом, вершинами которого являются элементы схемы,а ребрами - их связи. Каждое ребро графа считается пружиной.Для каждой связной пары вершин составляется вектор расстояния: где гї\- вектор силы взаимодействия между вершинами I и L ; ITUj.- характеризует упругость пружины (вес ребра).
Условие равновесия механической системы 21 Fit 0 дает искомое решение, которое получается хорошо разработанными методами анализа линейных схем, при этом величины S ,m , г заменяются соответственно на (J . . I (напряжение, проводимость, ток). Способ перехода к фиксированным координатам для данного метода описан в L98J.
B рассмотрен еще один подход, использующий идею силовых функций. Отличие данного алгоритма состоит в том, что в нем не решаются дифференциальные уравнения движения материальных точек. Прежде всего с помощью генератора псевдослучайных чисел получают первоначальное размещение, а затем вводятся силы притяжения между точками. Выбирается одна из точек, другие считаются неподвижными, подсчитывается сила, действующая на выбранную точку со стороны фиксированных точек, под действием которой выбранная точка перемещается. Аналогично вводятся силы, отталкивания. Данная процедура повторяется для каждой точки в отдельности, пока не будет получено приемлемое размещение.
Для алгоритмов, использующих идею силовых функций,положительным является то, что они позволяют свести задачу к вычислительным процедурам, для которых разработаны численные методы. К недостаткам нужно отнести следующее. Получаемое размещение, как правило, не обеспечивает нужной равномерности расположения элементов в монтажном пространстве. Метод силовых функций требует все же большого объема вычислений, сложен в подборе коэффициентов для различ -ных сил ц2б].
Методика выбора габаритных размеров макроэлементов
Задача определения габаритных размеров макроэлементов заключается в нахождении как габаритных размеров самих макроэлементов, так и их числа, при условии, что макроэлементами будет покрыта вся площадь поля размещения. Исходными данными для поставленной задачи служат габаритные размеры монтажного поля и размещаемых компонентов, а также количество компонентов каждого типоразмера.Как видно из формулировки задачи, данная задача относится к задачам комбинаторного типа и формально может быть задана следующим образом: найти минимальную площадь макроэлемента SM и число макроэлемен тов m при условиях: где K-u - число посадочных мест 1-го типа; S-L - площадь посадочного места L-го типа; S p - площадь монтажного поля; П - число типов посадочных мест.
Условие (I) означает, что посадочные места компонентов должны находиться в площади монтажного поля. Условие (2) предусматривает расположение посадочных мест лишь в областях макроэлементов, т.е. одно и то же посадочное место не может одновременно находиться в двух и более макроэлементах. Условие (3) ограничивает площадь макроэлемента. Условие (4) означает, что целое число макроэлементов должно полностью покрывать площадь поля размещения, не допуская пересечений макроэлементов и наличия площади, не покрытой ими.
Формализованная запись поставленной задачи сходна с задачами целочисленного программирования, так как в ходе решения необходимо не только найти площадь S н » а и целое число таких площадей. Подобные задачи решаются методами динамического программирования. Решение такими методами занимает длительное время и не всегда может быть приемлемым с практической точки зрения. В связи с этим предлагается эвристический способ решения данной задачи, позволяющий получить решение, близкое к одному из локальных оптимумов.
Прежде чем перейти к изложению предлагаемого способа, рассмотрим вопрос, связанный с определением площади, необходимой для установки компонента определенного типоразмера. Так как при размещении разногабаритных элементов установочные позиции не фиксиро ваны, то необходимо не только выбрать определенную площадь для установки самого компонента, но и зарезервировать часть площади,требуемой для подвода соединений к выводам компонента. Общая суммарная площадь определяет область монтажного поля, которую будем считать посадочным местом для компонента определенного типоразмера. На рис.2.1 показана область, необходимая для установки компонента с габаритными размерами X U} V и проведения трасс соединений к контактным площадкам, к которым подключены внешние выводы компо -нента.
Рассмотрим случай, когда трассы межсоединений могут располагаться лишь между установочными позициями, проведение трасс под установленными компонентами запрещено. Такое требование, определяющее правила построения трасс межсоединений, предъявляется к определенным классам печатных плат, больших гибридных и монолитных интегральных схем [92J и объясняется особенностями их конструкции и технологии изготовления. При определении общей площади, необходимой для размещения самого компонента и соединений, к нему подведенных, будем считать, что проводники, связывающие данный компонент с другими, распределены равномерно в области, охватывающей установленный компонент. Определим размеры этой области, т.е.(см. рис.2.1)определим величины AX1j,;AX2; AY1- AY .Допустим, что установленный компонент имеет Кі}КгіКі}К4внешних выводов, расположенных соответственно вдоль сторон компонента 1,2,3,4. Подсчитаем, исходя из условия равномерного расположения проводников,количество магистралей, необходимых для укладки соединений к контактным площадкам установочной позиции компонента. Рассмотрим одну из сторон, например, сторону 3 (см.рис.2.1) и определим предполагаемое число магистралей, проходящих вдоль данной стороны.
Унифицированное посадочное место и способ его представления в дискретном поле
Основная цель размещения - обеспечение благоприятных условий для построения трасс межсоединений. Под благоприятными условиями прежде всего следует понимать равномерность в распределении компонентов по всей площади монтажного поля и наличие каналов -областей между посадочными местами компонентов, по которым в дальнейшем будут прокладываться соединения между выводами компонентов. В задачах размещения однотипных элементов эти оба вопроса решаются заранее путем предварительного задания координат всех посадочных мест. При размещении разногабаритных компонентов данные вопросы, как правило, решаются непосредственно в ходе размещения при поиске местоположения установочных позиций, но так как речь идет о последовательном процессе размещения, то нет твердой гарантии, что полученное размещение компонентов будет равномерным. Поэтому для многих последовательных алгоритмов размещения разногабаритных компонентов характерна заключительная процедура перераспределения компонентов для достижения их равномерного расположения по площади монтажного поля. Однако данная процедура не всегда бывает эффективна, поэтому в настоящей работе предлагается новый подход к вопросу получения равномерной картины размещения разногабаритных компонентов. Суть предлагаемого подхода заключается в следующем. Вводится понятие унифицированного посадочного места, которое представляет собой некоторую область монтажного поля, предназначенную для установки в ней одного компонента наибольшего габарита или нескольких компонентов меньших габаритов. Унифицированные посадоч -ные места равномерно распределяются по всей площади монтажного поля, промежутки как между унифицированными посадочными местами,так и между компонентами, установленными на одном унифицированном посадочном месте, выполняют функции каналов, по которым будут разводиться все межсоединения.
Способ представления унифицированных посадочных мест определяется выбранной математической моделью монтажного поля, так как от принятой модели во многом зависит организация вычислительного процесса, связанного с нахождением координат расположения посадочных мест размещаемых компонентов. Известно, что при размещении разногабаритных компонентов значительная часть машинного времени расходуется именно на эти вычислительные операции, поэтому вполне понятно стремление многих авторов сократить объем данных вычислений. В настоящей работе уменьшение объема вычислительных операций достигается за счет использования дискретной модели монтажного поля, с заданными в ней унифицированными посадочными местами.
Для формального описания дискретной модели монтажного поля может быть использована матрица соответствующей размерности. Подобное представление монтажного поля названо матричной моделью монтажного поля \37]. В дальнейшем будем использовать также этот термин.
Использование матричной модели при размещении разногабаритных компонентов позволяет путем внесения определенных значений в матрицу поля задать унифицированные посадочные места, тем самым сведя операции геометрического анализа взаимного положения компонентов в поле размещения к операциям анализа значений соответст-вущих элементов матрицы поля.
Каждое унифицированное посадочное место рассчитано на установку в него компонента любого типоразмера.Поэтому для того,чтобы определить размеры згнифицированных посадочных мест и местоположение каждого из них, необходимо соответствующим образом закодировать определенные элементы матрицы поля. Для отличия дискретов поля, занимаемых унифицированными посадочными местами,от дискретов поля, не попавших в зоны этих мест, можно воспользоваться двоичным кодом. Однако двоичного кода не достаточно,так как кроме двух типов дискретов монтажного поля в поле размещения могут быть дискреты, занятые уже размещенными компонентами. Таким образом, монтажное поле будет содержать дискреты трех типов, которые необходимо качественно различать.
Организация программных комплексов для размещения разногабаритных компонентов
Разработанные в диссертационной работе алгоритмы размещения разногабаритных компонентов реализованы в виде комплексов программ, которые включены в систему автоматизированного проектирования топологии конструктивно-функциональных узлов (САПР КФУ) в качестве функциональных программных модулей (ФПМ).
САПР КФУ предназначена для проектирования топологии многослойных печатных плат, изготовляемых по методам открытых контактных площадок и сквозной металлизации переходных отверстий, и гибридных интегральных схем, изготовляемых методами толстопленочной технологии.
САПР КФУ является системой открытого типа, построенной по модульному принципу. Каждый из входящих в состав КФУ ФПМ реализует определенный этап конструкторского проектирования. Свойство наращиваемости, которым обладает система, позволяет вводить в состав системы новые программные модули, не нарушая при этом структуры и связей системы.
Выбор и установление нужного режима работы производится с помощью вводимого в систему описания работ,представляющего собой перечень тех из ФПМ, которые реализуют нужные этапы проектирования.
Исходной информацией для работы системы являются описания принципиальной электрической схемы на входном языке системы и конструктивно-технологических особенностей проектируемого узла, под которыми понимаются размеры коммутационного поля, габариты размещаемых компонентов, положение внешних разъемов, запрещенные для размещения и трассировки области и т.п.
Выходная информация представляет собой данные о топологии с размещенными компонентами и соединениями между ними. Выходные данные могут быть выведены через одно из внешних устройств.Форма и вид выходного документа зависят от установленного режима работы и выбранного устройства вывода.
Управление работой всей системы организуется супервизором стандартного математического обеспечения операционной системы единой системы (ОСЕС).
Оба включенных в систему ФПМ разработаны в соответствии с основными принципами построения САПР КФУ. ФПМ МЯКЫрпРеДназ-начен для решения задачи размещения разногабаритных компонентов в непрерывном монтажном поле, ФПМ HRKPP - в дискретном монтажном поле.
Работа ФПМ MRKMP организуется головной программой модуля, которая обеспечивает вызов исходных данных,вывод результатов размещения, выдачу аварийных сообщений и функционирование следущих подпрограмм модуля: - подпрограмма P0RU служит для определения габаритных размеров посадочных мест размещаемых компонентов; - подпрограмма PLRK формирует невозрастающий по максимальному из габаритных размеров посадочных мест массив. Если изменение ориентации устанавливаемых компонентов запрещено, то при формировании массива учитываются лишь размеры, определяющие высоту посадочных мест; - подпрограмма Р\д/Мопределяет габаритные размеры макроэлементов и их число; - подпрограмма Р\ЛЛ1/ производит размещение первого в макроэлементе посадочного места; - 105 - подпрограмма PW iK производит назначение в первое посадочное место макроэлемента одного из неразмещенных компонентов; - подпрограмма PWUM производит выбор неразмещенных посадочных мест, их примерку и установку выбранного посадочного места в макроэлементе. В случае разрешения переориентации компонентов в подпрограмме предусмотрен режим, позволяющий производить примерку посадочных мест с измененной ориентацией; - подпрограмма PWKL/ выбирает для размещения посадочного места соответствующего типоразмера компонент; - подпрограмма Р1/5М0ПРеДеляет число внешних связей каждого макроэлемента, формирует матрицу связности макроэлементов; - подпрограмма PR НЕ размещает макроэлементы в площади монтажного поля. В случае квадратной формы макроэлементов в программе предусмотрен режим, позволяющий изменять ориентацию макроэлемен -тов через каждые 90, а в случае прямоугольной формы - на 180. Данный режим разрешен, когда допускается переориентация всех компонентов.
Работа модуля MRKNP завершается выдачей данных о размещении компонентов. В выходном листинге содержатся следующие данные: - размеры поля размещения; - перечень размещенных компонентов с указанием координат их расположения, а также их габаритных размеров вдоль координатных осей.
