Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Богданова В.Г. 1 Горский С.А. 1 Пашинин А.А. 1

---

1 Институт динамики систем и теории управления имени В.М. Матросова СО РАН

В статье рассматривается мультиагентный подход к параллельному решению булевых уравнений в распределенной гетерогенной вычислительной среде. Описывается мультиагентная система, управляющая этим процессом, особенностью которой является реализация агентов в виде сервисов. Мультиагентная система декомпозирует исходную задачу на подзадачи, формирует очередь заданий для подзадач, осуществляет подбор подходящего кластера, постановку в очередь заданий, запуск решателя булевых уравнений, контроль выполнения заданий, объединение полученных результатов, информирование пользователя о ходе решения. Приводится гибридный алгоритм решения булевых уравнений, использующий параллельные технологии обмена сообщениями и работы с общей памятью. Рассматриваются примеры использования мультиагентной системы для решения ряда задач булевой выполнимости, являющейся фундаментальной в математической логике и теории вычислений. Решение этих задач осуществляется путем проведения многовариантных распределенных вычислений, что позволяет существенно сократить время их решения. В качестве распределенной вычислительной среды используются вычислительные кластеры суперкомпьютерного центра коллективного пользования при ИДСТУ СО РАН. Принципы работы рассмотренного инструментария обеспечивают широкий спектр использования его функциональных возможностей для управления параллельным выполнением приложения пользователя в распределенной вычислительной среде при проведении вычислительных экспериментов в разнообразных предметных областях, где естественным образом возникают дискретные модели в виде систем булевых уравнений.

Статья в формате PDF

430 KB

мультиагентная система

сервисы

инструментальные средства

булевы уравнения

1. Богданова В.Г., Горский С.А. Технология параллельного решения систем булевых уравнений на вычислительном кластере // Современные технологии. Системный анализ. Моделирование. – 2013. – № 1 (37). – С. 54–60.

2. Бычков И.В., Опарин Г.А., Феоктистов А.Г., Богданова В.Г., Пашинин А.А. Мультиагентные методы и инструментальные средства управления в сервис-ориентированной распределенной вычислительной среде // Труды ИСП РАН. – 2014. – т. 26. – Вып. 5. – С. 65–82.

3. Бычков И.В., Опарин Г.А., Феоктистов А.Г., Корсуков А.С. Децентрализованное управление потоками заданий в интегрированной кластерной системе // Вестник НГУ. Серия: Информационные технологии. – 2011. – Т. 9. – Вып. 2. – С. 42–54.

4. Бычков И.В., Опарин Г.А., Феоктистов А.Г., Богданова В.Г., Пашинин А.А. Сервис-ориентированный подход к мультиагентному управлению распределенными вычислениями // Труды XII Всероссийского совещания по проблемам управления «ВСПУ-2014» (Москва, 16–19 июня 2014 г.). – М.: ИПУ РАН, 2014. ISBN 978-5-91450-151-5. С. 8942–8953.

5. Бычков И.В., Опарин Г.А., Феоктистов А.Г., Богданова В.Г., Корсуков А.С. Сервис-ориентированный подход к организации распределенных вычислений с помощью инструментального комплекса DISCENT // Информационные технологии и вычислительные системы. – 2014. – № 2. – С. 7–15.

6. Валуев И.А., Морозов И.В. Библиотека для управления заданиями на удаленных вычислительных ресурсах и распределенных системах // Научный сервис в сети Интернет: все грани параллелизма: Тр. XV Междунар. суперкомпьютерной конф. (Новороссийск, 22–27 сентября 2013 г.). – М.: Изд-во МГУ, 2013. – С. 57–64.

7. Гергель В.П., Сенин А.В. Разработка системы управления интегрированной средой высокопроизводительных вычислений «метакластер» // Вестник НГУ. – 2010. – № 6. – С. 186–194.

8. Жуматий С.А., Соболев С.И., Стефанов К.С. Решение оптимизационных гидродинамических задач в распределенной среде на основе вычислительных ресурсов МГУ // Вычислительные методы и программирование: новые вычислительные технологии. – 2010. – Т. 11, № 2. – С. 66–68.

9. Иркутский суперкомпьютерный центр Сибирского отделения РАН // URL: http://hpc.icc.ru (дата обращения 12.12.2014).

