commit 88fb4e2fa4d1f06c01d80a8ac7cd9c99b42ad032
parent df87c1737cda6afbb2c63ed011202b655114efcd
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Tue, 31 Oct 2017 10:34:53 +0300
Outline the last part in Russian.
Diffstat:
2 files changed, 430 insertions(+), 417 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -1757,177 +1757,282 @@ arma.plot_nonlinear(file.path("build", "nit-standing"), args)
дальнейших исследований.
* Высокопроизводительный программный комплекс для моделирования морского волнения
-** Модель вычислений
-**** Отображение алгоритма генерации взволнованной поверхности на вычислительную модель.
-Модель АРСС реализована в программном комплексе, работающем по принципу
-вычислительного конвейера, в котором каждое звено применяет некоторую функцию к
-выходным данным предыдущего звена. Звенья конвейера распределяются по узлам
-вычислительного кластера, чтобы сделать возможным параллелизм по операциям, а
-затем данные, перемещающиеся между звеньями конвейера распределяются между
-ядрами процессора, чтобы сделать возможным параллелизм по данным. На рис.\nbsp{}[[fig-pipeline]] представлена схема конвейера обработки данных, в которой
-прямоугольниками со скругленными углами обозначены звенья конвейера, обычными
-прямоугольниками\nbsp{}--- массивы объектов из предметной области задачи, передаваемые
-от одного звена к другому, а стрелками\nbsp{}--- направление передачи данных.
-Некоторые звенья разделены на /секции/, каждая из которых обрабатывает отдельную
-часть массива. Если звенья соединены без использования /барьера/ (горизонтальная
-или вертикальная полоса), то передача отдельных объектов между такими звеньями
-происходит параллельно с вычислениями, по мере их готовности. Секции работают
-параллельно на нескольких ядрах процессора (нескольких узлах кластера). Таким
-образом, между множеством ядер процессора, секций звеньев конвейера и объектами
-устанавливается сюръективное отображение, т.е. на одном ядре процессора может
-работать несколько секций звеньев конвейера, каждая из которых может
-обрабатывать несколько объектов последовательно, но одна секция не может
-работать сразу на нескольких ядрах, а объект не может обрабатываться сразу
-несколькими секциями конвейера.
-
-#+name: fig-pipeline
-#+begin_src dot :exports results :file build/pipeline-ru.pdf
-digraph {
-
- node [fontsize=14,margin="0.055,0"]
- graph [nodesep="0.25",ranksep="0.25",rankdir="TB"]
- edge [arrowsize=0.66]
-
- # data
- subgraph xcluster_linear {
- label="Линейная модель"
-
- start [label="",shape=circle,style=filled,fillcolor=black,width=0.23]
- spectrum [label="S(ω,θ)",shape=box]
- acf [label="K(i,j,k)",shape=box]
- phi [label="Φ(i,j,k)",shape=box]
-
- # transformations
- fourier_transform [label="Преобразование Фурье",shape=box,style=rounded]
- solve_yule_walker [label="Решение уравнений\nЮла—Уокера",shape=box,style=rounded]
+** Реализация для систем с общей памятью (SMP)
+**** Параллельные алгоритмы для моделей АР, СС и ЛХ.
+**** Производительность реализаций на OpenMP и OpenCL.
+**** Производительность ввода-вывода.
+**** Параллельное вычисление поля потенциала скорости.
+**** Производительность OpenCL-решателя, вычисляющего поле потенциала скорости.
+**** Заключение.
+**** Алгоритм распределения нагрузки. :noexport:
+Наиболее простым и широко применяемым подходом к распределению нагрузки на
+вычислительную систему является разбиение данных на равные части (или разбиение
+задачи на однородные подзадачи) с последующим их равномерным распределением
+между отдельными ядрами процессора и узлами кластера, однако такой подход не
+всегда работает эффективно. Во-первых, часто общее количество частей, на которые
+разбиваются входные данные, диктуется не архитектурой и конфигурацией
+вычислительной системы, а самой задачей, и такое распределение не всегда
+эффективно с точки зрения вычислительной машины: количество частей оказывается
+либо слишком большим по сравнению с количеством процессоров, работающих
+параллельно, что ведет к увеличению накладных расходов на обмен данными, либо
+слишком маленьким, что не позволяет использовать все доступные вычислительные
+ядра. Во-вторых, накладываемые решаемой задачей ограничения могут не позволить
+разделить входные данные на равные части, что может стать причиной дисбаланса в
+загрузке ядер процессора. В-третьих, в вычислительной системе в вычислениях
+участвуют помимо процессора сразу несколько компонент (таких как векторные
+сопроцессоры и устройства хранения), то время решения конкретной задачи зависит
+от производительности всех задействованных устройств. Каким же образом сделать
+алгоритм распределения нагрузки более эффективным, принимая во внимание разный
+размер частей, на которые разделяются входные данные, и учитывая все устройства,
+задействованные в вычислениях?
- subgraph cluster_nonlinear_1 {
- label="Моделир. нелинейности\l"
- labeljust=left
- style=filled
- color=lightgrey
- acf2 [label="K*(i,j,k)",shape=box]
- transform_acf [label="Преобразование АКФ",shape=box,style=rounded]
- }
- }
+Алгоритм распределения нагрузки состоит из двух этапов. На первом этапе алгоритм
+размещает часть входных данных (или подзадачу), обернутую в управляющий объект,
+в соответствующем пуле управляющих объектов: для каждого устройства используется
+отдельный пул управляющих объектов и сопряженный с ним пул потоков. На втором
+этапе, управляющий объект извлекается из пула одним из потоков и обрабатывается.
+Благодаря отдельным пулам потоков все устройства работают параллельно, уменьшая
+тем самым время простоя оборудования по сравнению с использованием всех
+устройств из одного потока.
- subgraph xcluster_linear2 {
+Для того чтобы учесть неоднородность частей, на которые разбиваются входные
+данные, и неоднородность выполняемых задач, необходимо предсказать время
+выполнения каждой из задач. Соответствующее исследование сделано в\nbsp{}cite:degtyarev2016balance, поскольку реализация модели АРСС включает в себя, в
+основном, однородные задачи.
- eps_parts [label="<e1> ε₁|<e2> ε₂|<e3> …|<e4> εₙ|<e> ε(t,x,y)",shape=record]
- end [label="",shape=doublecircle,style=filled,fillcolor=black,width=0.23]
+Таким образом, распределение нагрузки осуществляется в два этапа: на первом
+этапе задача в форме урпавляющего объекта направляется на подходящее устройство,
+а на втором этапе она направляется в один из потоков из соответсвующего
+устройству пула. Неоднородность управляющих объектов может быть учтена путем
+предсказания времени их выполнения, однако такие объекты не встречаются в
+реализации модели АРСС.
- generate_white_noise [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Генерация\lбелого шума",shape=record,style=rounded]
- generate_zeta [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Генерация частей\lвзволнованной мор-\lской поверхности\l",shape=record,style=rounded]
+**** Производительность реализаций на MPI, OpenMP и OpenCL. :noexport:
+:PROPERTIES:
+:header-args:R: :results output org
+:END:
+Программная реализация состояла в создании и отладке прототипа программы и в
+последующем написании компоненты виртуального полигона на языке более низкого
+уровня. При этом тесты показали, что одной высокопроизводительной
+многопроцессорной машины достаточно для создания типовых реализаций морского
+волнения. Также использование видеокарт в качестве векторных ускорителей
+эффективно только в случае расчета давлений, в то время как генерация волновой
+поверхности выполняется быстрее на скалярном процессоре.
- zeta_parts [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> Несшитые части реализации",shape=record]
- overlap_add [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> Сшивание час-\lтей реализации\l",shape=record,style=rounded]
+Создание программной реализации происходило в два этапа: на первом этапе был
+создан и отлажен прототип в программной среде
+Mathematica\nbsp{}cite:mathematica10, а на втором этапе логика программы была
+переписана на более низкоуровневом языке C++, и для получения эффективно
+работающего параллельного кода были проведены эксперименты с рядом библиотек. С
+помощью этих библиотек были реализованы функции генерации взволнованной морской
+поверхности, а также процедура расчета гидродинамических давлений под
+сгенерированной поверхностью. Тестирование производилось на вычислительных
+машинах кластера РЦ ВЦ СПбГУ (см.\nbsp{}табл.\nbsp{}[[tab-autoreg-testbed]]) и
+позволило получить два основных результата. Во-первых, использование видеокарт
+неэффективно при генерации волновой поверхности
+(см.\nbsp{}табл.\nbsp{}[[tab-autoreg-performance]]), что обусловлено сравнительно
+небольшим количеством арифметических операций по отношению к количеству операций
+с памятью устройства, а также отсутствием трансцендентных функций в реализации
+алгоритма. Во-вторых, для генерации одной реализации взволнованной морского
+поверхности одной многопроцессорной машины достаточно для эффективного и
+быстрого решения задачи (см.\nbsp{}рис.\nbsp{}[[fig-autoreg-performance]]). По
+результатам тестирования стандарт OpenMP был выбран в качестве основного, как
+наиболее эффективный и наиболее подходящий для расчетов на многопроцессорной
+системе.
- zeta_parts:g1->overlap_add:g1
- zeta_parts:g2->overlap_add:g2
- zeta_parts:g3->overlap_add:g3
- zeta_parts:g4->overlap_add:g4
+#+name: fig-autoreg-performance
+#+caption: Скорость генерации взволнованной поверхности на многопроцессорной системе для типовых размеров реализации (сверху). Масштабируемость (относительное ускорение при увеличении количества процессоров) программной реализации на многопроцессорной системе для типовых размеров реализации (снизу). Временная протяженность 512 с.
+#+begin_figure
+[[file:graphics/speed.eps]]
+[[file:graphics/speedup.eps]]
+#+end_figure
- zeta_parts:g2->overlap_add:g1 [constraint=false]
- zeta_parts:g3->overlap_add:g2 [constraint=false]
- zeta_parts:g4->overlap_add:g3 [constraint=false]
+#+name: tab-autoreg-testbed
+#+caption: Конфигурация оборудования.
+#+attr_latex: :booktabs t
+| Вычислительная машина | HP SL390s G7 |
+| Процессор | 2\(\times\)Intel X5650 (всего 12 ядер) |
+| Оперативная память | 96ГБ RAM |
+| Операционная система | CentOS 5.6 (Linux) |
- overlap_add:g1->zeta2_parts:g1
- overlap_add:g2->zeta2_parts:g2
- overlap_add:g3->zeta2_parts:g3
- overlap_add:g4->zeta2_parts:g4
+#+name: tab-autoreg-performance
+#+caption: Время (с.) генерации взволнованной морской поверхности различными программными реализациями авторегрессионной модели.
+#+attr_latex: :booktabs t :align cllllll
+| | ЛХ | ЛХ | ЛХ | АР | АР | АР |
+| Размер | OpenCL | OpenMP | MPI | OpenCL | OpenMP | MPI |
+|--------+--------+--------+-------+--------+--------+-------|
+| 400000 | 0.82 | 40.44 | 32.60 | 1.80 | 0.800 | 0.750 |
+| 440000 | 0.90 | 44.59 | 35.78 | 1.92 | 0.100 | 0.930 |
+| 480000 | 0.99 | 48.49 | 38.93 | 2.29 | 0.970 | 0.126 |
+| 520000 | 1.07 | 52.65 | 41.92 | 2.43 | 0.118 | 0.117 |
+| 560000 | 1.15 | 56.45 | 45.00 | 2.51 | 0.117 | 0.161 |
+| 600000 | 1.23 | 60.85 | 48.80 | 2.54 | 0.123 | 0.132 |
+| 640000 | 1.31 | 65.07 | 53.02 | 2.73 | 0.123 | 0.160 |
+| 680000 | 1.40 | 68.90 | 54.92 | 2.80 | 0.138 | 0.136 |
+| 720000 | 1.48 | 72.49 | 58.42 | 2.88 | 0.144 | 0.173 |
+| 760000 | 1.56 | 76.86 | 61.41 | 3.47 | 0.156 | 0.155 |
+| 800000 | 1.64 | 81.03 | 66.42 | 3.25 | 0.166 | 0.174 |
- zeta2_parts:g1->transform_zeta:g1->zeta3_parts:g1->write_zeta:g1->eps_end
- zeta2_parts:g2->transform_zeta:g2->zeta3_parts:g2->write_zeta:g2->eps_end
- zeta2_parts:g3->transform_zeta:g3->zeta3_parts:g3->write_zeta:g3->eps_end
- zeta2_parts:g4->transform_zeta:g4->zeta3_parts:g4->write_zeta:g4->eps_end
+#+name: tab-arma-performance
+#+begin_src R :results output org :exports results
+source(file.path("R", "benchmarks.R"))
+model_names <- list(
+ ar.x="АР",
+ ma.x="СС",
+ lh.x="ЛХ",
+ ar.y="АР",
+ ma.y="СС",
+ lh.y="ЛХ",
+ Row.names="\\orgcmidrule{2-4}{5-6}Подпрограмма"
+)
+row_names <- list(
+ determine_coefficients="Определение коэффициентов",
+ validate="Проверка модели",
+ generate_surface="Генерация поверхности",
+ nit="НБП",
+ write_all="Запись вывода в файл",
+ copy_to_host="Копирование данных с GPU",
+ velocity="Выч. потенциалов скорости"
+)
+arma.print_openmp_vs_opencl(model_names, row_names)
+#+end_src
- }
+#+name: tab-arma-performance
+#+caption: Время работы (с.) реализации OpenMP и OpenCL для моделей АР, СС и ЛХ.
+#+attr_latex: :booktabs t
+#+RESULTS: tab-arma-performance
+#+BEGIN_SRC org
+| | | | OpenMP | | OpenCL |
+| \orgcmidrule{2-4}{5-6}Подпрограмма | АР | СС | ЛХ | АР | ЛХ |
+|------------------------------------+------+------+--------+--------+--------|
+| Определение коэффициентов | 0.02 | 0.01 | 0.19 | 0.01 | 1.19 |
+| Проверка модели | 0.08 | 0.10 | | 0.08 | |
+| Генерация поверхности | 1.26 | 5.57 | 350.98 | 769.38 | 0.02 |
+| НБП | 7.11 | 7.43 | | 0.02 | |
+| Копирование данных с GPU | | | | 5.22 | 25.06 |
+| Выч. потенциалов скорости | 0.05 | 0.05 | 0.06 | 0.03 | 0.03 |
+| Запись вывода в файл | 0.27 | 0.27 | 0.27 | 0.28 | 0.27 |
+#+END_SRC
- subgraph part3 {
+Кроме выбора стандарта параллельных вычислений на время работы программы влияет
+выбор библиотек типовых вычислительных методов, и эффективность этих библиотек
+была показана тестированием их разработчиками. В качестве библиотеки для
+матричных операций (расчета коэффициентов авторегрессионной модели) была выбрана
+GotoBLAS и основанная на ней LAPACK, для непрерывной аппроксимации поля волновых
+чисел использовалась библиотека CGAL\nbsp{}cite:fabri2009cgal и для статистической
+проверки интегральных характеристик реализации взволнованной поверхности
+использовалась библиотека GSL\nbsp{}cite:gsl2008scientific. В случае GotoBLAS
+эффективность библиотеки показана в работах\nbsp{}cite:goto2008high,goto2008anatomy,
+для других библиотек эффективность не является важной, и они были выбраны,
+исходя из удобства их использования.
- zeta2_parts [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> Поверхность с нормаль-\lным законом распреде-\lления\l",shape=record]
+#+name: tab-arma-libs
+#+caption: Список библиотек, используемых в реализации модели АРСС.
+#+attr_latex: :booktabs t
+| Библиотека | Назначение |
+|--------------------------------------------------------------+----------------------------------|
+| DCMT\nbsp{}cite:matsumoto1998dynamic | параллельный ГПСЧ |
+| Blitz\nbsp{}cite:veldhuizen1997will,veldhuizen2000techniques | многомерные массивы |
+| GSL\nbsp{}cite:gsl2008scientific | вычисление ФПР, ФР, БПФ |
+| | проверка стационарности процесса |
+| LAPACK, GotoBLAS\nbsp{}cite:goto2008high,goto2008anatomy | определение коэффициентов АР |
+| GL, GLUT\nbsp{}cite:kilgard1996opengl | трехмерная визуализация |
+| CGAL\nbsp{}cite:fabri2009cgal | триангуляция волновых чисел |
- subgraph cluster_nonlinear_2 {
- label="Моделир. нелинейности\r"
- labeljust=right
- style=filled
- color=lightgrey
- zeta3_parts [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> ζ(t,x,y)",shape=record]
- transform_zeta [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Преобразование за-\lкона распределения\lвзволнованной мор-\lской поверхности\l",shape=record,style=rounded]
- }
+**** Производительность алгоритма распределения нагрузки. :noexport:
+Программная реализация генерации взволнованной поверхности сбалансирована с
+точки зрения нагрузки на процессорные ядра, однако, как показывают тесты,
+характеризуется высокой нагрузкой на устройства хранения. До проведения
+тестирования генерация взволнованной поверхности была реализована с
+использованием OpenMP для параллельных вычислений, и была переписана с
+использованием POSIX потоков для того чтобы реализовать алгоритм распределения
+нагрузки. Производительность двух реализаций сравнивалась на платформе,
+конфигурация которой приведена в табл.\nbsp{}[[tab-multicore-specs]].
- # barriers
- eps_start [label="",shape=box,style=filled,fillcolor=black,height=0.05]
- eps_end [label="",shape=box,style=filled,fillcolor=black,height=0.05]
+#+name: tab-multicore-specs
+#+caption: Конфигурация многоядерной системы.
+#+attr_latex: :booktabs t
+| Компонента | Подробности |
+|-------------------------------+----------------------------------|
+| Язык программирования | C++11 |
+| Библиотека потоков | C++11 STL threads |
+| Библиотека атомарных операций | C++11 STL atomic |
+| Подпрограммы замера времени | ~clock_gettime(CLOCK_MONOTONIC)~ |
+| | ~/usr/bin/time -f \%e~ |
+| Компилятор | GCC 4.8.2 |
+| Опции компиляции | ~-std=c++11 -O2 -march=native~ |
+| Операционная система | Debian 3.2.51-1 x86_64 |
+| Файловая система | ext4 |
+| Процессор | Intel Core 2 Quad Q9650 |
+| Частота процессора (ГГц) | 3.00 |
+| Количество ядер | 4 |
+| Объем оперативной памяти (ГБ) | 8 |
+| Диск | Seagate ST3250318AS |
+| Скорость диска (об./мин.) | 7200 |
- write_zeta [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Запись готовых\lчастей в файл\l",shape=record,style=rounded]
- }
+Эксперимент состоял в запуске двух программных реализаций на многоядерной
+машине, изменяя размер поверхности. Размер пула потоков процессора и пула
+потоков ввода/вывода оставался неизменным во время эксперимента. Пул потоков
+ввода/вывода состоял из одного потока, а количество потоков процессора равнялось
+количеству физических ядер процессора.
- # edges
- start->spectrum->fourier_transform->acf->transform_acf
- transform_acf->acf2
- acf2->solve_yule_walker
- solve_yule_walker->phi
- phi->eps_start [constraint=false]
- eps_start->generate_white_noise:g1
- eps_start->generate_white_noise:g2
- eps_start->generate_white_noise:g3
- eps_start->generate_white_noise:g4
- generate_white_noise:g1->eps_parts:e1->generate_zeta:g1->zeta_parts:g1
- generate_white_noise:g2->eps_parts:e2->generate_zeta:g2->zeta_parts:g2
- generate_white_noise:g3->eps_parts:e3->generate_zeta:g3->zeta_parts:g3
- generate_white_noise:g4->eps_parts:e4->generate_zeta:g4->zeta_parts:g4
+В эксперименте алгоритм распределения нагрузки показал большую эффективность по
+сравнению с реализацией без него. Чем больше размер генерируемой поверхности,
+тем больше разрыв в производительности (рис.\nbsp{}[[fig-factory-performance]]), что
+является следствием наложения вычислительной фазы и фазы вывода данных друг на
+друга (рис.\nbsp{}[[fig-factory-overlap]]). В реализации OpenMP фаза вывода данных
+начинается только тогда, когда заканчивается вычислительная фаза, в то время как
+использование алгоритма распределения нагрузки приводит почти к одновременному
+завершению обеих фаз. Таким образом, /выполнение параллельных изнутри,
+последовательных фаз в режиме конвейера более эффективно, чем их
+последовательное выполнение/, и это позволяет сбалансировать нагрузку на
+различные устройства, задействованные в вычислениях.
- eps_end->end
-}
+#+name: fig-factory-performance
+#+header: :width 5 :height 4
+#+begin_src R :file build/factory-vs-openmp-ru.pdf
+source(file.path("R", "common.R"))
+arma.plot_factory_vs_openmp(
+ xlab="Размер реализации",
+ ylab="Время, с.",
+ power=6
+)
#+end_src
-#+caption: Схема конвейера обработки данных, реализующего генерацию взволнованной морской поверхности по АР модели.
-#+label: fig-pipeline
-#+RESULTS: fig-pipeline
-[[file:build/pipeline-ru.pdf]]
-
-Конвейер объектов можно считать развитием модели BSP (Bulk Synchronous
-Parallel)\nbsp{}cite:valiant1990bridging, применяемой в системах обработки
-графов\nbsp{}cite:malewicz2010pregel,seo2010hama. Конвейер позволяет исключить
-глобальную синхронизацию (где это возможно) между последовательно идущим этапами
-вычислений путем передачи данных между звеньев параллельно с вычислениями, в то
-время как в модели BSP глобальная синхронизация происходит после каждого шага.
-
-Конвейер объектов ускоряет программу путем параллельного выполнения блоков кода,
-работающих с разными вычислительными устройствами: в то время как текущая часть
-взолнованной поверхности генерируется на процессоре, предыдущая часть
-записывается на диск. Такой подход позволяет получить ускорение, потому что
-различные вычислительные устройства работают асинхронно, и их параллельное
-использование увеличивает производительность программы.
+#+caption: Сравнение производительности реализаций программы на OpenMP и Factory.
+#+label: fig-factory-performance
+#+RESULTS: fig-factory-performance
+[[file:build/factory-vs-openmp-ru.pdf]]
-Поскольку передача данных между звеньями конвейера происходит параллельно с
-вычислениями, то на одном и том же конвейере можно запустить сразу несколько
-копий приложения с разными параметрами (генерировать сразу несколько
-взволнованных морских поверхностей с разными характеристиками). На практике
-оказывается, что высокопроизводительные приложения не всегда загружают
-процессор на 100%, тратя время на синхронизацию параллельных процессов и
-запись данных на диск. Использование конвейера в таком случае позволит на одном
-и том же множестве процессов запустить сразу несколько расчетов и максимально
-эффективно использовать все устройства компьютера. Например, во время записи в
-файл одной задачей может производиться расчет на процессоре другой задачей. Это
-минимизирует время простоя процессора и других устройств компьютера и повышает
-общую пропускную способность кластера.
+#+name: fig-factory-overlap
+#+header: :width 7 :height 4
+#+begin_src R :file build/factory-vs-openmp-overlap-ru.pdf
+source(file.path("R", "common.R"))
+par(mar=c(5, 6, 0, 1), pty="m")
+arma.plot_factory_vs_openmp_overlap(
+ xlab="Время, с.",
+ labels=c("Factory", "OpenMP"),
+ scale=10**9
+)
+#+end_src
-Конвейеризация шагов программы, которые в противном случае последовательны,
-выгодно не только для кода, работающего с различными устройствами, но и для
-кода, различные ветки которого могут быть запущены на нескольких аппаратных
-потоках одного процессорного ядра, т.е. ветки, осуществляющие доступ к различным
-блокам памяти или использующие смешанную арифметику (целочисленную и с плавающей
-точкой). Ветки кода, которые используют различные модули процессора, являются
-хорошими кандидатами для параллельного запуска на процессорном ядре с
-несколькими аппаратными потоками.
+#+caption: Наложение параллельных вычислений на \([G_0,G_1]\) и записи данных на диск на \([W_0,W_1]\). В реализации OpenMP наложение отсутствует.
+#+label: fig-factory-overlap
+#+RESULTS: fig-factory-overlap
+[[file:build/factory-vs-openmp-overlap-ru.pdf]]
-Таким образом, вычислительную модель на основе конвейера можно рассматривать как
-/массивно асинхронную модель/ (bulk-asynchronous model) из-за параллельной
-природы шагов программы. Эта модель является основой модели отказоустойчивости,
-которая будет описана далее.
+Предложенный алгоритм распределения нагрузки на многоядерную систему позволяет
+получить прирост производительности для приложений, считывающих и записывающих
+большой объем данных на диск, но может быть использован также и в других
+случаях. Основная идея алгоритма состоит в определении типа нагрузки и поиске
+подходящего устройства для перенаправления нагрузки на него. Таким образом любое
+устройство помимо дисков может быть использовано.
+** Отказоустойчивый планировщик пакетных задач
+*** Архитектура системы
+**** Физический уровень.
+**** Уровень резидентных процессов.
+**** Уровень управляющих объектов.
**** Программная реализация.
Из соображений эффективности конвейер объектов и методы обеспечения
отказоустойчивости (которые будут описаны далее) были реализованы во фреймворке
@@ -2163,28 +2268,7 @@ graph G {
Таким образом, управляющие объекты обладают свойствами как сопрограмм, так и
обработчиков событий одновременно.
-**** Определения иерархий.
-Для устранения неоднозначности иерархических связей между сервисами и
-управляющими объектами и для того чтобы упростить изложение, мы будем
-использовать в тексте следующие условные обозначения. Если связь установлена
-между двумя процессами-сервисами, то отношения обозначаются
-/руководитель-подчиненный/. Если связь установлена между двумя управляющими
-объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо
-/родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни
-один управляющий объект не может иметь связь с сервисом, и наоборот. Поскольку
-иерархия сервисом используется для распределения нагрузки на узлы кластера,
-иерархия управляющих объектов отображается на нее, и это отображение может быть
-произвольным: обычна ситуация, когда руководящий управляющий объект находится на
-подчиненном узле, а его подчиненные управляющие объекта распределены равномерно
-между всеми узлами кластера (включая узел, где находится руководящий объект).
-Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются
-предпочтительными для высоко параллельных программ, так как в них меньше
-количество промежуточных узлов, через которые должны пройти управляющие объекты
-при распределении между узлами кластера. Поскольку существует однозначное
-соответствие между сервисами и узлами кластера, в данной работе они используются
-как взаимозаменяемые термины.
-
-**** Структура управляющих объектов и алгоритмы.
+**** Программный интерфейс.
Каждый управляющий объект имеет четыре типа полей (перечисленных в
табл.\nbsp{}[[tab-kernel-fields]]):
- поля, относящиеся к управлению потоком исполнения,
@@ -2249,278 +2333,182 @@ downstream-объектов метод ~react~ их родителя вызыв
программах, где параллельные части не имеют таких информационных зависимостей
между друг другом: в этом случае только части с вышедших из строя узлов
вычисляются заново, а все ранее вычисленные части сохраняются.
+**** Отображение алгоритма генерации взволнованной поверхности на архитектуру системы.
+Модель АРСС реализована в программном комплексе, работающем по принципу
+вычислительного конвейера, в котором каждое звено применяет некоторую функцию к
+выходным данным предыдущего звена. Звенья конвейера распределяются по узлам
+вычислительного кластера, чтобы сделать возможным параллелизм по операциям, а
+затем данные, перемещающиеся между звеньями конвейера распределяются между
+ядрами процессора, чтобы сделать возможным параллелизм по данным. На рис.\nbsp{}[[fig-pipeline]] представлена схема конвейера обработки данных, в которой
+прямоугольниками со скругленными углами обозначены звенья конвейера, обычными
+прямоугольниками\nbsp{}--- массивы объектов из предметной области задачи, передаваемые
+от одного звена к другому, а стрелками\nbsp{}--- направление передачи данных.
+Некоторые звенья разделены на /секции/, каждая из которых обрабатывает отдельную
+часть массива. Если звенья соединены без использования /барьера/ (горизонтальная
+или вертикальная полоса), то передача отдельных объектов между такими звеньями
+происходит параллельно с вычислениями, по мере их готовности. Секции работают
+параллельно на нескольких ядрах процессора (нескольких узлах кластера). Таким
+образом, между множеством ядер процессора, секций звеньев конвейера и объектами
+устанавливается сюръективное отображение, т.е. на одном ядре процессора может
+работать несколько секций звеньев конвейера, каждая из которых может
+обрабатывать несколько объектов последовательно, но одна секция не может
+работать сразу на нескольких ядрах, а объект не может обрабатываться сразу
+несколькими секциями конвейера.
-** Реализация для систем с общей памятью (SMP)
-**** Алгоритм распределения нагрузки.
-Наиболее простым и широко применяемым подходом к распределению нагрузки на
-вычислительную систему является разбиение данных на равные части (или разбиение
-задачи на однородные подзадачи) с последующим их равномерным распределением
-между отдельными ядрами процессора и узлами кластера, однако такой подход не
-всегда работает эффективно. Во-первых, часто общее количество частей, на которые
-разбиваются входные данные, диктуется не архитектурой и конфигурацией
-вычислительной системы, а самой задачей, и такое распределение не всегда
-эффективно с точки зрения вычислительной машины: количество частей оказывается
-либо слишком большим по сравнению с количеством процессоров, работающих
-параллельно, что ведет к увеличению накладных расходов на обмен данными, либо
-слишком маленьким, что не позволяет использовать все доступные вычислительные
-ядра. Во-вторых, накладываемые решаемой задачей ограничения могут не позволить
-разделить входные данные на равные части, что может стать причиной дисбаланса в
-загрузке ядер процессора. В-третьих, в вычислительной системе в вычислениях
-участвуют помимо процессора сразу несколько компонент (таких как векторные
-сопроцессоры и устройства хранения), то время решения конкретной задачи зависит
-от производительности всех задействованных устройств. Каким же образом сделать
-алгоритм распределения нагрузки более эффективным, принимая во внимание разный
-размер частей, на которые разделяются входные данные, и учитывая все устройства,
-задействованные в вычислениях?
+#+name: fig-pipeline
+#+begin_src dot :exports results :file build/pipeline-ru.pdf
+digraph {
-Алгоритм распределения нагрузки состоит из двух этапов. На первом этапе алгоритм
-размещает часть входных данных (или подзадачу), обернутую в управляющий объект,
-в соответствующем пуле управляющих объектов: для каждого устройства используется
-отдельный пул управляющих объектов и сопряженный с ним пул потоков. На втором
-этапе, управляющий объект извлекается из пула одним из потоков и обрабатывается.
-Благодаря отдельным пулам потоков все устройства работают параллельно, уменьшая
-тем самым время простоя оборудования по сравнению с использованием всех
-устройств из одного потока.
+ node [fontsize=14,margin="0.055,0"]
+ graph [nodesep="0.25",ranksep="0.25",rankdir="TB"]
+ edge [arrowsize=0.66]
-Для того чтобы учесть неоднородность частей, на которые разбиваются входные
-данные, и неоднородность выполняемых задач, необходимо предсказать время
-выполнения каждой из задач. Соответствующее исследование сделано в\nbsp{}cite:degtyarev2016balance, поскольку реализация модели АРСС включает в себя, в
-основном, однородные задачи.
+ # data
+ subgraph xcluster_linear {
+ label="Линейная модель"
-Таким образом, распределение нагрузки осуществляется в два этапа: на первом
-этапе задача в форме урпавляющего объекта направляется на подходящее устройство,
-а на втором этапе она направляется в один из потоков из соответсвующего
-устройству пула. Неоднородность управляющих объектов может быть учтена путем
-предсказания времени их выполнения, однако такие объекты не встречаются в
-реализации модели АРСС.
+ start [label="",shape=circle,style=filled,fillcolor=black,width=0.23]
+ spectrum [label="S(ω,θ)",shape=box]
+ acf [label="K(i,j,k)",shape=box]
+ phi [label="Φ(i,j,k)",shape=box]
-**** Производительность реализаций на MPI, OpenMP и OpenCL.
-:PROPERTIES:
-:header-args:R: :results output org
-:END:
-Программная реализация состояла в создании и отладке прототипа программы и в
-последующем написании компоненты виртуального полигона на языке более низкого
-уровня. При этом тесты показали, что одной высокопроизводительной
-многопроцессорной машины достаточно для создания типовых реализаций морского
-волнения. Также использование видеокарт в качестве векторных ускорителей
-эффективно только в случае расчета давлений, в то время как генерация волновой
-поверхности выполняется быстрее на скалярном процессоре.
+ # transformations
+ fourier_transform [label="Преобразование Фурье",shape=box,style=rounded]
+ solve_yule_walker [label="Решение уравнений\nЮла—Уокера",shape=box,style=rounded]
-Создание программной реализации происходило в два этапа: на первом этапе был
-создан и отлажен прототип в программной среде
-Mathematica\nbsp{}cite:mathematica10, а на втором этапе логика программы была
-переписана на более низкоуровневом языке C++, и для получения эффективно
-работающего параллельного кода были проведены эксперименты с рядом библиотек. С
-помощью этих библиотек были реализованы функции генерации взволнованной морской
-поверхности, а также процедура расчета гидродинамических давлений под
-сгенерированной поверхностью. Тестирование производилось на вычислительных
-машинах кластера РЦ ВЦ СПбГУ (см.\nbsp{}табл.\nbsp{}[[tab-autoreg-testbed]]) и
-позволило получить два основных результата. Во-первых, использование видеокарт
-неэффективно при генерации волновой поверхности
-(см.\nbsp{}табл.\nbsp{}[[tab-autoreg-performance]]), что обусловлено сравнительно
-небольшим количеством арифметических операций по отношению к количеству операций
-с памятью устройства, а также отсутствием трансцендентных функций в реализации
-алгоритма. Во-вторых, для генерации одной реализации взволнованной морского
-поверхности одной многопроцессорной машины достаточно для эффективного и
-быстрого решения задачи (см.\nbsp{}рис.\nbsp{}[[fig-autoreg-performance]]). По
-результатам тестирования стандарт OpenMP был выбран в качестве основного, как
-наиболее эффективный и наиболее подходящий для расчетов на многопроцессорной
-системе.
+ subgraph cluster_nonlinear_1 {
+ label="Моделир. нелинейности\l"
+ labeljust=left
+ style=filled
+ color=lightgrey
+ acf2 [label="K*(i,j,k)",shape=box]
+ transform_acf [label="Преобразование АКФ",shape=box,style=rounded]
+ }
+ }
-#+name: fig-autoreg-performance
-#+caption: Скорость генерации взволнованной поверхности на многопроцессорной системе для типовых размеров реализации (сверху). Масштабируемость (относительное ускорение при увеличении количества процессоров) программной реализации на многопроцессорной системе для типовых размеров реализации (снизу). Временная протяженность 512 с.
-#+begin_figure
-[[file:graphics/speed.eps]]
-[[file:graphics/speedup.eps]]
-#+end_figure
+ subgraph xcluster_linear2 {
-#+name: tab-autoreg-testbed
-#+caption: Конфигурация оборудования.
-#+attr_latex: :booktabs t
-| Вычислительная машина | HP SL390s G7 |
-| Процессор | 2\(\times\)Intel X5650 (всего 12 ядер) |
-| Оперативная память | 96ГБ RAM |
-| Операционная система | CentOS 5.6 (Linux) |
+ eps_parts [label="<e1> ε₁|<e2> ε₂|<e3> …|<e4> εₙ|<e> ε(t,x,y)",shape=record]
+ end [label="",shape=doublecircle,style=filled,fillcolor=black,width=0.23]
-#+name: tab-autoreg-performance
-#+caption: Время (с.) генерации взволнованной морской поверхности различными программными реализациями авторегрессионной модели.
-#+attr_latex: :booktabs t :align cllllll
-| | ЛХ | ЛХ | ЛХ | АР | АР | АР |
-| Размер | OpenCL | OpenMP | MPI | OpenCL | OpenMP | MPI |
-|--------+--------+--------+-------+--------+--------+-------|
-| 400000 | 0.82 | 40.44 | 32.60 | 1.80 | 0.800 | 0.750 |
-| 440000 | 0.90 | 44.59 | 35.78 | 1.92 | 0.100 | 0.930 |
-| 480000 | 0.99 | 48.49 | 38.93 | 2.29 | 0.970 | 0.126 |
-| 520000 | 1.07 | 52.65 | 41.92 | 2.43 | 0.118 | 0.117 |
-| 560000 | 1.15 | 56.45 | 45.00 | 2.51 | 0.117 | 0.161 |
-| 600000 | 1.23 | 60.85 | 48.80 | 2.54 | 0.123 | 0.132 |
-| 640000 | 1.31 | 65.07 | 53.02 | 2.73 | 0.123 | 0.160 |
-| 680000 | 1.40 | 68.90 | 54.92 | 2.80 | 0.138 | 0.136 |
-| 720000 | 1.48 | 72.49 | 58.42 | 2.88 | 0.144 | 0.173 |
-| 760000 | 1.56 | 76.86 | 61.41 | 3.47 | 0.156 | 0.155 |
-| 800000 | 1.64 | 81.03 | 66.42 | 3.25 | 0.166 | 0.174 |
+ generate_white_noise [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Генерация\lбелого шума",shape=record,style=rounded]
+ generate_zeta [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Генерация частей\lвзволнованной мор-\lской поверхности\l",shape=record,style=rounded]
+
+ zeta_parts [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> Несшитые части реализации",shape=record]
+ overlap_add [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> Сшивание час-\lтей реализации\l",shape=record,style=rounded]
-#+name: tab-arma-performance
-#+begin_src R :results output org :exports results
-source(file.path("R", "benchmarks.R"))
-model_names <- list(
- ar.x="АР",
- ma.x="СС",
- lh.x="ЛХ",
- ar.y="АР",
- ma.y="СС",
- lh.y="ЛХ",
- Row.names="\\orgcmidrule{2-4}{5-6}Подпрограмма"
-)
-row_names <- list(
- determine_coefficients="Определение коэффициентов",
- validate="Проверка модели",
- generate_surface="Генерация поверхности",
- nit="НБП",
- write_all="Запись вывода в файл",
- copy_to_host="Копирование данных с GPU",
- velocity="Выч. потенциалов скорости"
-)
-arma.print_openmp_vs_opencl(model_names, row_names)
-#+end_src
+ zeta_parts:g1->overlap_add:g1
+ zeta_parts:g2->overlap_add:g2
+ zeta_parts:g3->overlap_add:g3
+ zeta_parts:g4->overlap_add:g4
-#+name: tab-arma-performance
-#+caption: Время работы (с.) реализации OpenMP и OpenCL для моделей АР, СС и ЛХ.
-#+attr_latex: :booktabs t
-#+RESULTS: tab-arma-performance
-#+BEGIN_SRC org
-| | | | OpenMP | | OpenCL |
-| \orgcmidrule{2-4}{5-6}Подпрограмма | АР | СС | ЛХ | АР | ЛХ |
-|------------------------------------+------+------+--------+--------+--------|
-| Определение коэффициентов | 0.02 | 0.01 | 0.19 | 0.01 | 1.19 |
-| Проверка модели | 0.08 | 0.10 | | 0.08 | |
-| Генерация поверхности | 1.26 | 5.57 | 350.98 | 769.38 | 0.02 |
-| НБП | 7.11 | 7.43 | | 0.02 | |
-| Копирование данных с GPU | | | | 5.22 | 25.06 |
-| Выч. потенциалов скорости | 0.05 | 0.05 | 0.06 | 0.03 | 0.03 |
-| Запись вывода в файл | 0.27 | 0.27 | 0.27 | 0.28 | 0.27 |
-#+END_SRC
+ zeta_parts:g2->overlap_add:g1 [constraint=false]
+ zeta_parts:g3->overlap_add:g2 [constraint=false]
+ zeta_parts:g4->overlap_add:g3 [constraint=false]
-Кроме выбора стандарта параллельных вычислений на время работы программы влияет
-выбор библиотек типовых вычислительных методов, и эффективность этих библиотек
-была показана тестированием их разработчиками. В качестве библиотеки для
-матричных операций (расчета коэффициентов авторегрессионной модели) была выбрана
-GotoBLAS и основанная на ней LAPACK, для непрерывной аппроксимации поля волновых
-чисел использовалась библиотека CGAL\nbsp{}cite:fabri2009cgal и для статистической
-проверки интегральных характеристик реализации взволнованной поверхности
-использовалась библиотека GSL\nbsp{}cite:gsl2008scientific. В случае GotoBLAS
-эффективность библиотеки показана в работах\nbsp{}cite:goto2008high,goto2008anatomy,
-для других библиотек эффективность не является важной, и они были выбраны,
-исходя из удобства их использования.
+ overlap_add:g1->zeta2_parts:g1
+ overlap_add:g2->zeta2_parts:g2
+ overlap_add:g3->zeta2_parts:g3
+ overlap_add:g4->zeta2_parts:g4
-#+name: tab-arma-libs
-#+caption: Список библиотек, используемых в реализации модели АРСС.
-#+attr_latex: :booktabs t
-| Библиотека | Назначение |
-|--------------------------------------------------------------+----------------------------------|
-| DCMT\nbsp{}cite:matsumoto1998dynamic | параллельный ГПСЧ |
-| Blitz\nbsp{}cite:veldhuizen1997will,veldhuizen2000techniques | многомерные массивы |
-| GSL\nbsp{}cite:gsl2008scientific | вычисление ФПР, ФР, БПФ |
-| | проверка стационарности процесса |
-| LAPACK, GotoBLAS\nbsp{}cite:goto2008high,goto2008anatomy | определение коэффициентов АР |
-| GL, GLUT\nbsp{}cite:kilgard1996opengl | трехмерная визуализация |
-| CGAL\nbsp{}cite:fabri2009cgal | триангуляция волновых чисел |
+ zeta2_parts:g1->transform_zeta:g1->zeta3_parts:g1->write_zeta:g1->eps_end
+ zeta2_parts:g2->transform_zeta:g2->zeta3_parts:g2->write_zeta:g2->eps_end
+ zeta2_parts:g3->transform_zeta:g3->zeta3_parts:g3->write_zeta:g3->eps_end
+ zeta2_parts:g4->transform_zeta:g4->zeta3_parts:g4->write_zeta:g4->eps_end
-**** Производительность алгоритма распределения нагрузки.
-Программная реализация генерации взволнованной поверхности сбалансирована с
-точки зрения нагрузки на процессорные ядра, однако, как показывают тесты,
-характеризуется высокой нагрузкой на устройства хранения. До проведения
-тестирования генерация взволнованной поверхности была реализована с
-использованием OpenMP для параллельных вычислений, и была переписана с
-использованием POSIX потоков для того чтобы реализовать алгоритм распределения
-нагрузки. Производительность двух реализаций сравнивалась на платформе,
-конфигурация которой приведена в табл.\nbsp{}[[tab-multicore-specs]].
+ }
-#+name: tab-multicore-specs
-#+caption: Конфигурация многоядерной системы.
-#+attr_latex: :booktabs t
-| Компонента | Подробности |
-|-------------------------------+----------------------------------|
-| Язык программирования | C++11 |
-| Библиотека потоков | C++11 STL threads |
-| Библиотека атомарных операций | C++11 STL atomic |
-| Подпрограммы замера времени | ~clock_gettime(CLOCK_MONOTONIC)~ |
-| | ~/usr/bin/time -f \%e~ |
-| Компилятор | GCC 4.8.2 |
-| Опции компиляции | ~-std=c++11 -O2 -march=native~ |
-| Операционная система | Debian 3.2.51-1 x86_64 |
-| Файловая система | ext4 |
-| Процессор | Intel Core 2 Quad Q9650 |
-| Частота процессора (ГГц) | 3.00 |
-| Количество ядер | 4 |
-| Объем оперативной памяти (ГБ) | 8 |
-| Диск | Seagate ST3250318AS |
-| Скорость диска (об./мин.) | 7200 |
+ subgraph part3 {
-Эксперимент состоял в запуске двух программных реализаций на многоядерной
-машине, изменяя размер поверхности. Размер пула потоков процессора и пула
-потоков ввода/вывода оставался неизменным во время эксперимента. Пул потоков
-ввода/вывода состоял из одного потока, а количество потоков процессора равнялось
-количеству физических ядер процессора.
+ zeta2_parts [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> Поверхность с нормаль-\lным законом распреде-\lления\l",shape=record]
-В эксперименте алгоритм распределения нагрузки показал большую эффективность по
-сравнению с реализацией без него. Чем больше размер генерируемой поверхности,
-тем больше разрыв в производительности (рис.\nbsp{}[[fig-factory-performance]]), что
-является следствием наложения вычислительной фазы и фазы вывода данных друг на
-друга (рис.\nbsp{}[[fig-factory-overlap]]). В реализации OpenMP фаза вывода данных
-начинается только тогда, когда заканчивается вычислительная фаза, в то время как
-использование алгоритма распределения нагрузки приводит почти к одновременному
-завершению обеих фаз. Таким образом, /выполнение параллельных изнутри,
-последовательных фаз в режиме конвейера более эффективно, чем их
-последовательное выполнение/, и это позволяет сбалансировать нагрузку на
-различные устройства, задействованные в вычислениях.
+ subgraph cluster_nonlinear_2 {
+ label="Моделир. нелинейности\r"
+ labeljust=right
+ style=filled
+ color=lightgrey
+ zeta3_parts [label="<g1> ζ₁|<g2> ζ₂|<g3> …|<g4> ζₙ|<gen> ζ(t,x,y)",shape=record]
+ transform_zeta [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Преобразование за-\lкона распределения\lвзволнованной мор-\lской поверхности\l",shape=record,style=rounded]
+ }
-#+name: fig-factory-performance
-#+header: :width 5 :height 4
-#+begin_src R :file build/factory-vs-openmp-ru.pdf
-source(file.path("R", "common.R"))
-arma.plot_factory_vs_openmp(
- xlab="Размер реализации",
- ylab="Время, с.",
- power=6
-)
-#+end_src
+ # barriers
+ eps_start [label="",shape=box,style=filled,fillcolor=black,height=0.05]
+ eps_end [label="",shape=box,style=filled,fillcolor=black,height=0.05]
-#+caption: Сравнение производительности реализаций программы на OpenMP и Factory.
-#+label: fig-factory-performance
-#+RESULTS: fig-factory-performance
-[[file:build/factory-vs-openmp-ru.pdf]]
+ write_zeta [label="<g1> g₁|<g2> g₂|<g3> …|<g4> gₙ|<gen> Запись готовых\lчастей в файл\l",shape=record,style=rounded]
+ }
-#+name: fig-factory-overlap
-#+header: :width 7 :height 4
-#+begin_src R :file build/factory-vs-openmp-overlap-ru.pdf
-source(file.path("R", "common.R"))
-par(mar=c(5, 6, 0, 1), pty="m")
-arma.plot_factory_vs_openmp_overlap(
- xlab="Время, с.",
- labels=c("Factory", "OpenMP"),
- scale=10**9
-)
+ # edges
+ start->spectrum->fourier_transform->acf->transform_acf
+ transform_acf->acf2
+ acf2->solve_yule_walker
+ solve_yule_walker->phi
+ phi->eps_start [constraint=false]
+ eps_start->generate_white_noise:g1
+ eps_start->generate_white_noise:g2
+ eps_start->generate_white_noise:g3
+ eps_start->generate_white_noise:g4
+ generate_white_noise:g1->eps_parts:e1->generate_zeta:g1->zeta_parts:g1
+ generate_white_noise:g2->eps_parts:e2->generate_zeta:g2->zeta_parts:g2
+ generate_white_noise:g3->eps_parts:e3->generate_zeta:g3->zeta_parts:g3
+ generate_white_noise:g4->eps_parts:e4->generate_zeta:g4->zeta_parts:g4
+
+ eps_end->end
+}
#+end_src
-#+caption: Наложение параллельных вычислений на \([G_0,G_1]\) и записи данных на диск на \([W_0,W_1]\). В реализации OpenMP наложение отсутствует.
-#+label: fig-factory-overlap
-#+RESULTS: fig-factory-overlap
-[[file:build/factory-vs-openmp-overlap-ru.pdf]]
+#+caption: Схема конвейера обработки данных, реализующего генерацию взволнованной морской поверхности по АР модели.
+#+label: fig-pipeline
+#+RESULTS: fig-pipeline
+[[file:build/pipeline-ru.pdf]]
-Предложенный алгоритм распределения нагрузки на многоядерную систему позволяет
-получить прирост производительности для приложений, считывающих и записывающих
-большой объем данных на диск, но может быть использован также и в других
-случаях. Основная идея алгоритма состоит в определении типа нагрузки и поиске
-подходящего устройства для перенаправления нагрузки на него. Таким образом любое
-устройство помимо дисков может быть использовано.
+Конвейер объектов можно считать развитием модели BSP (Bulk Synchronous
+Parallel)\nbsp{}cite:valiant1990bridging, применяемой в системах обработки
+графов\nbsp{}cite:malewicz2010pregel,seo2010hama. Конвейер позволяет исключить
+глобальную синхронизацию (где это возможно) между последовательно идущим этапами
+вычислений путем передачи данных между звеньев параллельно с вычислениями, в то
+время как в модели BSP глобальная синхронизация происходит после каждого шага.
+
+Конвейер объектов ускоряет программу путем параллельного выполнения блоков кода,
+работающих с разными вычислительными устройствами: в то время как текущая часть
+взолнованной поверхности генерируется на процессоре, предыдущая часть
+записывается на диск. Такой подход позволяет получить ускорение, потому что
+различные вычислительные устройства работают асинхронно, и их параллельное
+использование увеличивает производительность программы.
+
+Поскольку передача данных между звеньями конвейера происходит параллельно с
+вычислениями, то на одном и том же конвейере можно запустить сразу несколько
+копий приложения с разными параметрами (генерировать сразу несколько
+взволнованных морских поверхностей с разными характеристиками). На практике
+оказывается, что высокопроизводительные приложения не всегда загружают
+процессор на 100%, тратя время на синхронизацию параллельных процессов и
+запись данных на диск. Использование конвейера в таком случае позволит на одном
+и том же множестве процессов запустить сразу несколько расчетов и максимально
+эффективно использовать все устройства компьютера. Например, во время записи в
+файл одной задачей может производиться расчет на процессоре другой задачей. Это
+минимизирует время простоя процессора и других устройств компьютера и повышает
+общую пропускную способность кластера.
+
+Конвейеризация шагов программы, которые в противном случае последовательны,
+выгодно не только для кода, работающего с различными устройствами, но и для
+кода, различные ветки которого могут быть запущены на нескольких аппаратных
+потоках одного процессорного ядра, т.е. ветки, осуществляющие доступ к различным
+блокам памяти или использующие смешанную арифметику (целочисленную и с плавающей
+точкой). Ветки кода, которые используют различные модули процессора, являются
+хорошими кандидатами для параллельного запуска на процессорном ядре с
+несколькими аппаратными потоками.
+
+Таким образом, вычислительную модель на основе конвейера можно рассматривать как
+/массивно асинхронную модель/ (bulk-asynchronous model) из-за параллельной
+природы шагов программы. Эта модель является основой модели отказоустойчивости,
+которая будет описана далее.
-** Реализация для систем с распределенной памятью (MPP)
*** Алгоритм обнаружения узлов кластера
:PROPERTIES:
:CUSTOM_ID: sec:node-discovery
:END:
+**** Алгоритмы выбора лидера.
Многие системы пакетной обработки задач построены по принципу /субординации/: в
каждом кластере выбирается руководящий узел, который управляет очередью задач,
планирует их запуск на подчиненных узлах и следит за их состоянием. Роль
@@ -2957,6 +2945,27 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
В последующих разделах будут описаны компоненты необходимые для написания
параллельной программы и планировщика, которые устойчивы к сбоям узлов кластера.
+**** Определения иерархий.
+Для устранения неоднозначности иерархических связей между сервисами и
+управляющими объектами и для того чтобы упростить изложение, мы будем
+использовать в тексте следующие условные обозначения. Если связь установлена
+между двумя процессами-сервисами, то отношения обозначаются
+/руководитель-подчиненный/. Если связь установлена между двумя управляющими
+объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо
+/родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни
+один управляющий объект не может иметь связь с сервисом, и наоборот. Поскольку
+иерархия сервисом используется для распределения нагрузки на узлы кластера,
+иерархия управляющих объектов отображается на нее, и это отображение может быть
+произвольным: обычна ситуация, когда руководящий управляющий объект находится на
+подчиненном узле, а его подчиненные управляющие объекта распределены равномерно
+между всеми узлами кластера (включая узел, где находится руководящий объект).
+Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются
+предпочтительными для высоко параллельных программ, так как в них меньше
+количество промежуточных узлов, через которые должны пройти управляющие объекты
+при распределении между узлами кластера. Поскольку существует однозначное
+соответствие между сервисами и узлами кластера, в данной работе они используются
+как взаимозаменяемые термины.
+
**** Иерархия управляющих объектов.
Для распределения нагрузки узлы кластера объединяются в древовидную иерархию
(см.\nbsp{}раздел [[#sec:node-discovery]]), и нагрузка распределяется между
@@ -3301,6 +3310,9 @@ Keepalived\nbsp{}cite:cassen2002keepalived.
сбой\nbsp{}cite:fischer1985impossibility и невозможность надежной передачи
данных в случае сбоя одного из узлов\nbsp{}cite:fekete1993impossibility.
+** Реализация для систем с распределенной памятью (MPP)
+**** Распределенный алгоритм для модели АР.
+**** Производительность реализации распределенного алгоритма для АР модели.
** Сравнение предложенного подхода с современными подходами
Современный подход к разработке и запуску параллельных программ на кластере
заключается в использовании библиотеки передачи сообщений MPI и планировщика
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -3497,7 +3497,7 @@ process\nbsp{}cite:fischer1985impossibility and impossibility of reliable
communication in the presence of node
failures\nbsp{}cite:fekete1993impossibility.
-*** Conclusions
+*** Comparison of the proposed approach with state-of-the-art approaches
Current state-of-the-art approach to developing and running parallel programmes
on the cluster is the use of MPI message passing library and job scheduler, and
despite the fact that this approach is highly efficient in terms of parallel
@@ -3790,7 +3790,7 @@ equations\nbsp{}eqref:eq-problem is written as
& \zeta(x,t) = -\frac{1}{g} \phi_t, & \text{на }z=\zeta(x,t),
\end{align*}
where \(\frac{p}{\rho}\) includes \(\phi_t\). The solution to the Laplace
-equation is sought in a form of Fourier series cite:kochin1966theoretical:
+equation is sought in a form of Fourier series\nbsp{}cite:kochin1966theoretical:
\begin{equation*}
\phi(x,z,t) = \int\limits_{0}^{\infty} e^{k z}
\left[ A(k, t) \cos(k x) + B(k, t) \sin(k x) \right] dk.
@@ -3802,8 +3802,9 @@ Plugging it in the boundary condition yields
&= -\frac{1}{g} \int\limits_{0}^{\infty} C_t(k, t) \cos(kx + \epsilon(k, t)).
\end{align*}
Here \(\epsilon\) is white noise and \(C_t\) includes \(dk\). Substituting
-integral with infinite sum yields two-dimensional form of
-eq.\nbsp{}[[eq-longuet-higgins]].
+integral with infinite sum yields two-dimensional form
+of\nbsp{}eqref:eq-longuet-higgins.
+
** Derivative in the direction of the surface normal
:PROPERTIES:
:CUSTOM_ID: directional-derivative
