ЦЕНТРАЛЬНО-КОЛЬЦЕВОЙ ПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ РАСПРЕДЕЛЕНИЯ ВЫЧИСЛИТЕЛЬНО-ВРЕМЕННЫХ РЕСУРСОВ В ГРИД-СИСТЕМАХ

  • Д.Ю. Кравченко Южный федеральный университет
  • Ю.А. Кравченко Южный федеральный университет
  • Э. В. Кулиев Южный федеральный университет
  • А.Э. Саак Южный федеральный университет
Ключевые слова: Диспетчирование, параллельные вычисления, grid-системы, распределенные вычислительные ресурсы, центрально-кольцевой полиномиальный алгоритм, централизованная архитектура.

Аннотация

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

Литература

1. Magoulès F., Nguyen T., Yu L. Grid resource management: toward virtual and services compliant
grid computing, Numerical analysis and scientific computing. CRC Press, UK, 2009.
2. Magoulès F. ed. Fundamentals of grid computing: theory, algorithms and technologies, Numerical
analysis and scientific computing. CRC Press, UK, 2010.
3. Patel S. Survey Report of Job Scheduler on Grids, International Journal of Emerging Research
in Management &Technology, 2013, 2 (4), pp. 115-125.
4. Li M., Baker M. The grid: core technologies. John Wiley & Sons Ltd, England. 2005.
5. Saak A.E., Kureichik V.V., Kravchenko Y.A. Scheduling quality of precise form sets which
consist of tasks of circular type in GRID systems, Journal of Physics: Conference Series,
2018, 1015 (4).
6. Saak A.E., Kureichik V.V., Lezhebokov A.A. Scheduling of parabolic-type tasks arrays in GRID
systems, Advances in Intelligent Systems and Computing, 2017, pp. 292-298.
7. Saak A., Kureichik, V., Kravchenko Y. To scheduling quality of sets of precise form which
consist of tasks of circular and hyperbolic type in grid systems, Advances in Intelligent Systems
and Computing, 2016, pp. 157-166.
8. Saak A.E., Kureichik V.V., Kuliev E.V. Ring algorithms for scheduling in grid systems, Advances
in Intelligent Systems and Computing, 2015, pp. 201-209.
9. Wäscher G., Hauβner H., Schumann H.. An improved typology of cutting and packing problems.
European Journal of Operational Research, 2007, Vol. 183, pp. 1109-1130.
10. Huang E., Korf R. Optimal rectangle packing: an absolute placement approach. Journal of
Artificial Intelligence Research, 2012, Vol. 46, pp. 47-87.
11. Simonis H., O'Sullivan B. Search strategies for rectangle packing. In Stuckey, P. (ed.), 14th
International Conference on Principles and Practice of Constraint Programming (CP 2008),
Vol. 5202 of Lecture Notes in Computer Science. Springer, 2008, pp. 52-66.
12. Clautiaux F., Carlie, J., Moukrim A. A new exact method for the two-dimensional orthogonal packing
problem, European Journal of Operational Research, 2007, Vol. 183 (3), pp. 1196-1211.
13. Bastos-Filho C.J.A., Lima-Neto F.B., Lins Sousa M.F.C., Pontes M.R. On the influence of the
swimming operators in the fish school search algorithm, IEEE International Conference on
Systems Man and Cybernetics, 2009 pp. 5012-5017.
14. Kenmochi M., Imamichi T., Nonobe K., Yagiura M., Nagamochi H. Exact algorithms for the
two- dimensional strip packing problem. European Journal of Operational Research, 2009,
Vol. 198, pp. 73-83.
15. Moffitt M., Pollack M. Optimal rectangle packing: a meta-csp approach. In Long, D., Smith,
S., Borrajo, D., McCluskey, L. (ed)., ICAPS, 2006, pp. 93-102. AAAI.
16. Hifi M., Ouafi R. A best-first branch-and-bound algorithm for orthogonal rectangular packing
problems. Int. Trans. in Operational Research, 1998, No. 5 (5), pp. 345-356.
17. Foster I., Kesselman C. The Grid in a nutshell. In: Nabrzyski, J., Schopf, J., Weglarz, J. (ed.)
Grid Resource Management: state of the art and future trends. Kluwer, 2003.
18. Kureychik V.M. Overview and problem state of ontology models development, 9th International
Conference on Application of Information and Communication Technologies, AICT
2015 - Proceedings 9, 2015, pp. 558-564.
19. Semenova A.V. and Kureychik V.M. Application of swarm intelligence for domain ontology
alignment, Proceedings of the First International Scientific Conference “Intelligent Information
Technologies for Industry” (IITI’16), 2016, Vol. 1, pp.261-270.
20. Bova V., Kureichik V. and Zaruba D. Heuristic approach to model of corporate knowledge
construction in information and analytical systems, 2016 IEEE 10th International Conference
on Application of Information and Communication Technologies (AICT), Baku, 2016, pp. 1-5.
21. Kureichik V., Zaporozhets D., and Zaruba D. Generation of bioinspired search procedures for
optimization problems, Application of Information and Communication Technologies, AICT
2016 - Conference Proceedings, 2016, Vol. 10.
22. Pulyavina N., Taratukhin V. The Future of Project-Based Learning for Engineering and Management
Students: Towards an Advanced Design Thinking Approach, ASEE Annual Conference
and Exposition, Conference Proceeding, 2018, No. 125.
23. Becker J. Next-Gen Design Thinking. Using Project-Based and Game-Oriented Approaches to
Support Creativity and Innovation, J. Becker, N. Pulyavina, V. Taratukhin // Proceedings of
the 1st International Conference of Information Systems and Design, 2020.
24. Bova V.V., Nuzhnov E.V., Kureichik V.V. The combined method of semantic similarity estimation
of problem oriented knowledge on the basis of evolutionary procedures, Advances in Intelligent
Systems and Computing, 2017, Vol. 573, pp. 74-83.
Опубликован
2022-08-09
Выпуск
Раздел
РАЗДЕЛ II. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