Menu
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief
Nikiforov
Vladimir O.
D.Sc., Prof.
Partners
doi: 10.17586/2226-1494-2023-23-5-1001-1008
Job scheduling in a distributed computing system on a chip with power consumption minimization
Read the full article
';
Article in Russian
For citation:
Abstract
For citation:
Kolesov N.V., Litunenko E.G., Skorodumov Iu.M., Tolmacheva M.V. Job scheduling in a distributed computing system on a chip with power consumption minimization. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 5, pp. 1001–1008 (in Russian). doi: 10.17586/2226-1494-2023-23-5-1001-1008
Abstract
Scheduling of computing operations takes an important place in the process of distributed information processing and control systems design, especially in conditions of limited energy resources of the system. This becomes especially important for computers located on autonomous carriers, such as unmanned aerial vehicles, autonomous underwater vehicles, etc. The energy resources in such systems are limited that leads to high requirements for the energy efficiency of the carrier systems including computing ones. The paper presents the job scheduling method for a distributed computing system on a chip which allows reducing the power consumed by the system. The proposed task scheduling method includes two stages. At the first stage, jobs are assigned with the determination of an energy-efficient architecture of the system characterized by the minimum power consumption. At the second stage, jobs are scheduled taking into account the criterion that minimalizes the average job implementation time. A feature of the problem being solved in this case is the necessity of job scheduling in the system with more than one information output which does not allow applying any of the known scheduling methods to the system. The first stage of the proposed method is implemented by implementation additional processors with a simultaneous decrease in the clock frequency and supply voltage. For the second stage of the method, the job scheduling algorithm is proposed which involves the preliminary construction of a private schedule for each output of the system with further integration of these schedules into the general schedule using a heuristic procedure. The scheduling algorithm functioning is illustrated by an example of a solution for a simple system. The advantage of the proposed heuristic method is the possibility of scheduling calculations, taking into account criteria of the minimum power consumption and the minimum average residence time of a task in the system simultaniously. This makes it possible to increase the energy efficiency of solving problems in distributed computing systems on a chip, which contributes to increasing the autonomy of systems in which they are used in. The proposed algorithm has polynomial complexity, therefore, due to the relative simplicity of the algorithm, it can be used for scheduling and rescheduling jobs in real time for complex systems.
Keywords: computing scheduling, real-time distributed computing system, power consumption reduction, flow shop scheduling, energy-efficient computing
Acknowledgements. This work was supported by the project no. 22-29-00339 of the Russian Science Foundation, Russian Federation.
References
Acknowledgements. This work was supported by the project no. 22-29-00339 of the Russian Science Foundation, Russian Federation.
References
- 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, no. 11, no. 1, pp. 91–95. https://doi.org/10.1016/0305-0483(83)90088-9
- Lazarev A.A., Gafarov E.R. Scheduling Theory. Problems and Algorithms. Moscow, MSU, 2011, 222 p. (in Russian)
- Malashenko Yu.E., Nazarova I.A. Controlling computationally intensive heterogeneous computational tasks with directive deadlines. Journal of Computer and Systems Sciences International, 2012, vol. 51, no. 5, pp. 628–635. https://doi.org/10.1134/s1064230712050024
- Liu J.W.S. Real-Time Systems. Englewood Cliffs, NJ, Prentice Hall, 2000, 600 p.
- Cottet F., Delacroix J., Kaiser J., Mammeri Z. Scheduling in Real-Time Systems. John Wiley & Sons, 2002, 282 p.
- Kolesov N.V., Tolmacheva M.V., Yukhta P.V. Real Time Systems. Planning, Analysis, Diagnosis. St. Petersburg, Concern CSRI Elektropribor, 2014, 185 p. (in Russian)
- 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, vol. 88, no. 5-8,pp. 1535–1546. https://doi.org/10.1007/s00170-016-8828-5
- Gruzlikov A.M., Kolesov N.V., Skorodumov Y.M., Tolmacheva M.V. Task scheduling in distributed real-time systems. Journal of Computer and Systems Sciences International, 2017, vol. 56, no. 2, pp. 236–244. https://doi.org/10.1134/s1064230717020101
- Panda P.R., Silpa B.V.N., Shrivastava A., Gummidipudi K. Power-efficient System Design. Springer, New York, 2010, 260 p. https://doi.org/10.1007/978-1-4419-6388-8
- 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, pp. 25–38. https://doi.org/10.1109/rtss.2007.49
- Sun H., He Y., Hsu W.-J., Fan R. Energy-efficient multiprocessor scheduling for flow time and makespan. Theoretical Computer Science, 2014, vol. 550, pp. 1–20. https://doi.org/10.1016/j.tcs.2014.07.007
- Gruzlikov A.M., Kolesov N.V., Kostygov D.V., Oshuev V.V. Energy-efficient scheduling in distributed real-time computing systems. Journal of Computer and Systems Sciences International, 2019, vol. 58, no. 3, pp. 393–403. https://doi.org/10.1134/s1064230719030092
- Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Skorodumov Yu.M. Routing in networks of autonomous underwater vehicles. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2021, vol. 21, no. 6, pp. 984–990. (in Russian). https://doi.org/10.17586/2226-1494-2021-21-6-984-990
- Kolesov N.V., Gruzlikov A.M., Skorodumov Yu.M., Tolmacheva M.V. Mixed job scheduling in distributed real time systems. Vestnik Komp'iuternykh i Informatsionnykh Tekhnologi, 2016, no. 5, pp. 34–40. (in Russian). https://doi.org/10.14489/vkit.2016.05.pp.034-040
- Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Skorodumov Yu.M. Optimization of information exchange in a network of autonomous participants. Journal of Computer and Systems Sciences International, 2022, vol. 61, no. 6, pp. 935–943. https://doi.org/10.1134/S1064230722060107
