commit 9cfb110214ad5ae89252656d36036877ccab5213
parent 8313823ac515cea7e020c55fdf013690505023a5
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Thu, 26 Jan 2017 18:34:34 +0300
Sync LB algo p3-4.
Diffstat:
3 files changed, 54 insertions(+), 41 deletions(-)
diff --git a/bib/refs.bib b/bib/refs.bib
@@ -1691,4 +1691,20 @@ year={2013},
pages={1-6},
doi={10.1109/CSITechnol.2013.6710358},
art_number={6710358},
+}
+
+@inbook{degtyarev2016balance,
+ author={Degtyarev, Alexander and Gankevich, Ivan},
+ editor={Gavrilova, L. Marina and Tan, Kenneth C. J.},
+ title={Balancing Load on a Multiprocessor System with Event-Driven Approach},
+ bookTitle={Transactions on Computational Science XXVII},
+ year={2016},
+ publisher={Springer Berlin Heidelberg},
+ address={Berlin, Heidelberg},
+ pages={35--52},
+ isbn={978-3-662-50412-3},
+ doi={10.1007/978-3-662-50412-3_3},
+ url={http://dx.doi.org/10.1007/978-3-662-50412-3_3},
+ language={english},
+ category={hpc}
}
\ No newline at end of file
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2061,49 +2061,27 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
размер частей, на которые разделяются входные данные, и учитывая все устройства,
задействованные в вычислениях?
-Для учета производительности всех компонент вычислительной системы и
-неоднородности различных частей, на которые делятся входные и выходные данные,
-распределение нагрузки можно провести в два этапа. На первом этапе часть входных
-данных (или подзадача) направляется на соответствующее устройство, на которое
-предполагается произвести нагрузку, например, видеокарту или процессор; если же
-предполагается произвести нагрузку на устройство хранения, то подзадача
-направляется на процессор или процессорное ядро, специально выделенное под такой
-тип нагрузки. На втором этапе, когда тип устройства уже выбран, подзадача
-распределяется на одно из доступных в системе устройств данного типа. Несмотря
-на то, что на этом этапе подсистема в большинстве случаев является однородной
-(состоящей из устройств одного типа), для учета неоднородных подзадач необходим
-алгоритм распределения, который бы учитывал размер частей, на которые делится
-задача.
-
-Такой алгоритм можно построить на основе алгоритма "заполнения" (англ.
-backfill), который широко применяется для распределения нагрузки на узлы
-вычислительного кластера, но для его эффективной работы в случае
-многопроцессорной системы нужно произвести определенные модификации. Для расчета
-времени решения задачи на кластере не существует надежного метода, и часто это
-время задается вручную перед отправкой задачи в очередь cite:zotkin1999job, что
-неприемлемо в случае многопроцессорной системы, и поэтому время решения
-отдельных подзадач необходимо предсказать. Для получения надежного предсказания
-можно воспользоваться любым подходящим статистическим методом и использовать
-время выполнения предыдущих подзадач в качестве исходных данных. Для учета
-неоднородной производительности устройств можно воспользоваться тем же методом,
-только в качестве исходных данных взять производительность устройства на
-предыдующих задачах (количество задач, завершенных в единицу времени). Чтобы
-сократить накладные расходы, метод должен быть достаточно простым, и поэтому в
-тестах был использовано осреднение $N$ последних значений характеристики.
-Использование статистических методов в случае многопроцессорной системы
-оправдано, поскольку в отличие от задач, решаемых на кластерах, время решения
-подзадач достаточно мало, чтобы статистические методы работали эффективно. В
-случае же кластерных систем ввиду очень большого времени решения одной задачи
-использование статистических методов не может дать надежный результат, и
-алгоритм "заполнения" работает эффективно для небольших задач
-cite:zotkin1999job.
+Алгоритм распределения нагрузки состоит из двух этапов. На первом этапе алгоритм
+размещает часть входных данных (или подзадачу), обернутую в управляющий объект,
+в соответствующем пуле управляющих объектов: для каждого устройства используется
+отдельный пул управляющих объектов и сопряженный с ним пул потоков. На втором
+этапе, управляющий объект извлекается из пула одним из потоков и обрабатывается.
+Благодаря отдельным пулам потоков все устройства работают параллельно, уменьшая
+тем самым время простоя оборудования по сравнению с использованием всех
+устройств из одного потока.
+
+Для того чтобы учесть неоднородность частей, на которые разбиваются входные
+данные, и неоднородность выполняемых задач, необходимо предсказать время
+выполнения каждой из задач. Соответствующее исследование сделано в
+cite:degtyarev2016balance, поскольку реализация модели АРСС включает в себя, в
+основном, однородные задачи.
Таким образом, распределение нагрузки осуществляется в два этапа: на первом
-этапе задача направляется на соответствующее ее типу нагрузки устройство, а на
-втором этапе она направляется на одно из выбранных устройств по алгоритму
-распределения. Сам же алгоритм является алгоритмом "заполнения" с модификациями,
-позволяющими автоматически предсказывать время выполнения задачи и
-производительность устройств.
+этапе задача в форме урпавляющего объекта направляется на подходящее устройство,
+а на втором этапе она направляется в один из потоков из соответсвующего
+устройству пула. Неоднородность управляющих объектов может быть учтена путем
+предсказания времени их выполнения, однако такие объекты не встречаются в
+реализации модели АРСС.
*** Результаты тестирования
**** Производительность реализаций на MPI, OpenMP и OpenCL.
diff --git a/phd-diss.org b/phd-diss.org
@@ -1975,6 +1975,25 @@ performance of all the components involved. So, how to make load balancing
algorithm more efficient in the presence of non-homogeneous input data parts and
take into account all the devices involved in the computation?
+The load balancing algorithm consists of two stages. In the first stage, the
+algorithm places input data part (or a subtask) wrapped in a kernel into an
+appropriate kernel pool: there is a separate pool for each device and an
+associated thread pool. In the second stage, a kernel is retrieved from the pool
+by one of the threads and processed. Due to separate thread pools all devices
+work in parallel to each other, lowering overall system resources downtime
+compared to using all devices from a single thread.
+
+In order to take into account non-homogeneous input data parts or tasks, one may
+predict execution time of each task. Relevant study is done in
+cite:degtyarev2016balance since ARMA model implementation includes mostly
+homogeneous tasks.
+
+So, load balancing is done in two stages: in the first stage the task wrapped in
+the kernel is routed to the appropriate device and in the second stage the
+kernel is routed to one of the thread from the device thread pool.
+Non-homogeneous kernels may be handled by predicting their execution time, but
+such kernels are not present in ARMA model implementation.
+
*** Evaluation
**** Performance of MPI, OpenMP, OpenCL implementations.
**** Performance of load balancing algorithm.
