|
КОМПЬЮТЕРНЫЕ НАУКИ
Решение задачи об оптимальном распределении заданий методом динамического программирования с применением параллельных вычислений
А. М. Григорьев Институт математики и механики УрО РАН, 620219, Россия, г. Екатеринбург, ул. С. Ковалевской, 16
Аннотация:
Исследование посвящено построению параллельного алгоритма решения задачи «на узкие места», связанного с поиском разбиения конечного множества заданий на конечное число исполнителей (работников). Описывается алгоритм нахождения оптимального разбиения заданий с использованием метода динамического программирования с элементами параллельных вычислений при построении массива значений функции Беллмана. Выполнена оценка вычислительной сложности двух алгоритмов (с использованием и без использования параллельной структуры). Создана программа, с помощью которой проведен вычислительный эксперимент по решению поставленной задачи на суперкомпьютере «УРАН». Выполнен сравнительный анализ реализации алгоритмов как с использованием, так и без использования параллельной структуры. Представлена зависимость времени счета реализованной программы на суперкомпьютере от количества вычислительных ядер.
Ключевые слова:
динамическое программирование, разбиение, параллельный алгоритм.
Поступила в редакцию: 25.01.2017
Образец цитирования:
А. М. Григорьев, “Решение задачи об оптимальном распределении заданий методом динамического программирования с применением параллельных вычислений”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 27:1 (2017), 129–137
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vuu574 https://www.mathnet.ru/rus/vuu/v27/i1/p129
|
Статистика просмотров: |
Страница аннотации: | 421 | PDF полного текста: | 179 | Список литературы: | 44 |
|