Проект Templet

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

Перевод статьи: Identifying Quick Starters: Towards an Integrated Framework for Efficient Predictions of Queue Waiting Times of Batch Parallel Jobs

Авторы: Rajath Kumar and Sathish Vadhiyar Supercomputer Education and Research Center, Indian Institute of Science, Bangalore, India rajath@ssl.serc.iisc.in,vss@serc.iisc.in 

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

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

**Ключевые слова**: время ожидания очереди, высокопроизводительные вычисления, пакетные системы, предсказание, планирование.

==== Введение ====

Параллельные системы многих суперкомпьютеров являются пакетными системами, которые обеспечивают совместное использование общих доступных процессоров среди множества параллельных приложений и задач. Хорошо известные системы планирования, включая IBM Loadleveler, PBS, Platform LSF и Maui Scheduler, используются в суперкомпьютерах для управления задачами в пакетных системах. Эти фреймворки используют пакетные системы, в которых задачи, добавленные в пакетную систему, ставятся в очередь до выделения ресурсов планировщиком из набора доступных для исполнения процессоров. Таким образом, в дополнение ко времени, необходимому для исполнения, задача, добавленная в пакетную систему затрачивает время на ожидание ресурсов из набора процессоров для исполнения.

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

Анализы выполнения задач, широко используемых на суперкомпьютерах, выявляют наличие большого числа задач с коротким временем ожидания в очереди. Таблица 1 показывает статистику для 8 различных трассировок исполнения задач, которые мы используем в этой работе. Все восемь трассировок выбраны из архива нагрузки Feitelson. Последняя колонка таблицы показывает процент работ со временем ожидания меньшим или равным 1 часа. Мы считаем, что большиство задач, в частности 56-99% от общего числа задач, добавленных в систему ожидают в очереди не более 1 часа. Мы называем эти задачи быстро стартующими. Правильная идентификация и хорошее предсказание этих быстро стартующих, которые составляют большинство, необходимы для общего точного прогнозирования.

Важно отметить, что эти быстрые запуски не обязательно соответствуют тестированию/отладке задач, которые связаны с коротким временем исполнения, и чьи прогнозы имеют намного меньшее значение. Многие системы имеют отдельные очереди для отладки и тестирования задач. Наши эксперименты проводились на общей очереди, в которой исполняются расчётные задачи, и где предсказание времени ожидания требуется. Значительное число быстрых запусков в этих расчётных очередях имеют высокое время исполнения. Например, в очередях CTC и ANL около 30% быстро стартующих имеют время исполнения большее 1 часа и некоторые из них имеют время исполнения до 120 часов. Прогнозирование времени ожидания является сложной задачей из-за различных факторов, в том числе различных алгоритмов планирования, следующих за фреймворками планирования работ, изменяющихся во времени политик, применяемых к одной очереди и приоритетов работ. Высокие значения прогнозов будут иметь более сильное воздействие на предсказания быстрого старта, чем работы с длительным временем исполнения. Высокое завышенное планируемое время для быстро стартующих может иметь пагубное влияние даже для работ, добавляемых в систему. Например, верхняя граница в 8 часов для задачи, которая исполняется в течение 15 минут, и чьё фактическое время ожидания составит 30 минут, может показать пользователю, что не стоит отправлять задание в систему, чем если бы пользователь решил, что окружение подходит для запуска без этого завышения. Поэтому очень важно, чтобы верхние границы были точными, особенно для быстро стартующих задач. В нашей работе мы зафиксировали эту верхнюю границу как 1 час для всех быстро запускаемых задач. Предполагается, что, даже если фактическое время ожидания быстрого запуска находиться в пределах 5 минут, эта верхняя граница в 1 час не представляет проблемы для пользователя, так как пользователь, как правило, ожидает как минимум от нескольких минут до часа в многопользовательской системе.

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

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

