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

коммутационного пространства;
количество и геометрические размеры конструктивных элементов, подлежащих размещению;
схема

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

условия для по следующей трассировки проводников;
электричество: минимум искажения логических сигналов

в проводниках, минимальная задержка сигнала и др.
тепловыделение: равномерное распределение тепловыделяющих элементов по плате и т.п.

которых больше заданной;
минимум числа пересечение проводников;
максимальное число соединений между

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

(парных перестановок и групповых перестановок).
4. Дихотомические.
5. Силовые (алгоритм попарных релаксаций

и алгоритм Гото).

начиная от выходов КЛС к ее входам;
– элементам и цепям

каждого маршрута присваиваются ранги, соответствующие его длине, определяемой количеством элементов, включен-ных последовательно в данном пути распространения сигналов;
– наибольший ранг присваивается элементам самого длинного (критического) маршрута с максимальной задержкой сигнала N*tз.р.;
– если один и тот же элемент входит в несколько маршрутов, то его ранг определяется рангом элементов маршрута с наибольшей длиной (маршрута, для которого N  имеет наибольшее значение).

с элементом-приемником, позиция которого на коммутационном поле кристалла задано.
2. Выбрать

позицию на кристалле для размещения хА  в e-окрестности элемента-приемника и линии наикратчайшего распространения сигнала по данному маршруту.
3. Составить список смежных с хА элементов ХА = {хi / i = 1,n} и упорядочить их по рангам, где n – число элементов хi, , смежных с хА.
4. Выбрать во множестве ХА среди не размещенных элементов элемент с наибольшим рангом. Если наибольший ранг среди не размещенных имеет только один элемент хк, то перейти к п. 6, иначе – к п. 5.
5. Если среди не размещенных элементов наибольший ранг имеют два или более элементов, например, элементы хк и хq, то выбрать хк, с которым связаны большее число цепей с наибольшим рангом. Если элементы хк и хq эквиваленты и по этому показателю, то выбор одного из них осуществить в произвольном порядке.
6. Выбранный элемент хк  разместить на коммутационном поле кристалла в e - окрестности приоритетной позиции.
7. По отображению элемента хк составить список (множество) цепей        U = {uj / j =1, s}, где s – число цепей, инцидентных с входными выводами хк.
8. Упорядочить цепи в списке в соответствии с рангами элементов, инцидентных к ним и просматривать их последовательно, в порядке убывания рангов элементов.

Алгоритм выбора элементов и их размещения на кристалле:

элементов, инцидентных к двум или более цепям равны, то выбор

цепи осуществить в произвольном порядке.
10. Определить для выбранной цепи up элемент хp, который инцидентен к цепи up своим выходным выводом.
11. Если элемент хp окажется уже размещенным или элементом-источником сигнала, позиция которого на монтажном поле задано, то перейти к   п. 12, иначе – к п. 6.
         12. Проверить, все ли цепи uj, связанные с входными выводами элемента  хк  просмотрены. Если да, то перейти к п. 13, иначе выбрать следующую по списку цепь uк из множества U, т. е. uкÎU,  k ¹ p, p := k и перейти к п. 10.
13. Определить цепь uк, связанную с выходным выводом элемента хк.
14. Из числа элементов, инцидентных своими входными выводами цепи uк, выбрать элемент хt , который уже размещен.
15. Проверить смежность хt с элементами хi множества ЕА, т. е.  наличие его в списке ХА (хt Î ХА)  Если элемент хt отсутствует в списке ХА, то перейти к п. 10, если хt принадлежит к множеству ХА, то перейти к  п. 16.
16. Проверить, все ли элементы хi в списке ХА просмотрены. Если да, то перейти к п. 17, иначе – выбрать следующий по списку (среди не размещенных элементов) элемент и перейти к п. 6.
17. Перейти к размещению элементов по маршрутам, сходящимся к следующему элементу-приемнику.