Реферат: Методы и алгоритмы компоновки, размещения и трассировки печатных плат

Московский государственный институт электроники иматематики

(Технический университет)

Кафедра ИТАС

РЕФЕРАТ

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

                                                                                                                                  Выполнил:

                                                                                                            

                                                                                                                   Проверил:

                Принял:       

МОСКВА 2003

ОГЛАВЛЕНИЕ

1.<span Times New Roman"">     

Введение

2.<span Times New Roman"">     

Алгоритмы компоновка

3.<span Times New Roman"">     

Алгоритмы размещения

4.<span Times New Roman"">     

Алгоритмы трассировки<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">
ВВЕДЕНИЕ

При конструкторском проектировании РЭА(радиоэлектронной аппаратуры) решаются задачи, связанные с поиском наилучшеговарианта конструкции, удовлетворяющего требованиям технического задания имаксимально учитывающего возможности технологической базы производства. Теснаявзаимосвязанность задач и большая размерность каждой из них обычно не позволяетпредложить метод поиска оптимального конструктивного решения в едином цикле всвязи с трудностями создания общей математической модели, комплексноучитывающей особенности конструкторско-технологической базы производства.Поэтому  разработка и реализацияалгоритмов и методов решения отдельных задач этапа конструкторскогопроектирования: компоновки, размещения и трассировки,- до сих пор остаютсяактуальными проблемами, решение которых неотъемлемо связано с развитием системавтоматизации проектирования.

2.<span Times New Roman"">     

АЛГОРИТМЫ КОМПОНОВКИ

На этапе конструкторского проектирования решаютсявопросы, связанные с компоновкой элементов логической схемы в модули,модулей  в ячейки, ячеек в панели и т. д.Эти задачи в общем случае тесно связаны между собой, и их решение позволяетзначительно сократить затраты и трудоемкость указанного этапа в САПР. Обычнозадачи компоновки рассматриваются как процесс принятия решений в определенныхили неопределенных условиях, в результате выполнения которого части  логической схемы располагаются вконструктивных элементах i-го уровня, аэти элементы размещаются в конструктивных элементах  (i+1) –гоуровня и т. д., причем расположение выполняется с оптимизацией по выбранномукритерию.

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

 Для построенияформальной математической модели компоновочных задач удобно использовать теориюграфов. При этом электрическую схему интерпретируют ненаправленным мультиграфом,в котором каждому конструктивному элементу (модулю) ставят в соответствиевершину мультиграфа, а электрическим связям схемы – его ребра. Тогда задачакомпоновки формулируется следующим образом, Задан мультиграф G(X,U). Требуется “разрезать” его на отдельные куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) так, чтобы число ребер, соединяющих эти куски, быломинимальным, т.е.

минимизировать  <img src="/cache/referats/15557/image002.gif" v:shapes="_x0000_i1025">  i≠j

при<img src="/cache/referats/15557/image004.gif" v:shapes="_x0000_i1026"><img src="/cache/referats/15557/image006.gif" v:shapes="_x0000_i1027">  i,j=  1,2,…,k,

гдеUij– множество ребер, соединяющих куски Gi(Xi,Ui) и Gj(Xj,Uj).

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

            Известные алгоритмы компоновки можноусловно разбить на пять групп:

1.<span Times New Roman"">     

алгоритмы, использующие методы целочисленногопрограммирования.

2.<span Times New Roman"">     

последовательные алгоритмы

3.<span Times New Roman"">     

итерационные алгоритмы

4.<span Times New Roman"">     

смешанные алгоритмы

