Algoritm imitatsii otzhiga dlya postroeniya spisochnykh raspisaniy s ogranicheniem na kolichestvo mezhprotsessornykh peredach dannykh

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

Предложен алгоритм имитации отжига для построения многопроцессорных списочных расписаний минимальной длительности с дополнительным ограничением на количество передач между процессорами. Данное ограничение характерно для вычислительных систем с жесткими ограничениями на ресурсы межпроцессорной сети передачи данных. В целом задача минимизации длительности расписания возникает при разработке систем обработки данных в реальном масштабе времени, таких как бортовые и телекоммуникационные системы. Также задача актуальна для периферийных вычислений (edge computing). Экспериментальное исследование свойств алгоритма показало его высокую точность, стабильность и масштабируемость.

作者简介

V. Balashov

Московский государственный университет им. М.В. Ломоносова

Email: hbd@cs.msu.ru
Москва

V. Kostenko

Московский государственный университет им. М.В. Ломоносова

Email: kostmsu@gmail.com
Москва

I. Fedorenko

Московский государственный университет им. М.В. Ломоносова

Email: iliasfedorenko@mail.ru
Москва

Ts. Gao

Московский исследовательский центр компании Хуавэй

Email: gaojiexing@huawei.com
Москва

Ch. Sun

Гонконгский исследовательский центр компании Хуавэй

Email: sunchumin@huawei.com
Гонконг

Ts. Sun

Гонконгский исследовательский центр компании Хуавэй

Email: j.sun@huawei.com
Гонконг

参考

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.
  2. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. М.: Наука, 1984.
  3. Костенко В.А. Алгоритмы комбинаторной оптимизации, сочетающие жадные стратегии и ограниченный перебор // Известия РАН. Теория и системы управления. 2017. № 2. C. 48-56.
  4. Lawler E.L., Wood D.E. Branch-and-Bound Methods: A Survey // Oper. Res. 1966. V. 14. No. 4. P. 699-719. https://doi.org/10.1287/opre.14.4.699
  5. Fujita S. A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques // IEEE Transact. Comput. 2011. https://doi.org/10.1016/j.procs.2016.07.216
  6. Калашников А.В., Костенко В.А. Параллельный алгоритм имитации отжига для построения многопроцессорных расписаний // Известия РАН. Теория и системы управления. 2008. № 3. С. 133-142.
  7. Зорин Д.А., Костенко В.А. Алгоритм имитации отжига для решения задач построения многопроцессорных расписаний // АиТ. 2014. № 10. С. 97-110.
  8. Holland J.N. Adaptation in Natural and Arti cial Systems / Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
  9. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008.
  10. Akbari M., Rashidi H. An E cient Algorithm for Compile-Time task scheduling problem on heterogeneous computing systems // Int. J. Academ. Res. 2015. V. 7. No. 1. P. 192-202. https://doi.org/10.7813/2075-4124.2015/7-1/A.45
  11. Rzadca K., Seredynski F. Heterogeneous Multiprocessor Scheduling with Di erential Evolution // IEEE Congress on Evolutionary Computation, 2005. V. 3. P. 2840-2847. https://doi.org/10.1109/CEC.2005.1555051
  12. Dorigo M. Optimization, Learning and Natural Algorithms // Ph.D. Thesis. Dipartimentodi Elettronica. Milano: Politechnico Di Milano, 1992.
  13. Штовба С.Д. Муравьиные алгоритмы: теория и применение // Программирование. 2005. № 4. С. 1-15.
  14. Myszkowski P.B., Skowronski M.E., Olech L.P. et al. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem // Soft Comput. 2015. V. 19. No. 12. P. 3599-3619. https://doi.org/10.1007/s00500-014-1455-x
  15. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968.
  16. Шахбазян К.В., Тушкина Т.А. Обзор методов составления расписаний для многопроцессорных систем // Зап. научн. сем. ЛОМИ. 1975. Т. 54. C. 229-258.
  17. Garey M.R., Johnson D.S.Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., 1979.
  18. Rahman M. Branch and Bound Algorithm for Multiprocessor Scheduling // M.S. Thesis, Dept.Comput. Eng., Dalarna Univ., Sweden, 2009.
  19. Venugopalan S., Sinnen O. Optimal Linear Programming Solutions for Multiprocessor Scheduling with Communication Delays // Proc. ICA3PP 2012: Algorithms and Architectures for Parallel Processing, 2012. P. 129-138. https://doi.org/10.1016/j.jpdc.2016.03.003
  20. Mallach S. Improved Mixed-Integer Programming Models for the Multiprocessor Scheduling Problem with Communication Delays // J. Combinat. Optim. 2018. V. 36. P. 871-895. https://doi.org/10.1007/s10878-017-0199-9
  21. Hwang R., Gen M., Katayama H. A Comparison of Multiprocessor Task Scheduling Algorithms with Communication Costs // Comput. Oper. Res. 2008. V. 35. P. 976-993. https://doi.org/10.1016/j.cor.2006.05.013
  22. Красовский Д.В. Алгоритмы решения задачи составления оптимального расписания без прерываний // Дисс.. канд. физ.-мат. наук, 05.13.18 Москва, 2007, 109 с.
  23. da Silva E.C., Gabriel P.H.R. Genetic Algorithms and Multiprocessor Task Scheduling: A Systematic Literature Review // Proc. ENIAC 2019. P. 250-261. https://doi.org/10.5753/eniac.2019.9288
  24. Sheikh H.F., Ahmad I., Fan D. An Evolutionary Technique for Performance-Energy-Temperature Optimized Scheduling of Parallel Tasks on Multi-Core Processors // IEEE Trans. Parallel Distributed Syst., 2016. V. 27. No. 3. P. 668-681. https://doi.org/10.1109/TPDS.2015.2421352
  25. Lo S.-T., Chen R.-M., Huang Y.-M., Wu C.-L. Multiprocessor System Scheduling with Precedence and Resource Constraints Using an Enhanced Ant Colony System // Expert Syst. Appl. 2008. V. 34. No. 3. P. 2071-2081. https://doi.org/10.1016/j.eswa.2007.02.022
  26. METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering: [Электронный ресурс]. URL: http://glaros.dtc.umn.edu/gkhome/metis/metis/overview (Дата обращения: 21.11.2022).
  27. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 5.1.0: [Электронный ресурс]. URL: http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/manual.pdf (Дата обращения: 21.11.2022).
  28. Wu M.-Y., Gajski D.D. Hypertool: A programming aid for message-passing systems // IEEE Trans. Parallel Distributed Syst. 1990. V. 1. P. 330-343. https://doi.org/10.1109/71.80160
  29. Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. 2002. № 3. С. 64-80.

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © The Russian Academy of Sciences, 2023

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».