Scalability methodology

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

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. Получаем двумерную сетку значений изменения производительности и эффективности по всем рассмотренным значениям числа процессоров и рассматриваемым размерам задачи или другим параметрам. Полученные данные можно дальнейшего анализа масштабируемости параллельного приложения.