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

Авторы

  • А.А. Семенов
  • О.С. Заикин

Ключевые слова:

база ограничений
неполнота
крупноблочный параллелизм
декомпозиция
программирование в ограничениях
параллельные программы
прогнозная функция

Аннотация

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


Загрузки

Опубликован

2008-04-07

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.А. Семенов

О.С. Заикин


Библиографические ссылки

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