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

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

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

About the authors

V. V Balashov

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

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

V. A Kostenko

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

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

I. A Fedorenko

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

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

Ts. Gao

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

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

Ch. M Sun

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

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

Ts. Sun

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

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

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 The Russian Academy of Sciences