Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач
Ключевые слова:
база ограничений, неполнота, крупноблочный параллелизм, декомпозиция, программирование в ограничениях, параллельные программы, прогнозная функцияАннотация
Для некоторых типов NP-трудных комбинаторных задач исследуются технологии поиска их решений посредством неполных алгоритмов, т.е. алгоритмов, конечность работы которых в общем случае не гарантируется. Речь идет об алгоритмах «программирования в ограничениях», использующих в своей работе идею пополнения базы ограничений с отбрасыванием нерелевантных ограничений. Сравниваются два подхода к решению ряда комбинаторных задач посредством неполных алгоритмов. Основой первого подхода является крупноблочное распараллеливание исходной задачи с последующим решением получаемых задач неполным алгоритмом на кластере. Во втором подходе исходная задача решается на одном процессора кластера (фактически на ПК) тем же самым алгоритмом. Показано, что в ряде случаев коэффициент ускорения, которое достигается в первом подходе, может существенно превосходить число процессоров кластера. Работа выполнена при финансовой поддержке РФФИ (код проекта 07-01-00400-а) и при частичной поддержке гранта Президента РФ НШ 1676.2008.1. Статья подготовлена по материалам доклада авторов на международной научной конференции «Параллельные вычислительные технологии» (ПаВТ-2008; http://agora.guru.ru/pavt2008).
Библиографические ссылки
- Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
- Cook S.A. The complexity of theorem-proving procedures// Proc. of the Third Ann. ACM Symp. on Theory of Computing. Shaker Heights (Ohio, USA), 1971. 151-158 (Русский перевод: Кук С.А. Сложность процедур вывода теорем. Кибернетический сборник: Новая серия. 1975. Вып. 12. 5-15).
- Davis M., Longemann G., Loveland D. A machine program for theorem proving // Communications of the ACM. 1962. 5. 394-397.
- Devis M., Putnam H. A computing procedure for quantification theory // J. of ACM. 1960. 7. 201-215.
- Marqeus-Silva J.P., Sakallah K.A. GRASP: a search algorithm for propositional satisfiability // IEEE Trans. on Computers. 1999. 48, N 5. 506-521.
- Zchaff (http://www.princeton.edu/ chaff/zchaff.html).
- Berkmin (http://eigold.tripod.com/BerkMin.html).
- MiniSat (http://minisat.se/MiniSat.html).
- Robinson J.A. A machine-oriented logic based on the resolution principle // J. ACM. 1965. 12, N 1. 23-41.
- Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
- Buchberger B. Groebner bases: an algorithmic method in polynomial ideal theory // Recent Trends in Multidimensional System Theory. Dordrecht: Reidel Publishing Company, 1985. 184-232.
- Кокс Д., Литтл Дж., О’Ши Д. Идеалы, многообразия и алгоритмы. М.: Мир, 2000.
- Агибалов Г.П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского гос. ун-та. Приложение. 2003. № 6. 31-41.
- Заикин О.С., Семенов А.А. Технология крупноблочного параллелизма в SAT-задачах // Проблемы управления. 2008. № 1. 43-50.
- Заикин О.С., Семенов А.А., Сидоров И.А., Феоктистов А.Г. Параллельная технология решения SAT-задач с применением пакета прикладных программ D-SAT // Вестник Томского гос. ун-та. Приложение. 2007. № 23. 83-95.
- Заикин О.С., Сидоров И.А. Технология крупноблочного распараллеливания в криптоанализе некоторых генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ’07. Челябинск, ЮУрГУ, 2007. 1. 158-169.
- Cеменов А.А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ’07. Челябинск, ЮУрГУ, 2007. 1. 170-180.
- Bruer J.O. On pseudo random sequences as crypto generators // Proc. Int. Zurich Seminar on Digital Communication. Zurich (Switzerland), 1984. 157-161.
- Menezes A., Van Oorschot P., Vanstone S. Handbook of Applied Cryptography. Boca Raton: CRC Press, 1997.
- Суперкомпьютерный центр ИДСТУ СО РАН (http://www.mvs.icc.ru).
