Проект 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 представляет собой резюме нашей работы и планы будущей работы.