Scalability methodology

1 Проведение исследования масштабируемости реализации алгоритма.

1. Выбор реализации параллельного алгоритма
2. Составление списка изменяющихся параметров работы реализации (размер задачи – a, число процессов – b, размер блока – c, число процессов на узел и т.п.) – набор значений этих параметров будем называть конфигурацией запуска К=(a,b,c…)
3. Выбор границ параметров, в которых будут проводиться эксперименты (максимальное и минимальное значение каждого параметра) min(a),max(a), min(b),max(b), min(c),max(c)…
4. Для каждого изменяемого параметра необходимо выбрать набор рассматриваемых значений параметров {ha}{hb}{hc}…, с которым каждый из параметров будет изменяться в серии экспериментов, лежащих в промежутке от минимального до максимального значения включительно.
5. В приложении необходимо оформить фиксацию в лог-файл информации, содержащей данные о значениях изменяющихся параметров запуска (ai,bi,ci…) и времени выполнения алгоритма (ti). Результатом выполнения R будем считать совокупность параметров выполнения и времени выполнения R = (ai,bi,ci…ti). Если в одном приложении необходимо исследовать несколько частей, то можно ввести либо идентификатор исследуемой части приложения "ind" и добавить его в результат, тогда для каждого приложения результат будет состоять из двух строк, либо добавить к результату еще одно значение времени: t1i, t2i.
6. Проведение серии экспериментов.
   1. Из списка выбранных параметров выбирается для каждого минимальное значение в выбранных границах (совокупность этих параметров назовем минимальной конфигурацией Kmin= (min(a), min(b), min(c),…))
   2. Проводится запуск приложения с минимальной конфигурацией
   3. Фиксируется результат выполнения (amin,bmin,cmin,…tmin)
   4. Выбирается из списка параметров один параметр Ki
   5. Значение выбранного параметра увеличивается, подставляя следующее значение из выбранного набора значений параметра {hki}.
   6. Проводится запуск на новой конфигурации запуска. Лучше каждый запуск проводить несколько раз. Таким образом, можно добиться уменьшения влияния различных случайных процессов, влияющих на производительность приложения.
   7. Фиксируется в лог-файле новый результат выполнения
   8. Пока значение параметра не достигнет значения max(Ki) повторять с шага е.
   9. При достижении максимума параметра Ki перейти к параметру Ki+1
   10. Значение следующего параметра выбрать из соответствующего набора значений следующим по возрастанию {hKi+1}
   11. Повторить для выбранного параметра шаги с d до j, до достижения максимума для этого параметра.
   12. Рекурсивно для каждого нового параметра необходимо проводить запуски приложения по описанной выше схеме, увеличивая значение его из выбранного набора значений и фиксировать результаты выполнения, аналогично проходя по всем значениям предыдущих параметров.