В этой работе мы разработали интегрированный фреймворк PQStar, для идетификации и прогнозирования быстрых запусков. Важный аспект нашей стратегии предсказания быстрых запусков в том, что он считает состояние занятости процессоров и состояние очереди во время добавления задач в дополнение к характеристикам задач, включая запрашиваемое количество процессоров и планируемое время исполнения. Состояние процессоров и очереди включает текущее количество свободных узлов, количество задач с большими запросами, исполняющихся в системе, и относительную разницу между текущей задачей и другими задачами в очереди в терминах размера запросов и планируемого времени исполнения. Эти состояния получаются с помощью имитатора, который обновляет состояния по мере поступления и завершения задач. Для задач, распознаваемых как задачи с потенциально долгим временем ожидания, мы используем существующие стратегии предсказания. Наши эксперименты с различными промышленными суперкомпьютерами и трассировками задач, приведённых в таблице 1, показывают, что наши стратегии прогнозирования могут привести к правильной идентификации до 20 раз больше быстрых запусков и обеспечить на 64% более точное прогнозирование, чем существующие методы. Наша модель была разработана, чтобы не использовать динамические и переменные параметры, включая алгоритмы планирования и приоритеты работы. Во многих случаях это не практично, получать / выводить приоритеты задач и алгоритм планирования. Алгоритмы планирования пакетных систем, как правило, не публикуются, и их не так легко смоделировать. Наша модель в основном использует трассировки работы и состояния при добавлении задач (очередь и занятые процессоры). Таким образом, наша система может быть универсально применена к различным пакетным системам с различным планированием и политикой приоритетов.

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

==== Связанные работы ====

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

В работах Смита предсказания времени выполнения получены с использованием аналогичных опытов в истории, и эти оценки в дальнейшем используются для имитации алгоритма планирования, таких как FCFS, LWF (меньшая работа - первая) и алгоритм обратного заполнения, для получения предсказаний времени ожидания очереди. Другая работа Ли пытается улучшить прогноз выполнения и имитации пакетной системы для планировщика Maui. Эти подходы рассматривают конкретные алгоритмы планирования для предсказания, в то время как наш подход рассматривает только трассировку задач и, следовательно, может работать с несколькими алгоритмами планирования. Более того, их подходы используют оценки времени выполнения для предсказания времени ожидания. Оценки времени исполнения, полученные при таком подходе, имеют большую ошибку в от 33% до 74% случаев, и, следовательно, по этим расчётам будут получены большие ошибки в прогнозе времени ожидания.

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

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

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

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

=== Прогноз с использованием ближайшей истории ===

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

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

=== Прогноз с использованием среднесрочной истории ===

Для задач, для которых ближайшая история не может использована в связи с неудовлетворением упомянутому выше критерию, PQStar обходит задачи в обратном хронологическом порядке добавления задач от ближайшей границы, пока состояние занятости процессоров не станет полностью другим с точки зрения выполнения задач. Другими словами, предположим A = {множество задач, исполняемых во время добавления целевой задачи} и B = {множество задач, исполняемых во время добавления задачи в истории}, то мы проводим границу среднесрочной истории в точке, где A ∪ B = ∅. 

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

**Критерий размера запроса.** Один полезный критерий мы нашли для ранжирвания целевых задач с точки зрения их размера запроса среди задач в очереди ожидания во время добавления задачи. В частности, мы рассчитываем jobrank<sub>reqsize</sub>, используя позицию целевой задачи в списке задач в очереди в момент времени при сортировке задач по возрастанию размера запроса. jobrank<sub>reqsize</sub> рассчитывается путём нормализации этой позиции по отношению к общему числу задач в очереди.

Большинство существующих стратегий группируют задачи только с точки зрения размеров запроса, и поиск задач с похожим размером запроса для предсказания времени ожидания в очереди. Однако, один размер запроса может соответствовать широкому диапазону времени ожидания как показано на графике 1(a), который показывает статистику для 1000 экземпляров задач с трассировкой CTC. Например, соотвествующий размер запроса 8 процессоров на графике, мы видим, что время ожидания очереди может варьироваться с 1 минуты до 32 часов. Таким образом, в дополнение к поиску схожих с целевой задач  с точки зрения размера запросов, мы рассматриваем ранг задачи в очереди с точки зрения размеров запроса, тем самым неявно учитывая и размер запроса и состояние очереди для предсказания. Мы учитываем целевые задачи со значениями jobrank<sub>reqsize</sub> меньшими, чем порог threshold<sub>reqsize</sub>, мы рассматриваем задачи в ближайшей истории, находим два порога: threshold<sub>reqsize1</sub> как максимум значений jobrank<sub>reqsize</sub> задач со временем ожидания в очереди меньшим или равным 1 часа и threshold<sub>reqsize2</sub> как минимум значений jobrank<sub>reqsize</sub> задач со временем ожидания в очереди большим чем 1 час и используем минимум этих порогов как threshold<sub>reqsize</sub>. Используя краткосрочную историю, чтобы найти пороги, PQStar использует самую последнюю историю и, следовательно, также принимает во внимание только те задачи, что имеют похожие состояния занятости процессоров.

