commit a2073f2593b92696ef6a579c75e2c3bb7b671aa3
parent 171e65f9f4756dd529e01097327ccd95ad5bfd99
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Wed, 18 Jan 2017 14:25:10 +0300
Copy pipeline mapping.
Diffstat:
2 files changed, 285 insertions(+), 93 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -25,103 +25,245 @@
(setq org-latex-image-default-width nil)
#+end_src
-** Plot distributions :noexport:
-#+begin_src gnuplot :exports none
-set loadpath GPVAL_PWD."/gnuplot"
-system "mkdir -p build"
-cd "build"
-
-load 'style.gnuplot'
-#load 'style-paper.gnuplot'
-
-set terminal svg fixed enhanced size 1920/5,900/3 font 'Old Standard, 12' dashed rounded
-set key top center Left reverse width -10 maxrows 2
-set xlabel 'z' offset 0,0.33
-set ylabel 'f(z)' offset 2,0
-
-set xrange [-3:3]
-set ytics 0,0.1
-set yrange [0:0.6]
-
-skew_normal_1(z, skewness, kurtosis) = (24 + 4*z*(-3 + z**2)* \
- skewness + (3 - 6*z**2 + z**4)* kurtosis)/(24*(exp((z**2)/2)*sqrt(2*pi)))
-
-#print skew_normal_1(1, 0.6, 1.0)
-# regular gamma γ
-
-set output 'skew-normal-1.svg'
-plot \
-skew_normal_1(x, 0, 0) with lines ls 1 title '𝛾_1=0, 𝛾_2=0', \
-skew_normal_1(x, 0.52, 0) with lines ls 2 title '𝛾_1=0.52, 𝛾_2=0', \
-skew_normal_1(x, 0, 0.7) with lines ls 3 title '𝛾_1=0, 𝛾_2=0.7', \
-skew_normal_1(x, 0.52, 0.7) with lines ls 4 title '𝛾_1=0.52, 𝛾_2=0.7'
-system "inkscape --without-gui --export-eps=skew-normal-1.eps skew-normal-1.svg
-
-skew_normal_2(z, alpha) = \
- erfc( -((z*alpha)/sqrt(2)) ) / \
- (exp((z**2)/2)*sqrt(2*pi))
-
-skewness(alpha) = \
- (sqrt(2) * (4 - pi) * (alpha**3)) \
- / \
- (sqrt(pi + (pi-2) * (alpha**2))**3)
-
-kurtosis(alpha) = \
- (8*(-3 + pi)*(alpha**4))/ \
- ((pi + (-2 + pi)*(alpha**2))**2)
-
-set terminal svg fixed enhanced size 1920/4,900/3 font 'Times, 12' dashed rounded
-set key top left Left reverse maxcols 1 maxrows 4
-set yrange [0:0.8]
-set output 'skew-normal-2.svg'
-alphas="0.00 0.87 2.25 4.90"
-a(i) = word(alphas, i)
-plot for [i=1:words(alphas)] \
-skew_normal_2(x, a(i)) with lines ls i \
-title 'α='.a(i).', 𝛾_1='.sprintf('%.2f',skewness(a(i))).', 𝛾_2='.sprintf('%.2f',kurtosis(a(i)))
-system "inkscape --without-gui --export-eps=skew-normal-2.eps skew-normal-2.svg
-
-exit
+** Produce data for Q-Q and ACF plots
+#+begin_src sh :exports none :results verbatim
+root=$(pwd)
+for testname in propagating_wave standing_wave
+do
+ wd=$root/build/$testname
+ rm -rf $wd
+ mkdir -p $wd
+ cd $wd
+ arma -c $root/config/$testname.arma 2>&1
+done
#+end_src
#+RESULTS:
+#+begin_example
+Input file = /home/igankevich/workspace/phd-diss/config/propagating_wave.arma
+ACF grid size = (20,10,10)
+ACF grid patch size = (0.526316,0.555556,0.555556)
+Output grid size = (200,40,40)
+Output grid patch size = (1,1,1)
+AR order = (10,10,10)
+Do least squares = 0
+ACF function = propagating_wave
+Model = MA
+MA algorithm = fixed_point_iteration
+Verification scheme = manual
+ACF variance = 5
+fixed_point_iteration:Iteration=0, var_wn=2.70831
+fixed_point_iteration:Iteration=1, var_wn=1.93791
+fixed_point_iteration:Iteration=2, var_wn=1.54801
+fixed_point_iteration:Iteration=3, var_wn=1.31202
+fixed_point_iteration:Iteration=4, var_wn=1.15328
+fixed_point_iteration:Iteration=5, var_wn=1.0386
+fixed_point_iteration:Iteration=6, var_wn=0.951442
+fixed_point_iteration:Iteration=7, var_wn=0.882674
+fixed_point_iteration:Iteration=8, var_wn=0.82688
+fixed_point_iteration:Iteration=9, var_wn=0.780623
+fixed_point_iteration:Iteration=10, var_wn=0.74161
+fixed_point_iteration:Iteration=11, var_wn=0.708244
+fixed_point_iteration:Iteration=12, var_wn=0.679374
+fixed_point_iteration:Iteration=13, var_wn=0.654145
+fixed_point_iteration:Iteration=14, var_wn=0.63191
+fixed_point_iteration:Iteration=15, var_wn=0.612168
+fixed_point_iteration:Iteration=16, var_wn=0.594523
+fixed_point_iteration:Iteration=17, var_wn=0.578663
+fixed_point_iteration:Iteration=18, var_wn=0.564333
+fixed_point_iteration:Iteration=19, var_wn=0.551325
+fixed_point_iteration:Iteration=20, var_wn=0.539469
+fixed_point_iteration:Iteration=21, var_wn=0.528623
+fixed_point_iteration:Iteration=22, var_wn=0.518666
+fixed_point_iteration:Iteration=23, var_wn=0.509497
+fixed_point_iteration:Iteration=24, var_wn=0.50103
+fixed_point_iteration:Iteration=25, var_wn=0.493191
+fixed_point_iteration:Iteration=26, var_wn=0.485916
+fixed_point_iteration:Iteration=27, var_wn=0.479148
+fixed_point_iteration:Iteration=28, var_wn=0.472841
+fixed_point_iteration:Iteration=29, var_wn=0.466951
+fixed_point_iteration:Iteration=30, var_wn=0.461442
+fixed_point_iteration:Iteration=31, var_wn=0.456279
+fixed_point_iteration:Iteration=32, var_wn=0.451435
+fixed_point_iteration:Iteration=33, var_wn=0.446882
+fixed_point_iteration:Iteration=34, var_wn=0.442597
+fixed_point_iteration:Iteration=35, var_wn=0.43856
+fixed_point_iteration:Iteration=36, var_wn=0.434752
+fixed_point_iteration:Iteration=37, var_wn=0.431155
+fixed_point_iteration:Iteration=38, var_wn=0.427755
+fixed_point_iteration:Iteration=39, var_wn=0.424538
+fixed_point_iteration:Iteration=40, var_wn=0.42149
+fixed_point_iteration:Iteration=41, var_wn=0.418601
+fixed_point_iteration:Iteration=42, var_wn=0.415859
+fixed_point_iteration:Iteration=43, var_wn=0.413256
+fixed_point_iteration:Iteration=44, var_wn=0.410782
+fixed_point_iteration:Iteration=45, var_wn=0.40843
+fixed_point_iteration:Iteration=46, var_wn=0.406191
+fixed_point_iteration:Iteration=47, var_wn=0.404059
+fixed_point_iteration:Iteration=48, var_wn=0.402029
+fixed_point_iteration:Iteration=49, var_wn=0.400092
+fixed_point_iteration:Iteration=50, var_wn=0.398246
+fixed_point_iteration:Iteration=51, var_wn=0.396483
+fixed_point_iteration:Iteration=52, var_wn=0.3948
+fixed_point_iteration:Iteration=53, var_wn=0.393193
+fixed_point_iteration:Iteration=54, var_wn=0.391656
+fixed_point_iteration:Iteration=55, var_wn=0.390188
+fixed_point_iteration:Iteration=56, var_wn=0.388782
+fixed_point_iteration:Iteration=57, var_wn=0.387438
+fixed_point_iteration:Iteration=58, var_wn=0.386151
+fixed_point_iteration:Iteration=59, var_wn=0.384918
+fixed_point_iteration:Iteration=60, var_wn=0.383738
+fixed_point_iteration:Iteration=61, var_wn=0.382606
+fixed_point_iteration:Iteration=62, var_wn=0.381522
+fixed_point_iteration:Iteration=63, var_wn=0.380482
+fixed_point_iteration:Iteration=64, var_wn=0.379485
+fixed_point_iteration:Iteration=65, var_wn=0.378528
+fixed_point_iteration:Iteration=66, var_wn=0.37761
+fixed_point_iteration:Iteration=67, var_wn=0.376729
+fixed_point_iteration:Iteration=68, var_wn=0.375882
+fixed_point_iteration:Iteration=69, var_wn=0.37507
+fixed_point_iteration:Iteration=70, var_wn=0.374289
+fixed_point_iteration:Iteration=71, var_wn=0.373539
+fixed_point_iteration:Iteration=72, var_wn=0.372818
+fixed_point_iteration:Iteration=73, var_wn=0.372126
+fixed_point_iteration:Iteration=74, var_wn=0.37146
+fixed_point_iteration:Iteration=75, var_wn=0.37082
+fixed_point_iteration:Iteration=76, var_wn=0.370204
+fixed_point_iteration:Iteration=77, var_wn=0.369612
+fixed_point_iteration:Iteration=78, var_wn=0.369042
+fixed_point_iteration:Iteration=79, var_wn=0.368494
+fixed_point_iteration:Iteration=80, var_wn=0.367966
+fixed_point_iteration:Iteration=81, var_wn=0.367458
+fixed_point_iteration:Iteration=82, var_wn=0.366969
+fixed_point_iteration:Iteration=83, var_wn=0.366499
+fixed_point_iteration:Iteration=84, var_wn=0.366046
+fixed_point_iteration:Iteration=85, var_wn=0.36561
+fixed_point_iteration:Iteration=86, var_wn=0.365189
+fixed_point_iteration:Iteration=87, var_wn=0.364785
+fixed_point_iteration:Iteration=88, var_wn=0.364395
+fixed_point_iteration:Iteration=89, var_wn=0.364019
+fixed_point_iteration:Iteration=90, var_wn=0.363657
+fixed_point_iteration:Iteration=91, var_wn=0.363309
+fixed_point_iteration:Iteration=92, var_wn=0.362973
+fixed_point_iteration:Iteration=93, var_wn=0.362649
+fixed_point_iteration:Iteration=94, var_wn=0.362337
+fixed_point_iteration:Iteration=95, var_wn=0.362036
+fixed_point_iteration:Iteration=96, var_wn=0.361746
+fixed_point_iteration:Iteration=97, var_wn=0.361466
+fixed_point_iteration:Iteration=98, var_wn=0.361197
+fixed_point_iteration:Iteration=99, var_wn=0.360937
+fixed_point_iteration:Iteration=100, var_wn=0.360686
+fixed_point_iteration:Iteration=101, var_wn=0.360444
+fixed_point_iteration:Iteration=102, var_wn=0.360211
+fixed_point_iteration:Iteration=103, var_wn=0.359986
+fixed_point_iteration:Iteration=104, var_wn=0.359769
+fixed_point_iteration:Iteration=105, var_wn=0.35956
+fixed_point_iteration:Iteration=106, var_wn=0.359358
+fixed_point_iteration:Iteration=107, var_wn=0.359163
+fixed_point_iteration:Iteration=108, var_wn=0.358975
+fixed_point_iteration:Iteration=109, var_wn=0.358794
+fixed_point_iteration:Iteration=110, var_wn=0.358619
+fixed_point_iteration:Iteration=111, var_wn=0.35845
+fixed_point_iteration:Iteration=112, var_wn=0.358288
+fixed_point_iteration:Iteration=113, var_wn=0.35813
+fixed_point_iteration:Iteration=114, var_wn=0.357979
+fixed_point_iteration:Iteration=115, var_wn=0.357832
+fixed_point_iteration:Iteration=116, var_wn=0.357691
+fixed_point_iteration:Iteration=117, var_wn=0.357555
+fixed_point_iteration:Iteration=118, var_wn=0.357423
+fixed_point_iteration:Iteration=119, var_wn=0.357296
+fixed_point_iteration:Iteration=120, var_wn=0.357173
+fixed_point_iteration:Iteration=121, var_wn=0.357055
+fixed_point_iteration:Iteration=122, var_wn=0.356941
+fixed_point_iteration:Iteration=123, var_wn=0.356831
+fixed_point_iteration:Iteration=124, var_wn=0.356724
+fixed_point_iteration:Iteration=125, var_wn=0.356621
+fixed_point_iteration:Iteration=126, var_wn=0.356522
+fixed_point_iteration:Iteration=127, var_wn=0.356426
+fixed_point_iteration:Iteration=128, var_wn=0.356334
+fixed_point_iteration:Iteration=129, var_wn=0.356244
+fixed_point_iteration:Iteration=130, var_wn=0.356158
+fixed_point_iteration:Iteration=131, var_wn=0.356075
+fixed_point_iteration:Iteration=132, var_wn=0.355994
+fixed_point_iteration:Iteration=133, var_wn=0.355917
+fixed_point_iteration:Iteration=134, var_wn=0.355842
+fixed_point_iteration:Iteration=135, var_wn=0.355769
+fixed_point_iteration:Iteration=136, var_wn=0.355699
+fixed_point_iteration:Iteration=137, var_wn=0.355632
+fixed_point_iteration:Iteration=138, var_wn=0.355567
+fixed_point_iteration:Iteration=139, var_wn=0.355504
+fixed_point_iteration:Iteration=140, var_wn=0.355443
+fixed_point_iteration:Iteration=141, var_wn=0.355384
+fixed_point_iteration:Iteration=142, var_wn=0.355327
+fixed_point_iteration:Iteration=143, var_wn=0.355273
+fixed_point_iteration:Iteration=144, var_wn=0.35522
+fixed_point_iteration:Iteration=145, var_wn=0.355169
+fixed_point_iteration:Iteration=146, var_wn=0.355119
+fixed_point_iteration:Iteration=147, var_wn=0.355072
+fixed_point_iteration:Iteration=148, var_wn=0.355026
+fixed_point_iteration:Iteration=149, var_wn=0.354981
+fixed_point_iteration:Iteration=150, var_wn=0.354938
+fixed_point_iteration:Iteration=151, var_wn=0.354897
+fixed_point_iteration:Iteration=152, var_wn=0.354856
+fixed_point_iteration:Iteration=153, var_wn=0.354818
+fixed_point_iteration:Iteration=154, var_wn=0.35478
+fixed_point_iteration:Iteration=155, var_wn=0.354744
+fixed_point_iteration:Iteration=156, var_wn=0.354709
+fixed_point_iteration:Iteration=157, var_wn=0.354676
+fixed_point_iteration:Iteration=158, var_wn=0.354643
+fixed_point_iteration:Iteration=159, var_wn=0.354612
+fixed_point_iteration:Iteration=160, var_wn=0.354581
+fixed_point_iteration:Iteration=161, var_wn=0.354552
+fixed_point_iteration:Iteration=162, var_wn=0.354524
+fixed_point_iteration:Iteration=163, var_wn=0.354496
+fixed_point_iteration:Iteration=164, var_wn=0.35447
+fixed_point_iteration:Iteration=165, var_wn=0.354444
+fixed_point_iteration:Iteration=166, var_wn=0.35442
+fixed_point_iteration:Iteration=167, var_wn=0.354396
+fixed_point_iteration:Iteration=168, var_wn=0.354373
+fixed_point_iteration:Iteration=169, var_wn=0.35435
+fixed_point_iteration:Iteration=170, var_wn=0.354329
+fixed_point_iteration:Iteration=171, var_wn=0.354308
+fixed_point_iteration:Iteration=172, var_wn=0.354288
+fixed_point_iteration:Iteration=173, var_wn=0.354269
+fixed_point_iteration:Iteration=174, var_wn=0.35425
+fixed_point_iteration:Iteration=175, var_wn=0.354232
+fixed_point_iteration:Iteration=176, var_wn=0.354214
+fixed_point_iteration:Iteration=177, var_wn=0.354198
+fixed_point_iteration:Iteration=178, var_wn=0.354181
+fixed_point_iteration:Iteration=179, var_wn=0.354165
+fixed_point_iteration:Iteration=180, var_wn=0.35415
+fixed_point_iteration:Iteration=181, var_wn=0.354136
+fixed_point_iteration:Iteration=182, var_wn=0.354121
+fixed_point_iteration:Iteration=183, var_wn=0.354108
+fixed_point_iteration:Iteration=184, var_wn=0.354094
+fixed_point_iteration:Iteration=185, var_wn=0.354082
+fixed_point_iteration:Iteration=186, var_wn=0.354069
+fixed_point_iteration:Iteration=187, var_wn=0.354057
+fixed_point_iteration:Iteration=188, var_wn=0.354046
+fixed_point_iteration:Iteration=189, var_wn=0.354034
+fixed_point_iteration:Iteration=190, var_wn=0.354024
+fixed_point_iteration:Iteration=191, var_wn=0.354013
+fixed_point_iteration:Iteration=192, var_wn=0.354003
+fixed_point_iteration:Iteration=193, var_wn=0.353994
+WN variance = 0.353994
+Input file = /home/igankevich/workspace/phd-diss/config/standing_wave.arma
+ACF grid size = (10,10,10)
+ACF grid patch size = (0.277778,0.555556,0.555556)
+Output grid size = (200,40,40)
+Output grid patch size = (1,1,1)
+AR order = (7,7,7)
+Do least squares = 0
+ACF function = standing_wave
+Model = AR
+MA algorithm = fixed_point_iteration
+Verification scheme = manual
+ACF variance = 5
+WN variance = 0.00261323
+Zeta size = (193,33,33)
+NaN: 29, -nan, 1.798e+36, -1.04284e+38, inf, -1.798e+36, -1.798e+36
+#+end_example
-** Plot velocities :noexport:
-#+begin_src gnuplot :exports none
-set loadpath GPVAL_PWD."/gnuplot" GPVAL_PWD."/data/velocity"
-system "mkdir -p build"
-cd "build"
-
-set terminal svg size 320, 200 font "Open Sans Regular, 12" linewidth 1 enhanced rounded dashed
-
-load 'linestyle.gnuplot'
-
-unset border
-set border 3
-set xtics nomirror out offset 0,0.5
-set ytics nomirror out offset 0.5,0
-
-set xrange [0:90]
-set yrange [-2:4]
-set xtics 0,30
-set ytics -2,2,4
-set xlabel 'x' offset 0,1
-set ylabel 'u(x)' offset 1.75,0
-
-set output 'high-amp-nocolor.svg'
-plot 'high-amp' title 'u_1(x)' ls 1 smooth csplines, \
- 'high-amp-0' title 'u_2(x)' ls 2 smooth csplines
-system "inkscape --without-gui --export-eps=high-amp-nocolor.eps high-amp-nocolor.svg
-
-set output 'low-amp-nocolor.svg'
-plot 'low-amp' title 'u_1(x)' ls 1 smooth csplines, \
- 'low-amp-0' title 'u_2(x)' ls 2 smooth csplines
-system "inkscape --without-gui --export-eps=low-amp-nocolor.eps low-amp-nocolor.svg
-
-exit
-#+end_src
-
-#+RESULTS:
* Введение
**** Актуальность темы.
Программы, моделирующие поведение судна на морских волнах, широко применяются
@@ -1628,6 +1770,27 @@ eqref:eq:old-sol-2d, сопоставимы для волн малых ампл
** Модель вычислений
*** Основополагающие принципы модели
*** Отображение алгоритма генерации взволнованной поверхности на вычислительную модель
+Модель АРСС реализована в программном комплексе, работающем по принципу
+вычислительного конвейера, в котором каждое звено применяет фильтр к выходным
+данным предыдущего звена. Такая архитектура позволяет распределить различные
+звенья конвейера по узлам вычислительного кластера, т.е. реализовать параллелизм
+по операциям, а внутри каждого звена применить параллелизм по данным. На
+[[fig:pipeline]] представлена схема конвейера обработки данных, в которой
+прямоугольниками со скругленными углами обозначены звенья конвейера, обычными
+прямоугольниками --- массивы данных, передаваемые от одного звена к другому, а
+стрелками --- направление передачи данных. Некоторые звенья разделены на
+/секции/, каждая из которых обрабатывает отдельную часть массива объектов из
+предметной области задачи. Если звенья соединены без использования /барьера/
+(горизонтальная или вертикальная полоса), то передача объектов между такими
+звеньями происходит параллельно с вычислениями, по мере их готовности. Секции
+работают параллельно на нескольких ядрах процессора (нескольких узлах кластера).
+Таким образом, между множеством ядер процессора, секций конвейера и объектами
+устанавливается сюръективное отображение, т.е. на одном ядре процессора может
+работать несколько секций конвейера, каждая из которых может обрабатывать
+несколько частей данных последовательно, но одна секция не может работать сразу
+на нескольких ядрах, а объект не может обрабатываться сразу несколькими секциями
+конвейера.
+
#+name: fig:pipeline
#+begin_src dot :exports results :file build/pipeline-ru.pdf
digraph {
@@ -1734,6 +1897,32 @@ digraph {
#+RESULTS: fig:pipeline
[[file:build/pipeline-ru.pdf]]
+Конвейер объектов можно считать развитием модели BSP (Bulk Synchronous
+Parallel), широко применяемой в системах обработки графов
+cite:malewicz2010pregel,seo2010hama. Преимущество конвейера заключается в том,
+что передача данных между звеньями, происходящая параллельно с вычислениями,
+позволяет исключить глобальную синхронизацию между последовательно идущим
+этапами вычислений, что, в свою очередь, позволяет эффективно распределить
+объекты по узлам кластера. В то же время, в модели BSP глобальная синхронизация
+происходит после каждого шага.
+
+Поскольку передача данных между звеньями конвейера происходит параллельно с
+вычислениями, то на одном и том же конвейере можно запустить сразу несколько
+приложений (генерировать сразу несколько взволнованных морских поверхностей с
+разными характеристиками). Обычно такой запуск производится либо в параллельных
+процессах, что может привести к перегрузке системы при недостаточном количестве
+процессорных ядер, либо через очередь задач, что не позволит получить
+максимальную производительность, поскольку процессорные ядра в таких очередях
+выделяются полностью под задачу. На практике оказывается, что
+высокопроизводительные приложения не всегода загружают процессор на максимум,
+тратя время на синхронизацию параллельных процессов и запись данных в файл.
+Использование конвейера в таком случае позволит на одном и том же множестве
+процессов запустить сразу несколько расчетов и эффективно использовать все
+устройства компьютера, насколько это позволяет задача. Например, во время записи
+в файл одной задачей может производиться расчет на процессоре другой задачей.
+Это минимизирует время простоя процессора и других устройств компьютера и
+повышает общую пропускную способность кластера.
+
** Реализация для систем с общей памятью (SMP)
*** Алгоритм распределения нагрузки
*** Результаты тестирования
@@ -1814,6 +2003,7 @@ digraph {
| <<<МНК>>> | метод наименьших квадратов |
| <<<ФПР>>> | функция плотности распределения |
| <<<ФР>>> | функция распределения |
+| <<<BSP>>> | Bulk Synchronous Parallel |
#+begin_export latex
diff --git a/phd-diss.org b/phd-diss.org
@@ -1751,6 +1751,7 @@ work.
communication of cluster nodes limiting it to adjacent nodes.
- No explicit synchronisation.
- Local communications between adjacent nodes in the hierarchy.
+
*** Mapping wavy surface generation algorithm on computational model
#+name: fig:pipeline
#+begin_src dot :exports results :file build/pipeline.pdf
@@ -1892,6 +1893,7 @@ digraph {
| <<<LS>>> | least squares |
| <<<PDF>>> | probability density function |
| <<<CDF>>> | cumulative distribution function |
+| <<<BSP>>> | Bulk Synchronous Parallel |
#+begin_export latex
\input{postamble}
