Проект Templet

Перевод статьи: Evaluation of a Workflow Scheduler Using Integrated Performance Modelling and Batch Queue Wait Time Prediction

Авторы: Daniel Nurmi¹, Anirbar Mandal², John Brevik¹, Chuck Koelbel², Rich Wolski¹, Ken Kennedy²

1. Computer Science Department, University of California, Santa Barbara, California
2. Computer Science Department, Rice University, Houston, Texas

Перевод: Артамонов Юрий

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

С тех пор как инструменты программирования созрели, возможность использования нескольких общих кластеров и/или суперкомпьютеров стала жизнеспособной для исполнения больших параллельных рабочих процессов. Предыдущая работа показала, что, если машины выделенны (но соединения по сети между ними нет), можно использовать модель производительности конкретного приложения(параметризованную динамически), чтобы выбрать настройки исполнения, которые оптимизируют общее время исполнения. Когда машины не являются выделенными, то они обычно находятся под управлением планировщика задач, который реализует локальную политику распределения места. Для выполнения, компоненты рабочего процесса должны быть добавлены в эти очереди, ожидая пока необходимые машины станут доступны. Если машина загружена полностью, время в очереди может сильно варьироваться и потенциально быть очень большим, во многих случаях больше самого времени исполнения.

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

В частности, в этой статье мы исследуем, как новый метод прогнозирования задержки пакетной системы может быть использован для улучшения времени исполнения широкомасштабных рабочих процессов в разделяемом Грид окружении. Наш метод использует планировщик приложений и модель производительности, чтобы определить отображение компонентов рабочего процесса на процессоры кластера, основываясь на предсказанном времени исполнения. Планировщик параметризует свою модель с предсказаниями задержки, которые генерируются динамически в момент инициализации рабочего процесса. На основе сопоставления она определяет наиболее выгодные, добавляет задачи, которые она генерирует на лету, в локальную очередь пакетной системы, контролирующую процессоры, которые задача хочет использовать. То есть, учитывая набор кластеров, управляемых пакетными системами, наша система отображает компоненты рабочего процесса на запросы добавления задач, таким образом, чтобы оптимизировать время работы рабочего процесса.

Мы исследуем эффективность этого подхода с помощью приложения Эман, VGrADS EMAN, новой функциональности предсказания задержки NWS, имея целью исследования TeraGrid, как Грид систему из кластеров. Наша цель в этом исследовании - выяснить, как моделирование производительности при помощи VGrADS и планировщика приложений может улучшить полное время исполнения, когда они комбинируются с методологией NWS для предсказания задержек пакетной системы.

Наши результаты показывают, что предсказание состояния очереди существенно снижает время работы рабочего процесса EMAN для этих настроек. Интегрируя эту функицональность в среду программирования VGrADS и системы исполнения, мы ожидаем похожих улучшений для рабочих процессов со сходными характеристиками.

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

Кнок и другие дают обзор различных эвристических методов планирования для групп DAG (или рабочих процессов) на гомогенных платформах. Эти эвристики также не могут быть напрямую применены к высоко гетерогенным высокопроизводительным системам. Топкуоглу, Си, О и другие приводят DAG планирование для гетерогенных платформ. Большинство эвристик являются обобщениями эвристик для гомогенных платформ на основе списка планирования, которые имеют несколько недостатков в гетерогенных система высокопроизводительных вычислений. Во-первых, они не учитывают глобальное влияние текущего решения по диспетчеризации. Во-вторых, они не группируют задачи для планирования и, в-третьих, гетерогенность ставит под вопрос средние значения, которые они используют для краёв и весов узлов. Мандал и Блайт описывают стратегии планирования рабочих процессов на гетерогенных распределённых Грид ресурсах с использованием моделей производительности. Но они предполагают мгновенный доступ к ресурсам, что в целом не верно для современных систем высокопроизводительных вычислений.

