Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

МОДЕЛИ ПРОГНОЗИРОВАНИЯ ВРЕМЕНИ ВЫПОЛНЕНИЯ СХЕМ РЕШЕНИЯ ЗАДАЧ В ГЕТЕРОГЕННОЙ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ

Феоктистов А.Г. 1 Башарина О.Ю. 2
1 ФГБУН «Институт динамики систем и теории управления им. В.М. Матросова» СО РАН
2 ФГБОУ ВО «Иркутский государственный университет»
В настоящее время распределенные пакеты прикладных программ играют существенную роль в рамках поддержки проведения крупномасштабных научных экспериментов в гетерогенной вычислительной среде. Гетерогенность подразумевает использование в рамках среды узлов (персональных компьютеров, серверов, кластеров, облачных платформ) с разными архитектурами и вычислительными характеристиками. Схемы решения задач в таких пакетах строятся на вычислительных моделях, представляющих собой частный случай семантической сети. Для построения схем решения задач используются методы планирования вычислений и информационного планирования. В статье предложены новые модели прогнозирования времени выполнения схем решения задач в гетерогенной среде. Задача прогнозирования времени выполнения программ в гетерогенной среде является чрезвычайно актуальной. Ее решение позволяет эффективно распределять и использовать ресурсы среды. Предложенные модели позволяют, в отличие от известных, учитывать различные оценки времени выполнения модулей, входящих в состав схем решения задач. В статье приведены результаты сравнительного анализа точности прогнозирования времени выполнения схем с использованием различных оценок времени выполнения модулей. Наибольшая точность достигается при использовании оценок времени выполнения модулей, полученных на основе динамического анализа программ.
распределенные вычисления
гетерогенные ресурсы
вычислительная модель
время выполнения программ
прогнозирование
1. Deelman E., Peterka T., Altintas I., Carothers C.D., van Dam K.K., Moreland K., Parashar M., Ramakrishnan L., Taufer M., Vetter J. The future of scientific workflows. The International Journal of High Performance Computing Applications. 2018. Vol. 32. № 1. P. 159–175. DOI: 10.1177/1094342017704893.
2. Cao F., Zhu M.M., Ding D. Distributed workflow scheduling under throughput and budget constraints in grid environments. Lecture Notes in Computer Science. 2013. Vol. 8429. P. 62–80. DOI: 10.1007/978-3-662-43779-7_4.
3. Qin J., Fahringer T. Semantic-based scientific workflow composition. Scientific Workflows. – Springer, Berlin, Heidelberg, 2012. P. 115–134. DOI: 10.1007/978-3-642-30715-7_7.
4. Deelman E., Vahia K., Juvea G., Ryngea M., Callaghan S., Maechling P.J.,Mayani R., Chen W, da Silva R.F., Livny M., Wenger K. Pegasus, a workflow management system for science automation. Future Generation Computer Systems. 2015. Vol. 46. P. 17–35. DOI: 10.1016/j.future.2014.10.008.
5. Феоктистов А.Г., Башарина О.Ю. Методика динамического анализа времени выполнения программ в гетерогенных распределенных вычислительных средах // Вестник Иркутского государственного технического университета. 2018. Т. 22. № 6. С. 109–119. DOI: 10.21285/1814-3520-2018-6-109-119.
6. Феоктистов А.Г., Горский С.А., Сидоров И.А., Костромин Р.О., Фереферов Е.С., Бычков И.В. Непрерывная интеграция функционального наполнения распределенных пакетов прикладных программ в Orlando Tools // Труды ИСП РАН. 2019. Т. 31. № 2. С. 83–96. DOI: 10.15514/ISPRAS-2019-31(2)-7.
7. Бычков И.В., Опарин Г.А., Феоктистов А.Г., Корсуков А.С. Децентрализованное управление потоками заданий в интегрированной кластерной системе // Вестник Новосибирского гос. ун-та. Серия: Информационные технологии. 2011. Т. 9. № 2. С. 42–54.
8. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ–Петербург, 2002. 608 с.
9. Опарин Г.А., Новопашин А.П. Булево моделирование планирования действий в распределенных вычислительных системах // Известия РАН. Теория и системы управления. 2004. № 5. С. 105–108.
10. ЦКП Иркутский суперкомпьютерный центр СО РАН. [Электронный ресурс]. URL: http://hpc.icc.ru/ (дата обращения: 23.10.2019).