7. Для проведения серии экспериментов целесообразно выстроить параметры запуска таким образом, чтобы самым последним был параметр – число процессов. В таком случае можно создать обертку для реализации алгоритма, которая будет минимизировать число запусков приложения на вычислительной системе и будет подставлять значения для других параметров, проходя рекурсивно по всем наборам значений остальных параметров запуска. Таким образом, в один физический запуск созданной обертки реализации алгоритма при фиксированном значении числа процессов необходимо уложить максимальный набор других изменяемых параметров, не влияющих на параметры физического запуска. Тогда число физических запусков обертки будет прямо пропорционально числу значений параметров влияющих на физический запуск приложения.
8. Сбор результатов выполнения приложения по всем выполненным запускам в логах.
9. Добавление всех собранных результатов работы приложения в базу данных следующим образом: данные из каждого файла с логами запуска приложения необходимо внести в общую таблицу базы данных. В таблице должны присутствовать поля, соответствующие каждому изменяемому параметру, поле идентификатора эксперимента, если они описаны разными строками или для каждого значения времени эксперимента должно присутствовать отдельное поле. Так же в таблицу целесообразно добавить колонки, характеризующие параметры вычислительной системы, на которой производились запуски приложения, и прочая информация о параметрах системы, которые могут отличаться при переходе к другой системе (тип и параметры процессора, параметры сети, тип и версия компилятора и т.п.). Так же целесообразно ввести поле, в котором будет содержаться информация об источнике данного результата. С помощью него можно найти из какого файла с логами работы приложения данные попали в базу, чтобы можно было отследить проблемные запуски приложения и например можно было бы отфильтровать данные этого запуска. Следует отметить, что чем более детальная информация о запуске приложения будет представлена в базе, тем более детальный анализ может быть проведен в дальнейшем.
10. Проводится анализ собранной базы данных. Для этого можно строить выборки из собранных результатов экспериментов, используя аналитические функции. Основным интересующим запросом был бы запрос минимального времени выполнения каждого эксперимента по всем проведенным экспериментам, сгруппированным по числу процессоров и размеру задачи. Таким запросом мы можем найти те конфигурации, в которых производительность была максимальной. Возможно использование и других запросов к собранной базе данных. Этими запросами можно узнать динамику изменений, каких либо параметров при изменениях других параметров запуска.
11. Из результатов запросов содержащих значения параметров и временя выполнения можно получить другие характеристики работы приложения, например значение производительности и эффективности. Для этого необходимо для каждого значения времени выполнения применить формулу вычисления производительности и эффективности. Для получения производительности необходимо оценить вычислительную сложность на рассматриваемом участке программы. Как правило, вычислительная сложность зависит от размера задачи. Производительность будет получена путем деления числительной сложности на время выполнения. Эффективность работы приложения можно вычислять как отношение полученной производительности к пиковой производительности. Пиковая производительность на данной конфигурации получается путем умножения числа процессов на пиковую производительность одного процессорного ядра.
12. Получаем двумерную сетку значений изменения производительности и эффективности по всем рассмотренным значениям числа процессоров и рассматриваемым размерам задачи или другим параметрам. Полученные данные можно дальнейшего анализа масштабируемости параллельного приложения.

2 Выведение метрики масштабируемости

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

Для расчета метрики рассмотрим выборку результатов экспериментов, сгруппированным по одинаковому числу процессов (Pn) и по размеру решаемой задачи (Dn), и при максимальной эффективности выполнения программы по всем проведенным запускам. Результаты эксперимента сгруппируем в группы по четыре значения эффективности из соседних значений с близкими параметрами запуска так, чтобы такими группами покрыть всю рассматриваемую область параметров. Такие группы значений будем называть элементами рассматриваемой области значений параметров. Тогда в рассматриваемой трехмерной сетке значений (по числу процессоров и размеру задачи) у каждой точки будет 3 соседних значения (для результата со значениями параметров Pn,Dn соседними будут результаты со значениями Pn+1,Dn, Pn,Dn+1, Pn+1,Dn+1). Следовательно, три соседние точки будут у всех результатов, у которых значения параметров отличны от максимальных Pn < max{Pn} и Dn<max{Dn}. Но соседние результаты не будут найдены, если по каким-то причинам были пропущены какие-либо конфигурации запуска. В этом случае можно составить три соседние точки так, чтобы соседними стали те результаты, значения которых следуют за пропущенными. Таким образом, мы разобьем рассматриваемую область значений параметров на отдельные элементы (Рисунок). Для минимальной конфигурации запуска (Pn,Dn) можно найти ее соседние значения, так как в рассматриваемых результатах серии экспериментов изменяется число процессов и размер задачи. Далее, начиная с минимальной конфигурации, необходимо найти соседние значения для всех рассматриваемых результатов, для которых можно найти 3 соседние точки. Полученные группы результатов 4-х экспериментов с соседними значениями будем рассматривать как массив значений эффективности (E11 ,E12, E21, E22).