О детерминированной параллельной реализации метода ветвей и границ на монотонных объектах
Аннотация:
Статья продолжает работу авторов по разработке двухуровневой системы детерминированного параллельного программирования и создания библиотек так называемых монотонных классов, реализуемых на универсальном объектно-ориентированном языке, составляющем нижний уровень системы. Входной язык подсистемы верхнего уровня похож на функциональные языки с дополнительной возможностью создания и использования неизменяемых и монотонных объектов. Библиотеки монотонных классов гарантируют, что все программы на подъязыке верхнего уровня, использующие только монотонные классы, являются детерминированными и идемпотентными при их распараллеливании классическим способом — асинхронным вызовом всех функций. Существенная часть разработки такой системы — создание библиотек монотонных классов для различных предметно-ориентированных областей и образов решения прикладных задач с их помощью. Данная статья посвящена конкретной задаче реализации поиска минимального веса пути на графе с дугами с неотрицательными весами методом ветвей и границ. Приводится решение, названное условно монотонным, где монотонность выполняется для неотрицательных весов дуг. Ставится задача точной реализации метода ветвей и границ на монотонных объектах.
Ключевые слова:
модели параллельных вычислений, детерминированные программы, метод ветвей и границ