10. Опарин Г.А., Феоктистов А.Г. Инструментальная распределенная вычислительная САТУРН-среда // Программные продукты и системы. – 2002. – № 2. – С. 27–30.

11. Bogdanova V.G., Bychkov I.V., Korsukov A.S., Oparin G.A., and Feoktistov A.G. Multiagent Approach to Controlling Distributed Computing in a Cluster Grid System //Journal of Computer and Systems Sciences International, 2014. – Vol. 53. – № 5. – Р. 713–722. DOI: 10.1134/S1064230714040030.

12. Experiences Running a Parallel Answer Set Solver on Blue Gene / L. Schneidenbach and al. // URL: http://www.cs.uni-potsdam.de/wv/pdfformat/scscgekakasc09a.pdf (дата обращения: 12.12.2014).

13. Hamadi Y., Wintersteiger C. Seven Challenges in Parallel SAT Solving // AI Magazine: AAAI. – 2013. – Vol. 34. – № 2. – Р. 99–106.

14. Martins R., Manquinho V., Lynce I. An Overview of Parallel SAT Solving // Constraints. – 2012. – Vol. 17. – № 3. – Р. 304–347.

15. The international SAT Competitions web page // URL: http://www.satcompetition.org (дата обращения: 12.12.2014).

В настоящее время представляется актуальным создание инструментальных средств, обеспечивающих разработку программных сред для доступа предметных специалистов к высокопроизводительным вычислительным ресурсам и использования этих ресурсов без необходимости углубленного знания вычислительных архитектур и низкоуровневых средств разработки приложений [6, 7, 8, 10]. Одновременно прослеживаются тенденции, с одной стороны, использования сервис-ориентированного подхода, подразумевающего организацию сервисов доступа к вычислительным ресурсам посредством сети интернет, с другой стороны, применения мультиагентных технологий для управления вычислениями [3, 5, 11]. Также в последние годы активно ведутся исследования, связанные с привлечением высокопроизводительных вычислений для решения задачи выполнимости булевых ограничений (SAT) – одной из фундаментальных проблем математической логики и теории вычислений. Эта задача состоит в том, чтобы определить, выполнима ли данная булева формула, представленная в конъюнктивной нормальной форме (КНФ), то есть существует ли набор булевых значений переменных формулы, при котором ее значение становится истинным. Известно, что многие практически важные задачи могут быть сформулированы как задачи булевой выполнимости (решения системы булевых уравнений). Высокая вычислительная сложность SAT-задач актуализирует разработку новых эффективных методов и параллельных программных средств их решения, в частности SAT-решателей. В зависимости от реализуемого подхода современные параллельные SAT-решатели делятся на два семейства – решатели, использующие кооперацию и конкуренцию. При первом подходе поисковое пространство делится на части, затем организуется поиск параллельно в каждой части пространства отдельным решателем. При втором подходе каждый решатель работает с одной и той же формулой, но использует альтернативные пути поиска.

Целью данного исследования является разработка алгоритма параллельного решения SAT-задач специального вида в гетерогенной распределенной вычислительной системе (РВС), позволяющего, в отличие от известных (см., например, [13, 14]), учитывать вычислительные характеристики узлов этой системы при динамическом распределении подзадач, полученных в результате расщепления исходной задачи. Новизной предложенного подхода является использование мультиагентных технологий для организации трехуровневого параллелизма процесса решения задачи на основе гибридного подхода с применением MPI и OpenMP. В статье рассматривается мультиагентная система (МАС) HpcSoMas [2, 4], управляющая распределенным решением SAT-задачи на уровне РВС, и гибридный решатель hpcsat [1], предназначенный для решения SAT-задач на вычислительных кластерах с SMP-узлами и использующий на уровне кластера первый подход, с возможностью применения второго подхода на нижнем уровне, в узле кластера.

Мультиагентная система. МАС HpcSoMas предназначена для организации вычислительных экспериментов в предметных областях, где используются дискретные модели в виде систем булевых уравнений. HpcSoMas была разработана на основе сервис-ориентированной технологии, использование которой позволяет реализовать агентов в виде web-сервисов. При дальнейшем изложении материала будем называть сервисы, реализованные на основе архитектурного стиля REST, rest-сервисами, на основе стандарта SOAP – soap-сервисами. В МАС можно выделить три уровня иерархии агентов: уровень пользовательских агентов, представленный клиентами в браузере; уровень агентов-менеджеров (rest-сервисов); уровень реактивных агентов выполнения заданий (soap-сервисов). Многоуровневая архитектура позволяет реализовывать функциональные части МАС по отдельности и при необходимости повторно использовать эти части в других приложениях.