В настоящее время научные приложения, ориентированные на проведение крупномасштабных научных экспериментов в гетерогенной распределенной вычислительной среде (ГРВС), играют существенную роль в процессе решения важных практических задач на основе математического моделирования исследуемых систем [1]. Как правило, такие приложения реализуются в виде распределенных пакетов прикладных программ (РППП). Гетерогенность среды подразумевает использование в ней узлов (персональных компьютеров, серверов, кластеров, облачных платформ) с разными программно-аппаратными архитектурами и вычислительными характеристиками.

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

Для эффективного решения задач в ГРВС и рационального использования ее ресурсов необходима возможность оценки времени выполнения схем решения этих задач. В статье предложены новые модели прогнозирования времени выполнения таких схем в ГРВС. Эти модели позволяют, в отличие от известных моделей аналогичного назначения [2–4], учитывать различные оценки времени выполнения модулей, входящих в состав схем. В их числе оценки, получаемые на основе методики динамического анализа времени выполнения программ, предложенной авторами статьи [5] и используемой в процессе непрерывной интеграции прикладного программного обеспечения разрабатываемых пакетов [6].

Модели прогнозирования времени выполнения схем решения задач

Вычислительная модель ГРВС определяется структурой

feokt01.wmf = <ASP, Z, F, M, PR, S, J,

R, A, Q, PLCS, MH, O>,

где ASP, Z, F, M, S, J, R, A, Q, O – это соответственно множества пакетов прикладных программ, параметров, операций, программных модулей, продукций, схем решения задач, заданий, ресурсов, агентов, ограничений на выполнение заданий и использование ресурсов, накладываемых множеством PLCS административных политик, а также отношений между перечисленными объектами. Структура данных MH отражает вычислительную историю работы модулей из M. Детальное описание компонентов модели можно найти в [5, 7].

Операции из F определяют отношения вычислимости на множестве параметров Z. Параметры могут быть представлены скалярами, векторами, матрицами различных базовых типов данных или произвольными структурами данных. Каждая операция fi∈F реализуется модулем mj∈M, где feokt02.wmf, feokt03.wmf, nf – число операций, nm – число модулей. Один модуль может реализовать несколько операций. С каждой операцией fi связано два подмножества параметров feokt04.wmf. feokt05.wmf включает параметры, значения которых необходимо задать, чтобы получить значения параметров из feokt06.wmf. Параметры подмножеств feokt07.wmf и feokt08.wmf отражают назначение и семантику формальных параметров модуля mj, реализующего операцию fi. Параметры передаются между модулями в виде файлов.

Процессы решения задач в пакетах представлены схемами из S. Схема s∈S выполнения операций из F является аналогом строгой параллельной формы графа алгоритма, а ее построение сходно с построением данной формы [8]. В рамках рассматриваемой вычислительной модели схема является связным подграфом ориентированного ациклического двудольного графа, представляющего схемные знания об алгоритмах исследования предметной области. На рис. 1 представлен пример такого графа. Операции и параметры изображены на нем закрашенными и незакрашенными кружками.

feoktis1.wmf

Рис. 1. Двудольный ориентированный граф схемы решения задачи

С целью поддержки общности планирования вычислений при построении схем решения задач с использованием их постановок в вычислительной модели выделяются две специальные операции f1 и f2 [9], моделирующие в дальнейшем условия задачи, подмножество параметров, значения которых заданы, и подмножество параметров, значения которых нужно вычислить. Операция f1 определяет подмножества feokt09.wmf и feokt10.wmf, а операция f2 обуславливает подмножества feokt11.wmf и feokt12.wmf. В приведенном выше примере feokt13.wmf и feokt14.wmf, а feokt15.wmf и feokt16.wmf.