Алгоритмы первой группы хотя и позволяют получитьточное решение задачи, однако для устройства реальной сложности фактически нереализуемы на ЭВМ. В последнее время наибольшее распространение получилиприближенные алгоритмы компоновки (последовательные, итерационные, смешанные).При использовании последовательных алгоритмов сначала по определенному правилувыбирают вершину графа, затем осуществляют последовательный выбор вершин (изчисла нераспределенных) и присоединение их к формируемому куску графа. Послеобразования первого куска переходят ко второму и т. д. до получения желаемогоразрезания исходного графа. В итерационных алгоритмах начальное разрезаниеграфа на куски выполняют произвольным образом; оптимизация компоновкидостигается парными или групповыми перестановками вершин графа из различныхкусков. Процесс перераспределения вершин заканчивают при получении локальногоэкстремума целевой функции, удовлетворяющим требованиям разработчика. Всмешанных алгоритмах компоновки для получения начального варианта “разрезания” используетсяалгоритм последовательного формирования кусков; дальнейшая оптимизация решенияосуществляется перераспределением вершин между отдельными кусками графа.

Последовательные алгоритмыкомпоновки

 

 

В последовательных алгоритмах компоновки «разрезание»исходного графа G(X,U) на куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) сводится к следующему. В графе G(X,U) находят вершину xi<img src="/cache/referats/15557/image008.gif" v:shapes="_x0000_i1028"> Xсминимальной локальной степенью <img src="/cache/referats/15557/image010.gif" v:shapes="_x0000_i1029">

Если таких вершин несколько, то предпочтение отдаютвершине с максимальным числом кратных ребер. Из множества вершин, смежных свершинами формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает минимальноеприращение связей куска с еще нераспределенными вершинами. Данную вершину xi<img src="/cache/referats/15557/image008.gif" v:shapes="_x0000_i1030"> XX1включают в G1(X1,U1), если не происходит нарушения ограничения по числувнешних связей куска, т.е.

<img src="/cache/referats/15557/image012.gif" v:shapes="_x0000_i1031">

гдеαjε– элемент матрицы смежностиисходно графа G(X,U); δ(xg) – относительный вес вершины xg, ,равный приращению числа внешних ребер куска G1(X1,U1) привключении вершины xg во множество X1; E– множество индексов вершин, включенных в формируемыйкусок графа на предыдущих шагах алгоритма; m– максимально допустимое число внешних связейотдельно взятого куска со всеми оставшимися.

            Указанный процесс продолжается дотех пор, пока множество X1не будет содержать nэлементов либоприсоединение очередной нераспределенной вершины xj к куску  G1(X1,U1) неприведет к нарушению ограничения по числу внешних соединений куска, равному

                                                 <img src="/cache/referats/15557/image014.gif" v:shapes="_x0000_i1032">

            Следует отметить, что величина  <img src="/cache/referats/15557/image014.gif" v:shapes="_x0000_i1033"> не является монотоннойфункцией |X1|, поэтому, для того чтобы убедится в невозможностидальнейшего формирования куска вследствие нарушения последнего ограничения,необходимо проверить его невыполнимость на последующих шагах увеличениямножества X1вплоть до n. Вкачестве окончательного варианта выбирают кусок G10(X10,U10), содержащий максимально возможное число вершин графаG(X,U), для которого выполняются ограничения на числовнешних связей и входящих в него вершин (nmin-nmax).

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

            Сформулируем алгоритмпоследовательной компоновки конструктивных элементов.

1)<span Times New Roman"">    

t:0

2)<span Times New Roman"">    

Xf= Xt= Ø; t=t+1; Θ=1; α=nmax,

Где t, Θ– порядковые номера формируемого куска иприсоединяемой вершины; α–ограничение на число вершин в куске.

3)<span Times New Roman"">    

По матрице смежности исходного графа | αhp|NxN, где N–число вершин исходного графа (при большом значении Nдля сокращения объема оперативной памяти ЭВМиспользуем не саму матрицу смежности, а её кодовую реализацию), определяемлокальные степени вершин <img src="/cache/referats/15557/image016.gif" v:shapes="_x0000_i1034">

4)<span Times New Roman"">    

Из множества нераспределенных вершин Xвыбираемвершину xjс ρ(xj) = <img src="/cache/referats/15557/image018.gif" v:shapes="_x0000_i1035">

5)<span Times New Roman"">    

