Application of SAT Approach to Switch Blocks Routing for Reconfigurable System-on-a-chip
IPPM RAS, D. V. Zhukov, IPPM RAS, Daniil A. Zheleznikov, IPPM RAS, Mariya A. Zapletina · Problems of advanced micro- and nanoelectronic systems development · 2020
Аннотация -В статье предлагается метод трассировки коммутационных блоков реконфигурируемых систем на кристалле островного типа на основе SAT подхода.Целью процедуры трассировки является достижение полной трассируемости списка межсоединений при стремлении к их минимальной длине и величине задержки.При SAT подходе для каждого блока коммутации создаются два списка ограничений.Базовые ограничения формируются, исходя из схемотехнической конфигурации коммутационного блока.Конфликтные ограничения задаются по мере итерационной трассировки списка цепей, назначенных на блок коммутации по завершению глобального этапа трассировки.Впоследствии ограничения обоих видов транслируются в булеву систему уравнений, передаваемую в SAT решатель.Задача детальной трассировки была решена для коммутационных блоков двух типов связности.На основании вычислительных экспериментов показано, что предложенный алгоритм, реализованный на языке программирования C, отвечает требованиям полноты трассируемости и способствует минимизации времени, затрачиваемого на процедуру трассировки.