Планирование заданий в распределенной вычислительной системе на кристалле с минимизацией потребляемой мощности

Введение. Планирование вычислений занимает важное место в процессе проектирования распределенных систем обработки информации и управления, особенно в условиях ограничения вычислительных и энергетических ресурсов системы. Эти ограничения особенно остро проявляются для вычислителей, размещенных на автономных носителях, таких как беспилотные летательные аппараты, необитаемые подводные и надводные аппараты. В данной работе представлен метод планирования заданий в распределенной вычислительной системе на кристалле, который позволяет сократить потребляемую системой мощность. Метод. Предложенный метод включает два этапа. На первом этапе осуществляется назначение заданий с определением энергоэффективной архитектуры системы, характеризующейся минимальной потребляемой мощностью. На втором этапе выполняется планирование заданий с учетом критерия, позволяющего минимизировать среднее время пребывания задания в системе. Особенностью решаемой задачи является появление в общем случае у разрабатываемой системы после первого этапа более одного информационного выхода, что не позволяет применять к системе ни один из известных методов планирования. Основные результаты. Первый этап метода реализован введением дополнительных процессоров с одновременным снижением тактовой частоты и напряжения питания. Для второго этапа предложен алгоритм планирования заданий, который выполняет предварительное построение для каждого выхода системы частного плана с дальнейшим их интегрированием в общий план путем применения эвристической процедуры. Приведен пример решения для пояснения работы алгоритма планирования. Обсуждение. Достоинством эвристического алгоритма является возможность планирования вычислений с учетом критериев минимумов потребляемой мощности и среднего времени пребывания задания в системе. Это позволяет повысить энергоэффективность решения задач в распределенных вычислительных системах на кристалле и автономность систем, в которых они применяются. Предложенный алгоритм обладает полиномиальной сложностью, поэтому благодаря относительной простоте алгоритма возможно его применение при планировании и перепланировании заданий в реальном времени в сложных системах.

1. Nawaz M., Enscore Jr. E.E., Ham I. A heuristic algorithm for the m-Machine, n-Job flow-shop sequencing problem // Omega – International Journal of Management Science. 1983. N 11. N 1. P. 91–95. https://doi.org/10.1016/0305-0483(83)90088-9

2. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. М.: МГУ, 2011. 222 с.

3. Малашенко Ю.Е., Назарова И.А. Управление ресурсоемкими разнородными вычислительными заданиями с директивными сроками окончания // Известия РАН. Теория и системы управления. 2012. № 5. С. 15–22.

4. Liu J.W.S. Real-Time Systems. Englewood Cliffs, NJ: Prentice Hall, 2000. 600 p.

5. Cottet F., Delacroix J., Kaiser J., Mammeri Z. Scheduling in Real- Time Systems. John Wiley & Sons, 2002. 282 p.

6. Колесов Н.В., Толмачева М.В., Юхта П.В. Системы реального времени. Планирование, анализ, диагностирование. СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2014. 185 с.

7. Gruzlikov A.M., Kolesov N.V., Skorodumov Iu.M., Tolmacheva M.V. Using solvable classes in flowshop scheduling // The International Journal of Advanced Manufacturing Technology. 2017. V. 88. N 5-8. P. 1535–1546. https://doi.org/10.1007/s00170-016-8828-5

8. Грузликов А.М., Колесов Н.В., Скородумов Ю.М., Толмачева М.В. Планирование заданий в распределенных системах реального времени // Известия РАН. Теория и системы управления. 2017. № 2. С. 67–76. https://doi.org/10.7868/S000233881702010X

9. Panda P.R., Silpa B.V.N., Shrivastava A., Gummidipudi K. Powerefficient System Design. Springer, New York, 2010. 260 p. https://doi.org/10.1007/978-1-4419-6388-8

10. Xu R., Melhem R., Moss D. Energy-aware scheduling for streaming applications on chip multiprocessors // Proc. of the 28th International Real-Time Systems Symposium (RTSS). 2007. P. 25–38. https://doi.org/10.1109/rtss.2007.49

11. Sun H., He Y., Hsu W.-J., Fan R. Energy-efficient multiprocessor scheduling for flow time and makespan // Theoretical Computer Science. 2014. V. 550. P. 1–20. https://doi.org/10.1016/j.tcs.2014.07.007

12. Грузликов А.М., Колесов Н.В., Костыгов Д.В., Ошуев В.В. Энергоэффективное планирование в распределенных вычислительных системах реального времени // Известия РАН. Теория и системы управления. 2019. № 3. С. 66–76. https://doi.org/10.1134/S0002338819030090

13. Грузликов А.М., Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М. Маршрутизация в сетях автономных необитаемых подводных аппаратов // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21. № 6. С. 984–990. https://doi.org/10.17586/2226-1494-2021-21-6-984-990

14. Колесов Н.В., Грузликов А.М., Скородумов Ю.М., Толмачева М.В. Смешанное планирование заданий в распределенных системах реального времени // Вестник компьютерных и информационных технологий. 2016. № 5. С. 34–40. https://doi.org/10.14489/vkit.2016.05.pp.034-040

15. Грузликов А.М., Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М. Оптимизация информационных обменов в сети автономных абонентов // Известия РАН. Теория и системы управления. 2022. № 6. С. 56–64. https://doi.org/10.31857/s0002338822060105