translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версияСледующая версия | Предыдущая версия | ||
translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs [2014/01/30 18:26] – 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 | ||
---|---|---|---|
Строка 10: | Строка 10: | ||
Параллельные системы - пространственно разделёны и, следовательно, | Параллельные системы - пространственно разделёны и, следовательно, | ||
- | Ключевые слова: время ожидания очереди, | + | **Ключевые слова**: время ожидания очереди, |
==== Введение ==== | ==== Введение ==== | ||
Строка 16: | Строка 16: | ||
Параллельные системы многих суперкомпьютеров являются пакетными системами, | Параллельные системы многих суперкомпьютеров являются пакетными системами, | ||
+ | Прогнозирование времени ожидания задач в пакетных системах будет весьма полезно для пользователей. Предсказания могут быть использованы пользователем для различных целей, включая планирование его работы и соблюдение сроков, | ||
+ | Анализы выполнения задач, широко используемых на суперкомпьютерах, | ||
+ | |||
+ | Важно отметить, | ||
+ | |||
+ | Цели для предсказания быстрого старта: | ||
+ | * Максимизировать число истинно положительных, | ||
+ | * Минимизировать число ложных срабатываний, | ||
+ | |||
+ | Первая цель имеет важное значение для улучшения общей точности предсказаний, | ||
+ | |||
+ | В этой работе мы разработали интегрированный фреймворк PQStar, для идетификации и прогнозирования быстрых запусков. Важный аспект нашей стратегии предсказания быстрых запусков в том, что он считает состояние занятости процессоров и состояние очереди во время добавления задач в дополнение к характеристикам задач, включая запрашиваемое количество процессоров и планируемое время исполнения. Состояние процессоров и очереди включает текущее количество свободных узлов, количество задач с большими запросами, | ||
+ | |||
+ | Раздел 2 представляет существующие стратегии предсказания времени ожидания в очереди. В разделе 3 детально описывается наша методика. Раздел 4 описывает эсперименты по симуляции с трассировками задач на суперкомпьютерах и представляет результаты, | ||
==== Связанные работы ==== | ==== Связанные работы ==== | ||
+ | Есть два основных подхода к прогнозированию времени ожидания очереди. Они могут быть классифицированы как нестатистические и статистические методы. Нестатистические методы пытаются имитировать точный алгоритм планирования и принятия решений, | ||
+ | |||
+ | В работах Смита предсказания времени выполнения получены с использованием аналогичных опытов в истории, | ||
+ | |||
+ | Статистический метод Дауни использует то наблюдение, | ||
+ | |||
+ | Некоторые статистические методы используют анализ временных рядов времени ожидания для задач в истории, | ||
+ | |||
+ | Подход Ли рассматривает состояние системы для предсказания времени ожидания очереди. В их методе, | ||
==== Методология ==== | ==== Методология ==== | ||
+ | Основа нашего метода, | ||
+ | |||
+ | === Прогноз с использованием ближайшей истории === | ||
+ | |||
+ | Для нахождения ближайшей истории, | ||
+ | |||
+ | С целью прогнозирования с помощью ближайшей истории, | ||
+ | |||
+ | === Прогноз с использованием среднесрочной истории === | ||
+ | |||
+ | Для задач, для которых ближайшая история не может использована в связи с неудовлетворением упомянутому выше критерию, | ||
+ | |||
+ | PQStar помечает среднесрочную границу после задачи, | ||
+ | |||
+ | **Критерий размера запроса.** Один полезный критерий мы нашли для ранжирвания целевых задач с точки зрения их размера запроса среди задач в очереди ожидания во время добавления задачи. В частности, | ||
+ | |||
+ | Большинство существующих стратегий группируют задачи только с точки зрения размеров запроса, | ||
+ | |||
+ | **Критерий ERT.** Подобно критерию размера запроса, | ||
+ | |||
+ | **Критерий свободных узлов.** Окончательный критерий, | ||
+ | |||
+ | Для предсказаний в среднесрочной истории PQStar помечает задачу как быстрый запуск, | ||
+ | |||
+ | === Предсказания с помощью дальней истории === | ||
+ | |||
+ | Для тех задач, на которые среднесрочная история не может быть использована, | ||
+ | |||
+ | === Общие прогнозы и использование IBL === | ||
+ | |||
+ | Таким образом, | ||
+ | |||
+ | Весь алгоритм, | ||
==== Эксперименты и результаты ==== | ==== Эксперименты и результаты ==== | ||
+ | === Детали эксперимента === | ||
+ | |||
+ | Эксперименты проводились с использованием дискретного симулятора событий который мы разработали. Он создаёт эмуляцию окружения с задачами, | ||
+ | |||
+ | Симулятор может работать в двух режимах. В первом режиме, | ||
+ | |||
+ | Для каждой суперкомпьютерной трассировки в наших экспериментах, | ||
+ | |||
+ | === Результаты === | ||
+ | |||
+ | **Предсказания для быстрых запусков**. Сначала покажем эффективность использования ближайшей истории в PQStar для предсказания быстрых запусков. Таблица 2 показывает процент быстрых запусков, | ||
+ | |||
+ | Таблица 3 показывает процент быстрых запусков, | ||
+ | |||
+ | **Дезинформирующие прогнозы.** Эти результаты показывают, | ||
+ | |||
+ | **Общие предсказания.** Поскольку установлено, | ||
+ | |||
+ | График 4 показывает распределение прогнозируемого времени ожидания для различных областей актуального времени ожидания для всех задач в ANL (График 4(a)) и CTC(График 4(b)) трассировок для QBETS, IBL и PQStar. Графики показывают, | ||
+ | |||
+ | Предсказанное время на одну задачу в нашем методе PQStar находиться на втором и общее время для симуляции для запуска всего набора данных было почти аналогично IBL и QBETS. Следовательно, | ||
+ | |||
+ | **Ошибка RMS(СКО) и предсказание времени ответа**. Для того, чтобы оценить влияние предсказания быстрых запусков при помощи PQStar на общую точность предсказания, | ||
+ | |||
+ | Обозначим процентное снижение как rmsdec< | ||
+ | |||
+ | Мы также вычисляем процент отличия предсказанного и фактического времени ответа для каждой задачи, | ||
+ | |||
+ | Этот показатель определяет влияние ошибок предсказания на задачи различной длинны или времени исполнения. Предсказание времени ожидания с ошибкой в 1 час будет иметь большее влияние на задачу с временем исполнения 15 минут, чем для задачи, | ||
+ | |||
+ | Мы считаем прогноз для задачи хорошим, | ||
+ | |||
+ | **Пороговые значения для быстрых запусков.** Для всех приведённых выше результатов, | ||
+ | |||
+ | Таким образом, | ||
==== Заключение и будущие работы ==== | ==== Заключение и будущие работы ==== | ||
+ | В этой работе мы разработали систему прогнозирования, |
translate/identifying_quick_starters/towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs.1391106416.txt.gz · Последнее изменение: 2014/01/30 18:26 — artamonov