Различия

Показаны различия между двумя версиями страницы.

--- translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs [2014/02/09 17:21] – [Методология] artamonov
+++ translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs [2014/05/12 19:24] (текущий) – [Методология] artamonov
@@ Строка 64: / Строка 64: @@
 **Критерий 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 для предсказания задач с потенциально долгим временем ожидания в очереди. Мы планируем изучить альтернативные стратегии для предсказания таких задач. Мы также планируем разработать методики предсказания времени исполнения, чтобы предсказать общее время ответа. Предсказание времени исполнения задач, добавленных в пакетную систему, является сложным в связи с ограниченной историей. Наконец, мы планируем разработать стратегии планирования и метапланирования, которые используют стохастические предсказания для выбора соответствующих ресурсов для исполнения.