Speaker
Darya Lemtyuzhnikova
(TNU)
Description
Предлагается параллельная версия локального элиминационного алгоритма (ЛЭА) для платформы распределённых вычислений BOINC. Рассматривается поэтапное решение разреженных задач дискретной оптимизации с помощью параллельного ЛЭА, а также выделение видов распараллеливания, свойственных ЛЭА. Выделяются процессы, необходимые для работы ЛЭА в контексте парадигмы Директор-Мастер-Рабочий.
Модели многих задач, возникающих на практике, можно представить в виде задач дискретной оптимизации (1): задачи теории расписаний, задачи маршрутизации, задачи оптимизации производства и многие другие. Сложность таких задач заключается в том, что они зависят от большого числа переменных, поэтому для их решения естественно использовать алгоритмы, которые не обладают экспоненциальной сложностью, но при этом дают точное решение. В этом смысле интересными являются локальные элиминационные алгоритмы (ЛЭА), которые разбивают большую задачу на подзадачи и элиминируют переменные, понижая тем самым величину перебора [1].
(1)
Для его работы кроме данных самой задачи – целевой функции, матрицы и вектора ограничений, необходим порядок элиминации, который указывает, каким образом будут исключаться переменные в задаче. Для этого нужно построить элиминационное дерево задачи (ЭД), которое строится из гиперграфа задачи при помощи некоторого критерия элиминации, связанного с характером задачи. Перспективным алгоритмом построения ЭД является древовидная декомпозиция [2].
Для разветвлённого ЭД имеет смысл применять технологию распараллеливания, так как подзадачи, находящиеся на одной высоте дерева, являются независимыми. Такой вид распараллеливания будем называть древовидным распараллеливанием.
Рассмотрим подзадачу, соответствующую вершине ЭД. Она имеет блочную структуру, так как первичная задача была разреженной. Блоки такой подзадачи слабо связные, поэтому имеет смысл разбивать такие блоки, перебирая переменные, которые являются сепараторами этих блоков. Такой вид распараллеливания будем называть блочным.
ЛЭА дважды проходит по ЭД. Прямой ход ЛЭА решает подзадачи и сохраняет промежуточные решения, а обратный ход ЛЭА анализирует и собирает решения подзадач. При параллельной трактовке ЛЭА необходимо, чтобы были следующие процессы:
1) процесс, который анализирует элиминационное дерево и выявляет подзадачи на данном уровне дерева;
2) процесс, который распределяет подзадачи;
3) процесс, который решает подзадачи;
4) процесс, который анализирует подзадачи, записывает результат и создаёт задачи следующего уровня на основе полученной информации;
5) процесс, который собирает информацию воедино;
6) процесс, который анализирует полученное решение.
Для реализации этих процессов возможно использование парадигмы Директор-Мастер-Рабочий. Директор анализирует ЭД, выделяет подзадачи на данном уровне и отправляет их мастеру. Мастер распределяет задачи среди рабочих, собирает полученные результаты и отправляет их обратно директору. Директор анализирует подзадачи, записывает результат в таблицу и, если корень ЭД не достигнут, создаёт задачи следующего уровня и отправляет Мастеру. Если же корень ЭД был достигнут, Директор просматривает таблицу промежуточных решений, выбирает оптимальное и проверяет целевую функцию. Если результат совпал, то задача выполнена.
Для реализации парадигмы Директор-Мастер-Рабочий хорошо подходит платформа распределённых вычислений BOINC (Berkeley Open Infrastructure for Network Computing)[5], где директором назначается компьютер, на котором непосредственно решается задача, Мастером назначается удалённый боинк-сервер, а рабочими процессами – удалённые компьютеры. Распределённые вычисления позволяют быстро решать объёмные задачи,
так как к процессу решения привлечено большое количество пользователей, а значит и удалённых компьютеров.
Список используемых источников:
1. Щербина O.A. Локальныe элиминационные алгоритмы решения разреженных дискретных задач // Журнал вычислительной математики и математической физики. - 2008. - T. 48, № 1. - C. 161-177.
2. Щербина О. А. Древовидная декомпозиция и задачи дискретной оптимизации (обзор) // Кибернетика и системный анализ. 2007. № 4. С. 102-118.
3. Российские распределенные вычисления на платформе BOINC [Электронный ресурс]. URL:http://www.boinc.ru/
Primary author
Darya Lemtyuzhnikova
(TNU)
