Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки

16+

Название статьи

ЭВРИСТИЧЕСКИЙ МЕТОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАСПАРАЛЛЕЛИВАНИЯ АЦИКЛИЧЕСКОГО АЛГОРИТМА НА МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

Номер журнала	4
Дата выпуска	2010

Тип статьи	научная статья	Коды УДК	519.874
Страницы	182-186	Ключевые слова	метод ветвей и границ, ациклический алгоритм, задача распараллеливания, каноническая совокупность взаимозависимых операций, многопроцессорная вычислительная система

Авторы

Слободской Виталий Витальевич

Место работы

Слободской Виталий Витальевич Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

Рассматривается задача распараллеливания алгоритма, реализуемого посредством канонической совокупности взаимозависимых операций, моделируемой ориентированным взвешенным ациклическим графом. Для решения задачи предлагается эвристический алгоритм, основанный на вычислительных процедурах метода ветвей и границ.

Загрузить статью

Библиографический список

1 . Слободской В.В. Задача распараллеливания ациклического алгоритма // Вестник ННГУ. 2008. №5. C. 113-119.
2 . Слободской В.В. Использование метода ветвей и границ для решения задачи распараллеливания ациклического алгоритма // Тезисы докладов конференции «Технологии Microsoft в теории и практике программирования». Н. Новгород: Издательство ННГУ, 2009.
3 . Прилуцкий М.Х., Слободской В.В. Распределение ресурсов в задачах балансирования с постоянными длительностями // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. 2006. Вып. 1.
4 . Jansen K., Porkolab L. Improved Approximation Schemes for Scheduling Unrelated Parallel Machines // Mathematics of Operations Research. 2001. V. 26. № 2. P. 324-338.
5 . Serna M., Xhafa F. Approximating Scheduling Unrelated Parallel Machines in Parallel // Computational Optimization and Applications. 2002. V. 21. P. 325-338.
6 . Lenstra J.K., Shmoys D.B., Tardos E. Approximation Algorithms for Scheduling Unrelated Parallel Machines // Mathematical Programming. 1990. V. 46. P. 259-271.
7 . Samadzadeh F.A., Hedrick G.E. Near-Optimal Multiprocessor Scheduling // Proceedings of the 1992 ACM Annual Conference on Communications. 1992. P. 477-484.
8 . Samadzadeh F.A., Hedrick G.E. A Heuristic Multiprocessor Scheduling Algorithm for Creating Near- Optimal Schedules Using Task System Graphs // Proceedings of the 1992 ACM/SIGAPP Symphosium on Applied Computing: Technological Challenges of the 1990`s. 1992. P. 711-718.
9 . Sinnen O., Kozlov A.V., Shahul A.Z.S. Optimal scheduling of task graphs on parallel systems // 25th LASTED International Multi-Conference Parallel and Distributed Computing and Networks. 2007.