Из подмножества вершин Xlс одинаковой локальной степенью выбирают вершину xjс максимальнымчислом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| = <img src="/cache/referats/15557/image020.gif" v:shapes="_x0000_i1036">

6)<span Times New Roman"">    

Запоминаем исходную вершину формируемого куска графа <img src="/cache/referats/15557/image022.gif" v:shapes="_x0000_i1037">

7)<span Times New Roman"">    

По матрице смежности <img src="/cache/referats/15557/image024.gif" v:shapes="_x0000_i1038"> строим множество Xs= <img src="/cache/referats/15557/image026.gif" v:shapes="_x0000_i1039"> и определяемотносительные веса вершин <img src="/cache/referats/15557/image028.gif" v:shapes="_x0000_i1040">

<img src="/cache/referats/15557/image030.gif" v:shapes="_x0000_i1041">.

8)<span Times New Roman"">    

Из множества XS выбираемвершину <img src="/cache/referats/15557/image032.gif" v:shapes="_x0000_i1042">  п.10.Если таких вершин несколько, то переходим к п.9.

9)<span Times New Roman"">    

Из подмножества вершин Xvс одинаковым относительным весом выбираем вершину xjс максимальнойлокальной степенью, т.е. <img src="/cache/referats/15557/image034.gif" v:shapes="_x0000_i1043">

10)<img src="/cache/referats/15557/image036.gif" v:shapes="_x0000_i1044">

11)Если >m, топереходим к п.13.

12)Рассмотренные вершины включаем в формируемый кусок  Xf= Xt.

13)Θ= Θ+ 1.

14)Если Θ> α, то переходим к п.15, а противном случае – к п.7.

15)Если |Xf|<nmin,где nmin–минимально допустимое число вершин в куске, то переходим к п.21.

16)Выбираем окончательный вариант сформированного кускаграфа:

Xt= Xf; X= XXt; α= nmax.

17)Если|X|> nmax, топереходим к п.20.

18)Если |X|< nmin  , то переходим к п.21.

19)Определяем число внешних связей последнего кускаграфа:

                  <img src="/cache/referats/15557/image038.gif" v:shapes="_x0000_i1045">

             где  F– множествоиндексов вершин, входящих в X. Если <img src="/cache/referats/15557/image040.gif" v:shapes="_x0000_i1046">

20)Если t<k– 1, где k  — число кусков разрезания графа, то переходимк п.2, в противном случае – к п.23.

21)Предыдущий цикл «разрезания» считаемнедействительным. Если t>1,  т.е. имеется как минимум один ранеесформированный кусок, то переходим к п.22. в противном случае – к п.23.

22)Ищем другой допустимый вариант формированияпредыдущего куска с меньшим числом вершин: t= t– 1; <img src="/cache/referats/15557/image042.gif" v:shapes="_x0000_i1047">

Переходим кп.7.

23)Задача при заданных ограничениях не имеет решения.

24)Конец работы алгоритма.

Рассмотренный алгоритм прост, легко реализуется на ЭВМи позволяет получить решение задачи компоновки. Также среди достоинств даннойгруппу алгоритмов выступает высокое быстродействие их при решении задачкомпоновки.

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

