РАЗРАБОТКА АЛГОРИТМА ДЕТАЛЬНОГО РАЗМЕЩЕНИЯ НА ПЛИС

Аннотация

Иерархические программируемые логические интегральные схемы (ПЛИС) состоят
из множества логических блоков, объединенных в группы. Для успешной трассировки необ-
ходимо оптимальное размещение элементов в пределах групп с учётом особенностей ар-
хитектуры локальных связей. Классические алгоритмы не способны обеспечить учёт раз-
личных особенностей архитектуры. Решение данной проблемы возможно только путем
разработки специализированных алгоритмов. В данной работе представлен алгоритм де-
тального размещения, в котором для вычисления оптимальных позиций элементов в группе
была разработана новая метрика, позволяющая оценить количество доступных локальных
связей между элементами в группах логических блоков с учётом особенностей архитекту-
ры связей между ними. Алгоритм детального размещения состоит из нескольких этапов.
На первом этапе группа логических элементов представляется в виде ориентированного
графа. На втором этапе определяется порядок размещения логических элементов в группе
с помощью алгоритма поиска в ширину. На финальном этапе для каждого элемента, со-
гласно полученному порядку, определяется оптимальное размещение в группе с учётом
разработанной метрики. Если среди свободных позиций для размещения в группе нет оп-
тимальной, то проверяются занятые позиции. Текущий элемент назначается на занятую
позицию, а для замененного элемента выполняется поиск новой. Такая замена может про-
водиться многократно, увеличивая вероятность нахождения оптимальной конфигурации.
Предложенный алгоритм был реализован и протестирован на наборах тестовых схем.
На основе результатов тестирования выполнено сравнение представленного алгоритма с
алгоритмом последовательного размещения. Сравнение алгоритмов показало, что применение разработанного алгоритма в маршруте проектирования в базисе специализированной ПЛИС позволяет сократить в среднем на 10% количество задействованных в трасси-
ровке глобальных коммутационных шин и увеличить количество используемых локальных
трассировочных ресурсов в среднем на 30%. Полученные результаты подтверждают работоспособность алгоритма и доказывают, что внедрение учета архитектуры внутренних связей ПЛИС повышает эффективность использования доступных трассировочных
ресурсов.