Проект Templet

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

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

Авторы: Daniel Nurmi<sup>1</sup>, Anirbar Mandal<sup>2</sup>, John Brevik<sup>1</sup>, Chuck Koelbel<sup>2</sup>, Rich Wolski<sup>1</sup>, Ken Kennedy<sup>2</sup>

  - Computer Science Department, University of California, Santa Barbara, California
  - 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<sub>0</sub>, k<sub>1</sub>, k<sub>2</sub> и k<sub>3</sub> - константы, //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 мы видим типичный снимок очереди для высоконагруженной машины под управлением пакетной системы. Из этого графика мы видим, что существуют различные режимы, резкие изменения в режимах, периоды относительного бездействия следующие за пакетами данных.

{{ :translate:queue-load.png |}}

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

=== Биномиальный метод прогноза для очереди пакетной системы ===

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

\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//<sub>q</sub> распределения, из которого проводились наблюдения с указанным уровнем достоверности.

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

В этой работе мы интегрируем наш БПМОПС в модель производительности улучшенного планировщика рабочих процессов, который является темой следующего раздела.
==== Архитектура планировщика ====

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

Оригинальный алгоритм планирования рабочих процессов использует 3 эвристики (min-min, max-min и голосование) и работает следующим образом. Для каждого правила, пока все компоненты рабочего процесса не отображены на ресурсы, текущий набор компонентов идентифицируется. Затем вычисляется ранг матрицы для набора доступных компонент. Запись (//i//,//j//) в ранге матрицы кодирует ожидаемую вычислительную производительность и производительность взаимодействия компонента приложения //i// на ресурсе //j// (полученного с использованием методов моделирования производительности описанных в секции 3). Тогда, расчётное время выполнения компонента //i// на ресурсе //j// (//ECT//(//i//,//j//)) получается путём добавления ранга матрицы к максимуму из двух значений - (1) ожидаемого времени доступности ресурса и (2) максимального ожидаемого времени выполнения среди родителей компонента //i//. Используя значения //ECT//, текущая эвристика планирования выполняется для получения отображения для текущего набора доступных компонентов. Это повторяется, пока весь рабочий процесс не будет отображён на ресурсы. В результате, отображения и длительности для каждого компонента становятся известны. Наконец, планировщик выбирает отображение (план), который даёт минимальную длительность среди трёх эвристик.

Мы изменили исходный алгоритм планирования рабочих процессов чтобы включить время ожидания в очередях пакетных систем. Изначально для каждого правила расчётное время наличия каждого ресурса заполняется с использованием предсказанного времени ожидания ресурса. Мы используем 95% верхней границы для предсказания среднего времени ожидания в очереди. Таким образом, в процессе планирования, расчётное время завершения для компонента учитывает время ожидания в очереди (//ECT// - функция ожидаемого времени доступности, ранг и максимальный //ECT// родительских компонентов). Мы отслеживаем время ожидания в очереди для каждого кластера и количество узлов, которые соответствуют каждому времени ожидания. С каждым новым отображением на ресурс //j// мы обновляем значения //ECT// указанного количества узлов кластера (ресурса //j//) с предполагаемым временем ожидания. Компоненту не нужно ждать ресурс, если другие компоненты уже были отображены на ресурс (предыдущий сбор ресурсов подразумевают, что время ожидания уже учтено). Мы запускаем эвристики, используя изменённые значения //ECT// для получения трёх отображений. Мы выбираем отображение(план) с минимальной длительностью как окончательное.
==== Эксперимент ====

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

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

Второй эксперимент пытается проверить результаты предыдущего на практике, воспроизводя те же условия, что и раньше, за исключением того, что мы используем реалистичные данные //EMAN//, для значительно более длительной работы. Для этого эксперимента мы запускали несколько экземпляров реальных задач //EMAN//, использующих БМПОПС и не использующих БМПОПС.

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

=== Тестовое окружение ===

Для этой работы мы решили использовать пять суперкомпьютеров, три из которых являются частью основного проекта TeraGrid [NSF], в пяти различных местах по всей стране. Первым из них является Rice Terascale Cluster из 119 узлов Intel Itanium расположенным в университете Хьюстона, Техас. Второй представляет собой кластер из 128 узлов Intel XEON расположенный в университете Калифорнии, Санта-Барбара. Наконец, мы используем машины SDSC, NCSA и UC/ANL Teragrid, которые состоят из 262, 887 и 62 процессоров Intel Itanium и расположены в Сан-Диего, провинции Урбане и Чикаго соответственно. Все эти системы в настоящее время находятся под управлением пакетных систем, описанных в разделе 4 и имеют предварительно рассчитанные модели производительности для индивидуальных ресурсов. Кроме того, все эти системы используют некоторую комбинацию Maui и PBS для планирования и управления ресурсами.

=== Приложение ===

Мы использовали приложение EMAN как тестовый образец рабочего процесса. EMAN (электронный анализ микрографии) - является приложением биологических изображений разработанным в Медицинском Колледже Baylor. В первую очередь оно работает с 3D реконструкциями отдельных частиц из электронной микрографии. Опыт человека необходим для построения предварительной 3D модели из зашумлённых электронных микрографий. Из шагов рабочего процесса приложения EMAN, уточнение от предварительной 3D модели до конечной 3D модели является вычислительно-сложным шагом, который наиболее выигрывает от использования силы высокопроизводительных вычислений. Уточнение EMAN может быть представлено как рабочий процесс, изображённый на рисунке 2. По существу, это линейныый рабочий процесс с некоторыми последовательными и параллельными этапами. Важными и трудоёмкими шагами являются крупные шаги, такие как "classesbymra". Мы используем два рабочих процесса EMAN, имеющих по существу одну структуру - (1) обычную, соответствующую "rdv" данным и (2) уменьшенную на один, соответствующую данным "GroEL".

=== Проведение эксперимента ===

Два наших эксперимента похожи, отличаясь в основном в размере приложения EMAN, которое мы выполняем (уменьшенное или обычное) и в выборе планировщика рабочих процессов (БМПОПС или без БМПОПС).

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

В этом разделе мы будем изучать результаты нашего эксперимента и покажем как сравнить расширенные при помощи БМПОПС планировщики рабочих процессов с планировщиками только на базе моделей производительности.

Рисунок 4 показывает результат нашего первого эксперимента, который сравнивает длительности малого EMAN использующего и планировщик на базе БМПОПС и планировщик без информации о времени ожидания в очереди пакетных систем. Как видно из графика, хотя есть определённые случаи, когда план с БМПОПС затрачивает больше времени, чем план без БМПОПС, большинство экспериментов показывают, что использование БМПОПС значительно снижает количество времени от начала рабочего процесса до конца. Из 27 пар измерений, план на базе БМПОПС предоставил более короткую длительность 26 раз. Средняя длительность плана с БМПОПС составила 262 секунды, в то время как средний показатель длительности планов без БМПОПС составил 895 секунд, разница в 633 секунд (около 10,5 минут). Для большинства испытаний, планировщики с БМПОПС предоставили планы с наблюдаемым временем выполнения, которое примерно в 3 раза быстрее, чем планировщики без БМПОПС, что является существенным улучшением производительности с той лишь разницей, что мы принимаем во внимание время задержки в очереди пакетной системы при расчёте длительности или модель производительности по отдельности.

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

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

Учитывая большое количество экспериментального и выделенного времени, мы ожидаем в конце концов, что мы сможем завершить некоторые не-БМПОПС планировщики, но этот результат является в некотором смысле более ценным в краткосрочной перспективе. Мы наблюдаем тот факт, что в условиях, когда одно приложение пытается использовать сильно распределённые ресурсы, есть одна большая проблема в том, что ресурсы могут отказывать в любой момент. Одним из возможных решений, что, безусловно, помогает уменьшить взаимодействие, является исполнение частей приложения, которые требуют сильно распределённых ресурсов, так быстро как только возможно, чтобы избежать потенциальные отказы отдельных компонентов. Поскольку наш планировщик БМПОПС мог планировать задачи на этих ресурсах таким образом, чтобы в результате относительно коротких планов, в течение половины дня, они были в состоянии эффективно избежать простоев, которые затронули планировщики без БМПОПС, для которых части приложения были поставлены в очередь после 1.5 и 2х дней.
==== Заключение ====

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

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

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