Второе поля для заимствований это создание точных моделей производительности, которые могут быть использованы в методе прогнозирования. Точные модели производительности компонентов используются как суррогаты фактического времени исполнения в процессе планирования рабочего процесса. Точно прогнозировать производительность параллельных и распределённых приложений - сложная задача и она широко изучена в литературе. Некоторые методы моделирования, такие как аналитический, на базе симуляции, гибридное моделировани и другие были использованы для точного прогнозирования производительности приложений на широком диапазоне архитектур. Сандарам - Стакел и Кербисон описывают подробные методы аналитического моделирования производительности для специальных типов приложений. Марин описывает полуавтоматическую стратегию моделирования статических и динамических характеристик приложений в независимом от окружения виде, используя комбинацию статического и динамического анализа двоичных файлов приложения. Фреймворк Prophesy использует исторические данные производительности, системные функции и описание приложения для создания аналитической модели компонентов приложения на различных платформах. Плана использует гибридную технику моделирования с использованием дискретного моделирования событий и математическое моделирование. Планировщик рабочих процессов может использовать любой доступный точный предсказатель производительности для ведения процесса планирования. Мы используем методы моделирования описанные Марином для выполнения этой работы.

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

В работе Брейвика, Нурми и Вольски авторы исследуют альтернативный способ прогнозирования времени ожидания, который использует только наблюдаемые раз за разом времена ожидания для того, чтобы сделать связные прогнозы по отдельным временам ожидания. В этой работе они предполагают, что часто пользователь может быть более заинтересован в верхнем и нижнем диапазонах предсказаний, вместе с мерой доверия или уверенности для времени ожидания работы, скажем, среднее (ожидаемое) время ожидания не особенно значимо для таких сильно смещённых вправо данных. Работа предоставляет инфраструктуру ПО, которая как было показано, предсказывает границы время ожидания для отдельных работ на 7 различных высокопроизводительных системах 9 лет.

В настоящей работе мы показываем, как связать планирование рабочих процессов, моделирование производительности и методы предсказания очереди задач, чтобы получить систему планирования рабочих процессов, которая сможет дать более быстрое время оборота чем при использовании этих компонентов отдельно. В следующем разделе мы кратко изложим метод моделирования производительности, метод предсказания очереди пакетной системы и, наконец, слияние этих технологий в высококачественном планировщике рабочих процессов.

В этом разделе описываются наши методологии моделирования производительности. Опишем сначала как оценить время выполнения компонента рабочего процесса на ресурсе. Мы анализируем поведение компонента приложения путём моделирования его характеристик в изоляции любых архитектурных деталей. Затем мы оцениваем затраты на исполнение компонента на целевой платформе, описываемой имеющимися аппаратными ресурсами (такими как количество и тип исполнительных модулей, размер кэша и задержки доступа к памяти). Для того, чтобы характеризовать производительность компонента на одном узле, мы принимаем во внимание количество операций с плавающей точкой и структуру доступа к памяти.

Для измерения количества вычислений, выполненных компонентом приложения для конкретного ввода программы, мы используем аппаратные счётчики производительности для сбора количества операций с плавающей точкой для нескольких запусков программы с различными небольшими входными задачами. Затем мы применяем метод наименьших квадратов для собранных данных, чтобы сделать прогноз для фактического набора данных.

Чтобы понять структуру доступа компонента к памяти мы собираем гистограммы повторного использования памяти - количество уникальных блоков памяти, доступ к которым по двум ссылкам к одному блоку - наблюдается для каждой «загрузить и записать» инструкции. Характеристика доступа к памяти для программ таким образом имеет два основных преимущества. Во-первых, расстояние повторного использования данных не зависит от конфигурации кэша или архитектурных деталей. Во-вторых, расстояние повторного использования является мерой повторного использования данных, которая является основным фактором, определяющим производительность кэша. Мы собираем информацию повторного использования для каждой ссылки в программе для нескольких небольших входных задач. Мы используем данные расстояний повторного использования памяти для моделирования поведения каждой инструкции памяти и для предсказания доли попаданий и промахов для данного размера задачи и конфигурации кэша. Наша стратегия моделирования динамически находит группы доступа, которые имеют схожие функции роста используя два полинома; один из них моделирует как количество обращений в этой группе меняется с размером задачи, а другой как среднее расстояние повторного использования этих обращений меняется с размером задачи. Для определения количества промахов кэша в задачах разного размера и конфигурации кэша, мы оцениваем гистограммы повторного использования памяти для каждой ссылки в указанном размере задачи и подсчитываем количество ссылок с расстоянием повторного использования большим, чем целевой размер кэша.

