Различия

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

--- translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs [2014/02/12 19:27] – [Эксперименты и результаты] 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.
@@ Строка 105: / Строка 105: @@
 Обозначим процентное снижение как 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 для предсказания задач с потенциально долгим временем ожидания в очереди. Мы планируем изучить альтернативные стратегии для предсказания таких задач. Мы также планируем разработать методики предсказания времени исполнения, чтобы предсказать общее время ответа. Предсказание времени исполнения задач, добавленных в пакетную систему, является сложным в связи с ограниченной историей. Наконец, мы планируем разработать стратегии планирования и метапланирования, которые используют стохастические предсказания для выбора соответствующих ресурсов для исполнения.