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

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Acesso é pago ou somente para assinantes

Resumo

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

Sobre autores

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
Гонконг

Bibliografia

  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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © The Russian Academy of Sciences, 2023