Итерационные алгоритмы компоновки

 

 

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

            Рассмотрим основную идеюитерационного алгоритма разбиения графа G, заданного матрицей смежности, с минимизацией числасоединительных ребер. Разбиение графа G= (X,U) на lподграфов G1= (X1,U1), G2= (X2,U2),…,Gl= (Xl,Ul)сведем к разбиению на два подграфа. С этой целью вматрице смежности Rвыделим по главной диагонали две подматрицы R1и R2. Приэтом порядок подматрицы R1равен числу вершин, которые должны находится в G1, апорядок подматрицы R2– числу всех оставшихся вершин графа. Необходимо такпереставить строки и столбцы матрицы R, чтобычисло ребер между G1и оставшейся частью графа Gбыломинимальным. После этого подматрицу R1из матрицы R исключаем, вычеркнув из Rстрокии столбцы, соответствующие элементам R1. Далее подматрицу R1’разбиваем снова на две подматрицы R2и R2’, причем порядок R2  соответствует числу вершин второговыделяемого подграфа, а порядок R2– числу оставшихся вершин графа. Переставляем строкии столбцы R1’с цельюминимизации числа соединительных ребер. После этого подматрица R2’исключается и процесс повторяется до тех пор, пока небудет выполнено разбиение графа Gна lподграфов.

            Основная идея алгоритма заключаетсяв выборе таких строк и столбцов, перестановка которых приводит к сосредоточениюв диагональных клетках матрицы Rмаксимального числа элементов. Построим прямоугольнуюматрицу   W= ||wi,j||nix(n-ni), в которой строки определяются вершинамииз множества I, а столбцы – из множества V, <img src="/cache/referats/15557/image044.gif" v:shapes="_x0000_i1048">kстроки(<img src="/cache/referats/15557/image046.gif" v:shapes="_x0000_i1049">и qстолбца <img src="/cache/referats/15557/image048.gif" v:shapes="_x0000_i1050"> находится элемент

    <img src="/cache/referats/15557/image050.gif" v:shapes="_x0000_i1051">

гдеrk,q–элемент матрицы смежности R.

            Элемент wk,qматрицы W характеризует изменение числа соединительныхребер между Giи Gjприперестановке вершин <img src="/cache/referats/15557/image052.gif" v:shapes="_x0000_i1052"> и <img src="/cache/referats/15557/image054.gif" v:shapes="_x0000_i1053">W,можно найти подстановку, которая увеличит число элементов в подматрицах R1и R1’. Такой процесс повторяется до тех пор, пока  в подматрице R1несосредоточится максимальное число единиц.

            В итерационных алгоритмахпредусмотрена возможность поиска оптимального варианта для различных начальныхразбиений. Это связано с тем, что при использовании итерационных алгоритмовоптимальность решения в значительной мере зависит от того, насколько удачно былопроизведено начальное разбиение графа G(X,U).

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

3.<span Times New Roman"">     

АЛГОРИТМЫ РАЗМЕЩЕНИЯ

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

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

Поэтому все применяемые в настоящее время алгоритмыразмещения используют промежуточные критерии, которые лишь качественноспособствуют решению основной задачи: получению оптимальной трассировкисоединений. К таким критериям относятся: 1) минимум суммарной взвешенной длинысоединений; 2) минимум числа соединений, длина которых больше заданной; 3)минимум числа пересечение проводников; 4) максимальное число соединений междуэлементами, находящимися в соседних позициях либо в позициях, указанныхразработчиком; 5) максимум числа цепей простой конфигурации.

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

В зависимости от конструкции коммутационной платы испособов выполнения соединений расстояние между позициями установки элементовподсчитывается по одной из следующих формул:

<img src="/cache/referats/15557/image056.gif" v:shapes="_x0000_i1054"><img src="/cache/referats/15557/image058.gif" v:shapes="_x0000_i1055"><img src="/cache/referats/15557/image060.gif" v:shapes="_x0000_i1056">

В общем виде задача размещения конструктивныхэлементов на коммутационной плате формулируется следующим образом. Заданомножество конструктивных элементов R={r1,r2,…,rn}и множество связей между этими элементами V={v1,v2,…,vp}, а также множество установочных мест (позиций) накоммутационной плате T={t1,t2,…,tk}. Найти такое отображение множества Rнамножестве T, которое обеспечивает экстремум целевой функции

<img src="/cache/referats/15557/image062.gif" v:shapes="_x0000_i1057">,    где cij–коэффициент взвешенной связности.

Силовые алгоритмы размещения

 

 