**Критерий ERT.** Подобно критерию размера запроса, мы также используем примерное время запуска (ERT) для идетификации целевой задачи как быстрого запуска. В частности, PQStar находит метрику jobrank<sub>ert</sub>, используя список задач в очереди на момент поступления целевой задачи, отсортированные в порядке возрастания расчётного времени запуска, и находя нормализованную позицию целевой задачи в списке по отношению к общему числу задач в очереди. PQStar помечает целевую задачу как быстрый запуск если её jobrank<sub>ert</sub> меньше чем порог threshold<sub>ert</sub>. threshold<sub>ert</sub> находится аналогично threshold<sub>reqsize</sub> с помощью времени ожидания задач в ближайшей истории. График 1(b) учитывает только ERT и их влияние на время ожидания в очереди. Подобно рассмотрению только резмера запроса, мы находим, что один ERT может соответствовать широкому диапазону времени ожидания. Таким образом, существующие стратегии, использующие только ERT для нахождения похожих задач могут дать высокие верхние границы предсказаний. Рассматривая jobrank<sub>ert</sub>, PQStar определяет сходство используя характеристики и задачи и состояния очереди. Предположением о размере запроса и ERT является то, что целевая задача с малым размером запроса и ERT относительно других задач в очереди имеет более высокие шансы на заполнение ресурсов и, следовательно, может быть быстро запущена.

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

Для предсказаний в среднесрочной истории PQStar помечает задачу как быстрый запуск, если она удовлетворяет одному из трёх критериев, а именно: размеру запроса, ERT или критерию свободных узлов.

=== Предсказания с помощью дальней истории ===

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

=== Общие прогнозы и использование IBL ===

Таким образом, PQStar пытается найти аналогичную задачу в ближайшей, средней и дальней истории и использует набор критериев для того, чтобы пометить задачу как быстрый запуск. В дополнение к рассмотрению только характеристик задачи: размера запроса и планируемого времени исполнения, PQStar явно или неявно учитывает состояние системы, а именно: состояние занятости процессоров и состояние очереди, для определения схожести и получения предсказания. В наших исследованиях мы обнаружили, что краткосрочная история обычно состоит из около 50 задач, охватывающих около 1-3 часов, а среднесрочная история обычно состоит из более чем 500 задач, охватывающих 10-25 часов. Для целевых задач, которые либо не помечены как быстрый запуск или для которых подобные работы не могут быть найдены в истории, PQStar использует существующую стратегию для прогнозирования времени ожидания. Мы используем метод IBL для таких прогнозов, с тех пор как мы выяснили в наших экспериментах, что IBL даёт лучшие предсказания, чем QBETS. IBL (обучение на основе образца) использует взвешенную сумму гетерогенных эвклидовых-перекрываемых расстояний между атрибутами задач для выявлениях похожих задач и использует похожие задачи в истории, чтобы дать точечные прогнозы для целевой задачи на основе метода одново ближайшего соседа или средневзвешенное методом k-ближайших соседей.

Весь алгоритм, которому следует PQStar показан на схеме 2.
==== Эксперименты и результаты ====

=== Детали эксперимента ===

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

