ИССЛЕДОВАНИЕ МЕТОДОВ ОЦЕНКИ ЭФФЕКТИВНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ ФУНКЦИОНАЛЬНЫХ МОДЕЛЕЙ

Полный текст

Введение. Эффективность вычислительной системы определяет степень соответствия системы своему назначению. Она измеряется либо количеством затрат, необходимых для получения определенного результата, либо результатом, полученным при определенных затратах. Функциональная модель вычислительной системы, максимально приближенная по своим свойствам к реальной вычислительной системе, может дать представление об эффективности её работы. Понятие функциональной модели. Функциональная модель вычислительной системы представ-ляет собой программу, состоящую в общем случае из описания алгоритмов распределения задач, описания вычислительной инфраструктуры (серверов, каналов связи, вычислительных узлов), анализатора исходных данных и инструментов представления результатов её исполнения. Запуск такой модели может происходить как на персональном компьютере, так и на оборудовании, аппаратно приближенном к реальному вычислительному комплексу. В общем случае функциональная модель вычислительной системы, а также алгоритмы распределения заданий в этой системе описываются с помощью одного из современных языков программирования - С, C#, Java, Python и др. [1]. Кроме того, в системах моделирования активно применяется декларативное описание свойств вычислительной инфраструктуры в рамках модели с помощью языков разметки XML и YAML. Далее приведен пример описания кластерной вычислительной системы с помощью XML в системе моделирования SimGrid [2]: <?xml version='1.0'?> <!DOCTYPE platform SYSTEM "http://simgrid. gforge.inria.fr/simgrid.dtd"> <platform version="3"> <AS id="sfu" routing="Full"> <cluster id="big-cluster" prefix=" node-" suffix=".ikit.sfu-kras.ru radical="0-279" power=" 16.2e12" bw="25e8" lat="2.4e-5" sharing_policy= "FULLDUPLEX"/> </AS> </platform> Таким образом описывается количество и связность вычислительных узлов в кластерной системе, задаются их характеристики. Вычислительная мощность системы описывается с помощью атрибута power тега cluster; пропускная способность каналов связи между ними - с помощью атрибутов bw (bandwidth), sharing_policy; среднее время отклика узлов - с помощью атрибута latency. Также существует возможность описания каждого вычислительного узла системы по отдельности [3]. Данное описание вычислительной инфраструктуры используется планировщиком заданий для распределения задач внутри модели вычислительной системы. Подготовка исходных данных и процесс моделирования. Важным этапом в построении модели вычислительной системы является получение и подготовка исходных данных. Существует стандарт представления исходных данных, разработанный группой лабораторий Grid Consorcium [4]. Этот стандарт регламентирует формат данных о запуске ресурсоемких заданий, пригодный для использования в качестве исходных данных при моделировании вычислительных систем. Формат предусматривает наличие таких данных, как идентификатор (название) задачи, дата и время начала её исполнения, дата и время окончания её исполнения, узел или узлы, на которых производилось её исполнение, запрошенные задачей аппаратные и программные ресурсы. Соответственно, планировщик заданий в функциональной модели вычислительной системы учитывает эти требования и производит распределение задачи на вычислительный узел согласно описанному алгоритму. На рис. 1 приведена общая схема функциональной модели вычислительной системы. Для наиболее точного исследования и оценки эффективности работы модели вычислительной системы в качестве исходных данных можно использовать журналы запуска реальных задач, сгенерированные с помощью менеджера ресурсов при условии приведения этих данных в вышеописанный стандартный формат. Самым важным этапом моделирования вычислительной системы является описание алгоритмов распределения заданий. В общем случае алгоритм представляет собой функцию или метод, с помощью набора определенных инструментов реализующий общий принцип распределения заданий. Приведем пример реализации алгоритма Round Robin в системе моделирования SimGrid: for (i = 0; i < number_of_tasks; i++) { // Отправка задания агенту. При отправке указывается название (идентификатор) задачи, // а также требования к аппаратному обеспечению - требуемое процессорное время // (comp_amount) и требуемый объем передаваемых данных (comm_amount) sprintf(mailbox,"worker-%d", i % workers_count); XBT_INFO("Sending \"%s\" (comp. size: %f, comm. size: %f) to mailbox \"%s\"", tasks_info[i].task->name, tasks_info[i].comp_amount, tasks_info[i].comm_amount, mailbox ); MSG_task_send(tasks_info[i].task, mailbox); } Подобным образом возможно реализовать практически любой алгоритм распределения заданий и использовать его для проверки эффективности в рамках той или иной модели вычислительной системы. К сожалению, универсальных алгоритмов распределения заданий, одинаково хорошо проявляющих себя при расчетах всех типов проблемно ориентированных заданий, не существует. В этом случае целесообразно сочетать различные алгоритмы распределения, а также исходить из специфичных требований и свойств подобных задач [5]. Работа систем, имеющих в своем составе специализированное аппаратное обеспечение, например вычислительные узлы, оснащенные GPU, моделируется аналогичным образом с поправками на то, что для успешного выполнения задачи на узле также должно быть установлено определенное программное обеспечение. В частности, узлы, оснащенными GPU Nvidia, должны быть оснащены программным обеспечением CUDA Library, представляющим собой набор библиотек и расширений для языков программирования C/C++, Fortran и др [6]. Эти свойства могут быть описаны также декларативно. Критерии эффективности вычислительных систем. Для того, чтобы оценить эффективность функциональной модели вычислительной системы, необходимо разработать адекватную методику оценки результатов её работы. Она должна выражаться в выявлении определенных количественных и качественных критериев оценки эффективности исполнения различного рода заданий в рамках используемой функциональной модели. Критерий эффективности - это правило, служащее для сравнительной оценки качества вариантов вычислительных системы. Строятся критерии эффективности на основе частных характеристик эффективности (показателей качества) [7]. Это могут быть следующие характеристики [8]: 1. Общая производительность смоделированной вычислительной системы. 2. Время выполнения одного и того же набора заданий относительно различных алгоритмов распределения. 3. Уровень утилизации (использования) вычислительной инфраструктуры на протяжении всего времени исследования. 4. Отношение задействованных и простаивающих вычислительных узлов. 5. Отношение выполняющихся и ожидающих заданий. Современные системы моделирования вычислительных систем позволяют достаточно точно оценить все вышеназванные характеристики как с помощью журналов (логов), содержащих подобную информацию, так и с помощью средств графического представления выходных данных. В данном исследовании рассматриваются прежде всего вычислительные системы общего назначения и способы оценки производительности именно таких вычислительных систем. Оценка производительности вычислительной системы. Производительность вычислительной системы общего назначения тесно связана с продолжительностью процессов обработки задач. Основным инструментом оценки времени обработки задач в рамках модели вычислительной системы являются средства представления выходных данных в выбранной системе моделирования. В частности, система моделирования SimGrid предоставляет как текстовый, так и графический вариант представления результатов исследования. Графический вариант может быть представлен в виде диаграммы Гантта или в виде плоского графика. Рис. 1. Общая схема функциональной модели вычислительной системы Применение модели вычислительной системы позволяет производить измерения при использовании различных алгоритмов распределения заданий и конфигураций вычислительной инфраструктуры без значительных временных и трудозатрат. В рамках данного исследования проводились эксперименты по запуску реального набора заданий, ранее запущенных на исполнение в высокопроизводительной вычислительной системе Сибирского федерального университета. В результате, в исходное множество заданий вошло 2334 задания, каждое из которых требовало для выполнения различное количество процессорного времени и оперативной памяти. Для проведения экспериментов использовалось как полное множество заданий, так и случайным образом взятые «срезы» этого множества. Также были описаны различные алгоритмы распределения заданий: SJF (Shortest Job First), LJF (Longest Job First), RR (Round-Robin), FCFS (First Come First Serve). Кроме того, эти алгоритмы исследовались в условиях совместной работы с алгоритмами Backfilling и Fairshare. Далее приведем пример описания алгоритма SJF в системе SimGrid: for (j=1; j<number_of_tasks; j++) for (i=0; i<number_of_tasks-j; i++) if (tasks_info[i].comp_amount > tasks_info[i+1].comp_amount) { // Задачи сортируются в порядке возрастания требуемого процессорного // времени. task_info_buff=tasks_info[i]; tasks_info[i]=tasks_info[i+1]; tasks_info[i+1]=task_info_buff; } Массив task_info здесь содержит список запускаемых в системе заданий со всей необходимой для симулятора информацией о запрашиваемых задачей ресурсах. Подобным образом описаны и другие алгоритмы: LJF, RR, Priority Based и др. В результате было получены данные о времени исполнения заданий в рамках модели вычислительной системы. В табл. 1 представлены данные, полученные в результате исследования алгоритмов SJF и RR. Измерение уровня утилизации ресурсов функциональной модели вычислительной системы. Высокая степень утилизации (использования) вычислительных ресурсов означает их эффективное использование. Она достигается, прежде всего, эффективным распределением задач за счет правильно подобранных алгоритмов распределения [9]. Значительное влияние на уровень утилизации ресурсов может оказать применение алгоритмов, использующих технологию Backfilling. В рамках данного исследования это было экспериментально доказано в процессе анализа выходных данных, полученных после обработки исходного множества заданий с использованием системы моделирования Alea [10]. Эксперименты проводились с помощью вышеописанной функциональной модели вычислительной системы. В случае применения технологии Backfilling процесс расчета заданий закончился значительно раньше. Произошло это за счет эффективного динамического перераспределения заданий в очередях. Наиболее эффективно данная технология проявляет себя в тех вычислительных системах, нагрузка на которые неравномерна: в определенные моменты такие вычислительные системы испытывают пиковые нагрузки, а в другие - простаивают. Измерение отношения простаивающих и задействованных вычислительных узлов. В гетерогенных вычислительных системах, содержащих вычислительные ресурсы различной аппаратной и программной конфигурации, при обработке пула проблемно ориентированных заданий приходится часто сталкиваться с проблемой отсутствия на узлах того или иного необходимого программного обеспечения или требуемых аппаратных ресурсов [11]. Ввиду этого узел не имеет возможности принять задачу на выполнение и при отсутствии иных подходящих задач простаивает. Это неизбежно отрицательно сказывается на общем уровне утилизации ресурсов вычислительной системы и означает неэффективное её использование [12]. Таблица 1 Сравнение результатов работы функциональной модели вычислительной системы на базе алгоритмов распределения SJF и RR Число задач Время исполнения, с (Shortest Job First) Время исполнения, с (Round-Robin) 200 6,37976e+07 6,37976e+07 400 1,39462e+08 2,03258e+08 600 1,39539e+08 2,03496e+08 800 1,3963e+08 2,73934e+08 1000 1,39797e+08 2,96567e+08 1200 1,40139e+08 3,20913e+08 1400 1,40695e+08 3,43273e+08 1600 1,41422e+08 3,76413e+08 1800 1,41827e+08 3,77149e+08 2000 1,42527e+08 4,31322e+08 Для того чтобы избегать подобных проблем, применяются менеджеры ресурсов, информирующие брокера (планировщика) задач о наличии тех или иных программных и аппаратных ресурсов на вычислительном узле. Чаще всего применяется агентный подход к построению таких систем - устанавливается некий управляющий сервер, который соединяется с агентами-демонами, работающими на вычислительных узлах. Таким образом, управляющий сервер собирает данные о доступности узлов для выполнения определенной задачи [13]. Как уже было сказано ранее, в системах моделирования активно применяется декларативный подход к описанию вычислительной инфраструктуры, доступной для использования в рамках модели, который позволяет также описать наличие тех или иных свойств у вычислительных узлов, в том числе задать программную и аппаратную конфигурацию узлов. Эти данные, в свою очередь, могут быть учтены при описании алгоритмов распределения. В данном случае для анализа целесообразно применять средства визуального представления результатов эксперимента. Измерение отношения выполняющихся и ожидающих заданий. При проведении ресурсоемких расчетов неизбежна ситуация, при которой возникают очереди ожидающих ресурсов, заданий. Происходит это ввиду отсутствия в конкретный момент времени необходимых для запуска задания аппаратных или программных ресурсов на вычислительных узлах. Увеличение процента ожидающих заданий по отношению к выполняющимся приводит к возрастанию времени расчета и, как следствие, уменьшает уровень утилизации [14]. Снизить количество ожидающих заданий можно различными способами: 1. Приведение вычислительных узлов к предельно близкой программной и аппаратной конфигурации. 2. Использование технологии динамического измене-ния приоритетов исполнения заданий - Backfilling. Оценить отношение количества выполняющихся к числу ожидающих заданий можно в процессе анализа выходных данных эксперимента в системе моделирования. В табл. 2 показано число ожидающих задач при использовании алгоритмов Aggressie Backfilling и FCFS в период пиковой нагрузки (взят отрезок в 10 дней). Для того чтобы оценить эффективность использования того или иного алгоритма распределения заданий, найдем коэффициент корреляции между соответствующими величинами количества ожидающих заданий. Коэффициент корреляции R может принимать значения от -1 до +1. Если абсолютное значение находится ближе к 1, то это свидетельство сильной связи между величинами, а если ближе к 0, то это говорит о слабой связи или ее отсутствии. Воспользуемся следующими формулами: Так как абсолютное значение коэффициента корреляции близко к 1, между величинами существует достаточно сильная линейная связь. Примем количество ожидающих заданий за y, а порядковый номер дня за x. Рассчитав коэффициент уравнения регрессии в случае применения алгоритмов FCFS, получим значение -4,67. Коэффициент регрессии b = -4,67 показывает среднее изменение результативного показателя (в единицах измерения у) с повышением или понижением величины фактора х на единицу его измерения. В данном случае с увеличением x на 1 единицу y понижается в среднем на -4,67, а уравнение регрессии принимает вид y = -4,67x + 285,4. Проведя аналогичные расчеты для алгоритма Aggressive Backfilling, получим коэффициент регрессии b = -12,86, а уравнение регрессии примет вид y = -12,86x + 180,13. На рис. 2 показана зависимость количества ожидающих задач от времени в указанном временном отрезке. Количество заданий при использовании алгоритма FCFS показано с помощью линии 1, при использовании Agressive Backfilling - с помощью линии 2. Таблица 2 Количество ожидающих задач при применении алгоритмов FCFS и Aggressive Backfilling в период пиковой нагрузки День Количество ожидающих задач (FCFS) Количество ожидающих задач (Backfilling) 1 282 171 2 277 162 3 273 141 4 267 126 5 260 111 6 254 96 7 250 84 8 247 73 9 245 69 10 242 61 Рис. 2. Зависимость числа ожидающих заданий от времени Таким образом, при использовании технологии Backfilling число ожидающих заданий в период пиковой нагрузки снижалось почти в 3 раза быстрее, чем при использовании обычного алгоритма распределения FCFS. Это связано с тем, что при наличии свободных вычислительных ресурсов динамически изменялись приоритеты исполнения заданий [15]. Полученные результаты позволяют рекомендовать использование алгоритмов с применением технологии Backfilling. Заключение. В статье приведены способы описания функциональных моделей вычислительных систем, примеры декларативного описания свойств вычислительных узлов, показаны способы оценки эффективности работы вычислительных систем по следующим критериям: общая производительность смоделированной вычислительной системы, время выполнения одного и того же набора заданий относительно различных алгоритмов распределения, уровень утилизации вычислительной инфраструктуры на протяжении всего времени исследования, отношение задействованных и простаивающих вычислительных узлов, отношение выполняющихся и ожидающих заданий. Полученные результаты позволяют судить о высокой эффективности алгоритмов распределения заданий, использующих технологию динамического изменения приоритетов исполнения Backfilling. Благодарности. Работа выполнена в рамках проекта «Геномные исследования основных бореальных лесообразующих хвойных видов и их наиболее опасных патогенов в Российской Федерации» (договор № 14.Y26.31.0004).

Об авторах

Д. Ю. Астриков

Сибирский федеральный университет

Email: astrikov.d@gmail.com
Российская Федерация, 660041, г. Красноярск, просп. Свободный, 79

Д. А. Кузьмин

Сибирский федеральный университет

Российская Федерация, 660041, г. Красноярск, просп. Свободный, 79

Список литературы

Дополнительные файлы