Прогноз времени выполнения типовых последовательных «тяжелых» вычислений в многопроцессорной системе в условиях непрогнозируемого поступления заявок +9


Идея написания первой статьи на Хабр возникла в процессе «собирания камней» для создания серверной системы, основные задачи которой:

  • получение заявок от пользователей на некоторые типовые последовательные «тяжелые» вычисления;
  • осуществление вычислений;
  • выдача информации (по запросу) об оставшемся времени вычислений;
  • выдача результатов вычислений по их завершению.


Следует уточнить ряд обстоятельств исследования:

  • под последовательным вычислением будем понимать вычисление, которое осуществляется не более чем одним ядром процессора (нераспараллеливаемый процесс), т.к. на данном этапе создания системы задача распараллеливания самих вычислений не стоит. В дальнейшем слово «последовательное» будем опускать;
  • вычисления являются типовыми, т.е. используется один и тот же алгоритм для рассчетов, время выполнения которого для заданной вычислительной системы преимущественно зависит от размерности исходных данных (размерность обозначим числом N), а не от их фактических значений;
  • вычисления предполагаются преимущественно «тяжелыми», что требует существенное время на выполнение (от секунд до часов и, возможно, более);
  • предполагается неизвестным характер изменения интенсивности заявок на вычисления и соответствующие им значения размерностей N.


Первоначальные попытки автора прогнозировать время вычислений имели слабую точность. Для алгоритма «на глаз» подбиралась зависимость времени от N с помощью степенных коэффициентов так, чтобы минимизировать среднее отклонение. В результате таких пробных расчетов были получены не слишком приятные результаты:
N Реальное время (сек) Расчетное время (сек)
417 9,60 5,04 ± 0,96
689 26,20 18,33 ± 3,50
1165 78,40 70,56 ± 13,48
2049 264,60 300,34 ± 57,40
3001 654,20 799,24 ± 152,74
3341 875,80 1 052,50 ± 201,13
4769 2323,60 2 621,69 ± 501,01
5449 3424,10 3 690,10 ± 705,18
6129 4811,80 4 988,97 ± 953,40

На помощь, как это нередко бывает, пришли классики. Вспомнились давно забытые слова «интерполяция», «экстраполяция», и начались поиски в интернете в подозрении правильности выбранного направления. Был перечитан ряд постов, статей и прочих ресурсов. Главный вывод таков: для решения задачи прогнозирования значений некоторой неизвестной функции одной переменной чаще всего используют полиномы Чебышева или Лагранжа. Оказалось, что имеет смысл применять полиномы Чебышева (в принципе, их заменой мог бы стать и МНК) в тех случаях, когда нет доверия к имеющемуся набору «аргумент-значение», а полиномы Лагранжа хороши в обратном случае. Второе выглядело тем, что нужно. Действительно, почему бы не создать «идеальные» условия для тестирования алгоритма вычислений на конкретной системе (выделить ядро с нагрузкой 100%) и не набрать достаточную статистику для построения полинома Лагранжа?
Графический пример построения полинома Лагранжа
Lagrange polynomial.svg
«Lagrange polynomial» участника User:Acdx — Self-made, based on Image:Lagrangepolys.png. Под лицензией CC BY-SA 3.0 с сайта Викисклада.

Между тем, встречаются уже реализованные алгоритмы построения полинома Лагранжа, например здесь. Адаптированный под задачу алгоритм начал показывать похожие (по модулю отклонения) результаты при экстраполяции на возрастающем наборе статистики (для прогноза при N=1165 использовалось реальное время при N=417 и N=689, для прогноза при N=2049: N=417, N=689 и N=1165, и т.д.):
N Реальное время (сек) Расчетное время (сек)
417 9,60 -
689 26,20 -
1165 78,40 55,25
2049 264,60 253,51
3001 654,20 617,72
3341 875,80 863,74
4769 2323,60 2899,77
5449 3424,10 2700,96
6129 4811,80 5862,79

При интерполяции полиномом Лагранжа результаты получились впечатляющими начиная с N=2049 (из выборки последовательно исключалось по одному измерению и производился расчет по аргументу исключенного измерения):
N Реальное время (сек) Расчетное время (сек)
417 9,60 -
689 26,20 2,58
1165 78,40 98,35
2049 264,60 245,74
3001 654,20 664,15
3341 875,80 862,91
4769 2323,60 2407,75
5449 3424,10 3251,71
6129 4811,80 -

Действительно, при N=689 и N=1165 отклонение прогнозируемого значения от реального значения составило соответственно около 90% и 25%, что недопустимо, однако, начиная с N=2049 и далее отклонение держалось в пределах 1,5-7%, что можно трактовать как хороший результат.