Симулятор может работать в двух режимах. В первом режиме, пользователь может вызывать симулятор с трассировкой суперкомпьютерной задачи в формате SWF и получать предсказанное время ожидания для новой работы. Этому режиму следует система предсказания QBETS. В этом режиме симулятор создаёт симулированное окружение задач в системе используя статистику, доступную в логе. Во втором режиме симулятор может быть выполнен на управляющем узле пакетной системы, которой требуются прогнозы. Он будет отслеживать добавление, исполнение и выход реальных задач в системе, и будет создавать симулированное окружение, использующего эти реальные работы. В этом втором режиме, атрибуты задач поддерживаемые и используемые симулятором могут быть получены с помощью команд очереди и команд управления задачами. Например, для пакетных систем на основе PBS, команда **qstat** (с опцией -f) выдаст все параметры задач используемые PQStar. Таким образом во втором режиме, предсказания получаются "живые" в режиме реального времени. Симулятор срабатывает по трём основным событиям, соответстующим добавлению задачи, началу исполнения задачи и прекращению работы. Всякий раз, когда работа добавляется, она будет добавлена в очередь ожидания, поддерживаемую симулятором. Как только время ожидания задачи истекает и она начинает исполнение, она удаляется из очереди ожидания и добавляется в список запущенных в симуляторе. Также в это время, свободные узлы, доступные в системе, уменьшаются на значение равное размеру запроса задачи. После того, как задача, которая работает, завершает своё выполнение, она удаляется из списка запущенных и количество свободных узлов в системе увеличивается на величину равную размеру запроса задачи. Этот процесс повторяется для каждого задания и, таким образом, моделируется состояние системы, с помощью которого мы выделяем состояние занятости процессоров и свойства очереди, которые нужны для нашего алгоритма.

Для каждой суперкомпьютерной трассировки в наших экспериментах, мы выполнили предсказания для всех задач с 100001 по 50000 или до конца файла журнала. Каждая из задач в этом наборе содержит данные исследования, для которых было сделано предсказание. Для данной целевой задачи, для которой предсказывается время ожидания, все добавленные до неё задачи составляют историю. Из этих задач истории мы используем подмножество задач и используем их время ожидания для предсказания целевой задачи. Подмножество формируется на основе сходства с целевой задачей и используя ближайшую, среднесрочную и дальнюю границы как описано ранее. После того, как целевые задачи запускаются и их время ожидания известно, они добавляются в набор исторических задач. Мы сравнили предсказания нашего метода PQStar с результатами IBL, QBETS и параметрической модели, а именно: с помощью логнормального распределения времени ожидания для предсказания. Мы использовали логнормальную модель, поскольку она дала сравнимые с QBETS Результаты в некоторых случаях.

=== Результаты ===

**Предсказания для быстрых запусков**. Сначала покажем эффективность использования ближайшей истории в PQStar для предсказания быстрых запусков. Таблица 2 показывает процент быстрых запусков, идентифицированных при помощи ближайшей истории и среднее число задач до ближней границы. Результаты показывают, что прогнозы, основанные на ближайшей истории в значительной мере способствуют идентификации большого числа быстрых запусков.

Таблица 3 показывает процент быстрых запусков, которые успешно идентифицированы логнормальной моделью, QBETS, IBL и нашим методом, PQStar. Удачная идентификация соответствует верхней границе быстрых запусков как меньше или равной 1 часа. Мы видим, что наш метод, PQStar, работает лучше, чем следующая стратегия IBL, путём успешной идентификации до 1.95 раз больше быстрых запусков. Он также успешно идентифицирует до 20 раз больше быстрых запусков, чем QBETS. Наш метод также более последователен и идентифицирует более чем 80% быстрых запусков независимо от журнала.  

**Дезинформирующие прогнозы.** Эти результаты показывают, что наша система прогнозирования PQStar имеет большие успехи в получении большого количества истинно положительных, то есть выявления большого количества быстрых запусков. Наша другая цель состоит в том, чтобы свести к минимуму количество ложных срабатываний, то есть, количество рабочих мест с большим временем ожидания ложно определённых как быстрые запуски. Таблица 4 показывает, что для суперкомпьютерных трассировок, использованных в наших экспериментах, PQStar даёт такие дезинформирующие прогнозы только для 1-10% от общего числа задач. Последняя колонка таблицы также показывает, что 32-72% этих задач имеют время ожидания менее 4х часов. Это означает, что половина неверных предсказаний находится в разумных пределах.