Пользователь может подключаться к агенту-менеджеру через web-интерфейс пользовательского агента, доступный для компьютеров и мобильных устройств, подключенных к сети Интернет, при наличии соответствующей учетной записи пользователя на вычислительном кластере. Все основные функции агента-менеджера вынесены в отдельные soap-сервисы, что позволяет производить замену отдельных компонентов системы либо подключение новых без ее полного обновления. Soap-сервисы могут выполнять следующие функции: расчета ставок на выполнение задания, уведомления пользователей, постановки задания в очередь системы управления заданиями (СУПЗ) вычислительного кластера (ВК), получения информации о состоянии ВК, декомпозиции заданий, расчета оценки состояния ВК, аутентификации пользователей и др. Sat-решатель так же представлен, как soap-сервис, с помощью разработанных авторами средств оформления приложения пользователя в виде сервиса [2].

С помощью web-интерфейса пользователь формулирует постановку задачи (передает файл с исходной КНФ) и инициирует процесс решения задачи. На основе полученных исходных данных пользовательский агент генерирует множество подзадач и передает их агенту планирования вычислений, который, в свою очередь, формирует задание для каждой подзадачи. Сформированный пул заданий направляется агенту-менеджеру. Агент-менеджер, получив задание, при помощи сервисов мониторинга состояния системы, параметров, заданных пользователем, а также полученных из самого задания, оценивает дальнейшие возможности по его обработке, отправляя запросы другим агентам-менеджерам для проведения тендера. Агенты взаимодействуют на основе координированного сотрудничества, достигаемого в процессе торгов за выполнение задания, которое не смог самостоятельно выполнить получивший его агент. Агент, получивший задание, ставит его в очередь СУПЗ ВК. На этапе выполнения задания запускается решатель hpcsat. Агенты мониторинга отслеживают состояние каждого задания. В случае появления в РВС дополнительных свободных вычислительных ресурсов и пустого пула заданий у агента-менеджера процесс вычислений приостанавливается, одна из активных подзадач снимается с решения, для нее производится дальнейшая декомпозиция, после чего формируются дополнительные задания и процесс вычислений возобновляется. Если решение найдено, задания снимаются с решения или удаляются из очереди (в зависимости от текущего статуса). Если в результате выполнения всех заданий решение не найдено, пользователь получает уведомление о завершении процесса решения с ответом «UNSAT» (функция невыполнима).

Применение HpcSoMas совместно с решателем hpcsat позволяет организовать трехуровневый параллелизм: на уровне РВС (агент-менеджер МАС, rest-сервис), на уровне узла РВС (главный процесс hpcsat, технология MPI, soap-сервис) и на уровне узла кластера (дочерние процессы hpcsat, технология OpenMP). Реализация такого многоуровневого параллелизма показана на рис. 1.

Решатель hpscat. Решатель hpcsat [1, 4] представляет собой MPI-приложение на языке C++. Главный процесс приложения организует динамическую очередь подзадач, получаемых в результате декомпозиции исходной булевой модели. В дочернем процессе может выполняться как многопоточное, так и однопоточное приложение. В качестве такого приложения может использоваться программа, осуществляющая декомпозицию булевой модели методом расщепления либо SAT-решатель (собственный или сторонней разработки). При использовании последовательного решателя в hpcsat реализуется одноуровневый параллелизм по данным, при использовании многопоточного – двухуровневый параллелизм на основе гибридного подхода. Для распараллеливания на уровне узла кластера применяется технология работы с общей памятью.

Рис. 1. Схема организации работы МАС HpcSoMas и hpcsat

