commit 1d19e39b4cfad1a515f46bf786389e3f63d37257
parent ebb4fbdbbc980ef7151d03cf400fe0a16098f9f2
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Tue, 13 Jun 2017 11:55:44 +0300
Definitions of kernel and daemon hierarchies.
Diffstat:
2 files changed, 54 insertions(+), 15 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -2186,9 +2186,10 @@ Parallel)\nbsp{}cite:valiant1990bridging, применяемой в систем
должна быть ответственна за повторное выполнение не удавшейся задачи на одном из
выживших узлов, тривиально. Чтобы повторно выполнить задачу на вершине иерархии,
создается резервная задача, выполняющаяся на другом узле. Существует ряд систем,
-которые способны выполнять направленные ациклические графы задач параллельно\nbsp{}cite:acun2014charmpp,islam2012oozie, но графы не подходят для определения
-отношений руководитель-подчиненный между задачами, поскольку узел графа может
-иметь несколько родительских узлов.
+которые способны выполнять направленные ациклические графы задач
+параллельно\nbsp{}cite:acun2014charmpp,islam2012oozie, но графы не подходят для
+определения отношений руководитель-подчиненный между задачами, поскольку узел
+графа может иметь несколько родительских узлов.
Основное назначение модели состоит в упрощении разработки распределенных
приложений для пакетной обработки данных и промежуточного программного
@@ -2351,7 +2352,6 @@ graph G {
#+label: fig-subord-ppl
#+RESULTS: fig-subord-ppl
[[file:build/subord-ppl-ru.pdf]]
-
**** Основополагающие принципы модели.
Модель конвейера обработки данных строится по следующим принципам, следование
которым обеспечивает максимальную эффективность программы.
@@ -2405,6 +2405,27 @@ graph G {
Таким образом, управляющие объекты обладают свойствами как сопрограмм, так и
обработчиков событий одновременно.
+**** Определения иерархий
+Для устранения неоднозначности иерархических связей между сервисами и
+управляющими объектами и для того чтобы упростить изложение, мы будем
+использовать в тексте следующие условные обозначения. Если связь установлена
+между двумя процессами-сервисами, то отношения обозначаются
+/руководитель-подчиненный/. Если связь установлена между двумя управляющими
+объектами, то отношения обозначаются либо /руководитель-подчиненный/, либо
+/родитель-потомок/. Две иерархии ортогональны друг к другу в том смысле, что ни
+один управляющий объект не может иметь связь с сервисом, и наоборот. Поскольку
+иерархия сервисом используется для распределения нагрузки на узлы кластера,
+иерархия управляющих объектов отображается на нее, и это отображение может быть
+произвольным: обычна ситуация, когда руководящий управляющий объект находится на
+подчиненном узле, а его подчиненные управляющие объекта распределены равномерно
+между всеми узлами кластера (включая узел, где находится руководящий объект).
+Обе иерархии может быть сколь угодно глубокими, но "неглубокие" являются
+предпочтительными для высоко параллельных программ, так как в них меньше
+количество промежуточных узлов, через которые должны пройти управляющие объекты
+при распределении между узлами кластера. Поскольку существует однозначное
+соответствие между сервисами и узлами кластера, в данной работе они используются
+как взаимозаменяемые термины.
+
** Реализация для систем с общей памятью (SMP)
**** Алгоритм распределения нагрузки.
Наиболее простым и широко применяемым подходом к распределению нагрузки на
@@ -2633,7 +2654,7 @@ arma.plot_factory_vs_openmp_overlap(
:END:
Многие распределенные системы построены по принципу /субординации/: в каждом
-кластере выбирается главный (руководящий) узел, который управляет очередью
+кластере выбирается руководящий узел, который управляет очередью
задач, планирует их запуск на подчиненных узлах и следит за их состоянием. Роль
главного узла задается либо /статически/, путем выделения конкретного
физического узла под нее, либо /динамически/, путем избрания какого-либо из
@@ -2646,15 +2667,17 @@ arma.plot_factory_vs_openmp_overlap(
требует наличия простаивающих резервных узлов на случай отказа главного узла.
Алгоритмы выбора лидера (которые иногда называют алгоритмами /распределенного
-консенсуса/) являются частными случаями волновых алгоритмов. В\nbsp{}cite:tel2000introduction Тель определяет их как алгоритмы, в которых событие
-завершения программы предваряется хотя бы одним каким-либо другим событием,
-происходящем в /каждом/ параллельном процессе. Волновые алгоритмы не определены
-для анонимных сетей, т.е. они работают только с теми параллельными процессами,
-которые могут себя уникально идентифицировать. Однако, количество процессов,
-которых затрагивает "волна", может быть определено по мере выполнения алгоритма.
-В рамках распределенных систем это означает, что волновые алгоритмы подходят для
-вычислительных кластеров с динамически меняющимся количеством узлов, так что
-включение и выключение отдельных узлов не влияет на работу алгоритма.
+консенсуса/) являются частными случаями волновых алгоритмов.
+В\nbsp{}cite:tel2000introduction Тель определяет их как алгоритмы, в которых
+событие завершения программы предваряется хотя бы одним каким-либо другим
+событием, происходящем в /каждом/ параллельном процессе. Волновые алгоритмы не
+определены для анонимных сетей, т.е. они работают только с теми параллельными
+процессами, которые могут себя уникально идентифицировать. Однако, количество
+процессов, которых затрагивает "волна", может быть определено по мере выполнения
+алгоритма. В рамках распределенных систем это означает, что волновые алгоритмы
+подходят для вычислительных кластеров с динамически меняющимся количеством
+узлов, так что включение и выключение отдельных узлов не влияет на работу
+алгоритма.
Подход к динамическому выбору главного узла, исследованный в данной работе, не
использует волновые алгоритмы, а значит не требует опроса всех узлов кластера
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -3236,7 +3236,6 @@ graph G {
#+label: fig-subord-ppl
#+RESULTS: fig-subord-ppl
[[file:build/subord-ppl.pdf]]
-
**** Governing principles.
Data processing pipeline model is based on the following principles, following
which maximises efficiency of a programme.
@@ -3284,6 +3283,23 @@ which maximises efficiency of a programme.
So, control flow objects (or kernels) possess properties of both cooperative
routines and event handlers.
+**** Definitions of hierarchies
+To disambiguate hierarchical links between daemon processes and kernels and to
+simplify the discussion, we will use the following naming conventions throughout
+the text. If the link is between two daemon processes, the relationship is
+denoted as /master-slave/. If the link is between two kernels, then the
+relationship is denoted as either /principal-subordinate/ or /parent-child/. Two
+hierarchies are orthogonal to each other in a sense that no kernel may have a
+link to a daemon, and vice versa. Since daemon hierarchy is used to distribute
+the load on cluster nodes, kernel hierarchy is mapped onto it, and this mapping
+can be arbitrary: It is common to have principal kernel on a slave node with its
+subordinate kernels distributed evenly between all cluster nodes (including the
+node where the principal is located). Both hierarchies can be arbitrarily deep,
+but "shallow" ones are preferred for highly parallel programmes, as there are
+less number of hops when kernels are distributed between cluster nodes. Since
+there is one-to-one correspondence between daemons and cluster nodes, they are
+used interchangeably in the work.
+
** SMP implementation
**** Load balancing algorithm.
The simplest approach to balance the load on a multi-processor system is to
