ИСПОЛЬЗОВАНИЕ ГЕТЕРОГЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ УЗЛОВ В ГРИД-СИСТЕМАХ ПРИ РЕШЕНИИ КОМБИНАТОРНЫХ ЗАДАЧ
Аннотация
В настоящее время для решения больших вычислительных задач используются не
только многопроцессорные вычислительные системы, но и различные виды распределенных
систем. Распределенные вычислительные системы имеют ряд особенностей: возможное
наличие отказов узлов и каналов связи, непостоянное время работы узлов, возможные ошиб-
ки в расчетах, гетерогенность вычислительных узлов. Под гетерогенностью вычислитель-
ных узлов будем понимать не только различную вычислительную способность и различные
архитектуры центральных процессоров, но и наличие на узле других компонентов, способных
проводить вычисления. К таким компонентам можно отнести видеокарты и математиче-
ские сопроцессоры. Узел распределенной вычислительной системы будем называть гетеро-
генным, если помимо одного или нескольких центральных процессоров в его составе есть
дополнительные вычислительные устройства. При решении вычислительной задачи на рас-
пределенной системе необходимо максимизировать использование всех доступных вычисли-
тельных ресурсов. Для этого необходимо не только распределить вычислительные подзадачи
на узлы в соответствии с их вычислительной способностью, но и учесть особенности допол-
нительных вычислительных устройств. Исследованию методов максимизации использования
ресурсов на гетерогенных узлах распределенной вычислительной системы посвящена эта
работа. Основной целью данной работы является создание переносимого приложения, произ-
водящего параллельные вычисления с использованием многопоточной модели выполнения. При
разработке приложения акцент делается на наиболее полном использовании доступных ап-
паратных ресурсов. Одним из основных требований к реализации является оптимизация про-
изводительности приложения для различных компьютерных архитектур, а также возмож-
ность параллельного выполнения приложения на разнородных вычислительных устройствах,
входящих в состав гетерогенного вычислительного комплекса. Была исследована возмож-
ность применения ряда методов программно-алгоритмической оптимизации для многопро-
цессорных архитектур различных поколений. А также была проведена оценка эффективно-
сти их использования для высоконагруженных многопоточных приложений. Представлено
решение проблемы квазиоптимального динамического распределения вычислительных зада-
ний между всеми доступными на данный момент вычислительными устройствами гетеро-
генного вычислительного комплекса.
Литература
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.
