Решение - задача - трассировка
Cтраница 1
Решение задачи трассировки в два этапа облегчает реализацию этого метода на ЭВМ, так как на этапе макротрассировки в качестве ограничений учитываются лишь основные метрические параметры коммутационного поля, а на последующем этапе микротрассировки рассматриваются только геометрические характеристики трасс. При этом результаты решения задачи на первом этапе используются как ограничения на втором этапе. [1]
Для решения задач трассировки используется, как правило, несколько алгоритмов. Этот алгоритм позволяет отыскивать кратчайший путь между двумя заданными точками в дискретном пространстве и строит этот путь при минимальном количестве пересечений других путей. На основе волнового алгоритма разрабатываются многие другие алгоритмы, позволяющие решать разнообразные задачи трассировки. При разработке систем автоматизированного проектирования самым важным и сложным вопросом остается разработка алгоритмических блоков. [2]
Перед решением задачи трассировки производится распределение инвариантных ( логически равнозначных) контактов различных конструктивных единиц. Распределение инвариантных контактов следует рассматривать как средство для дополнительного улучшения возможностей последующей трассировки соединений. [3]
При решении задачи трассировки строят множество трасс, соединяющих выводы элементов соответствующих цепей схемы. Разработка отдельной трассы представляет собой построение на фиксированных вершинах минимального покрывающего или связывающего дерева, а разработка множества трасс сводится к построению леса непересекающихся минимально покрывающих или связывающих деревьев. Известно, что на п вершинах можно построить п - 2 различных деревьев, поэтому точное решение задачи трассировки методом полного перебора практически нереализуемо. [4]
При решении задачи трассировки линий связи системность подхода заключается в нахождении приемлемого компромисса с учетом схемотехнических ( минимизация помех), конструкторских ( минимизация числа слоев) и технологических ( минимизация изгибов трасс, межслойных переходов, перемычек из объемного провода) факторов. При увеличении числа слоев трассировка упрощается, но стоимость платы растет. При малом числе слоев ( ОПП, ДПП) стоимость платы снижается, но увеличивается сложность трассировки без перемычек, которые увеличивают стоимость сборки и снижают надежность платы. Трассировка печатных плат может осуществляться вручную, автоматизированным или автоматическим методом. Таким образом, при проектировании электрических соединений необходимо учитывать возможности технологических процессов и их стабильность. [5]
Результаты компановки являются исходными данными для решения задачи трассировки. В настоящее время разработано большое число алгоритмов трассировки, принцип действия которых основан на том, что поле условно представляется в виде дискретного пространства с заданным шагом координатной сетки от 0 5 до 3 мм. Элементы соединяются путем последовательного заполнения дискретов проводниками по одному из известных алгоритмов. Наибольшее распространение получили следующие классы алгоритмов и их модификации: волновые ( алгоритмы ЛИ), лучевые, топографические. [6]
 |
Сети магистралей ( а и каналов ( б межсоединений БИС. [7] |
Такой подход позволяет уменьшить зависимость результата решения задачи трассировки в целом от порядка прокладки отдельных трасс, которая в сильной степени проявляется в последовательных процедурах трассировки на основе волнового метода. Для этой же цели используют двухступенчатые методы трассировки, в которых сначала распределяют магистрали по каналам, а затем выполняют окончательную разводку магистралей внутри каждого канала. Предварительное распределение магистралей по каналам позволяет учесть взаимное влияние расположения трасс в масштабе всего коммутационного поля кристалла, в результате чего зависимость от порядка прокладки трасс существенно уменьшается. [8]
В настоящее время существуют несколько хорошо отработанных алгоритмов решения задач трассировки соединений. Большинство из них базируются на использовании волнового алгоритма, суть которого заключается в следующем. [9]
 |
Вспомогательное объединение нейронной сети с генетическим алгоритмом. [10] |
К немногочисленным обратным случаям относится гибридная сие тема, предназначенная для решения задачи трассировки [26, 27], которая классифицируется в [39] как пример вспомогательного объединения нейронных сетей и генетических алгоритмов. В этой системе генетический алгоритм используется в качестве оптимизационной процедуры, предназначенной для нахождения кратчайшего пути. Нейронная сеть применяется при формировании исходной популяции для генетического алгоритма. [11]
Участие конструктора не только позволит учесть все особенности работы схемы, но и заложить предпосылки для 100 % - ного решения ЭВМ задачи трассировки при ограниченном числе слоев, а также предопределить качественный результат работы ЭВМ, что очень важно для ее эффективного использования. [12]
Для реализации волновых алгоритмов монтажное поле разбивается на прямоугольные площадки исходя из допустимых размеров проводников и расстояний между ними, Решение задачи трассировки сводится к определению последовательности прохождения прямоугольных площадок. [13]
Рассмотренные алгоритмы в основном характерны для задач покрытия, разбиения и размещения. Для решения задач трассировки применяют другие алгоритмы. Различают два этапа решения задач трассировки. На первом этапе производится распределение соединений по слоям. Эта задача сводится к задаче построения минимального связывающего дерева. Алгоритмы, предназначенные для решения задач первого этапа трассировки, можно назвать распределительными. [14]
Поэтому важным фактором организации трассировки является правильная очередность прокладки соединений. Накопленный в настоящее время опыт решения задач трассировки БИС показывает, что применение простейших способов установления очередности прокладки трасс ( например, сначала наиболее коротких или, наоборот, сначала наиболее длинных) не дает заметного эффекта улучшения показателей качества рассматриваемой задачи. Поэтому для увеличения процента разведенных цепей применяют несколько более сложные приемы формирования последовательности прокладки проводников. Одним из них является метод прямоугольника, когда очередность устанавливается равной числу выводов других цепей, попадающих в прямоугольник, построенный таким образом, чтобы выводы оцениваемого соединения находились в его противоположных углах. [15]
Страницы: 1 2