Для представления узла дерева разработан ряд методов, в том числе рекурсивных, для работы с деревом. Управление состоянием дерева диспетчером подзадач осуществляется с помощью этих методов. Следует отметить, что ветви дерева, для которых в процессе расщепления на этапе упрощения остаточной функции получено значение «UNSAT», отсекаются. Узел дерева становится готовым для формирования подзадачи базовому решателю, когда количество переменных остаточной функции принимает граничные значения, заданные в начале работы hpcsat. Однако в процессе работы может возникнуть ситуация, когда из очереди первыми попадают на выполнение подзадачи, не имеющие решения. Поэтому в разработанном решателе применены механизмы квантования времени и отложенных подзадач. Под квантованием времени понимается прерывание процесса выполнения базового решателя при достижении определенного лимита по времени.

Вычислительные эксперименты. Для проверки работоспособности и эффективности разработанных средств были проведены вычислительные эксперименты [4]. В качестве РВС использована интегрированная кластерная среда, объединяющая вычислительные кластеры суперкомпьютерного центра ИДСТУ СО РАН [9].

Эксперименты проводились на ряде булевых моделей: для классической тестовой задачи о голубях и клетках (оценивались ускорение и эффективность), для четырех задач с соревнований SAT Competition13 [15] (эти задачи не были решены ни одним из участвовавших SAT-решателей за 5000 секунд), для задачи Эйлера о ходе шахматного коня (сформулированной как задача булевой выполнимости).

Результаты тестирования решателя hpcsat при решении задачи о голубях и клетках на вычислительном кластере «Академик В.М. Матросов» [9] (рис. 2, 3) не уступают по эффективности результатам, полученным с помощью ASP-солвера claspar на IBM Blue Gene/P (см. [12], рис. 1). При этом решатель hpcsat достигает более высокой размерности, имея относительное преимущество над claspar по времени решения (табл. 1).

Рис. 2. Ускорение решателя hpcsat на задаче о голубях и клетках

Рис. 3. Эффективность решателя hpcsat на задаче о голубях и клетках

Таблица 1

Время решения (в секундах) задачи о голубях и клетках для размерности 12 и 13

Таблица 2

Время решения (в секундах) задач с соревнованиий SAT Competition13

Таблица 3

Время решения задачи о ходе шахматного коня различными решателями

Результаты, приведенные на рис. 2 и 3, показывают, что с увеличением размерности ускорение приближается к линейному и эффективность становится стабильно высокой.

Для тестирования задач, не решенных в рамках соревнований SAT Competition13, решатель hpcsat успешно получил решение, приведены результаты для 256 и 1024 ядер (табл. 2).

Задача Эйлера о ходе шахматного коня является частным случаем задачи о нахождении гамильтонова пути в графе. Данная задача имеет много решений, но при этом тяжела для SAT-решателей в силу высокой размерности. В табл. 3 приведены результаты решения задачи о ходе шахматного коня, полученные с помощью решателя hpcsat в автономном режиме и в режиме интеграции с МАС HpcSoMas. В табл. 3 для сравнения сведены результаты работы сторонних SAT-решателей (minisat, manysat, penelope) и разработанного решателя hpcsat. Прочерк в графе таблицы присутствует, если решение задачи не было получено (задача заканчивалась аварийно или время ожидания завершения превышало 5 часов).

Приведенные эксперименты позволяют сделать вывод о работоспособности и эффективности разработанных методов и инструментальных средств.

Заключение

В статье рассмотрен сервис-ориентированный подход к организации проблемно-ориентированных распределенных вычислений в РВС. В рамках данного подхода выработана общая концепция реализации многоуровневого параллелизма в РВС, для решения булевых уравнений разработан sat-решатель на основе гибридного метода полного поиска с интеллектуальным возвратом, сочетающий технологии MPI и OpenMP, разработаны мультиагентные средства управления вычислениями, новые высокоуровневые инструментальные средства построения интерфейсов сервис-ориентированных приложений. Предложенный подход позволяет существенно сократить время решения задачи под управлением мультиагентной системы по сравнению со стандартизированными менеджерами ресурсов за счет средств динамической декомпозиции заданий и возможности миграции заданий по узлам вычислительной среды.

Ружников Г.М., д.т.н., старший научный сотрудник, зав. отделением информационных технологий и систем, Институт динамики систем и теории управления СО РАН имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск;

Данеев А.В., д.т.н., профессор кафедры информационных систем и защиты информации, Иркутский государственный университет путей сообщения, г. Иркутск.

Работа поступила в редакцию 06.03.2015.

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