**Общие предсказания.** Поскольку установлено, что IBL лучшая стратегия, чем QBETS, как показано в таблице 3, наша система PQStar использует IBL для предсказания небыстрых запусков. Мы иллюстрируем сравнение предсказаний QBETS, IBL и PQStar на рисунке 3, для 5000 задач суперкомпьютерной трассировки. График 3(a) показывает среднюю ошибку предсказания (абсолютная разница в предсказанном и актуальном времени ожидания) для различных областей актуального времени. Исходя из этого, мы видим, что PQStar даёт наименьшую ошибку предсказания для быстрых запусков, и даёт ту же ошибку предсказания как IBL для остальной части задач, так как PQStar использует IBL для предсказания небыстрых запусков задач. В целях дальнейшего развития преимущества PQStar над IBL, мы показываем график рассеяния актуальных и предсказанных времён ожидания для быстрых запусков, как показано на графике 3(b) и 3(c). Мы ясно видим, что PQStar обеспечивает низкие верхние границы, в то время как IBL даёт высокие верхние границы для большого числа быстрых запусков.

График 4 показывает распределение прогнозируемого времени ожидания для различных областей актуального времени ожидания для всех задач в ANL (График 4(a)) и CTC(График 4(b)) трассировок для QBETS, IBL и PQStar. Графики показывают, что задачи с актуальным временем ожидания меньшим или равным 1 часа, т.е. быстрые запуски, PQStar в состоянии идентифицировать большинство из них как быстрые запуски. Для других быстрых запусков, предсказания PQStar соответствуют низким диапазонам времени ожидания в очереди. С QBETS и IBL, высокие предсказанные диапазоны наблюдались для большого числа быстрых запусков. Для поиска работы с фактическим быстрым временем ожидания от 1 до 12 часов, PQStar даёт маленькие диапазоны предсказанного времени ожидания для больших работ, чем QBETS и IBL.

Предсказанное время на одну задачу в нашем методе PQStar находиться на втором и общее время для симуляции для запуска всего набора данных было почти аналогично IBL и QBETS. Следовательно, есть минимальное или нет добавленного времени времени с точки зрения предсказания методом PQStar по отношение к существующему методу IBL.

**Ошибка RMS(СКО) и предсказание времени ответа**. Для того, чтобы оценить влияние предсказания быстрых запусков при помощи PQStar на общую точность предсказания, мы вычисляем RMS (среднеквадратичное отклонение) между фактическим и прогнозируемым временем ожидания для всех задач. Мы вычисляем процент снижения ошибки RMS для PQStar по сравнению с другими методами. Например, для сравнения ошибок RMS PQStar и QBETS мы вычисляем [...].

Обозначим процентное снижение как rmsdec<sub>fromlu</sub>, rmsdec<sub>fromqbets</sub> и rmsdec<sub>fromibl</sub> для сравнения с логнормальным, QBETS и IBL, сооветственно. Положительные значения для процентного снижения указывают лучшие предсказания при помощи PQStar. Таблица 5 показывает снижение ошибки в PQStar для всех предсказаний. Мы считаем, что PQStar даёт лучшую точность предсказания, чем другие методы. Наш метод даёт до 90% среднего улучшения в общей точности предсказания для всех задач по сравнению с логнормальной моделью и до 64% среднего улучшения по сравнению с QBETS. Среднее улучшение по сравнению с IBL всего 2% в связи с тем, что PQStar использует IBL для небыстрых запусков. Фактическое время ожидания и ошибки предсказания для этих небыстрых запусков имеют большие значения, и эти большие предсказания доминируют в общей ошибки RMS с учётом всех задач. Отсюда малая разница в ошибке RMS между PQStar и IBL. Последняя колонка таблицы показывает nrmsdec<sub>fromibl</sub>, процент снижения нормированной ошибки RMS из-за PQStar по сравнению с IBL. Нормализованная RMS рассчитывается путём нормализации отдельных ошибок предсказания используя фактическое время ожидания. КАк показывают результаты в этой колонке, PQStar даёт значительную выгоду до 42% в общей точности предсказания по сравнению с IBL.

Мы также вычисляем процент отличия предсказанного и фактического времени ответа для каждой задачи, где время ответа - сумма времени ожидания и времени исполнения. Для времени исполнения, мы рассматриваем предсказанное время исполнения равным фактическому времени исполнения.Поэтому процент ошибки предсказания времени ответа рассчитывается как [...].

