Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки

16+

Название статьи

ОПЫТ ОРГАНИЗАЦИИ ДОБРОВОЛЬНЫХ ВЫЧИСЛЕНИЙ НА ПРИМЕРЕ ПРОЕКТОВ OPTIMA@HOME И SAT@HOME

Номер журнала	5
Дата выпуска	2012

Тип статьи	научная статья	Коды УДК	519.7
Страницы	340-347	Ключевые слова	добровольные распределенные вычисления, грид из персональных компьютеров, BOINC, задача о булевой выполнимости

Авторы

Заикин Олег СергеевичПосыпкин Михаил АнатольевичСемёнов Александр АнатольевичХрапов Николай Павлович

Место работы

Заикин Олег Сергеевич Институт динамики систем и теории управления СО РАН, Иркутск
Посыпкин Михаил Анатольевич Институт системного анализа РАН, Москва
Семёнов Александр Анатольевич Институт динамики систем и теории управления СО РАН, Иркутск
Храпов Николай Павлович Институт системного анализа РАН, Москва

Аннотация

Описывается процесс построения проектов добровольных вычислений, базирующихся на платформе BOINC и предназначенных для решения задач, предполагающих массовый крупноблочный параллелизм. Детали и особенности этого процесса иллюстрируются на примере реально функционирующих проектов добровольных вычислений OPTIMA@home и SAT@home. Первый проект предназначен для решения задач глобальной оптимизации, второй – для решения комбинаторных задач, сведенных к задачам о булевой выполнимости (SAT).

Загрузить статью

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

1 . Платформа BOINC для организации добровольных вычислений http://boinc.berkeley.edu/ (дата обращения: 14.02.2012).
2 . Рейтинг и описание 500 самых мощных общественно известных суперкомпьютеров. URL: http://www. top500.org/ (дата обращения: 14.02.2012).
3 . Formula BOINC – статистический сайт проектов добровольных вычислений. URL: http://formula-boinc. org/ (дата обращения: 14.02.2012).
4 . Проект добровольных вычислений OPTIMA @home. URL: http://boinc.isa.ru/dcsdg/ (дата обращения: 14.02.2012).
5 . Evtushenko Y., Posypkin M., Sigal I. A framework for parallel large-scale global optimization // Computer Science – Research and Development. 2009. V. 23. Issue 3-4. P. 211–215.
6 . Marosi A.C., Balaton Z., Kacsuk P. GenWrapper: A Generic Wrapper for Running Legacy Applications on Desktop Grids // IEEE International Symposium on Parallel&Distributed Processing. Rome, Italy, 2009. P. 1–6.
7 . GenWrapper – упаковщик для запуска приложений в гридах из персональных компьютеров. URL: http://genwrapper.sourceforge.net/ (дата обращения: 14.02.2012).
8 . Leary R.H. Global Optima of Lennard-Jones Clusters // Journal of Global Optimization. 1997. V. 11. Is. 1. P. 35–53.
9 . Longjiu Cheng, Jinlong Yang. Global Minimum Structures of Morse Clusters as a Function of the Range of the Potential: 81 ? N ? 160 // Journal of Physical Chemistry A. 2007. V. 111. P. 5287–5293.
10 . Посыпкин М.А. Методы и распределенная программная инфраструктура для численного решения задачи поиска молекулярных кластеров с минимальной энергией // Вестник ННГУ Н.И. Лобачевского. 2010. № 1. С. 210–219.
11 . Cook S.A. The complexity of theorem-proving procedures // Third Annual ACM Symposium on Theory of Computing. Ohio, USA, 1971. P. 151–159.
12 . Thomas D., Moorby P. The Verilog hardware description language. Springer, 2002. 381 p.
13 . Отпущенников И.В., Семeнов А.А. Технология трансляции комбинаторных проблем в булевы уравнения // Прикладная дискретная математика. 2011. № 1. С. 96–115.
14 . Davis M., Logemann G., Loveland D. A machine program for theorem proving // Communication of the ACM. 1962. V. 5. Is. 7. P. 394–397.
15 . Bohm M., Speckenmeyer E. A fast parallel SAT solver – ef?cient workload balancing // Annals of Mathematics and Arti?cial Intelligence. 1996. V. 17, №2. P. 381–400.
16 . SATLive! – современные ссылки по задаче SAT. URL: http://www.satlive.org/ (дата обращения: 14.02.2012).
17 . Schulz S., Blochinger W. Parallel SAT Solving on Peer-to-Peer Desktop Grids // Journal of Grid Computing. 2010. V. 8. №3. P. 443–471.
18 . Заикин О.С., Семёнов А.А. Технология крупноблочного параллелизма в SAT-задачах // Проблемы управления. 2008. № 1. С. 43–50.
19 . Semenov A., Zaikin O., Bespalov D., Posypkin M. Parallel algorithms for SAT in application to inversion problems of some discrete functions. arXiv:1102.3563v1 [cs.DC].
20 . Semenov A., Zaikin O., Bespalov D., Posypkin M. Parallel logical cryptanalysis of the generator A5/1 in BNB-Grid system // Lecture Notes in Computer Science. 2011. V. 6873. P. 473–483.
21 . Prestwich S. CNF encodings // In: Handbook of Satisfiability / Editors: A. Biere, M.Heule, H. van Maaren, T. Walsh. IOS Press, 2009. P. 75–97.
22 . Посыпкин М.А., Заикин О.С., Беспалов Д.В., Семёнов А.А. Решение задач криптоанализа поточных шифров в распределенных вычислительных средах // Труды ИСА РАН. 2009. Т. 46. С. 119–137.
23 . Biryukov A., Shamir A., Wagner D. Real Time Cryptanalysis of A5/1 on a PC // Seventh Fast Software Encryption Workshop, 2000, New York, USA. Springer-Verlag, 2000. P. 1–18.
24 . Проект добровольных вычислений SAT@ home. URL: http://sat.isa.ru/pdsat/ (дата обращения: 14.02.2012).
25 . Kacsuk P., Kovacs J., Farkas Z. et al. SZTAKI Desktop Grid (SZDG): A Flexible and Scalable Desktop Grid System // Journal of Grid Computing. 2009. V. 7, № 4. P. 439–461.
26 . Balaton Z., Gombas G., Kacsuk P. et al. SZTAKI desktop grid: a modular and scalable way of building large computing grids // 21th International Parallel and Distributed Processing Symposium. Long Beach, California, USA, 2007. P. 1–8.
27 . Заикин О.С. Реализация процедур прогно-зирования трудоемкости параллельного решения SAT-задач // Вестник УГАТУ. 2010. Т. 14, № 4. С. 210–220.
28 . Суперкомпьютерный центр ИДСТУ СО РАН. URL: http://www.mvs.icc.ru (дата обращения: 14.02.2012).
29 . SAT решатель MiniSat. URL: http://minisat.se/ MiniSat.html (дата обращения: 14.02.2012).
30 . Free-DC – cтатистический сайт проектов добровольных вычислений. URL: http://www.free-dc.org/ (дата обращения: 14.02.2012).
31 . Barkan E., Biham E., Keller N. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication // Proceedings in Crypto. 2003. P. 600–616.
32 . A5/1 Cracking project. URL: http://reflextor. com/trac/a51/wiki (дата обращения 14.02.2012).
33 . Статистика проектов на платформе BOINC. URL: http://ru.boincstats.com (дата обращения 14.02.2012).
34 . Список активных проектов добровольных вычислений на платформе BOINC. URL: http: // boinc. berkeley.edu /projects.php (дата обращения 14.02.2012).