commit 2be05f7f4becfabacb39a33bdc60c112d5cf400d
parent 3c8c3927f7362fb28c083f20531558210304bb23
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Fri, 27 Jan 2017 16:31:57 +0300
Sync LB algo evaluation.
Diffstat:
| phd-diss-ru.org | | | 69 | +++++++++++++++++++++++++++------------------------------------------ |
| phd-diss.org | | | 40 | ++++++++++++++++++++++++---------------- |
2 files changed, 51 insertions(+), 58 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2161,10 +2161,11 @@ GotoBLAS и основанная на ней LAPACK, для непрерывно
Программная реализация генерации взволнованной поверхности сбалансирована с
точки зрения нагрузки на процессорные ядра, однако, как показывают тесты,
характеризуется высокой нагрузкой на устройства хранения. До проведения
-тестирования программа была реализована на OpenMP и для тестирования алгоритма
-распределения нагрузки переписана с использованием POSIX потоков.
-Производительность двух реализаций сравнивалась на платформе, конфигурация
-которой приведена в таблице [[tab:multicore-specs]].
+тестирования генерация взволнованной поверхности была реализована с
+использованием OpenMP для параллельных вычислений, и была переписана с
+использованием POSIX потоков для того чтобы реализовать алгоритм распределения
+нагрузки. Производительность двух реализаций сравнивалась на платформе,
+конфигурация которой приведена в таблице [[tab:multicore-specs]].
#+name: tab:multicore-specs
#+caption: Конфигурация многоядерной системы.
@@ -2187,27 +2188,23 @@ GotoBLAS и основанная на ней LAPACK, для непрерывно
| Диск | Seagate ST3250318AS |
| Скорость диска (об./мин.) | 7200 |
-В процессе экспериментов была измерена эффективность описанного метода
-распределения нагрузки, и он показал более высокую производительность в задаче
-генерации взволнованной поверхности (в задаче генерации большого объема данных)
-по сравнению с реализацией OpenMP. В результате предыдущих исследований было
-установлено, что реализация OpenMP имеет наилучшую производительность по
-сравнению с другими технологиями параллельного программирования
-cite:degtyarev2011effi, поэтому эксперимент заключался в сравнении ее
-производительности с производительностью нового метода на ряде входных данных.
-При каждом запуске варьировался только размер взволнованной поверхности. В
-результате эксперимента было установлено, что с увеличением размера поверхности
-увеличивается разрыв в производительности этих двух реализаций (см. рис.
-[[fig:factory-performance]]), а высокая производительность предложенного метода
-обуславливается наложением по времени фазы генерации взволнованной поверхности и
-фазы записи ее на диск (см. рис. [[fig:factory-overlap]]). В реализации OpenMP
-такого наложения не происходит, и запись на диск начинается сразу после
-окончания генерации поверхности в отличие от новой реализации, в которой
-генерация и запись на диск заканчиваются почти одновременно. Таким образом, в
-программах, работающих с большим объемом данных, конвейеризация параллельных
-вычислительных фаз более эффективна, чем их последовательное выполнение и
-позволяет сбалансировать нагрузку не только на процессорные ядра, но и на
-дисковую подсистему.
+Эксперимент состоял в запуске двух программных реализаций на многоядерной
+машине, изменяя размер поверхности. Размер пула потоков процессора и пула
+потоков ввода/вывода оставался неизменным во время эксперимента. Пул потоков
+ввода/вывода состоял из одного потока, а количество потоков процессора равнялось
+количеству физических ядер процессора.
+
+В эксперименте алгоритм распределения нагрузки показал большую эффективность по
+сравнению с реализацией без него. Чем больше размер генерируемой поверхности,
+тем больше разрыв в производительности (рис. [[fig:factory-performance]]), что
+является следствием наложения вычислительной фазы и фазы вывода данных друг на
+друга (рис. [[fig:factory-overlap]]). В реализации OpenMP фаза вывода данных
+начинается только тогда, когда заканчивается вычислительная фаза, в то время как
+использование алгоритма распределения нагрузки приводит почти к одновременному
+завершению обеих фаз. Таким образом, /выполнение параллельных изнутри,
+последовательных фаз в режиме конвейера более эффективно, чем их
+последовательное выполнение/, и это позволяет сбалансировать нагрузку на
+различные устройства, задействованные в вычислениях.
#+name: fig:factory-performance
#+begin_src R :results output graphics :exports results :file build/factory-vs-openmp-ru.pdf
@@ -2239,24 +2236,12 @@ arma.plot_factory_vs_openmp_overlap(
#+RESULTS: fig:factory-overlap
[[file:build/factory-vs-openmp-overlap-ru.pdf]]
-Несмотря на то, что технология OpenMP содержит примитивы для создания
-конвейеров, соединить конвейером две распараллеленные фазы программы можно
-только вручную. Такое соединение можно реализовать с помощью синхронизированной
-очереди, в которую направляются сгенерированные части взволнованной поверхности,
-готовые к записи в файл. Используя директиву /omp section/, можно описать работу
-каждого из звеньев получившегося конвейера, однако реализовать параллельную
-обработку каждого из звеньев (или хотя бы первого) не представляется возможным,
-так как требуется поддержка вложенных директив /omp parallel/, что редко
-встречается в реализациях OpenMP. Таким образом, реализация описанного метода
-распределения нагрузки в рамках стандарта OpenMP затруднена.
-
-Предложенный метод распределения нагрузки на многопроцессорную систему позволяет
+Предложенный алгоритм распределения нагрузки на многоядерную систему позволяет
получить прирост производительности для приложений, считывающих и записывающих
-большой объем данных на диск, позволяет сбалансировать нагрузку на процессорные
-ядра вычислительной системы и назначить различные типы рабочей нагрузки разным
-процессорным ядрам, а также различным устройствам, в том числе дискам. В
-дальнейших исследованиях предполагается обобщить этот метод на распределенную
-вычислительную среду.
+большой объем данных на диск, но может быть использован также и в других
+случаях. Основная идея алгоритма состоит в определении типа нагрузки и поиске
+подходящего устройства для перенаправления нагрузки на него. Таким образом любое
+устройство помимо дисков может быть использовано.
** Реализация для систем с распределенной памятью (MPP)
*** Обзор архитектур распределенных систем
diff --git a/phd-diss.org b/phd-diss.org
@@ -1996,12 +1996,12 @@ such kernels are not present in ARMA model implementation.
*** Evaluation
**** Performance of MPI, OpenMP, OpenCL implementations.
-**** Performance of load balancing algorithm.
+**** Performance of load balancing method.
Software implementation of wavy surface generation is balanced in terms of the
load on processor cores, however, as shown by tests, has high load on storage
-device. Before testing software implementation used OpenMP for parallel
-computations and for the purpose of load balancing algorithm evaluation was
-rewritten to use POSIX threads. Performance of the two implementations was
+device. Before testing wavy surface generation was implemented using OpenMP for
+parallel computations and in order to implement load balancing algorithm was
+rewritten using POSIX threads. Performance of the two implementations was
compared on the platform with the configuration listed in table
[[tab:multicore-specs]].
@@ -2026,18 +2026,20 @@ compared on the platform with the configuration listed in table
| Disk | Seagate ST3250318AS |
| Disk speed (rpm) | 7200 |
-In the experiment load balancing algorithm showed higher performance than OpenMP
-implementation. In each application run only the size of the realisation was
-varied. The figure The more the size of the realisation is the more the gap in
-performance is (as shown in figure [[fig:factory-performance]]). High performance is
-a result of overlap of computation phase and data output phase (as shown in
-figure [[fig:factory-overlap]]). In OpenMP implementation there is no such overlap
-and data output phase begins when computation is over. In contrast to this, in
-the second implementation load balancing algorithm makes both phases end almost
-simultaneously. So, /pipelining internally parallel sequential phases is more
-efficient than their sequential execution/, and this allows balancing the load
-across different compute devices.
-
+The experiment consisted of running both implementations on a multi-core machine
+varying the size of the surface; the size of CPU thread pool and I/O thread pool
+was not changed during the experiment. I/O thread pool consisted of one thread,
+and CPU thread pool size was equal the number of physical processor cores.
+
+In the experiment load balancing algorithm showed higher performance than
+implementation without it. The more the size of the generated surface is the
+more the gap in performance is (fig. [[fig:factory-performance]]) which is a result
+of overlap of computation phase and data output phase (fig.
+[[fig:factory-overlap]]). In OpenMP implementation data output phase begins only
+when computation is over, whereas load balancing algorithm makes both phases end
+almost simultaneously. So, /pipelined execution of internally parallel
+sequential phases is more efficient than their sequential execution/, and this
+allows balancing the load across different devices involved in computation.
#+name: fig:factory-performance
#+begin_src R :results output graphics :exports results :file build/factory-vs-openmp.pdf
@@ -2069,6 +2071,12 @@ arma.plot_factory_vs_openmp_overlap(
#+RESULTS: fig:factory-overlap
[[file:build/factory-vs-openmp-overlap.pdf]]
+Proposed load balancing method for multi-core systems allows increasing
+performance of applications that read or write large volumes of data to disk,
+but may be used in other cases too. The main idea of the algorithm is to
+classify the load and find the suitable device to route the load to. So, any
+devices other than disks may be used as well.
+
** MPP implementation
*** Overview of distributed system architectures
*** Cluster node discovery algorithm
