Specificity of Task Scheduling Algorithms in Geographically Distributed Computer Systems
https://doi.org/10.34020/2073-6495-2021-3-019-030
Abstract
The work is devoted to the consideration of the main widespread algorithms for scheduling tasks in geographically distributed computing systems. The specific features of the algorithms are characterized and their comparative analysis is presented in accordance with the selected criteria. The main factors that should be taken into account when constructing job control algorithms in geographically distributed computing systems are determined.
About the Authors
E. V. Agapov
Novosibirsk State University of Economics and Management
Russian Federation
Russian Federation
Agapov Efim V., Postgraduate Student
Novosibirsk
L. K. Bobrov
Novosibirsk State University of Economics and Management
Russian Federation
Russian Federation
Bobrov Leonid K., Doctor of Technical Sciences, Professor of the Department of Applied Informatics
Novosibirsk
K. A. Zaykov
Novosibirsk State University of Economics and Management
Russian Federation
Russian Federation
Zaykov Kirill A., Candidate of Economic Sciences, Associate Professor, Department of Statistics
Novosibirsk
References
1. Mazalov V.V., Nikitina N.N. Ocenka harakteristik algoritma Backfill pri upravlenii potokami zadach na vychislitel’nom klastere // Vychislitel’nye tehnologii. 2012. T. 17. № 5. P. 71–79.
2. Mamojlenko S.N., Efimov A.V. Algoritmy planirovanija reshenija masshtabiruemyh zadach na raspredelennyh vychislitel’nyh sistemah // Vestnik GOU VPO «SibGUTI». 2010. № 2. P. 66–78.
3. Volovich K.I. Metody i algoritmy organizacii vychislitel’nogo processa v gibridnom vysokoproizvoditel’nom komplekse na osnove virtual’noj sredy ispolnenija: dis. … kand. tehn. nauk: 05.13.15. M., 2019. 114 p.
4. Tihomirov A.I. Metody i sredstva organizacii sistemy upravlenija vychislitel’nymi zadanijami v territorial’no raspredelennoj seti superkomp’juternyh centrov kollektivnogo pol’zovanija: dis. … kand. tehn. nauk: 05.13.11. M., 2019. 143 p.
5. Tjutljaeva E.O., Odincov I.O., Moskovskij A.A., Marmuzov G.V. Tendencii razvitija vychislitel’nyh uzlov sovremennyh superkomp’juterov // Vestnik JuUrGU. Serija «Vychislitel’naja matematika i informatika». 2019. P. 92–114.
6. Carrington L.A., Snavely A., Wolter N. Performance Prediction Framework for Scientific Applications // Future Generation Computer Systems. 2006.Vol. 22. P. 336–346.
7. Cirne W., Berman F.A Comprehensive Model of the Supercomputer Workload // Proc. IEEE Fourth Ann.Workshop Workloads Characterization. 2001. P. 140–148.
8. Chen C.L., Lee C.S., Hou E.S. Efficient scheduling algorithms for robot inverse dynamics computation on a multiprocessor system // IEEE Trans. System Man Cybernetics. 1988.Vol. 18. P. 729–743.
9. Clement M.J., Quinn M.J. Analytical Performance Prediction on Multicomputers // J. Supercomputing. 1993. P. 886–894.
10. Conway R.W., Maxwell W., Miller L. Theory of Scheduling // Massachusetts Addison Wesley Publications. 1967. P. 304.
11. Dinda P.A., O’Hallaron D.R. Host Load Prediction Using Linear Models // Cluster Computing. 2000.Vol. 3. P. 265–280.
12. Feitelson D., Rudolph L.H., Schwiegelshohn U., Wong P.Theory and Practice in Parallel Job Scheduling // Theoretical Computer Science. 2004. P. 17–47.
13. Gandhi T., Nitin, Alam T. Quantum Genetic Algorithm with Rotation Angle Refinement for Dependent Task Scheduling on Distributed Systems // Tenth International Conference on Contemporary Computing (IC3). 2017. P. 12–15.
14. Gonzalez M.J. Deterministic processor scheduling // Computing Surveys. 1977. Vol. 9. № 3. P. 173–204.
15. Hellstrom B., Kanal L. Asymmetric mean-field neural networks for multiprocessor scheduling // Neural Nerworks. 1992.Vol. 5. P. 671–686.
16. Hisao I., Murata T.A multi-objective genetic local search algorithm and its application to flowshop scheduling // IEEE Transactions on Systems, Man, and Cybernetics, Part C (Application and Reviews). 1998.Vol. 28. № 3. P. 392–403.
17. Jahanshah M., Meybodi M.R., Dehghan M. A New Approach for Task Scheduling in Distributed Systems Using Learning Automata // Proceedings of the IEEE International Conference on Automation and Logistics Shenyang. 2009. P. 62–67.
18. Kasahara H., Narita S. Practical multiprocessing scheduling algorithms for efficient parallel processing // IEEE Trans. Computer. 1984.Vol. C-33. № 11. P. 1023–1029.
19. Kasahara H., Narita S. Parallel processing of robot-arm control computation on a multimicroprocessor system // IEEE J. Roboric J Automarion. 1985. Vol. RA-1. № 2. P. 104–113.
20. Kettimuthu R., Subrasani V., Srinivasan S., Gopalasamy T. Selective Preemption Strategies for Parallel Job Scheduling // Proc. Int. Conf. on Par. Proc. (ICPP). 2002. P. 12–23.
21. Laarhoven V., Peter J., Emile A., Lenstra J. Job shop scheduling by simulated annealing // Operations Research. 1992.Vol. 40. № 1. P. 113–125.
22. Merkle D., Middendorf M., Schmeck H. Ant colony optimization for resource-constrained project scheduling // IEEE transactions on evolutionary computation. 2002. Vol. 6. № 4. P. 333–346.
23. Narendra K.S., Thathachar M.L. Learning automata: an introduction // Englewood Cliffs, NJ: Prentice Hall, 1989.
24. O’Sullivan D., Unwin J. Geographic Information Analysis, Second Edition. 2010. P. 432.
25. Ramamoorthy C.V. Optimal scheduling strategies in a multiprocessor system // IEEE Trans. Computers. 1972. P. 137–146.
26. Shmueli E., Feitelson D. Backfilling with Lookahead to Optimize the Packing of Parallel Jobs // J. of Parallel and Distributed Computing. 2005.Vol. 65. P. 1090–1107.
27. Topcuoglu H., Hariri S., Wu M. Performanceeffective and low-complexity task scheduling for heterogeneous computing // IEEE transactions on parallel and distributed systems. 2002.Vol. 13. № 3. P. 260–274.
28. Thathachar M. Stochastic automata and learning systems // Department of Electrical Engineering, Indian Institute of Science. 1990. P. 263–283.
29. Tsafrir D., Etsion Y., Feitelson D. Backfilling using system-generated predictions rather than user runtime estimates // IEEE Trans. Parallel and Distributed Systems. 2007. Vol. 18. № 6. P. 789–803.
30. Venter G., Sobieszczanski-Sobieski J. Particle swarm optimization // AIAA Journal. 2003.Vol. 41. № 8. P. 1583–1589.
31. Zasedanie prezidiuma Soveta pri Prezidente Rossijskoj Federacii po strategicheskomu razvitiju i nacional’nym proektam ot 17.09.2018 g. URL: http://government.ru/news/ 34001 (data obrashhenija: 13.05.2020).
32. Oficial’nyj sajt Nacional’nogo proekta «Nauka». URL: https://futurerussia.gov.ru/all (data obrashhenija: 10.05.2020).
33. Oficial’nyj sajt Nacional’nogo proekta «Cifrovaja jekonomika». URL: https://digital. gov.ru/ (data obrashhenija: 13.05.2020).
34. Rejting top 50 superkomp’juterov. URL: http://top50.supercomputers.ru/ (data obrashhenija: 12.12.2020).
Review
For citations:
Agapov E.V., Bobrov L.K., Zaykov K.A. Specificity of Task Scheduling Algorithms in Geographically Distributed Computer Systems. Vestnik NSUEM. 2021;(3):19-30. (In Russ.) https://doi.org/10.34020/2073-6495-2021-3-019-030
Email this article 
