commit f951693c77c446c05d84950fb8c2353eba376a3f
parent 2e27c0cf07412b3eb2a9f4d392816fba9ef005d2
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Wed, 18 Jan 2017 16:21:40 +0300
Copy load balancing algorithm.
Diffstat:
| phd-diss-ru.org | | | 146 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 146 insertions(+), 0 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -1937,9 +1937,155 @@ cite:malewicz2010pregel,seo2010hama. Преимущество конвейера
** Реализация для систем с общей памятью (SMP)
*** Алгоритм распределения нагрузки
+Наиболее простым и широко применяемым подходом к распределению нагрузки на
+вычислительную систему является разбиение данных на однородные части (или
+разбиение задачи на однородные подзадачи) с последующим распределением их между
+отдельными ядрами вычислительного устройства или узлами кластера, однако такой
+подход не всегда работает эффективно. Во-первых, часто общее количество частей,
+на которые разбиваются входные данные, диктуется не архитектурой и конфигурацией
+вычислительной системы, а самой задачей и присущими ей ограничениями, и такое
+распределение не всегда эффективно с точки зрения вычислительной машины:
+количество частей оказывается либо слишком большим по сравнению с количеством
+процессоров, работающих параллельно, что ведет к увеличению накладных расходов
+на обмен данными, либо слишком маленьким, что не позволяет эффективно
+использовать все доступные вычислительные ядра. Во-вторых, сам характер деления
+входных данных на части может стать причиной появления неоднородности в размерах
+различных частей и дисбаланса нагрузки на отдельные вычислительные ядра системы.
+В-третьих, поскольку в вычислительной системе процессор --- не единственное
+устройство, справляющееся с нагрузкой, и существуют другие компоненты,
+участвующие в вычислениях (такие как векторные ускорители, видеокарты и
+устройства хранения), то окончательная производительность системы и время
+решения конкретной задачи зависят от производительности не только процессоров,
+но и всех устройств, принимающих участие в вычислениях. Таким образом, учет
+только лишь процессоров при распределении нагрузки на вычислительную систему
+является лишь первым приближением к решению задачи о достижении высокой
+производительности, и учет всех компонент системы позволит улучшить этот
+результат.
+
+Для учета производительности всех компонент вычислительной системы и
+неоднородности различных частей, на которые делятся входные и выходные данные,
+распределение нагрузки можно провести в два этапа. На первом этапе часть входных
+данных (или подзадача) направляется на соответствующее устройство, на которое
+предполагается произвести нагрузку, например, видеокарту или процессор; если же
+предполагается произвести нагрузку на устройство хранения, то подзадача
+направляется на процессор или процессорное ядро, специально выделенное под такой
+тип нагрузки. На втором этапе, когда тип устройства уже выбран, подзадача
+распределяется на одно из доступных в системе устройств данного типа. Несмотря
+на то, что на этом этапе подсистема в большинстве случаев является однородной
+(состоящей из устройств одного типа), для учета неоднородных подзадач необходим
+алгоритм распределения, который бы учитывал размер частей, на которые делится
+задача.
+
+Такой алгоритм можно построить на основе алгоритма "заполнения" (англ.
+backfill), который широко применяется для распределения нагрузки на узлы
+вычислительного кластера, но для его эффективной работы в случае
+многопроцессорной системы нужно произвести определенные модификации. Для расчета
+времени решения задачи на кластере не существует надежного метода, и часто это
+время задается вручную перед отправкой задачи в очередь cite:zotkin1999job, что
+неприемлемо в случае многопроцессорной системы, и поэтому время решения
+отдельных подзадач необходимо предсказать. Для получения надежного предсказания
+можно воспользоваться любым подходящим статистическим методом и использовать
+время выполнения предыдущих подзадач в качестве исходных данных. Для учета
+неоднородной производительности устройств можно воспользоваться тем же методом,
+только в качестве исходных данных взять производительность устройства на
+предыдующих задачах (количество задач, завершенных в единицу времени). Чтобы
+сократить накладные расходы, метод должен быть достаточно простым, и поэтому в
+тестах был использовано осреднение $N$ последних значений характеристики.
+Использование статистических методов в случае многопроцессорной системы
+оправдано, поскольку в отличие от задач, решаемых на кластерах, время решения
+подзадач достаточно мало, чтобы статистические методы работали эффективно. В
+случае же кластерных систем ввиду очень большого времени решения одной задачи
+использование статистических методов не может дать надежный результат, и
+алгоритм "заполнения" работает эффективно для небольших задач
+cite:zotkin1999job.
+
+Таким образом, распределение нагрузки осуществляется в два этапа: на первом
+этапе задача направляется на соответствующее ее типу нагрузки устройство, а на
+втором этапе она направляется на одно из выбранных устройств по алгоритму
+распределения. Сам же алгоритм является алгоритмом "заполнения" с модификациями,
+позволяющими автоматически предсказывать время выполнения задачи и
+производительность устройств.
+
*** Результаты тестирования
**** Производительности реализаций на MPI, OpenMP и OpenCL.
**** Производительность алгоритма распределения нагрузки.
+Программа, реализующая генерацию взволнованнной поверхности сбалансированна с
+точки зрения нагрузки на процессорные ядра, однако, как показали тесты,
+характеризуется высокой нагрузкой на устройства хранения. До проведения
+тестирования программа была реализована на OpenMP и для сравнения переписана в
+соответствии с разработанным подходом к распределению нагрузки, реализованным в
+виде отдельной библиотеки. Конфигурация оборудования, использованная в тестах,
+приведена в таблице [[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 |
+
+В процессе экспериментов была измерена эффективность описанного метода
+распределения нагрузки, и он показал более высокую производительность в задаче
+генерации взволнованной поверхности (в задаче генерации большого объема данных)
+по сравнению с реализацией OpenMP. В результате предыдущих исследований было
+установлено, что реализация OpenMP имеет наилучшую производительность по
+сравнению с другими технологиями параллельного программирования
+cite:degtyarev2011effi, поэтому эксперимент заключался в сравнении ее
+производительности с производительностью нового метода на ряде входных данных.
+При каждом запуске варьировался только размер взволнованной поверхности. В
+результате эксперимента было установлено, что с увеличением размера поверхности
+увеличивается разрыв в производительности этих двух реализаций (см. рис.
+[[fig:factory-performance]]), а высокая производительность предложенного метода
+обуславливается наложением по времени фазы генерации взволнованной поверхности и
+фазы записи ее на диск (см. рис. [[fig:factory-overlap]]). В реализации OpenMP
+такого наложения не происходит, и запись на диск начинается сразу после
+окончания генерации поверхности в отличие от новой реализации, в которой
+генерация и запись на диск заканчиваются почти одновременно. Таким образом, в
+программах, работающих с большим объемом данных, конвейеризация параллельных
+вычислительных фаз более эффективна, чем их последовательное выполнение и
+позволяет сбалансировать нагрузку не только на процессорные ядра, но и на
+дисковую подсистему.
+
+#+name: fig:factory-performance
+#+caption: Сравнение производительности реализаций программы на OpenMP и на разработанной технологии.
+
+#+name: fig:factory-overlap
+#+caption: Наложение параллельных вычислений на $[G_0,G_1]$ и записи данных на диск на $[W_0,W_1]$. В реализации OpenMP наложение отсутствует.
+
+Несмотря на то, что технология OpenMP содержит примитивы для создания
+конвейеров, соединить конвейером две распараллеленные фазы программы можно
+только вручную. Такое соединение можно реализовать с помощью синхронизированной
+очереди, в которую направляются сгенерированные части взволнованной поверхности,
+готовые к записи в файл. Используя директиву /omp section/, можно описать работу
+каждого из звеньев получившегося конвейера, однако реализовать параллельную
+обработку каждого из звеньев (или хотя бы первого) не представляется возможным,
+так как требуется поддержка вложенных директив /omp parallel/, что редко
+встречается в реализациях OpenMP. Таким образом, реализация описанного метода
+распределения нагрузки в рамках стандарта OpenMP затруднена.
+
+Предложенный метод распределения нагрузки на многопроцессорную систему позволяет
+получить прирост производительности для приложений, считывающих и записывающих
+большой объем данных на диск, позволяет сбалансировать нагрузку на процессорные
+ядра вычислительной системы и назначить различные типы рабочей нагрузки разным
+процессорным ядрам, а также различным устройствам, в том числе дискам. В
+дальнейших исследованиях предполагается обобщить этот метод на распределенную
+вычислительную среду.
+
** Реализация для систем с распределенной памятью (MPP)
*** Алгоритм обнаружения узлов кластера
*** Алгоритм восстановления после сбоев