Мы используем следующую упрощённую модель для прогнозирования времени выполнения для компонентов рабочего процесса.

\begin{equation} EstExecTime(psize) = \frac{A + B + C + D}{CpuClock(arch)} \end{equation}

где:

\begin{equation} A = k_{0}\times\frac{totalFp(psize)}{FpPipelineNum(arch)}\times FpRptRt(arch)
B = k_{1}\times L1MissCnt(psize)\times L1MissPnlty(arch)
C = k_{2}\times L2MissCnt(psize)\times L2MissPnlty(arch)
D = k_{3}\times L3MissCnt(psize)\times L3MissPnlty(arch)
\end{equation}

В выражениях, k₀, k₁, k₂ и k₃ - константы, psize - размер задачи и arch - целевая архитектура. FpRptRt(arch) - скорость повторения конвейера чисел с плавающей запятой. Это количество циклов, которые произойдут между появлением одной инструкции и появлением следующей инструкции в этом же блоке исполнения. MissPnlty - штраф за промах в произвольном уровне иерархии памяти, разница между временем доступа к следующему уровню памяти и временем доступа к текущему уровню памяти.

\begin{equation} L(j)MissPnlty(arch) = P - Q
P = L(j+1)Latency(arch)
Q = L(j)Latency(arch) \end{equation}

Мы также получаем модель производительности связи для конкретного компонента рабочего процесса C конкретного ресурса R. Во-первых, мы находим множество ресурсов, которым соответствовали предшественники C. Затем мы добавляем стоимость перемещения данных от каждого из этих ресурсов в R для получения общей стоимости взаимодействия. Расходы рассчитываются в зависимости от измеренных значений задержки / пропускной способности между парами ресурсов и известного объёма взаимодействия, указанного на рёбрах рабочего процесса. Мы получаем окончательную модель производительности компонента рабочего процесса, добавив ожидаемое время выполнения к ожидаемому времени взаимодействия.

Как правило, высокопроизводительные ресурсы управляются при помощи разделяемого пространства, высокоуровневой стратегии планирования в соответствии с которой каждому приложению выделяется специальный набор ресурсов в течение всего срока его исполнения. Большинство современных систем разделяемого пространства используют стандартное ПО управления ресурсами и планирования, таких как LoadLeveler, EASY, PBS, NQS/NQE, Maui и GridEngine для управления отображением приложений на ресурсы. Поскольку обычно большему множеству задач требуется доступ к выделенным ресурсам чем имеется доступных ресурсов в каждый момент времени, эти программные системы обычно реализуют некоторую форму пакетной очереди для работ, которые готовы к выполнению как только ресурс становится доступен. Одна из проблем, которая возникает в этом окружении, - это то, что пользователь имеет смутное представление о том, как долго его работа будет ждать в очереди. Мы заметили, что работы на загруженных машинах имеют меньшее время выполнения, нежели время ожидания в очереди задач. Поскольку учёные получают доступ к нескольким суперкомпьютерам под управлением пакетных систем, мы утверждаем, что понимание относительной задержки очереди пакетной системы становится важным вопросом.

Хотя некоторая работа была сосредоточена на прогнозировании значений в точках для времени ожидания задачи в очереди пакетной системы, мы считаем, что часто более важным вопросом является определение границ ожидания одной работы в очереди. Определение точного значения практически невозможно, и даже среднее время ожидания имеет ограниченную практическую ценность, учитывая сложный и краней неравномерный характер данных о времени ожидания. В наших собственных исследованиях, мы рассмотрели данные 7 различных сайтов высокопроизводительных вычислений за более чем 9 лет. Ясно, что время ожидания работы для набора данных очень сложно для моделирования. На рисунке 1 мы видим типичный снимок очереди для высоконагруженной машины под управлением пакетной системы. Из этого графика мы видим, что существуют различные режимы, резкие изменения в режимах, периоды относительного бездействия следующие за пакетами данных.

