МЕТОД РЕШЕНИЯ ГРАФОВЫХ NP-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ПРИНЦИПА РАСПАРАЛЛЕЛИВАНИЯ ПО ИТЕРАЦИЯМ
Аннотация
При решении графовых NP-полных задач на многопроцессорных системах рост обо- рудования не приводит к пропорциональному росту производительности системы, поэто- му не всегда удается решить задачу за приемлемое время. Целью работы, описанной в статье, является минимизация времени решения задачи поиска максимальных клик графа с использованием реконфигурируемых вычислительных систем (РВС). При решении задачи на РВС методом распараллеливания по слоям рост производительности также замедля- ется, несмотря на лучшую степень масштабируемости по сравнению с многопроцессор- ными реализациями. В статье предложен метод создания параллельно-конвейерных про- грамм для реконфигурируемых вычислительных систем на основе распараллеливания по итерациям для решения графовых NP-полных задач. Рассмотрено, что использовать би- товый способ представления множеств (как в методе распараллеливания по слоям) для метода распараллеливания по итерациям не является эффективным. Новый метод отли- чается организацией вычислений, а именно – обработкой неупорядоченных множеств, доступ к элементам которых осуществляется не по адресам (как в массивах), а по значе- ниям (именам вершин и именам дуг графа). Показано, что новый метод на основе распа- раллеливания по итерациям, несмотря на более низкую удельную производительность, свя- занную с тем, что вычислительным подструктурам из-за символьного представления множеств необходимо обработать большее число промежуточных данных, обеспечивает практически линейный рост реальной производительности РВС при значительно большем количестве вычислительного ресурса по сравнению с методом распараллеливания по слоям.