Прогнозирование времени выполнения схем решения задач здесь и ниже базируется на подходе к оценке производительности вычислительных устройств, предложенном в [7]. Пусть матрица P размерности k×k представляет сведения о предшествовании k операций схемы решения задачи. Элемент pij = 1 (pij = 0) матрицы P означает, что выполнение операции fi в схеме решения задачи предшествует (не предшествует) выполнению операции fi и feokt17.wmf. Матрица feokt18.wmf размерности k×k отражает оценки объемов передаваемых данных между операциями. Элемент матрицы feokt19.wmf показывает объем данных, передаваемых операцией fi операции fj. Матрица W размерности k×k предоставляет информацию о пропускной способности интерконнекта между узлами, в которых запускаются модули, реализующие операции схемы. Элемент матрицы wij ≥ 0 демонстрирует пропускную способность интерконнекта между узлами, в которых работают модули, реализующие операции fi и fj. Тогда оценка feokt20.wmf времени выполнения схемы в асинхронном режиме по готовности данных определяется следующим образом:

feokt21.wmf,

feokt22.wmf

где feokt23.wmf (feokt24.wmf) – оценка времени, прошедшего с начала обработки схемы до завершения операции fi (fj), feokt25.wmf – оценка времени нахождения в очереди модуля, реализующего операцию fi (в то время, когда все данные, необходимые для его выполнения, готовы), feokt26.wmf – прогнозная оценка времени выполнения этого модуля, k – число операций схемы, 0 < ωji(t) ≤ 1 – коэффициент снижения пропускной способности интерконнекта в момент времени t между узлами, в которых функционируют модули, реализующие операции fi и fj.

Пусть матрица S размерности m×k представляет собой ярусно-параллельную форму, описывающую обработку схемы в режиме fork/join, m – число ярусов схемы. Элемент sli = 1 означает, что операция fi должна быть выполнена на l-м ярусе. Переход к операциям (l + 1)-го яруса возможен при условии завершения всех операций на l-м ярусе. Тогда оценка feokt27.wmf времени выполнения схемы в режиме fork/join находится следующим образом:

feokt28.wmf

feokt29.wmf

Оценка feokt30.wmf времени выполнения схемы в среде с виртуализированными ресурсами в асинхронном режиме определяется следующим образом:

feokt31.wmf feokt32.wmf

где feokt33.wmf и feokt34.wmf – это соответственно оценки времени на запуск и завершение ВМ для выполнения модуля, реализующего операцию fi. Оценки feokt35.wmf и feokt36.wmf определяются экспериментальным путем для ВМ различной конфигурации.

Оценка feokt37.wmf времени выполнения схемы в среде с виртуализированными ресурсами соответственно в режиме fork/join определяется следующим образом:

feokt38.wmf feokt39.wmf

Оценка feokt40.wmf времени выполнения схемы в асинхронном режиме с рестартом модулей определяется следующим образом:

feokt41.wmf feokt42.wmf

где feokt43.wmf и feokt44.wmf – это соответственно оценки времени обнаружения и идентификации отказа, а также повторного запуска (рестарта) модуля, реализующего операцию fi, в случае программно-аппаратного отказа. Оценки feokt45.wmf и feokt46.wmf определяются средним временем выполнения таких процессов системой метамониторинга для разных видов программно-аппаратных отказов, feokt47.wmf – время выполнения модуля до отказа.

Оценка feokt48.wmf времени выполнения схемы в среде с виртуализированными ресурсами соответственно в режиме fork/join определяется следующим образом:

feokt49.wmf feokt50.wmf

Оценка feokt51.wmf времени выполнения схемы в асинхронном режиме по готовности данных на основе пользовательских оценок времени выполнения модулей определяется следующим образом:

feokt52.wmf feokt53.wmf

где feokt54.wmf – пользовательская оценка времени выполнения модуля.

Оценка feokt55.wmf времени выполнения схемы в режиме fork/join определяется следующим образом:

feokt56.wmf feokt57.wmf

Оценка feokt58.wmf времени выполнения схемы в среде с виртуализированными ресурсами в асинхронном режиме определяется следующим образом:

feokt59.wmf feokt60.wmf

Оценка feokt61.wmf времени выполнения схемы в среде с виртуализированными ресурсами соответственно в режиме fork/join определяется следующим образом:

feokt62.wmf feokt63.wmf

Оценка feokt64.wmf времени выполнения схемы в асинхронном режиме с рестартом модулей определяется следующим образом:

feokt65.wmf feokt66.wmf

Оценка feokt67.wmf времени выполнения схемы в среде с виртуализированными ресурсами соответственно в режиме fork/join определяется следующим образом:

