Различия

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

--- translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs [2014/02/09 19:07] – [Эксперименты и результаты] 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
@@ Строка 75: / Строка 75: @@
 === Общие прогнозы и использование IBL ===
-Таким образом, PQStar пытается найти аналогичную задачу в ближайшей, средней и дальней истории и использует набор критериев для того, чтобы пометить задачу как быстрый запуск. В дополнение к рассмотрению только характеристик задачи: размера запроса и планируемого времени исполнения, PQStar явно или неявно учитывает состояние системы, а именно: состояние занятости процессоров и состояние очереди, для определения схожести и получения предсказания. В наших исследованиях мы обнаружили, что краткосрочная история обычно состоит из около 50 задач, охватывающих около 1-3 часов, а среднесрочная история обычно состоит из более чем 500 задач, охватывающих 10-25 часов. Для целевых задач, которые либо не помечены как быстрый запуск или для которых подобные работы не могут быть найдены в истории, PQStar использует существующую стратегию для прогнозирования времени ожидания. Мы используем метод IBL для такиъ прогнозов, с тех пор как мы выяснили в наших экспериментах, что IBL даёт лучшие предсказания, чем QBETS. IBL (обучение на основе образца) использует взвешенную сумму гетерогенных эвклидовых-перекрываемых расстояний между атрибутами задач для выявлениях похожих задач и использует похожие задачи в истории, чтобы дать точечные прогнозы для целевой задачи на основе метода одново ближайшего соседа или средневзвешенное методом k-ближайших соседей.
+Таким образом, PQStar пытается найти аналогичную задачу в ближайшей, средней и дальней истории и использует набор критериев для того, чтобы пометить задачу как быстрый запуск. В дополнение к рассмотрению только характеристик задачи: размера запроса и планируемого времени исполнения, PQStar явно или неявно учитывает состояние системы, а именно: состояние занятости процессоров и состояние очереди, для определения схожести и получения предсказания. В наших исследованиях мы обнаружили, что краткосрочная история обычно состоит из около 50 задач, охватывающих около 1-3 часов, а среднесрочная история обычно состоит из более чем 500 задач, охватывающих 10-25 часов. Для целевых задач, которые либо не помечены как быстрый запуск или для которых подобные работы не могут быть найдены в истории, PQStar использует существующую стратегию для прогнозирования времени ожидания. Мы используем метод IBL для таких прогнозов, с тех пор как мы выяснили в наших экспериментах, что IBL даёт лучшие предсказания, чем QBETS. IBL (обучение на основе образца) использует взвешенную сумму гетерогенных эвклидовых-перекрываемых расстояний между атрибутами задач для выявлениях похожих задач и использует похожие задачи в истории, чтобы дать точечные прогнозы для целевой задачи на основе метода одново ближайшего соседа или средневзвешенное методом k-ближайших соседей.
 Весь алгоритм, которому следует PQStar показан на схеме 2.
@@ Строка 88: / Строка 88: @@
 Для каждой суперкомпьютерной трассировки в наших экспериментах, мы выполнили предсказания для всех задач с 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 для предсказания задач с потенциально долгим временем ожидания в очереди. Мы планируем изучить альтернативные стратегии для предсказания таких задач. Мы также планируем разработать методики предсказания времени исполнения, чтобы предсказать общее время ответа. Предсказание времени исполнения задач, добавленных в пакетную систему, является сложным в связи с ограниченной историей. Наконец, мы планируем разработать стратегии планирования и метапланирования, которые используют стохастические предсказания для выбора соответствующих ресурсов для исполнения.