commit d6422fa977574dc0f124fe92c061691ff08fd616
parent eb12725ef135ec043d0347dd0054f8ae2a58b5ee
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Tue, 7 Nov 2017 20:05:50 +0300
Edit benchmarks.
Diffstat:
3 files changed, 153 insertions(+), 154 deletions(-)
diff --git a/R/benchmarks.R b/R/benchmarks.R
@@ -219,7 +219,7 @@ arma.aggregate_by_size <- function (data, framework) {
}
arma.filter_copy_to_host <- function (data) {
- data[data["routine"] == "harts_copy_to_host",]
+ data[data["routine"] != "harts_copy_to_host",]
}
arma.add_text <- function (data, str, pos=4, off=1) {
@@ -244,7 +244,7 @@ arma.plot_realtime_data <- function (data, ...) {
box()
arma.add_text(openmp, "OpenMP", pos=3, off=1.5)
arma.add_text(opencl, "OpenCL", pos=3, off=1.5)
- arma.add_text(opengl, "OpenCL/OpenGL")
+ arma.add_text(opengl, "OpenCL/OpenGL", pos=3, off=-1.5)
}
arma.filter_by_framework_and_size <- function (data, size, framework) {
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -1794,37 +1794,36 @@ arma.plot_nonlinear(file.path("build", "nit-standing"), args)
:CUSTOM_ID: sec-parallel
:END:
-Несмотря на то что модели АР и СС являются частью одной смешанной модели АРСС,
-они имеют разные параллельные алгоритмы, которые отличаются от тривиального
+Несмотря на то что модели АР и СС являются частью одной смешанной модели, они
+имеют разные параллельные алгоритмы, которые отличаются от тривиального
алгоритма модели ЛХ. Алгоритм АР заключается в разбиении взволнованной
поверхности на трехмерные части одинакового размера вдоль каждой из координатных
осей и их параллельном вычислении с учетом каузальных ограничений, накладываемых
авторегрессионными зависимостями между точками поверхности. В модели СС такие
-зависимости между точками поверхности отсутствуют, а ее формула представляет
-собой свертку белого шума с коэффициентами модели, которая сводится к вычислению
-трех преобразований Фурье посредством теоремы о свертке. Таким образом, алгоритм
-СС заключается в параллельном вычислении свертки, которая основана на
-параллельном вычислении БПФ. Наконец, алгоритм ЛХ делается параллельным простым
-вычислением каждой точки параллельно в нескольких потоках. Таким образом,
-параллельная реализация модели АРСС включает в себя два параллельных алгоритма,
-по одному для каждой составляющей модели, которые сложнее, чем алгоритм для
-модели ЛХ.
+зависимости отсутствуют, а ее формула представляет собой свертку белого шума с
+коэффициентами модели, которая сводится к вычислению трех преобразований Фурье
+посредством теоремы о свертке. Таким образом, алгоритм СС заключается в
+параллельном вычислении свертки, которая основана на вычислении БПФ. Наконец,
+алгоритм ЛХ делается параллельным простым вычислением каждой точки параллельно в
+нескольких потоках. Таким образом, параллельная реализация модели АРСС включает
+в себя два параллельных алгоритма, по одному для каждой составляющей модели,
+которые сложнее, чем алгоритм для модели ЛХ.
Основная особенность формулы модели АР\nbsp{}--- авторегрессионные зависимости
между точками взволнованной поверхности по каждому из измерений,\nbsp{}---
который препятствуют параллельному вычислению каждой точки поверхности. Вместо
этого поверхность разделяется на равные части по каждому из измерений, и для
каждой части устанавливаются информационные зависимости, определяющие порядок
-вычисления. На рис.\nbsp{}[[fig-ar-cubes]] показаны эти зависимости. Здесь стрелка
-обозначает зависимость одной части от наличия другой, т.е. вычисление части
-может начаться, только если все части, от которых она зависит, уже вычислены.
-Здесь часть \(A\) не имеет зависимостей, части \(B\) и \(D\) зависят только от
-\(A\), а часть \(E\) зависит от \(A\), \(B\) и \(C\). В общем случае, каждая
-часть зависит от всех частей, имеющих предыдущий индекс хотя бы по одному из
-измерений (если такие части существуют). Первая часть не имеет никаких
-зависимостей, а размер части по каждому из измерений выбирается большим или
+вычисления. На рис.\nbsp{}[[fig-ar-cubes]] показаны эти зависимости. Стрелка
+обозначает зависимость одной части от наличия другой, т.е.\nbsp{}вычисление
+части может начаться, только если все части, от которых она зависит, уже
+вычислены. Здесь часть \(A\) не имеет зависимостей, части \(B\) и \(D\) зависят
+только от \(A\), а часть \(E\) зависит от \(A\), \(B\) и \(C\). В общем случае,
+каждая часть зависит от всех частей, имеющих предыдущий индекс хотя бы по одному
+из измерений (если такие части существуют). Первая часть не имеет никаких
+зависимостей; размер каждой части по каждому из измерений выбирается большим или
равным количеству коэффициентов по соответствующему измерению, чтобы принимать
-во внимание только прилегающие части.
+во внимание только прилегающие части в разрешении зависимостей.
#+name: fig-ar-cubes
#+header: :width 5 :height 5
@@ -1843,9 +1842,9 @@ arma.plot_ar_cubes_2d(3, 3, xlabel="Индекс части (X)", ylabel="Инд
частей), извлекает эту часть из очереди, генерирует взволнованную поверхность
для этой части и устанавливает состояние завершения. Алгоритм заканчивается,
когда очередь становится пустой. Доступ к очереди из разных потоков
-синхронизируется посредством блокировок. Алгоритм подходит для SMP машин, а для
-MPP части, от которых зависит данная, должны быть предварительно скопированы на
-узел, на котором будут проводится вычисления.
+синхронизируется посредством блокировок. Алгоритм подходит для SMP машин; в
+случае MPP части, от которых зависит данная, должны быть предварительно
+скопированы на узел, на котором будут проводится вычисления.
Таким образом, параллельный алгоритм модели АР сводится к созданию
минималистичного планировщика задач, в котором
@@ -1870,7 +1869,7 @@ MPP части, от которых зависит данная, должны б
вычисляется параллельно для каждой части, домножается на заранее вычисленное
преобразование Фурье от коэффициентов и обратное преобразование Фурье
вычисляется от результата. После этого, каждая часть записывается в выходной
-массив, а перекрывающие друг друга точки (из-за заполнения нулями) складываются
+массив, а перекрывающие друг друга (из-за заполнения нулями) точки складываются
друг с другом. Этот алгоритм известен в области обработки сигналов как
"overlap-add"\nbsp{}cite:svoboda2011efficient. Заполнение нулями необходимо для
предотвращения маскированных ошибок: без него результатом вычислений была бы
@@ -1878,11 +1877,11 @@ MPP части, от которых зависит данная, должны б
Несмотря на то что алгоритм модели СС разбивает поверхность на те же самые части
(но, возможно, другого размера), что и алгоритм модели АР, отсутствие
-авторегрессионных зависимостей между ними позволяет вычислять из параллельно без
+авторегрессионных зависимостей между ними позволяет вычислять их параллельно без
использования специализированного планировщика задач. Однако, этот алгоритм
также требует дополнение каждой части нулями, чтобы результат вычислений
совпадал с результатом, полученным по исходной формуле модели СС. Таким образом,
-алгоритм модели СС лучше масштабируется а большое количество узлов ввиду
+алгоритм модели СС лучше масштабируется на большое количество узлов ввиду
отсутствия информационных зависимостей между частями, но размер частей больше,
чем в алгоритме модели АР.
@@ -1895,42 +1894,41 @@ MPP части, от которых зависит данная, должны б
процессоре, что делает видеокарту еще более выгодным выбором.
Итого, несмотря на то что модели АР и СС являются составными частями одной
-смешанной модели АРСС, их параллельные алгоритмы фундаментально отличаются и
-являются более сложными, чем тривиальный параллельный алгоритм модели ЛХ.
-Эффективная реализация алгоритма АР требует специализированного планировщика
-задач для учета авторегрессионных зависимостей между частями взволнованной
-поверхности, в то время как алгоритм СС требует дополнения каждой части нулями,
-чтобы иметь возможность обработать из параллельно. В отличие от этих моделей, в
-модели ЛХ отсутствуют информационные зависимости между частями, но она также
-требует больше вычислительных ресурсов (операций с плавающей точкой в секунду)
-ввиду наличия трансцендентных функций в формуле.
+смешанной модели, их параллельные алгоритмы фундаментально отличаются и являются
+более сложными, чем тривиальный параллельный алгоритм модели ЛХ. Эффективная
+реализация алгоритма АР требует специализированного планировщика задач для учета
+авторегрессионных зависимостей между частями взволнованной поверхности, в то
+время как алгоритм СС требует дополнения каждой части нулями, чтобы иметь
+возможность обработать их параллельно. В отличие от этих моделей, в модели ЛХ
+отсутствуют информационные зависимости между частями, но она также требует
+больше вычислительных ресурсов (операций с плавающей точкой в секунду) для
+трансцендентных функций в формуле.
**** Производительность реализаций на OpenMP и OpenCL.
:PROPERTIES:
:header-args:R: :results output raw :exports results
:END:
-Разница параллельных алгоритмов моделей делает их эффективными на разных
-архитектурах процессоров, и для того чтобы найти наиболее эффективную все модели
-были протестированы на процессоре и видеокарте.
-
-Модель АРСС не требует высоко оптимизированных кодов для того чтобы быть
-эффективными, его производительность высокая и без использования сопроцессоров;
-на это есть две причины. Во-первых, сама модель АРСС не использует
-трансцендентные функции (синусы, косинусы и экспоненты) в отличие от модели ЛХ.
-Все вычисления (исключая коэффициенты модели) производятся через полиномы,
-которые эффективно вычисляются на современных процессорах, используя
-последовательность инструкций FMA. Во-вторых, вычисления давлений происходит по
-явной аналитической формуле, используя несколько БПФ. Поскольку двухмерное БПФ
-одного и того же размера постоянно вычисляется на каждом временном срезе, его
-коэффициенты (комплексные экспоненты) вычисляются один раз для всех временных
-срезов, и дальнейшие вычисления включают в себя лишь несколько трансцендентных
-функций. В случае модели СС, производительность также повышается за счет
-вычисления свертки с помощью БПФ. Таким образом, высокая производительность
-модели АРСС обусловлена скудным использованием трансцендентных функций и
-интенсивным использованием БПФ, не говоря уже о том что высокая сходимость и
-отсутствие периодичности позволяют использовать гораздо меньше коэффициентов по
-сравнению с моделью ЛХ.
+Различия в параллельных алгоритмах моделей делает их эффективными на разных
+архитектурах процессоров, и для того чтобы найти наиболее эффективную из них,
+все модели были протестированы как на процессоре, так и на видеокарте.
+
+Модели АР и СС не требуют высоко оптимизированных кодов, для того чтобы быть
+эффективными, их производительность высокая и без использования сопроцессоров;
+на это есть две причины. Во-первых, эти модели не используют трансцендентные
+функции (синусы, косинусы и экспоненты) в отличие от модели ЛХ. Все вычисления
+(исключая коэффициенты модели) производятся через полиномы, которые эффективно
+вычисляются на современных процессорах, используя инструкции FMA. Во-вторых,
+вычисление давлений происходит по явной формуле с использованием нескольких
+вложенных БПФ. Поскольку двухмерное БПФ одного и того же размера постоянно
+вычисляется на каждом временном срезе, его коэффициенты (комплексные экспоненты)
+вычисляются один раз для всех временных срезов, а дальнейшие вычисления включают
+в себя лишь несколько трансцендентных функций. В случае модели СС,
+производительность также повышается за счет вычисления свертки с помощью БПФ.
+Таким образом, высокая производительность моделей АР и СС обусловлена скудным
+использованием трансцендентных функций и интенсивным использованием БПФ, не
+говоря уже о том, что высокая скорость сходимости и отсутствие периодичности
+позволяют использовать гораздо меньше коэффициентов по сравнению с моделью ЛХ.
#+name: tab-gpulab
#+caption: Конфигурация системы Gpulab.
@@ -1943,17 +1941,17 @@ MPP части, от которых зависит данная, должны б
| Количество процессорных ядер | 4 |
| Количество потоков на ядро | 2 |
-Программа АРСС использует несколько библиотек математических функций, численных
-алгоритмов и примитивов визуализации (перечисленных в таб.\nbsp{}[[tab-arma-libs]]),
-и написана с использованием нескольких технологий параллельного программирования
-(OpenMP, OpenCL), чтобы найти наиболее эффективную. Для каждой технологии и
-каждой модели была оптимизирована генерация взволнованной поверхности (за
-исключением модели СС, для которой была сделана только реализация OpenMP).
-Вычисление потенциала скорости было реализована на OpenMP, реализация на OpenCL
-была сделана только для визуализации взволнованной поверхности в реальном
-времени. Для каждой технологии программа перекомпилировалась, запускалась
-несколько раз и измерялась производительность каждой высокоуровневой функции
-посредством системных часов.
+Программа реализация использует несколько библиотек математических функций,
+численных алгоритмов и примитивов визуализации (перечисленных в
+таб.\nbsp{}[[tab-arma-libs]]), и написана с использованием нескольких технологий
+параллельного программирования (OpenMP, OpenCL) для возможности выбора наиболее
+эффективной. Для каждой технологии и каждой модели была оптимизирована генерация
+взволнованной поверхности (за исключением модели СС, для которой была сделана
+только реализация OpenMP). Вычисление потенциала скорости было реализовано на
+OpenMP, реализация на OpenCL была сделана только для визуализации взволнованной
+поверхности в реальном времени. Для каждой технологии программа
+перекомпилировалась, запускалась несколько раз и измерялась производительность
+каждой высокоуровневой функции посредством системных часов.
Результаты тестирования представлены в таб.\nbsp{}[[tab-arma-performance]]. Все
тесты запускались на машине с видеокартой, характеристики которой собраны в
@@ -1961,12 +1959,12 @@ MPP части, от которых зависит данная, должны б
параметрами для всех моделей: реализация длиной в 10000 сек. и размер выходной
сетки \(40\times40\)м. Единственный параметр, который отличался, это порядок
(количество коэффициентов): порядок моделей АР и СС был выбран равным \(7,7,7\),
-а порядок модели ЛХ \(40,40\). Это связано с большим количеством коэффициентов,
-необходимым для исключения периодичности модели ЛХ.
+а порядок модели ЛХ \(40,40\). Это связано с б\oacute{}льшим количеством
+коэффициентов, необходимым для исключения периодичности модели ЛХ.
-Во всех тестах генерация взволнованной поверхности и НБП занимают большую часть
-времени счета, в то время как вычисления потенциала скорости вместе с остальными
-подпрограммами лишь малую его часть.
+Во всех тестах генерация взволнованной поверхности и НБП занимают
+б\oacute{}льшую часть времени работы, а вычисление потенциала скорости вместе с
+остальными подпрограммами лишь малую его часть.
#+name: tab-arma-libs
#+caption: Список библиотек, используемых в программе АРСС.
@@ -1983,10 +1981,10 @@ MPP части, от которых зависит данная, должны б
Модель АР показывает наибольшую производительность в реализации на OpenMP и
наименьшую в реализации на OpenCL, что также является наибольшей и наименьшей
-производительностью среди всех комбинация моделей и технологий. В самой
+производительностью среди всех комбинаций моделей и технологий. В самой
оптимальной комбинации производительность АР в 4,5 раз выше, чем
производительность СС, и в 20 раз выше, чем производительность ЛХ; в самой
-неоптимальной конфигурация\nbsp{}--- в 137 раз медленней, чем СС и в два раза
+неоптимальной комбинации\nbsp{}--- в 137 раз медленней, чем СС и в два раза
медленней, чем ЛХ. Отношение между наибольшей (OpenMP) и наименьшей (OpenCL)
производительностью модели АР составляет несколько сотен. Это объясняется тем,
что формула модели\nbsp{}eqref:eq-ar-process эффективно отображается на
@@ -2013,8 +2011,8 @@ MPP части, от которых зависит данная, должны б
Наконец, архитектура видеокарты не содержит примитивы синхронизации, позволяющих
эффективно реализовать авторегрессионные зависимости между отдельными частями
взволнованной поверхности; вместо этого отдельная подпрограмма OpenCL
-запускается для каждой части, а управление зависимостями между ними
-осуществляется на стороне центрального процессора. Таким образом, в случае
+запускается для каждой части, а управление информационными зависимостями между
+ними осуществляется на стороне центрального процессора. Таким образом, в случае
модели АР архитектура центрального процессора превосходит архитектуру
видеокарты, поскольку более эффективно обрабатывает сложные информационные
зависимости, простые вычисления (сложения и умножения) и сложные шаблоны доступа
@@ -2072,16 +2070,16 @@ arma.print_openmp_vs_opencl(model_names, row_names)
Несмотря на то что видеокарта на тестовой системе более производительна, чем
центральный процессор (с точки зрения операций с плавающей точкой в секунду),
общая производительность модели ЛХ по сравнению с моделью АР меньше. Причиной
-этого служит медленная передача данных между памятью видеокарты и центрального
+этому служит медленная передача данных между памятью видеокарты и центрального
процессора.
Модель СС быстрее, чем модель ЛХ, но медленнее, чем модель АР. Поскольку свертка
в ее формуле реализована с помощью БПФ, ее производительность зависит от
-производительности реализации БПФ: библиотека GSL для центрального процессора и
-clFFT для видеокарты. В данной работе производительность модели СС на видеокарте
-не была протестирована ввиду недоступности трехмерного БПФ в библиотеке clFFT;
-если бы преобразование было доступно, оно могло бы сделать модель даже более
-быстрой, чем АР.
+производительности реализации БПФ: библиотека GSL в случае центрального
+процессора и clFFT в случае видеокарты. В данной работе производительность
+модели СС на видеокарте не была протестирована ввиду недоступности трехмерного
+БПФ в библиотеке clFFT; если бы преобразование было доступно, оно могло бы
+сделать модель даже более быстрой, чем АР.
НБП занимает меньше времени на видеокарте, чем на центральном процессоре,
однако, если принять во внимание время передачи данных между ними, время
@@ -2108,8 +2106,8 @@ clFFT для видеокарты. В данной работе производ
временного среза завершена (рис.\nbsp{}[[fig-arma-io-events]]): запускается
отдельный поток, который начинает запись, как только первый временной срез
становится доступен, и завершает, после того как основная группа потоков
-заканчивает вычисления, и последний срез записывается в файл. Суммарное время,
-затрачиваемое на ввод/вывод, увеличиваться, но суммарное время работы программы
+заканчивает вычисления и последний срез записывается в файл. Суммарное время,
+затрачиваемое на ввод/вывод, увеличивается, но суммарное время работы программы
уменьшается, поскольку ввод/вывод производится параллельно вычислениям
(таб.\nbsp{}[[tab-arma-io-performance]]). Использование этого подхода для локальных
систем имеет тот же эффект, но выигрыш в производительности меньше.
@@ -2167,7 +2165,7 @@ arma.plot_io_events(names)
занимает лишь малую долю суммарного времени работы программы, однако, абсолютное
время вычисления на плотной сетке \(XY\) может быть большим. Одно из приложений,
в котором используется плотная сетка,\nbsp{}--- это имитационное моделирование и
-визуализация в реальном времени взволнованной поверхности. Визуализации в
+визуализация в реальном времени взволнованной поверхности. Визуализация в
реальном времени позволяет
- настроить параметры модели и АКФ, мгновенно получая результат изменений, и
- визуально сравнить размер и форму областей, в которых сконцентрирована
@@ -2187,7 +2185,7 @@ arma.plot_io_events(names)
- она явная и не имеет информационных зависимостей между отдельными точками в
измерениях \(t\) и \(z\).
-Для того чтобы выяснить, насколько использование видеокарты может ускорить
+Для того чтобы выяснить, на сколько использование видеокарты может ускорить
вычисления поля потенциала скорости, была протестирована упрощенная
версия\nbsp{}eqref:eq-phi-3d:
\begin{align}
@@ -2202,9 +2200,9 @@ arma.plot_io_events(names)
Код, вычисляющий потенциал скорости, был переписан на языке OpenCL и его
производительность сравнивалась с реализацией на OpenMP.
-Для каждой реализации измерялось время работы выбранных подпрограмм и время
-передачи данных между устройствами. Поле потенциала скорости вычислялось для
-одной точки по оси \(t\), 128 точек по оси \(z\), расположенных под
+Для каждой реализации измерялось время работы соответствующих подпрограмм и
+время передачи данных между устройствами. Поле потенциала скорости вычислялось
+для одной точки по оси \(t\), 128 точек по оси \(z\), расположенных под
взволнованной поверхностью, и для каждой точки по оси \(x\) и \(y\)
четырехмерной сетки \((t,x,y,z)\). Между запусками программы изменялся размер
сетки по оси \(x\).
@@ -2220,7 +2218,7 @@ arma.plot_io_events(names)
автоматически, в то время как библиотека GSL выдает искаженные значения в этой
точке, поэтому с случае GSL значения в этих точках интерполируются.
Другие отличия подпрограмм БПФ, влияющие на производительность, не были
-найдены.
+выявлены.
**** Производительность кода OpenCL, вычисляющего поле потенциала скорости.
:PROPERTIES:
@@ -2228,12 +2226,12 @@ arma.plot_io_events(names)
:END:
Эксперименты показали, что реализация OpenCL превосходит OpenMP по
-производительности в 10--15 раз (рис.\nbsp{}[[fig-arma-realtime-graph]]), однако,
+производительности в 2--6 раз (рис.\nbsp{}[[fig-arma-realtime-graph]]), однако,
распределение времени работы между подпрограммами отличается
(таб.\nbsp{}[[tab-arma-realtime]]). В случае процессора больше всего времени
тратится на вычисление \(g_1\), а в случае видеокарты время вычисления \(g_1\)
сопоставимо с \(g_2\). Копирование результирующего поля потенциала скорости
-между процессором и видеокартой занимает \(\approx{}20\%\) общего времени
+между процессором и видеокартой занимает \(\approx{}70\%\) общего времени
вычисления этого поля. Вычисление \(g_2\) занимает больше всего времени в случае
OpenCL и меньше всего времени в случае OpenMP. В обоих реализациях \(g_2\)
вычисляется на центральном процессоре, поскольку готовая подпрограмма вычисления
@@ -2314,8 +2312,9 @@ OpenGL увеличивает производительность путем и
в этот формат выполняется быстро, однако он требует больше памяти, поскольку
каждая точка записывается как вектор из трех компонент. Другим недостатком
совместного использования OpenCL и OpenGL является требование ручной блокировки
-общего буфера: невыполнение этого требования может стать причиной артефактов
-изображения на экране, которые можно убрать, только перезагрузив компьютер.
+общего буфера: невыполнение этого требования может стать причиной появления
+артефактов изображения на экране, которые можно убрать, только перезагрузив
+компьютер.
**** Заключение.
Тесты показали, что видеокарта превосходит центральный процессор по
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -1759,35 +1759,34 @@ work.
:CUSTOM_ID: sec-parallel
:END:
-Although, AR and MA models are part of the single mixed ARMA model they have
+Although, AR and MA models are part of the single mixed model they have
disparate parallel algorithms, which are different from trivial one of LH model.
AR algorithm consists in partitioning wavy surface into equally-sized
three-dimensional parts in each dimension and computing them in parallel taking
into account causal constraints imposed by autoregressive dependencies between
-surface points. There are no such dependencies between surface points in MA
-model, and its formula represents convolution of white noise with model
-coefficients, which is reduced to computation of three Fourier transforms via
-convolution theorem. So, MA algorithm consists in parallel computation of the
-convolution which is based on parallel FFT computation. Finally, LH algorithm is
-made parallel by simply computing each wavy surface point in parallel in several
-threads. So, parallel implementation of ARMA model consists of two parallel
-algorithms, one for each part of the model, which are more sophisticated than
-the one for LH model.
+surface points. There are no such dependencies in MA model, and its formula
+represents convolution of white noise with model coefficients, which is reduced
+to computation of three Fourier transforms via convolution theorem. So, MA
+algorithm consists in parallel computation of the convolution which is based on
+FFT computation. Finally, LH algorithm is made parallel by simply computing each
+wavy surface point in parallel in several threads. So, parallel implementation
+of ARMA model consists of two parallel algorithms, one for each part of the
+model, which are more sophisticated than the one for LH model.
AR model's formula main feature is autoregressive dependencies between wavy
surface points in each dimension which prevent computing each surface point in
parallel. Instead the surface is partitioned along each dimension into equal
three-dimensional parts, and for each part information dependencies, which
define computation order, are established. Figure\nbsp{}[[fig-ar-cubes]] shows these
-dependencies. Here arrow denotes dependency of one part on availability of
-another, i.e. computation of a part may start only when all parts on which it
-depends were computed. Here part \(A\) does not have dependencies, parts \(B\)
-and \(D\) depend only on \(A\), and part \(E\) depends on \(A\), \(B\) and
+dependencies. An arrow denotes dependency of one part on availability of
+another, i.e.\nbsp{}computation of a part may start only when all parts on which
+it depends were computed. Here part \(A\) does not have dependencies, parts
+\(B\) and \(D\) depend only on \(A\), and part \(E\) depends on \(A\), \(B\) and
\(C\). In essence, each part depends on all parts that have previous index in at
least one dimension (if such parts exist). The first part does not have any
-dependencies, and the size of each part along each dimension is made greater or
+dependencies; and the size of each part along each dimension is made greater or
equal to the corresponding number of coefficients along the dimension to
-consider only adjacent parts.
+consider only adjacent parts in dependency resolution.
#+name: fig-ar-cubes
#+header: :width 5 :height 5
@@ -1806,7 +1805,7 @@ dependencies are satisfied (by checking the completion status of each part),
removes the part from the queue, generates wavy surface for this part and sets
completion status. The algorithm ends when the queue becomes empty. Access to
the queue from different threads is synchronised by locks. The algorithm is
-suitable for SMP machines, for MPP all parts on which the current one depends,
+suitable for SMP machines; for MPP all parts on which the current one depends,
dependent parts needs to be copied to the node where computation is carried out.
So, parallel AR model algorithm reduces to implementing minimalistic job
@@ -1831,7 +1830,7 @@ match the number of the coefficients along each dimension multiplied by two.
Then Fourier transform of each part is computed in parallel, multiplied by
previously computed Fourier transform of the coefficients, and inverse Fourier
transform of the result is computed. After that, each part is written to the
-output array with overlapping points (due to padding) added to each other. This
+output array with overlapping (due to padding) points added to each other. This
algorithm is commonly known in signal processing as
"overlap-add"\nbsp{}cite:svoboda2011efficient. Padding with noughts is needed to
prevent aliasing errors: without it the result would be circular convolution.
@@ -1854,15 +1853,15 @@ hardware thread simply computes its own point. In addition, sine and cosine
functions in the model's formula are slow to compute on CPU, which makes GPU
even more favourable choice.
-To summarise, even though AR and MA models are part of the single mixed ARMA
-model, their parallel algorithms are fundamentally different and are more
-complicated than trivial parallel algorithm of LH model. Efficient
-implementation AR algorithm requires specialised job scheduler to manage
-autoregressive dependencies between wavy surface parts, whereas MA algorithm
-requires padding each part with noughts to be able to compute them in parallel.
-In contrast to these models, LH model has no information dependencies between
-parts, but requires more computational resources (floating point operations per
-seconds) to calculate transcendental functions in its formula.
+To summarise, even though AR and MA models are part of the single mixed model,
+their parallel algorithms are fundamentally different and are more complicated
+than trivial parallel algorithm of LH model. Efficient implementation AR
+algorithm requires specialised job scheduler to manage autoregressive
+dependencies between wavy surface parts, whereas MA algorithm requires padding
+each part with noughts to be able to compute them in parallel. In contrast to
+these models, LH model has no information dependencies between parts, but
+requires more computational resources (floating point operations per seconds)
+for transcendental functions in its formula.
**** Performance of OpenMP and OpenCL implementations.
:PROPERTIES:
@@ -1870,20 +1869,20 @@ seconds) to calculate transcendental functions in its formula.
:END:
Differences in models' parallel algorithms make them efficient on different
-processor architectures, and to find the most efficient one all the models were
+processor architectures, and to find the most efficient one, all the models were
benchmarked in both CPU and GPU.
-ARMA model does not require highly optimised codes to be efficient, its
+AR and MA models do not require highly optimised codes to be efficient, their
performance is high even without use of co-processors; there are two main causes
-of that. First, ARMA model itself does not use transcendental functions (sines,
-cosines and exponents) as opposed to LH model. All calculations (except model
+of that. First, these models do not use transcendental functions (sines, cosines
+and exponents) as opposed to LH model. All calculations (except model
coefficients) are done via polynomials, which can be efficiently computed on
-modern processors using a series of FMA instructions. Second, pressure
-computation is done via explicit analytic formula using nested FFTs. Since
-two-dimensional FFT of the same size is repeatedly applied to every time slice,
-its coefficients (complex exponents) are pre-computed one time for all slices,
-and further computations involve only a few transcendental functions. In case of
-MA model, performance is also increased by doing convolution with FFT. So, high
+modern processors using FMA instructions. Second, pressure computation is done
+via explicit formula using a number of nested FFTs. Since two-dimensional FFT of
+the same size is repeatedly applied to every time slice, its coefficients
+(complex exponents) are pre-computed one time for all slices, and further
+computations involve only a few transcendental functions. In case of MA model,
+performance is also increased by doing convolution with FFT. So, high
performance of ARMA model is due to scarce use of transcendental functions and
heavy use of FFT, not to mention that high convergence rate and non-existence of
periodicity allows to use far fewer coefficients compared to LH model.
@@ -1899,15 +1898,16 @@ periodicity allows to use far fewer coefficients compared to LH model.
| No. of CPU cores | 4 |
| No. of threads per core | 2 |
-ARMA programme uses several libraries of mathematical functions, numerical
-algorithms and visualisation primitives (listed in table\nbsp{}[[tab-arma-libs]]),
-and was implemented using several parallel programming technologies (OpenMP,
-OpenCL) to find the most efficient one. For each technology and each model an
-optimised wavy surface generation was implemented (except for MA model for which
-only OpenMP implementation was done). Velocity potential computation was done in
-OpenMP and was implemented in OpenCL only for real-time visualisation of wavy
-surface. For each technology the programme was recompiled and run multiple times
-and performance of each top-level subroutine was measured using system clock.
+Software implementation uses several libraries of mathematical functions,
+numerical algorithms and visualisation primitives (listed in
+table\nbsp{}[[tab-arma-libs]]), and was implemented using several parallel
+programming technologies (OpenMP, OpenCL) to have a possibility to choose the
+most efficient one. For each technology and each model an optimised wavy surface
+generation was implemented (except for MA model for which only OpenMP
+implementation was done). Velocity potential computation was done in OpenMP and
+was implemented in OpenCL only for real-time visualisation of wavy surface. For
+each technology the programme was recompiled and run multiple times and
+performance of each top-level subroutine was measured using system clock.
Results of benchmarks of the technologies are summarised in
table\nbsp{}[[tab-arma-performance]]. All benchmarks were run on a machine equipped
@@ -1966,10 +1966,10 @@ model:
Finally, GPU architecture does not contain synchronisation primitives that allow
to implement autoregressive dependencies between distinct wavy surface parts;
instead of this a separate OpenCL kernel is launched for each part, and
-dependency management between them is done on CPU side. So, in AR model case CPU
-architecture is superior compared to GPU due to better handling of complex
-information dependencies, simple calculations (multiplications and additions)
-and complex memory access patterns.
+information dependency management between them is done on CPU side. So, in AR
+model case CPU architecture is superior compared to GPU due to better handling
+of complex information dependencies, simple calculations (multiplications and
+additions) and complex memory access patterns.
#+header: :results output raw :exports results
#+name: tab-arma-performance
@@ -2148,10 +2148,10 @@ field computation, we benchmarked simplified version of\nbsp{}eqref:eq-phi-3d:
Velocity potential computation code was rewritten in OpenCL and its performance
was compared to an existing OpenMP implementation.
-For each implementation running time of selected subroutines and time spent for
-data transfer between devices was measured. Velocity potential field was
-computed for one \(t\) point, for 128 \(z\) points below wavy surface and for
-each \(x\) and \(y\) point of four-dimensional \((t,x,y,z)\) grid. Between
+For each implementation running time of the corresponding subroutines and time
+spent for data transfer between devices was measured. Velocity potential field
+was computed for one \(t\) point, for 128 \(z\) points below wavy surface and
+for each \(x\) and \(y\) point of four-dimensional \((t,x,y,z)\) grid. Between
programme runs the size of the grid along \(x\) dimension was varied.
A different FFT library was used for each implementation: GNU Scientific Library
@@ -2164,7 +2164,7 @@ OpenCL. FFT routines from these libraries are different:
whereas GSL library produce skewed values at this point, thus in case of GSL
these points are interpolated.
Other differences of FFT subroutines, that have impact on performance, were not
-found.
+discovered.
**** Performance of velocity potential OpenCL solver.
:PROPERTIES:
@@ -2172,7 +2172,7 @@ found.
:END:
The experiments showed that OpenCL outperforms OpenMP implementation by a factor
-of 10--15 (fig.\nbsp{}[[fig-arma-realtime-graph]]), however, distribution of running
+of 2--6 (fig.\nbsp{}[[fig-arma-realtime-graph]]), however, distribution of running
time between subroutines is different (table\nbsp{}[[tab-arma-realtime]]). For CPU
the most of the time is spent to compute \(g_1\), whereas for GPU time spent to
compute \(g_1\) is comparable to \(g_2\). Copying the resulting velocity
@@ -2255,8 +2255,8 @@ format, that OpenGL can operate on. Conversion to this format is fast, but
requires more memory to store velocity potential field to be able to visualise
it, since each point now is a vector with three components. The other
disadvantage of using OpenCL and OpenGL together is the requirement for manual
-locking of shared buffer: failure to do so results in screen image artefacts
-which can be removed only by rebooting the computer.
+locking of shared buffer: failure to do so results in appearance of screen image
+artefacts which can be removed only by rebooting the computer.
**** Conclusions.
Benchmarks showed that GPU outperforms CPU in arithmetic intensive tasks,
