Статичні алгоритми управління паралельними асинхронними обчислювальними процесами
DOI:
https://doi.org/10.20535/1560-8956.44.2024.302427Ключові слова:
паралельні асинхронні обчислювальні процеси, комбінаторна оптимізація, статичне управління, ПДС-алгоритми, регресійні моделі, прийняття рішень, дискретні виробничі системиАнотація
Розглядається проблема управління паралельними асинхронними обчислювальними процесами. Приведено критичний порівняльний аналіз статичних та динамічних методів управління паралельними асинхронними обчислювальними процесами. Розглядаються дві постановки задачі управління паралельними асинхронних
обчислювальних процесів як одноетапних задач теорії розкладів. Пропонується для її розв’язання використовувати алгоритми, зокрема, ПДС-алгоритми, розроблені проф. Павловим О.А. та його учнями, що зазвичай використовуються для реалізації календарного та оперативного планування дискретними виробничими системами. Пропонуються
модифікації ПДС-алгоритмів відповідно до сформульованих задач комбінаторної оптимізації. Наведено приклади конкретних наукових та практичних проблем, для яких ефективність програмного забезпечення їх розв’язання досягається за допомогою розглянутих статичних моделей управління паралельними асинхронними обчислювальними процесами та запропонованими методами їх розв’язання.
Бібл. 22
Посилання
Стеценко И.В. Формальное описание систем средствами Петри-объектных моделей. Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка. 2011. Вип. 53. С. 74–81. URL: https://ela.kpi.ua/handle/123456789/3813 (дата звернення: 20.01.2024).
Стеценко И.В. Теоретические основы Петри-объектного моделирования систем. Математичні машини і системи. 2011. Том 4. С. 136–148. URL: https://dspace.nbuv.gov.ua/handle/123456789/83636 (дата звернення: 20.01.2024).
Stetsenko I.V., Pavlov A.A., Dyfuchyna O. Parallel algorithm development and testing using Petri-object simulation. International Journal of Parallel, Emergent and Distributed Systems. 2021. Vol. 36. Iss. 6. P. 549-564. DOI: 10.1080/17445760.2021.1955113.
Дифучина О. Метод оптимізації параметрів паралельних обчислень. Технічні науки та технології. 2023. Том 3. № 33. С. 130–140. URL: http://tst.stu.cn.ua/article/view/291211 (дата звернення: 20.01.2024).
A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems / T.D. Braun et al. // Journal of Parallel and Distributed Computing. 2021. Vol. 61. Iss. 6. P. 810–837. DOI: 10.1006/jpdc.2000.1714.
El-Rewini H., Lewis T., Ali H. Task Scheduling in Parallel and Distributed Systems. 2010. Prentice Hall, 290 p.
Dynamic grid scheduling with job migration and rescheduling in the GridLab resource management system / K. Kurowski et al. // Scientific Programming. 2004. Vol. 12. Iss. 4. P. 263–273. DOI: 10.1155/2004/892169.
Liou J., Palis M.A. A comparison of general approaches to multiprocessor scheduling. Proceedings of the 11th International Parallel Processing Symposium (IPPS '97). IEEE Computer Society. 1997. P. 152–156. DOI: 10.1109/ipps.1997.580873.
Минайленко Р.М. Аналіз алгоритмів планування ресурсами в розподіленому середовищі. National Interagency Scientific and Technical Collection of Works. 2020. Col. 50. P. 229–235. DOI: 10.32515/2414-3820.2020.50.229-235.
Topics in Parallel and Distributed Computing: Enhancing the Undergraduate Curriculum: Performance, Concurrency, and Programming on Modern Platforms. S.K. Prasad et al. Springer International Publishing. 2018. 337 p. ISBN: 978-3-319-93108-1.
Radulescu A., Gemund A.J.C. On the complexity of list scheduling algorithms for distributed memory systems. Supercomputing (SC’99): Proceedings of 13th International Conference. IEEE Computer Society. 1999. P. 68–75. DOI: 10.1145/305138.305162.
Yang T., Gerasoulis A. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Transactions on Parallel and Distributed Systems. 1994. Vol. 5. Iss. 9. P. 951–967. DOI: 10.1109/71.308533.
ПДС-алгоритми для двоетапної задачі календарного планування в детермінованій постановці та в умовах невизначеності / О.А. Павлов та ін. // Адаптивні системи автоматичного управління. 2023. Том 1. № 42. С.184–196. DOI: 10.20535/1560-8956.42.2023.279170.
Highly efficient scheduling algorithms for identical parallel machines with sufficient conditions for optimality of the solutions obtained / S.F. Telenyk et al. // Bulletin of the Polish Academy of Sciences: Technical Sciences. 2024. Vol. 72. Iss. 1. P. e148939. DOI:10.24425/bpasts.2024.148939.
Згуровский М.З., Павлов А.А. Труднорешаемые задачи комбинаторной оптимизации в планировании и принятии решений. Наукова думка, Київ. 2016. 716 с. ISBN:978-966-00-1543-2
Павлов О.А., Жданова О.Г., Сперкач М.О. Задача составления допустимого расписания с максимально поздним моментом запуска выполнения идентичными параллельными приборами работ с общим директивным сроком. Вісник НТУУ "КПІ". Серія "Інформатика, управління та обчислювальна техніка". 2014. Вип. 61. C. 93–102. URL: https://ela.kpi.ua/handle/123456789/16721 (дата звернення: 20.01.2024).
Zgurovsky M.Z., Pavlov A.A. Optimal scheduling for vector or scalar criterion on parallel machines with arbitrary due dates of tasks. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. 1st ed. Studies in Systems, Decision and Control. 2019. Vol. 173. P. 39–105. Springer, Cham. DOI:10.1007/978-3-319-98977-8_3.
Pavlov A.A., Holovchenko M.N. Modified method of constructing a multivariate linear regression given by a redundant description. Bulletin of National Technical University “KhPI”. Series: System analysis, control and information technologies. 2022. Vol. 2. Iss. 8. P. 3–8. DOI:10.20998/2079-0023.2022.02.01.
Дослідження ефективності методу побудови багатовимірної лінійної регресії, заданої надлишковим описом / О.А. Павлов та ін. // Матеріали тез доповідей конференції “Інженерія програмного забезпечення і передові інформаційні технології”
(SoftTech-2022 Осінь). 2023. С. 10–13. URL:https://drive.google.com/file/d/1CP9EaBTT_rJAXsINbanSVGnP2jkg9FJ0/view (дата звернення: 29.01.2024).
Zgurovsky M.Z., Pavlov A.A. The four-level model of planning and decision making. In: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. 1st ed. Studies in Systems, Decision and Control. Vol. 173. P. 265–290. –Springer, Cham, 2019. DOI:10.1007/978-3-319-98977-8_8.
Павлов О.А., Халус О.А., Медведєв М.Є. Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі. Фізико-математичне моделювання та інформаційні технології. 2023. Вип. 37. С. 57–61. DOI:10.15407/fmmit2023.37.057.
Згуровский М.З., Павлов А.А., Халус Е.А. Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением. Системні дослідження та інформаційні технології. 2015. № 2. С. 7–15. URL: http://journal.iasa.kpi.ua/article/view/51990 (дата звернення: 26.01.2024).
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у нашому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована нашим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у нашому журналі.
3. Політика журналу дозволяє і заохочує розміщення рукопису роботи авторами в мережі Інтернет (наприклад, на arXiv.org або на особистих веб-сайтах). Причому рукописи статей можуть бути розміщенні у відкритих архівах як до подання рукопису до редакції, так і під час його редакційного опрацювання. Це сприяє виникненню продуктивної наукової дискусії, позитивно позначається на оперативності ознайомлення наукової спільноти з результатами Ваших досліджень і як наслідок на динаміці цитування вже опублікованої у журналі роботи. Детальніше про це: The Effect of Open Access.
