Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач

Для некоторых типов NP-трудных комбинаторных задач исследуются технологии поиска их решений посредством неполных алгоритмов, т.е. алгоритмов, конечность работы которых в общем случае не гарантируется. Речь идет об алгоритмах “программирования в ограничениях”, использующих в своей работе идею пополнения базы ограничений с отбрасыванием нерелевантных ограничений. Сравниваются два подхода к решению ряда комбинаторных задач посредством неполных алгоритмов. Основой первого подхода является крупноблочное распараллеливание исходной задачи с последующим решением получаемых задач неполным алгоритмом на кластере. Во втором подходе исходная задача решается на одном процессора кластера (фактически на ПК) тем же самым алгоритмом. Показано, что в ряде случаев коэффициент ускорения, которое достигается в первом подходе, может существенно превосходить число процессоров кластера. Работа выполнена при финансовой поддержке РФФИ (код проекта 07-01-00400а) и при частичной поддержке гранта Президента РФ НШ 1676.2008.1. Статья подготовлена по материалам доклада авторов на международной научной конференции “Параллельные вычислительные технологии” (ПаВТ-2008; http://agora.guru.ru/pavt).