Этот показатель определяет влияние ошибок предсказания на задачи различной длинны или времени исполнения. Предсказание времени ожидания с ошибкой в 1 час будет иметь большее влияние на задачу с временем исполнения 15 минут, чем для задачи, чьё время исполнения 2 дня. Кроме того, для определения хороших предсказаний, мы разделим время ожидания и исполнения в различные корзины. Каждая корзина представляет диапазон времени ожидания/исполнения и ассоциирован с интервалом. Время ожидания/исполнения задачи округляется до ближайших значений интервала, связанных с корзиной, которой соответствуют время ожидания/запуска. Таблица 6 показывает корзины и размеры интервалов для каждой корзины в наших экспериментах. Например, если время ожидания задачи - 37 минут, будет использован размер интервала 15 минут (первая строка). Поэтому время ожидания округляется до 45 минут, который является следующим 15-минутным интевалом. Как видно, идея использовать корзины, в том, чтобы дать различные допустимые пределы ошибок предсказания для различных фактических и предсказанных времён ожидания. Ошибка прогнозирования в 15 минут больше для задачи, чьё фактическое время ожидания - 20 минут, но она меньше для задачи, чьё фактическое время ожидания 2,5 дня.

Мы считаем прогноз для задачи хорошим, если округлённое значение фактического и предсказанного времени ожидания лежат в одной корзине или их значение PPErt находиться в пределах 10%. Таблицы 7 показывают средние значения PPErt  и процент хороших предсказаний полученных различными методами. Таблица показывает, что среднее PPErt составляет до 35 раз меньше и число хороших предсказаний до 58% больше с PQStar по сравнению с другими методами. 

**Пороговые значения для быстрых запусков.** Для всех приведённых выше результатов, мы использовали порог времени ожидания в 1 час для определения быстрых запусков. Задачи с фактическим временем ожидания в очереди меньшим чем порог помечаются как быстрые запуски. Этот порог основывается на предположении, что время меньшее час может быть мало и ошибка предсказания до этого ограничения может быть приемлима для пользователя. Мы использовали величину одного часа в качестве порога для целевых задач с временем ожидания меньше чем этот порог для улучшения(снижения) границ этих задач, так как этот класс задач образуют большую часть задач, как мы показывали в таблице 1. Тем не менее, была серия работ, которые показывают, что время ответа задачи должно быть меньше 20 минут, чтобы рассматривать сессию добавленной задачи как интерактивную. В этом эксперименте мы анализируем влияние изменяющихся порогов для быстрых запусков при помощи различных порогов в PQStar для предсказания быстрых запусков. Таблица 8 показывает воздействие изменения пороговых значений для быстрых запусков от 10 минут до 1 часа предсказаний на PQStar для трассировок CTC. Мы считаем, что PQStar постоянно выявляет более 80% быстрых запусков для всхе порогов, а также отличия порогов не дают влияния на предсказание быстрых запусков.

Таким образом, PQStar работает лучше, чем IBL и QBETS, и он также превосходит параметрические модели, использующие логнормальное распределение, во всех выше указанных аспектах. Из этих результатов мы можем ясно видеть, что наш метод обеспечивает гораздо более агрессивные оценки для быстрых запусков по сравнению с остальными методами, а также по предсказаниям, сводящимся к ограничениям.
==== Заключение и будущие работы ====

В этой работе мы разработали систему прогнозирования, названную PQStar, для идентификации быстрых запусков или задач, что фактическое время ожидания меньше или равно 1 часу. Эти быстрые запуски составляют большинство добавленных задач во многих суперкомпьютерных трассировках. В данной работе мы рассматриваем обе характеристики задач для предсказаний, а именно: размер запроса ресурсов и планируемое время исполнения, а также состояние системы, а именно очередь и занятость процессоров. С помощью экспериментов с различными трассировками мы показали, что наши стратегии прогнозирования могут правильно идентифицировать до 20 раз больше быстрых запусков и обеспечить более жёсткие границы предсказания, и, таким образом, привести к на 64% более высокой общей точности прогнозирования, чем существующие методы. В настоящее время мы используем метод IBL для предсказания задач с потенциально долгим временем ожидания в очереди. Мы планируем изучить альтернативные стратегии для предсказания таких задач. Мы также планируем разработать методики предсказания времени исполнения, чтобы предсказать общее время ответа. Предсказание времени исполнения задач, добавленных в пакетную систему, является сложным в связи с ограниченной историей. Наконец, мы планируем разработать стратегии планирования и метапланирования, которые используют стохастические предсказания для выбора соответствующих ресурсов для исполнения.