THE USE OF HETEROGENEOUS COMPUTING NODES IN GRID SYSTEMS IN SOLVING COMBINATORIAL PROBLEMS
Abstract
The main goal of this work is to create a parallel application that performs computations
using a multithreaded execution model, optimized to make the best utilization of all available
hardware resources. One of the main implementation requirements is to optimize application performance
on different computer architectures, and to enable parallel execution of the application
on various computing devices that are part of a heterogeneous computing system. The possibility
of applying various methods of software and algorithmic optimization on multiprocessor architectures
of different generations was investigated as well as the effectiveness of their use for highly
loaded multithreaded applications was estimated. The problem of quasi-optimal dynamic distribution
of computational tasks among all currently available computing devices of a heterogeneous
computing system was also solved. Currently, not only multiprocessor computing systems are used
to solve large computational problems, but also various types of distributed systems. Distributed
computing systems have a number of features: possible failures of nodes and communication
channels, unstable operating time of nodes, possible errors in calculations, heterogeneity of computing
nodes. By heterogeneity of computing nodes, we will understand not only the different computing
capacity and different architectures of central processors, but also the presence of other
devices on the node capable of performing calculations. Such devices include video cards and
mathematical coprocessors. A node of a distributed computing system will be called heterogeneous
if, in addition to one or more central processing units, it contains additional computing devices.
When solving a computational problem on a distributed system, it is necessary to maximize the
utilization of all available computing resources. To do this, it is necessary not only to distribute
computing subtasks to nodes in accordance with their computing capacity, but also to take into
account the features of additional computing devices. This work is devoted to the study of methods
for maximizing the resources utilization of heterogeneous nodes.
References
2020, Vol. 18, No. 1, pp. 99-122.
2. Wang L., Jie W., Chen J. Grid computing: infrastructure, service, and applications. CRC Press,
2018.
3. Braun T.D. et al. A comparison of eleven static heuristics for mapping a class of independent
tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed
computing, 2001, Vol. 61, No. 6, pp. 810-837.
4. Cirne W. et al. Grid computing for bag of tasks applications, In Proc. of the 3rd IFIP Conference
on E-Commerce, E-Business and EGovernment, 2003.
5. Posypkin M., Semenov A., Zaikin O. Using BOINC desktop grid to solve large scale SAT problems,
Computer Science, 2012, Vol. 13, No. 1, pp. 25.
6. Yang C.T. et al. Performance benchmarking of deep learning framework on Intel Xeon Phi,
The Journal of Supercomputing, 2021, Vol. 77, No. 3, pp. 2486-2510.
7. Jennett C. et al. Motivations, learning and creativity in online citizen science, Journal of Science
Communication, 2016, Vol. 15, No 3.
8. Foster I., Kesselman C. (ed.). The Grid 2: Blueprint for a new computing infrastructure. Elsevier,
2003.
9. Amalarethinam D.I.G., Josphin A.M. Dynamic task scheduling methods in heterogeneous systems:
a survey, International Journal of Computer Applications, 2015, Vol. 110, No. 6.
10. Choi S.J. et al. Volunteer availability based fault tolerant scheduling mechanism in desktop
grid computing environment, Third IEEE International Symposium on Network Computing
and Applications, 2004.(NCA 2004). Proceedings. IEEE, 2004, pp. 366-371.
11. Vatutin E., Nikitina N., Belyshev A., Manzyuk M. On polynomial reduction of problems based on
diagonal Latin squares to the exact cover problem, ICCS-DE, 2020, Vol. 2638, pp. 289-297. DOI:
10.47350/ICCS-DE.2020.26.
12. Brown J.W., Cherry F., Most L., Most M., Parker E.T., Wallis W.D. Completion of the spectrum
of orthogonal diagonal Latin squares, Lecture notes in pure and applied mathematics,
1992, Vol. 139, pp. 43-49. DOI: 10.1201/9780203719916.
13. Intel Xeon Phi Coprocessor System Software Developers Guide. Intel Corporation, 2014, 164 p.
14. Al'bert'yan A.M., Kurochkin I.I. Ispol'zovanie soprotsessorov Intel Xeon Phi v grid-sistemakh
iz personal'nykh komp'yuterov [The use of Intel Xeon Phi coprocessors in grid systems from
personal computers], CEUR-Proceedings: Selected Papers of the II Intern. Sci. Conf." Convergent
Cognitive Information Technologies", Moscow, Russia, 2017, Vol. 2064, pp. 196-201.
15. Vatutin E., Belyshev A., Nikitina N., Manzuk M. Evaluation of Efficiency of Using Simple
Transformations When Searching for Orthogonal Diagonal Latin Squares of Order 10, Communications
in Computer and Information Science, Vol. 1304. Springer, 2020, pp. 127-146.
DOI: 10.1007/978-3-030-66895-2_9.
16. James Jeffers, James Reinders Intel Xeon Phi Processor High Performance Programming.
Morgan Kaufmann, 2013, 432 p. ISBN: 978-0-12-410414-3.
17. De Ravé E.G. et al. Using general-purpose computing on graphics processing units (GPGPU) to
accelerate the ordinary kriging algorithm, Computers & Geosciences, 2014, Vol. 64, pp. 1-6.
18. Nobile M.S. et al. Graphics processing units in bioinformatics, computational biology and
systems biology, Briefings in bioinformatics, 2017, Vol. 18, No. 5, pp. 870-885.
19. Morrison D.R. et al. Branch-and-bound algorithms: A survey of recent advances in searching,
branching, and pruning, Discrete Optimization, 2016, Vol. 19, pp. 79-102.
20. Hill M.D. et al. On the Spectre and Meltdown processor security vulnerabilities, IEEE Micro,
2019, Vol. 39, No. 2, pp. 9-19.
