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

Аннотация

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