Мы разработали метод, Биномиальный Метод Прогнозирования Очереди Пакетной Системы (БМПОПС), в котором показали как делать точные и корректные прогнозы (в очень специфичном смысле, которые будут обсуждаться ниже) для границ времени ожидания. БМПОПС решает эту задачу путём прогнозирования квантилей непосредственно из исторических данных времени ожидания. В качестве примера, БМПОПС способен определить наибольшее время, которое конкретная задача будет «вероятно» ожидать в определённой очереди, в том смысле, что есть, скажем, 75% вероятность того, что работа начнётся раньше. БМПОПС решает проблему нахождения верхней границы 0.75 квантиля случаной величины возможного времени ожидания для конкретной работы, используя исторический след времени ожидания работ находящихся в очереди. Обратите внимание, что отдельный вопрос в том, какой уровень доверия определяет верхнюю границу, по крайней мере столь же большую, как 0.75 квантиль. БМПОПС обычно использует уровень доверия 95%. Однако, оба численных значения (квантиль интереса и уровень доверенности) могут регулироваться пользователем, например, мы можем одинаково хорошо запустить БМПОПС для квантиля 0.5 или медианы с 90% уверенностью. Другими словами, БМПОПС позволяет пользователю ответить на вопрос: «Как долго моя работа вероятнее всего будет ждать в очереди?», где «вероятнее всего» может интерпретироваться пользователем через квантили (и при желании через уровень доверия).

Квантильные прогнозы границы, сделанные БМПОПС основаны на следующем простом наблюдении: Если X является случайной величиной и X_q - квантиль q распределения X, то единичное наблюдение x из X будет больше чем X_q с вероятностью (1 - q). Так (при возможных предположениях о независимости и одинаковом распределении) последовательность независимых испытаний Бернулли с вероятностью успеха, равной Q, где наблюдение рассматривается как успех, если оно меньше чем X_q. Если имеется n наблюдений, вероятность точно k успехов описывается биномиальным распределением с параметрами q и n. Таким образом, вероятность того, что k или меньше наблюдений больше X_q равна:

\begin{equation} \sum\limits_{j=0}^k\left( \begin{array}{c} n
j \end{array} \right)\cdot q^{n-j}\cdot (1 - q)^{j} \end{equation}

Используя этот базовый метод, мы можем найти наименьшее значение k, при котором уравнение 4.1 больше некоторого заданного уровня доверия, а значение k в отсортированном наборе наблюдений (достаточного размера) будет больше или равно квантилю X_q распределения, из которого проводились наблюдения с указанным уровнем достоверности.

На практике БМПОПС реализован в виде симуляции на базе трассировки, на основе исторических данных задач, указанных пользователем квантиле и уровне доверия. После короткого периода подготовки имитационная модель проходит по историческим данным, пока не достигнет настоящего времени. Во время моделирования мы используем простой метод обнаружения точек изменения, который используется для эффективного уменьшения учитываемых исторических данных, что позволяет использовать только историюЮ которая имеет отношение к текущим условиям времени ожидания. Кроме того, мы используем метод группировки задач на базе количества узлов, которое они запрашивают, который даёт эффект сходящегося предсказания, сделанного для конкретной задачи на основе только истории задач с похожим размером. В точке, где симулятор обработал все задачи вполть до настоящего времени, мы можем задать вопрос о работе с указанными требованиями узлов, для последнего квантиля предсказания с указанным уровнем доверия. Симулятор показал корректноый захват квантилей интереса почти для всех трасс работ, к которым у нас есть доступ. В нашем предыдущем эксперименте, прогнозы квантилей были успешными для 51 из 55 трасс.