feokt68.wmf feokt69.wmf

Оценка feokt70.wmf времени выполнения схемы в асинхронном режиме по готовности данных на основе пользовательских оценок времени выполнения модулей определяется следующим образом:

feokt71.wmf feokt72.wmf

где feokt73.wmf – скорректированная пользовательская оценка времени выполнения модуля, βi = ψ(i, MH, Th) > 0 – это корректирующий коэффициент, вычисляемый на основе вычислительной истории. Функция ψ(i, MH, Th) вычисляет значение коэффициента βi, используя среднее или медианное значения по выборке времени выполнения модуля, реализующего операцию fi, за определенный период Th.

Оценка feokt74.wmf времени выполнения схемы в режиме fork/join определяется следующим образом:

feokt75.wmf feokt76.wmf

Оценка feokt77.wmf времени выполнения схемы в среде с виртуализированными ресурсами в асинхронном режиме определяется следующим образом:

feokt78.wmf feokt79.wmf

Оценка feokt80.wmf времени выполнения схемы в среде с виртуализированными ресурсами соответственно в режиме fork/join определяется следующим образом:

feokt81.wmf feokt82.wmf

Оценка feokt83.wmf времени выполнения схемы в асинхронном режиме с рестартом модулей определяется следующим образом:

feokt84.wmf feokt85.wmf

Оценка feokt86.wmf времени выполнения схемы в среде с виртуализированными ресурсами соответственно в режиме fork/join определяется следующим образом:

feokt87.wmf feokt88.wmf

feoktis2.wmf

Рис. 2. Результаты реального и прогнозируемого времени выполнения заданий по перемножению матриц

feoktis3.wmf

Рис. 3. Погрешность прогнозируемого времени выполнения заданий

В качестве примера проведем сравнение погрешности различных способов прогнозирования времени выполнения заданий для задач линейной алгебры (перемножение матриц размерности n×n). Задачи решались в ГРВС, организованной на базе ресурсов Центра коллективного пользования «Иркутский суперкомпьютерный центр СО РАН» [10], в процессе непрерывной интеграции (модификации, контроля версий, сборки, тестирования, доставки и размещения) модулей, реализующих операции линейной алгебры. На рис. 2 приведены результаты времени выполнения заданий по перемножению матриц для n = 1000, 1500, 2000, 2500, 3000 одной и той же программой на эталонном и исследуемом узлах, а также время выполнения этих заданий, определенное с помощью трех способов его прогнозирования, рассмотренных выше.

Очевидно, что наиболее точный прогноз формируется на основе динамического анализа программ. На рис. 3 приведены погрешности различных способов прогнозирования времени выполнения заданий в сравнении с реальным временем их выполнения в исследуемом узле. Результаты, приведенные на рис. 3, показывают, что погрешность времени выполнения задания, спрогнозированного на основе динамического анализа программы, убывает с увеличением размерности матриц. В данном примере она не превышает 13,64 %. В то же время изменение погрешности времени выполнения задания, спрогнозированного на основе запроса пользователя, может иметь немонотонный характер. На практике время выполнения задания, спрогнозированного на основе запроса пользователя, как правило, завышается. Корректировка времени в запросе пользователя на основе вычислительной истории его заданий может уменьшить погрешность прогнозирования.

Заключение

Рассмотренные в статье модели прогнозирования схем решения задач в ГРВС будут использованы в процессе децентрализованного управления вычислениями [6].

Работа выполнена при поддержке РФФИ, проект № 19-07-00097-А и Президиума РАН, программа № 7, проект «Методы, алгоритмы и инструментальные средства децентрализованного группового решения задач в вычислительных и управляющих системах».


Библиографическая ссылка

Феоктистов А.Г., Башарина О.Ю. МОДЕЛИ ПРОГНОЗИРОВАНИЯ ВРЕМЕНИ ВЫПОЛНЕНИЯ СХЕМ РЕШЕНИЯ ЗАДАЧ В ГЕТЕРОГЕННОЙ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ // Современные наукоемкие технологии. – 2019. – № 11-1. – С. 102-108;
URL: https://top-technologies.ru/ru/article/view?id=37773 (дата обращения: 10.10.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674