Разработка методов и средств повышения эффективности использования ресурсов в вычислительных системах с жесткими требованиями к качеству обслуживанияНИР

Development of methods and tools for improving resource utilization efficiency for computer systems with strict quality of service requirements

Источник финансирования НИР

грант РФФИ

Этапы НИР

# Сроки Название
1 1 января 2019 г.-31 декабря 2019 г. Разработка методов и средств повышения эффективности использования ресурсов в вычислительных системах с жесткими требованиями к качеству обслуживания
Результаты этапа: 2019 г. 1. Разработана формальная постановка задачи отображения запросов на физические ресурсы ЦОД (планирования выполнения запросов), содержащая типизацию отношений между характеристиками ресурсов и критериями SLA и позволяющей задавать для виртуальных машин политики размещения. 2. Разработана формальная постановка задачи построения расписания выполнения функциональных задач в ИУС РВ (включая распределение разделов по процессорным ядрам и расписание выполнения окон) и построения систем виртуальных каналов в сети в составе ИУС РВ, ориентированной на взаимосвязанное (совместное или с обратной связью) решение этих задач. 3. Разработаны подходы к снижению фрагментации физических ресурсов ЦОД и сокращению вариативности производительности виртуальных машин. 4. Разработаны схемы выполнения шагов планирования вычислений в ИУС РВ с обратной связью между шагами.
2 1 января 2020 г.-31 декабря 2020 г. Разработка методов и средств повышения эффективности использования ресурсов в вычислительных системах с жесткими требованиями к качеству обслуживания
Результаты этапа: *** Алгоритм отображения запросов на физические ресурсы ЦОД (планирования запросов) *** Разработанный алгоритм основан на сочетании жадных стратегий и ограниченного перебора. Алгоритм построен по следующей схеме: * на каждом шаге работы алгоритма делается выбор в соответствии с используемой жадной стратегией: выбирается запрос, элемент запроса и ресурс для его размещения, * на каждом шаге осуществляется проверка того, что «жадный выбор не закрывает пути к оптимальному решению», * вызов процедуры ограниченного перебора, если проверка условия «жадный выбор не закрывает пути к оптимальному решению» дала отрицательный результат. Глубина перебора (количество запросов, участвующих в переборе) является параметром алгоритма. Увеличивая глубину перебора, можно улучшать точность алгоритма, но при этом увеличивается его вычислительная сложность. Алгоритм обладает следующими свойствами: 1. Поддерживает вычислительные ресурсы, хранилища данных и сетевые ресурсы в качестве планируемых ресурсов. 2. Позволяет устранять фрагментацию физических ресурсов. 3. Поддерживает опциональный учет политик размещения виртуальных ресурсов. 4. Предоставляет возможность построения плана миграции ранее размещенных виртуальных ресурсов. Данная возможность необходима для устранения фрагментации физических ресурсов, возникающей в ходе эксплуатации ЦОД. (подробная информация по п. 4 приведена в работе [Костенко В.А., Чупахин А.А. Схемы организации “живой” миграции в центрах обработки данных // Программирование, 2020, № 5, С. 11–15]) Ни один из известных авторам алгоритмов не обладает в совокупности всеми перечисленными свойствами. Более детально алгоритм описан в работе [Васильева Ю. О., Костенко В.А., Чупахин А.А. Влияние политик размещения виртуальных машин на эффективность использования ресурсов ЦОД // Известия РАН. Теория и системы управления, 2020, № 3, С. 95–100]. *** Экспериментальное исследование свойств разработанного алгоритма планирования запросов *** Экспериментальное исследование проводилось по следующим критериям, характеризующим эффективность использования ресурсов ЦОД: 1. Загрузка физических ресурсов ЦОД. 2. Доля размещенных запросов. Предметом исследования являлось: 1. Влияние учета политик размещения виртуальных ресурсов на долю размещенных запросов и загрузку центра обработки данных. 2. Влияние обязательных политик на долю неразмещенных запросов. 3. Влияние учета политик на время работы алгоритма. Эксперименты проводились на персональном компьютере с процессором Intel Core i7–6500U с тактовой частотой 2,5 ГГц и двумя ядрами. В ходе экспериментов, модель физических ресурсов ЦОД задавалась размеченным графом H=(P∪M∪K,L), где Р – множество вычислительных узлов, М – множество хранилищ данных, К – множество коммутационных элементов сети обмена ЦОД, L – множество физических каналов передачи данных. На множествах P, M, K и L были определены векторные функции скалярного аргумента, задающие соответственно характеристики вычислительных узлов, хранилищ данных, коммутационных элементов и каналов передачи данных. Были сгенерированы конфигурации ЦОД со следующими параметрами: * Топология: дерево * Количество физических серверов: 256 * Параметры физических узлов: количество ядер 16–32, объем памяти 32–64 Гб * Пропускные способности физических каналов сети: 200–300 Мб/с Запросы на создание виртуальных ресурсов задавались в виде графа G=(W∪S,E), где W – множество виртуальных машин, используемых приложениями, S – множество виртуальных хранилищ данных (storage-элементов), E – множество виртуальных каналов передачи данных между виртуальными машинами и storage-элементами запроса. На множествах W, S и E были определены векторные функции скалярного аргумента, задающие характеристики запрашиваемого виртуального элемента (service level agreement – SLA). Для части запросов были заданы политики размещения виртуальных машин. Были сгенерированы наборы запросов со следующими параметрами: * Топология: дерево, звезда, кольцо (выбор делается случайным образом) * Количество запросов: 190–200 * Количество виртуальных машин в запросе: 6–8 * Параметры виртуальных машин: - Количество ядер: 1–8 - Объем оперативной памяти: 2–16 Гб * Пропускные способности виртуальных каналов: 2–8 Мб/с * Доля виртуальных машин, для которых заданы политики: - Эксперименты 1, 2: 20% - Эксперименты 3, 4: 50% - Эксперименты 5, 6: 80% * Доля запросов с обязательными политиками: - Эксперименты 1, 3, 5: 20% - Эксперименты 2, 4, 6: 80% По результатам экспериментального исследования были сделаны следующие выводы: 1. Учет политик негативно сказывается на доле размещенных запросов. Причем чем выше доля запросов, содержащих политики, и чем выше доля обязательных политик, тем ниже доля размещенных запросов и загрузка ЦОД. 2. При учете политик основное негативное влияние на загрузку и долю размещенных запросов оказывают именно обязательные политики. 3. При высокой доле опциональных политик размещения запросов время работы алгоритма возрастает. Анализ результатов экспериментов приведен в работе [Васильева Ю. О., Костенко В.А., Чупахин А.А. Влияние политик размещения виртуальных машин на эффективность использования ресурсов ЦОД // Известия РАН. Теория и системы управления, 2020, № 3, С. 95–100]. *** Алгоритм планирования вычислений в ИУС РВ с обратной связью между шагами и с совместным выполнением шагов *** В рамках планирования вычислений в ИУС РВ необходимо: 1) распределить вычислительную нагрузку (разделы) по модулям и процессорным ядрам в их составе; 2) построить набор виртуальных каналов для передачи сообщений между модулями, в т.ч. определить маршруты виртуальных каналов в сети; 3) построить расписание окон для каждого ядра. Последовательному решению задач 1, 2, 3 соответствует последовательная схема планирования вычислений, состоящая из трех этапов, на каждом из которых при помощи некоторого алгоритма решается соответствующая задача. Разработанный алгоритм построен по итерационной схеме планирования вычислений, расширяющей последовательную схему за счет добавления на этапы (кроме первого) функций: * анализа причин неуспешности выполнения этапа; * уточнения ограничений на результаты предшествующего этапа; * возврата на предшествующий этап с уточненными ограничениями. В рамках разработанного алгоритма, обратная связь между этапами (шагами) планирования заключается в поддержке возврата на предыдущий этап с уточненными ограничениями, а совместное (согласованное) выполнение этапов планирования заключается в том, что уточненные ограничения для предшествующего этапа рассчитываются на основе анализа причин неуспешности выполнения последующего этапа. В результате проведенного исследования причин неуспешности построения набора виртуальных каналов, соответствующих заданным ограничениям на длительность передачи сообщений, были выявлены две основные причины: (а) перегрузка канала между модулем и коммутатором, к которому он подключен; (б) перегрузка канала между коммутаторами. Эти причины являются частными случаями перегрузки сети, но требуют различных мер по их устранению. Для устранения причины (а), для этапа 1 (распределение вычислительной нагрузки) были введены дополнительные ограничения, параметры которых рассчитываются по результатам анализа причин неуспешного выполнения этапа 2 (построение виртуальных каналов). Также для частного случая топологии сети (“двойная звезда”) предложены дополнительные ограничения для этапа 1, позволяющие устранить причину (б). Проведенное исследование причин неуспешности построения расписания окон показало, что эта неуспешность как правило связана с невозможностью выполнения работ в рамках их директивных интервалов, основными причинами которой являются: (а) перегрузка процессорного ядра, на котором выполняются эти работы, и (б) поздний старт этих работ из-за ожидания входных сообщений. Для раннего, до начала построения расписания окон, выявления невозможности построения расписания окон, между этапами 2 и 3 был добавлен этап проверки критерия PDC (Processor Demand Criterion) для набора работ. По результатам проверки PDC и анализа графа зависимостей работ, рассчитываются параметры дополнительных ограничений для этапа 1, в случае причины (а), и этапа 2, в случае причины (б). Алгоритмы, используемые на этапах 1 и 2, расширены для учета введенных дополнительных ограничений. Алгоритмы, используемые на этапах 2 и 3, расширены для расчета параметров введенных ограничений для предшествующих этапов, а также уточнения параметров ранее поддерживавшихся ограничений. Подробное описание разработанного итерационного алгоритма планирования вычислений приведено в работе [Balashov V., Antipina E. Iterative co-scheduling of tasks and their data exchange through virtual link-based packet switched network // 3rd International Scientific and Technical Conference Modern Computer Network Technologies (MoNeTeC-2020). — IEEE, 2020]. Для проверки корректности построенного расписания окон, т.е. того, что все работы в рамках окон выполняются в рамках своих директивных интервалов, может использоваться инструментальная система, описанная в работе [Глонина А. Б. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. — 2020. — № 3. — С. 16–29]. При этом для случая, когда для задач известна не только верхняя, но и нижняя оценка длительности выполнения, для проверки корректности расписания применим алгоритм, описанный в работе [Гонопольский М. Г., Глонина А. Б. Алгоритм оценки максимального времени отклика задач в многопроцессорных системах с интервальной неопределенностью длительности выполнения работ // Моделирование и анализ информационных систем. — 2020. — Т. 27, № 2. — С. 218–233]. *** Экспериментальное исследование алгоритма планирования вычислений в ИУС РВ *** Основной целью экспериментального исследования была оценка преимущества предложенной итерационной схемы планирования над последовательной схемой, использующей те же алгоритмы на этапах планирования, но не поддерживающей возврат на предшествующие этапы. Исследование проводилось на наборах исходных данных (конфигураций ИУС РВ, рабочих нагрузок на ИУС РВ) с характеристиками, соответствующими реальным бортовым авиационным ИУС РВ (от 3 до 12 модулей, от 9 до 16 разделов, от 1 до 8 задач в разделе; суммарная загрузка процессорных ядер от 60% до 80%; наличие зависимостей по данным между задачами; наличие как “легких” (от 50 до 100 байтов), так и “тяжелых” (от 1000 до 5000 байтов) сообщений). Все модули системы считались одноядерными, чтобы обеспечить нетривиальность задачи построения виртуальных каналов за счет достаточно большого (до 12) числа модулей, обменивающихся данными по сети, при этом оставаясь в рамках возможностей экспоненциального по сложности алгоритма распределения вычислительной нагрузки. Все ядра в составе системы считались однотипными, чтобы иметь возможность априорно (до распределения вычислительной нагрузки) рассчитывать такие характеристики рабочей нагрузки, как суммарный вклад всех разделов в загрузку процессорных ядер, а также суммарные длительности задач в цепочках задач. Это необходимо для формирования наборов данных с заданными характеристиками. В качестве топологии межмодульной сети рассматривалась топология “множественная звезда”, типичная для бортовых ИУС РВ. Эксперименты показали значительное преимущество разработанного алгоритма, построенного по итерационной схеме, над последовательным выполнением алгоритмов, соответствующих шагам планирования. Результаты экспериментов и их анализ приведены в работе [Balashov V., Antipina E. Iterative co-scheduling of tasks and their data exchange through virtual link-based packet switched network // 3rd International Scientific and Technical Conference Modern Computer Network Technologies (MoNeTeC-2020). — IEEE, 2020]. В ряде экспериментов происходило каскадное выполнение возвратов на предыдущие этапы планирования; в частности, была продемонстрирована возможность последовательного уточнения распределения вычислительной нагрузки для обеспечения: вначале – устранения локальной во времени перегрузки процессорных ядер, приводившей к нарушению критерия PDC; затем – разгрузки перегруженных каналов сети. При этом ограничения на распределение нагрузки только усиливались, поэтому зацикливания итерационной схемы не происходило.
3 22 марта 2021 г.-31 декабря 2021 г. Разработка методов и средств повышения эффективности использования ресурсов в вычислительных системах с жесткими требованиями к качеству обслуживания
Результаты этапа: Целью проекта является создание методов, алгоритмов и инструментальных средств повышения эффективности эксплуатации центров обработки данных (ЦОД), работающих в режиме «инфраструктура как услуга», и использования ресурсов информационно-управляющих систем реального времени (ИУС РВ) с архитектурой интегрированной модульной авионики (ИМА). В результате выполнения работ по проекту получены следующие основные результаты: * Формальная постановка задачи отображения запросов на физические ресурсы ЦОД (планирования выполнения запросов), содержащей типизацию отношений между характеристиками ресурсов и критериями SLA и позволяющей задавать для виртуальных машин политики размещения. * Формальная постановка задачи построения расписания выполнения функциональных задач в ИУС РВ (включая распределение разделов по процессорным ядрам и расписание выполнения окон) и построения систем виртуальных каналов в сети в составе ИУС РВ, ориентированной на взаимосвязанное (совместное или с обратной связью) решение этих задач. * Подходы к снижению фрагментации физических ресурсов ЦОД и сокращению вариативности производительности виртуальных машин. * Схема выполнения шагов планирования вычислений в ИУС РВ с обратной связью между шагами. * Алгоритм отображения на физические ресурсы ЦОД запросов на создание виртуальных ресурсов (алгоритм планирования запросов), который позволяет выбирать запрашиваемые характеристики виртуальных ресурсов из множества допустимых характеристик ресурсов, и учитывает заданные политики размещения виртуальных машин. * Результаты экспериментального исследования свойств разработанного алгоритма планирования запросов в ЦОД по критериям вычислительной сложности и точности, в т.ч. оценка влияния учета политик размещения виртуальных машин на загрузку физических ресурсов и на процент размещенных запросов из множества поступивших. * Алгоритмы, реализующие выполнение шагов планирования вычислений в ИУС РВ с обратной связью между шагами, а также алгоритмы, осуществляющие совместное выполнение отдельных шагов планирования. * Результаты экспериментального исследования разработанных алгоритмов планирования вычислений в ИУС РВ по критериям вычислительной сложности и точности, в т.ч. в сравнении с последовательным применением существующих алгоритмов для выполнения отдельных шагов планирования. * Прототип инструментального средства планирования распределения запросов в ЦОД (программный компонент для включения в состав облачной платформы). * Прототипы инструментальных средств для планирования вычислений в ИУС РВ, реализующих схему планирования вычислений с обратной связью между шагами планирования, а также схему совместного выполнения отдельных шагов планирования. * Результаты исследования и апробации созданных методов, алгоритмов и инструментальных средств.

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".