В основу этой группы алгоритмов положен динамическийметод В.С. Линского. Процесс размещения элементов на плате представляется какдвижение к состоянию равновесия системы материальных точек (элементов), накаждую из которых действуют силы притяжения и отталкивания, интерпретирующиесвязи между размещаемыми элементами. Если силы притяжения, действующие междулюбыми двумя материальными точками riи rjпропорциональнычислу электрических связей между данными конструктивными элементами, то состояниеравновесия такой системы соответствует минимуму суммарной длины всехсоединений. Введение сил отталкивания материальных точек друг от друга и отграниц платы исключает возможность слияния двух любых точек и способствует ихравномерному распределению по поверхности монтажного поля. Чтобы устранитьвозникновение в системе незатухающих колебаний, вводят силы сопротивлениясреды, пропорциональные скорости движения материальных точек.

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

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

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

Итерационные алгоритмы размещения

 

 

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

            В случае минимизации суммарнойвзвешенной длины соединений формула для расчета изменения значения целевойфункции при перестановке местами элементов riи rj, закрепленных в позициях tfи tg, имеет вид:

                        <img src="/cache/referats/15557/image064.gif" v:shapes="_x0000_i1058">

гдеpи h(p)–порядковый номер и позиция закрепления неподвижного элемента rp.Если <img src="/cache/referats/15557/image066.gif" v:shapes="_x0000_i1059">riи rj, приводящую к уменьшению целевой функции на <img src="/cache/referats/15557/image068.gif" v:shapes="_x0000_i1060">

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

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

Последовательные алгоритмы размещения

 

 

Последовательныеалгоритмы основаны на допущении, что для получения оптимального размещениянеобходимо в соседних позициях располагать элементы, максимально связанные другс другом. Сущность этих алгоритмов состоит в последовательном закреплениизаданного набора конструктивных элементов на коммутационной плате относительноранее установленных. В качестве первоначально закрепленных на плате элементовобычно выбирают разъемы, которые искусственно «раздвигают» до краев платы. Приэтом все контакты разъемов равномерно распределяются по секциям (столбцам истрокам координатной сетки). На каждом l-ом шаге (l=1,2,…,n) для установки на коммутационную плату выбираютэлемент <img src="/cache/referats/15557/image070.gif" v:shapes="_x0000_i1061"> из числа еще неразмещенных, имеющий максимальную степень связности с ранее закрепленнымиэлементами Rl-1. В большинстве используемых в настоящее времяалгоритмов оценку степени связности производят по одной из следующих формул:

<img src="/cache/referats/15557/image072.gif" v:shapes="_x0000_i1062">

<img src="/cache/referats/15557/image074.gif" v:shapes="_x0000_i1063">

где cij– коэффициент взвешенной связности элементов iи j; Jl-1– множество индексов элементов, закрепленных напредыдущих l-1шагах; n– общеечисло размещенных элементов.

            Если установочные размеры всехразмещаемых на плате элементов одинаковы, то выбранный на очередном шагеэлемент <img src="/cache/referats/15557/image070.gif" v:shapes="_x0000_i1064"> закрепляют в тойпозиции <img src="/cache/referats/15557/image076.gif" v:shapes="_x0000_i1065"> из числа незанятых,для которой значение целевой функции <img src="/cache/referats/15557/image078.gif" v:shapes="_x0000_i1066"> с учетом ранееразмещенных элементов Rl-1минимально. В частности, если критерием оптимальностиявляется минимум суммарной взвешенной длины соединений, то

<img src="/cache/referats/15557/image080.gif" v:shapes="_x0000_i1067">

где dfj– расстояние между f-ой позицией установки элемента <img src="/cache/referats/15557/image070.gif" v:shapes="_x0000_i1068"> и позициейразмещенного ранее элемента rj; Tl-1– множество позиций, занятых элементами после (l-1)-го шагаалгоритма.

            Процесс размещения алгоритма заканчивается послевыполнения nшаговалгоритма.

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

4.<span Times New Roman"">     

АЛГОРИТМЫ ТРАССИРОВКИ

 

 

 

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

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

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

            Основная задача трассировкиформулируется следующим образ

еще рефераты
Еще работы по радиоэлектронике