Полином: F(x) = -5.35771746746065e-22*x^7 + 1.23182612519573e-17*x^6 — 1.14069960055193e-13*x^5 + 5.44407657742344e-10*x^4 — 1.39944148088413e-6*x^3 + 0.00196094886960409*x^2 — 1.22001773413031*x + 263.749105425487
Степень полинома, при необходимости, можно снизить до требуемой путем легкого изменения алгоритма (в принципе, для задачи автора можно было обойтись и 3-й степенью)
Графики данного полинома

Важно отметить, что полином интерполяционный, а значит, при значениях вне диапазона [Nmin;Nmax] качество прогноза оставляет желать лучшего:



Вывод: имеет смысл заблаговременно набрать достаточную статистику в «идеальных» условиях (особенно для больших значений N), построить полином Лагранжа и при поступлении заявок получать прогноз времени их вычислений подставляя Ni в готовый полином.

Такой подход предельно понятен, однако, когда мы говорим о прогопроцессорной (многоядерной) системе, ситуация усложняется:

  • Во-первых, вышеописанный подход подходит для случаев, когда число заявок (выполняемых задач) X<=Y, где Y – число ядер. Иными словами, система ни делает ничего, кроме вычислений, и каждая задача обеспечивается 100%-м ресурсом соответствующего ядра.
  • Во-вторых, при X>Y ОС должна делить вычислительный ресурс между задачами (например, при ручном запуске задач в Ubuntu server 14.04 через screen вычислительный ресурс делился между задачами равномерно согласно формуле X/Y*100%).
  • В-третьих, заранее неизвестен характер поступления заявок и соответствующих значений N, что делает невозможным прогноз времени по какой-либо формуле распределения вычислительного ресурса (например, для той же X/Y*100%).

Анализ данных аспектов показал, что спрогнозировать время выполнения заявки заранее невозможно, но это значение может корректироваться при наступлении некоторых событий, влияющих на текущий вычислительный ресурс, выделяемый для вычислений, с последующей выдачей пользователю. Такими событиями являются: поступление новой задачи и завершение выполняемой задачи. Именно при наступлении этих событий предлагается осуществлять коррекцию прогноза.

image

Становится ясно, что при наступлении любого из этих событий необходимо осуществить пересчет выделяемого ресурса для каждой задачи (в случаях с известным распределением ресурса между задачами) либо получить каким-либо образом это значение с помощью встроенных (языковых или операционных) средств, затем пересчитать оставшееся время с учетом выделяемого ресурса. А вот для этого-то нам необходимо знать какой объем работ уже был выполнен процессом. Поэтому предлагается организовать некоторое хранилище (возможно таблицу в СУБД), в котором будет содержаться необходимая информация, например:
ID задачи Начало Конец Lagrange(N) Выполнено Последний запрос Последняя коррекция Текущий CPU
2457 12:46:11 Lagrange(N) 0,45324 12:46:45 1,00
6574 12:46:40 Lagrange(N) 0,08399 12:46:45 1,00
2623 12:44:23 12:46:45 Lagrange(N) 1,00 12:46:45 0

Предполагается реализовывать следующий алгоритм (метакод):

  • При поступившем запросе пользователя о состоянии задачи:
    • <Выполнено> += (<Момент запроса> — МАКС(<Последний запрос>,<Последняя коррекция>))*<Текущий CPU>/<Lagrange(N)>;
    • <Последний запрос> = <Момент запроса>;
    • Возврат пользователю <Выполнено> и <Текущий CPU>.
  • При поступлении новой задачи:
    • Создать новый <ID задачи>;
    • Записать время начала выполнения в <Начало>;
    • Рассчитать и записать прогноз времени выполнения в «идеальных» условиях в <Lagrange(N)>;
    • <Выполнено> = 0;
    • <Последний запрос> = 00:00:00;
    • Вызвать процедуру коррекции.
  • При завершении задачи можно удалить запись вовсе, но в любом случае вызвать процедуру коррекции.
  • Процедура коррекции:
    • Для всех записей: <Последняя коррекция> = <Текущее время> (имеет смысл хранить это значение где-то отдельно);
    • Получить и записать для каждой задачи соответствующий <Текущий CPU>.

Вывод: имея заблаговременный прогноз для «идеальных» условий мы можем практически «на лету» корректировать прогнозируемый процент выполнения «тяжелых» последовательных вычислений при изменении нагрузки на систему и выдавать пользователю эти значения по запросу.

Конкретные реализации могут иметь свои особенности, усложняющие или упрощающие жизнь, однако целью статьи не является разбор деликатных случаев, а лишь предложение вышеизложенного подхода на справедливый суд читателя (в первую очередь на предмет жизнеспособности).
Имеет ли смысл применять предложенный подход на боевом сервере?

Проголосовало 9 человек. Воздержалось 5 человек.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.




К сожалению, не доступен сервер mySQL