РЕАЛИЗАЦИЯ АЛГОРИТМА БРОНА-КЕРБОША НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Аннотация

Поиск максимальных клик графа является одной из фундаментальных проблем тео-рии графов и играет важную роль во многих приложениях. Задача о клике решается при анализе социальных сетей для обнаружения некоторого сообщества, в биоинформатике – для структурного выравнивания белка в трех измерениях, в САПР электрических схем – для размещения элементов и оптимизации. При этом данная задача является NP-полной, а это значит, что из-за ее высокой трудоемкости не всегда можно найти решение за приемле-мое время. Целью работы, описанной в статье, является минимизация времени решения задачи поиска максимальных клик графа с использованием реконфигурируемых вычисли-тельных систем (РВС). Предложен новый способ структурной реализации алгоритма Бро-на-Кербоша на РВС с применением оптимизации, помогающей в балансировке рабочей на-грузки между вычислительными ядрами и основанной на сортировке вершин по порядку вырождения. При реализации был выбран битовый способ представления множеств, когда позиция бита соответствует номеру элемента множества, а его значение является признаком присутствия либо отсутствия элемента во множестве. Выполнен анализ информационного графа одной итерации алгоритма и полного информационного графа всей задачи. Предложена вычислительная структура, реализующая информационный граф задачи на РВС с типом вычислений вложенный конвейер. Оценка скорости решения задачи на РВС выполнена на имитационной модели, которая моделирует выполнениеалгоритма так, как он будет исполняться на РВС. Результат работы модели представ-лен в том числе и в виде функций регрессии, которые отражают зависимость ускорения вычисления алгоритма от количества вычислительных узлов. Показано, что при решении задачи на многопроцессорной вычислительной системе при превышении определенного количества используемых процессорных ядер рост производительности практически не наблюдается, и дальнейшее уменьшение времени решения задачи становится невозможным. Однако при решении задачи на тех же графах на РВС рост производительности близок к линейному и, таким образом, увеличение аппаратных затрат приводит к почти линейному уменьшению времени решения задачи.