Различия

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

--- translate:identifying_quick_starters:towards_an_integrated_framework_for_efficient_predictions_of_queue_waiting_times_of_batch_parallel_jobs [2014/02/06 18:30] – [Связанные работы] 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
@@ Строка 45: / Строка 45: @@
 ==== Методология ====
+Основа нашего метода, PQStar, для идентификации быстрозапускаемых задач - установить границы предшествующих добавлений задачи в истории и использовать похожие работы с границами для предсказания. Таким образом, наиболее актуальная история используется для предсказания целевого быстрого запуска. В частности, PQStar разделяет историю для целевой работы на ближаюшую, средне- и долгосрочную на основе состояния занятости процессоров. Состояние занятости процессоров в данном случае обозначает выделение процессоров для задач, исполняющихся на этом экземпляре. Оно включает число процессоров, используемых каждой выполняемой задачей.
+=== Прогноз с использованием ближайшей истории ===
+Для нахождения ближайшей истории, PQStar обходит задачи, начиная с целевой задачи в обратном хронологическом порядке добавления задач до тех пор, пока состояние занятости процессоров во время добавления задачи не будет похоже на состояние занятости процессоров в момент добавления целевой задачи. Самая ранняя задача в истории, имеющая похожее состояние занятости процессоров обозначает краткосрочную границу и набор задач между целевой задачей и границей даёт ближающую историю. Для идентификации целевой задачи как быстро запускаемой, PQStar находит задачи в ближайшей историей с похожими характеристиками с точки зрения размеров запроса ресурсов и планируемого времени исполнения, которые начали исполнение. Он также проверяет, что ни одна из задач в очереди ожидания, которые пришли после ближайшей истории и которые имеют схожие характеристики с целевой задачей, не ждали больше часа в очереди. Если эти два условия выполнены, PQStar идетифицирует целевую задачу как быстрый запуск и устанавливает верхнюю границу в 1 час для целевой задачи.
+С целью прогнозирования с помощью ближайшей истории, два состояния занятости процессоров принимаются схожими если число задач с большими запросами ресурсов, которые исполняются в двух состояниях, одинаковы. Мы используем выполнение больших задач для определения схожести занятости процессоров для задач, которые могут быть запущены на оставшихся процессорах, и, таким образом, получить малое время ожидания и быть быстро запущенными. Так основа идентификации быстрых запусков с использованием ближаюшей истории в том, чтобы, глядя на задачи с аналогичными характеристиками в краткосрочной истории и аналогичными состояниями занятости и проверяя что эти задачи могут быть потенциально заполнить свободные ресурсы, это может предсказать, что текущая задача может заполнить свободные ресурсы и, следовательно, пометить задачу как быстрый запуск. Обратите внимание, что по нашему определению, два состояния занятости процессоров также принимаются схожими, если нет больших задач в обоих состояниях. Для нашей работы мы обозначаем задачу как большую, если её запрос ресурсов по крайней мере на степень двойки больше или равен квадратному корню общего количества ресурсов. Мы определяем характеристики двух задач как схожие, если их запросы ресурсов равны и если разница между их планируемым временем исполнения в рамках часа. Как покажут наши эксперименты, этот метод использования ближайшей истории для предсказания даёт большой процент идентификации быстрых запусков.
+=== Прогноз с использованием среднесрочной истории ===
+Для задач, для которых ближайшая история не может использована в связи с неудовлетворением упомянутому выше критерию, PQStar обходит задачи в обратном хронологическом порядке добавления задач от ближайшей границы, пока состояние занятости процессоров не станет полностью другим с точки зрения выполнения задач. Другими словами, предположим A = {множество задач, исполняемых во время добавления целевой задачи} и B = {множество задач, исполняемых во время добавления задачи в истории}, то мы проводим границу среднесрочной истории в точке, где A ∪ B = ∅.
+PQStar помечает среднесрочную границу после задачи, когда состояние становиться полностью другим и обозначает набор задач между средней и ближайшей границами как среднесрочную историю. Для идентификации того, что целевая задача является быстрым запуском, PQStar ищет задачу в среднесрочной истории с похожими характеристиками с точки зрения размера запросов процессоров и планируемым временем исполнения, которые начали исполнение. Он также проверяет что нет задач в очереди ожидания, которые добавлены после средней границы и которые имеют схожие характеристики с целевой задачей, прождавших более одного часа в очереди. Однако, в отличие от предсказаний с ближайшей историей, сами по себе эти условия не являются достаточными для предсказаний в среднесрочной истории, так как состояние процессоров в среднесрочной менее похоже на целевую задачу, чем их в ближайшей. Мы обнаружили, что задачи, удовлетворяющие условиям имели широко отличающиеся времена ожидания. Поэтому, мы вводим три дополнительных критерия для предсказания в среднейсрочной истории: критерий размера запроса, расчётное время выполнения (ERT) и критерий свободных узлов.
+**Критерий размера запроса.** Один полезный критерий мы нашли для ранжирвания целевых задач с точки зрения их размера запроса среди задач в очереди ожидания во время добавления задачи. В частности, мы рассчитываем jobrank<sub>reqsize</sub>, используя позицию целевой задачи в списке задач в очереди в момент времени при сортировке задач по возрастанию размера запроса. jobrank<sub>reqsize</sub> рассчитывается путём нормализации этой позиции по отношению к общему числу задач в очереди.
+Большинство существующих стратегий группируют задачи только с точки зрения размеров запроса, и поиск задач с похожим размером запроса для предсказания времени ожидания в очереди. Однако, один размер запроса может соответствовать широкому диапазону времени ожидания как показано на графике 1(a), который показывает статистику для 1000 экземпляров задач с трассировкой CTC. Например, соотвествующий размер запроса 8 процессоров на графике, мы видим, что время ожидания очереди может варьироваться с 1 минуты до 32 часов. Таким образом, в дополнение к поиску схожих с целевой задач  с точки зрения размера запросов, мы рассматриваем ранг задачи в очереди с точки зрения размеров запроса, тем самым неявно учитывая и размер запроса и состояние очереди для предсказания. Мы учитываем целевые задачи со значениями jobrank<sub>reqsize</sub> меньшими, чем порог threshold<sub>reqsize</sub>, мы рассматриваем задачи в ближайшей истории, находим два порога: threshold<sub>reqsize1</sub> как максимум значений jobrank<sub>reqsize</sub> задач со временем ожидания в очереди меньшим или равным 1 часа и threshold<sub>reqsize2</sub> как минимум значений jobrank<sub>reqsize</sub> задач со временем ожидания в очереди большим чем 1 час и используем минимум этих порогов как threshold<sub>reqsize</sub>. Используя краткосрочную историю, чтобы найти пороги, PQStar использует самую последнюю историю и, следовательно, также принимает во внимание только те задачи, что имеют похожие состояния занятости процессоров.
+**Критерий 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 для предсказания задач с потенциально долгим временем ожидания в очереди. Мы планируем изучить альтернативные стратегии для предсказания таких задач. Мы также планируем разработать методики предсказания времени исполнения, чтобы предсказать общее время ответа. Предсказание времени исполнения задач, добавленных в пакетную систему, является сложным в связи с ограниченной историей. Наконец, мы планируем разработать стратегии планирования и метапланирования, которые используют стохастические предсказания для выбора соответствующих ресурсов для исполнения.