Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Материал конференции: "Научный сервис в сети Интернет: труды XXI Всероссийской научной конференции (23-28 сентября 2019 г., г. Новороссийск)"
Авторы: Адамович А.И., Климов А.В.
О детерминированной параллельной реализации метода ветвей и границ на монотонных объектах
Аннотация:
Статья продолжает работу авторов по разработке двухуровневой системы детерминированного параллельного программирования и создания библиотек так называемых монотонных классов, реализуемых на универсальном объектно-ориентированном языке, составляющем нижний уровень системы. Входной язык подсистемы верхнего уровня похож на функциональные языки с дополнительной возможностью создания и использования неизменяемых и монотонных объектов. Библиотеки монотонных классов гарантируют, что все программы на подъязыке верхнего уровня, использующие только монотонные классы, являются детерминированными и идемпотентными при их распараллеливании классическим способом — асинхронным вызовом всех функций. Существенная часть разработки такой системы — создание библиотек монотонных классов для различных предметно-ориентированных областей и образов решения прикладных задач с их помощью. Данная статья посвящена конкретной задаче реализации поиска минимального веса пути на графе с дугами с неотрицательными весами методом ветвей и границ. Приводится решение, названное условно монотонным, где монотонность выполняется для неотрицательных весов дуг. Ставится задача точной реализации метода ветвей и границ на монотонных объектах.
Ключевые слова:
модели параллельных вычислений, детерминированные программы, метод ветвей и границ
Язык публикации: русский,  страниц: 16 (с. 3-18)
Полный текст на русском языке: Сведения об авторах:
  • Адамович Алексей Игоревич,  orcid.org/0000-0003-1392-8871,  Институт программных систем им. А.К. Айламазяна РАН
  • Климов Андрей Валентинович,  orcid.org/0000-0003-0418-7311,  ИПМ им. М.В. Келдыша РАН