Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач
Семенов А.А., Заикин О.С.

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

Семенов А.А., Заикин О.С. - Институт динамики систем и теории управления Сибирского отделения РАН, ул. Лермонтова, 134, 664033, Иркутск;     e-mail: biclop@rambler.ru,   oleg.zaikin@icc.ru