commit 8313823ac515cea7e020c55fdf013690505023a5
parent 3d29d6aa036645714778526dbf552f7ab7325f04
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Thu, 26 Jan 2017 17:00:58 +0300
Sync LB algo p1.
Diffstat:
2 files changed, 43 insertions(+), 29 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -2026,11 +2026,11 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
соответствующей сопрограммы. В результате, при аварийном завершении
сопрограммы, все его вложенные сопрограммы должны быть выполнены заново. Это
подталкивает программиста к созданию
- - глубоких иерархий сильно связанных управляющих объектов (которые
+ - глубоких древовидных иерархий сильно связанных управляющих объектов (которые
взаимодействуют между собой на одном уровне иерархии), уменьшающих накладные
расходы на повторное выполнение сопрограмм;
- - толстых иерархий слабо связанных управляющих объектов, обеспечивающих
- максимальную степень параллелизма.
+ - толстых древовидных иерархий слабо связанных управляющих объектов,
+ обеспечивающих максимальную степень параллелизма.
Глубокие иерархии это не только требование технологии, они помогают
оптимизировать сетевое взаимодействие большого количества узлов кластера,
сводя его к взаимодейсвтвию соседних узлов.
@@ -2041,29 +2041,25 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
** Реализация для систем с общей памятью (SMP)
*** Алгоритм распределения нагрузки
Наиболее простым и широко применяемым подходом к распределению нагрузки на
-вычислительную систему является разбиение данных на однородные части (или
-разбиение задачи на однородные подзадачи) с последующим распределением их между
-отдельными ядрами вычислительного устройства или узлами кластера, однако такой
-подход не всегда работает эффективно. Во-первых, часто общее количество частей,
-на которые разбиваются входные данные, диктуется не архитектурой и конфигурацией
-вычислительной системы, а самой задачей и присущими ей ограничениями, и такое
-распределение не всегда эффективно с точки зрения вычислительной машины:
-количество частей оказывается либо слишком большим по сравнению с количеством
-процессоров, работающих параллельно, что ведет к увеличению накладных расходов
-на обмен данными, либо слишком маленьким, что не позволяет эффективно
-использовать все доступные вычислительные ядра. Во-вторых, сам характер деления
-входных данных на части может стать причиной появления неоднородности в размерах
-различных частей и дисбаланса нагрузки на отдельные вычислительные ядра системы.
-В-третьих, поскольку в вычислительной системе процессор --- не единственное
-устройство, справляющееся с нагрузкой, и существуют другие компоненты,
-участвующие в вычислениях (такие как векторные ускорители, видеокарты и
-устройства хранения), то окончательная производительность системы и время
-решения конкретной задачи зависят от производительности не только процессоров,
-но и всех устройств, принимающих участие в вычислениях. Таким образом, учет
-только лишь процессоров при распределении нагрузки на вычислительную систему
-является лишь первым приближением к решению задачи о достижении высокой
-производительности, и учет всех компонент системы позволит улучшить этот
-результат.
+вычислительную систему является разбиение данных на равные части (или разбиение
+задачи на однородные подзадачи) с последующим их равномерным распределением
+между отдельными ядрами процессора и узлами кластера, однако такой подход не
+всегда работает эффективно. Во-первых, часто общее количество частей, на которые
+разбиваются входные данные, диктуется не архитектурой и конфигурацией
+вычислительной системы, а самой задачей, и такое распределение не всегда
+эффективно с точки зрения вычислительной машины: количество частей оказывается
+либо слишком большим по сравнению с количеством процессоров, работающих
+параллельно, что ведет к увеличению накладных расходов на обмен данными, либо
+слишком маленьким, что не позволяет использовать все доступные вычислительные
+ядра. Во-вторых, накладываемые решаемой задачей ограничения могут не позволить
+разделить входные данные на равные части, что может стать причиной дисбаланса в
+загрузке ядер процессора. В-третьих, в вычислительной системе в вычислениях
+участвуют помимо процессора сразу несколько компонент (таких как векторные
+сопроцессоры и устройства хранения), то время решения конкретной задачи зависит
+от производительности всех задействованных устройств. Каким же образом сделать
+алгоритм распределения нагрузки более эффективным, принимая во внимание разный
+размер частей, на которые разделяются входные данные, и учитывая все устройства,
+задействованные в вычислениях?
Для учета производительности всех компонент вычислительной системы и
неоднородности различных частей, на которые делятся входные и выходные данные,
diff --git a/phd-diss.org b/phd-diss.org
@@ -1944,9 +1944,9 @@ which maximises efficiency of a programme.
of a neighbour node, because a node may fail in the middle of its execution of
the corresponding routine. As a result, upon failure of a routine all of its
subroutines must be restarted. This encourages a programmer to construct
- - deep hierarchies of tightly-coupled kernels (which communicate on the same
- level of hierarchy) to reduce overhead of recomputation;
- - fat hierarchies of loosely-coupled kernels, providing maximal degree of
+ - deep tree hierarchies of tightly-coupled kernels (which communicate on the
+ same level of hierarchy) to reduce overhead of recomputation;
+ - fat tree hierarchies of loosely-coupled kernels, providing maximal degree of
parallelism.
Deep hierarchy is not only requirement of technology, it helps optimise
communication of large number of cluster nodes reducing it to communication of
@@ -1957,6 +1957,24 @@ routines and event handlers.
** SMP implementation
*** Load balancing algorithm
+The simplest approach to balance the load on a multi-processor system is to
+split data into equal parts (or a task into homogeneous subtasks) and to
+distribute them evenly between processor cores and cluster nodes, however, this
+approach does not work efficiently in all cases. First, the total number of
+parts, into which input data is split, is often dictated by the problem being
+solved, rather than computer system architecture. Such load balancing may not
+efficient from the computer system point of view: the number of parts is either
+too large compared to the number of processors working in parallel, which
+increases data transfer overhead, or too small, which prevents using all
+available processor cores. Second, restrictions of problem being solved may not
+allow splitting input data into even parts which may result in load imbalance
+across processor cores. Third, there are multiple components in the system aside
+from the processor that take part in the computation (such as vector
+co-processors and storage devices), and the problem solution time depends on the
+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?
+
*** Evaluation
**** Performance of MPI, OpenMP, OpenCL implementations.
**** Performance of load balancing algorithm.
