commit 3d29d6aa036645714778526dbf552f7ab7325f04
parent e95e62f46b2f878fc95d5bd53539eb5f651315df
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Thu, 26 Jan 2017 14:32:05 +0300
Sync governing principles.
Diffstat:
| phd-diss-ru.org | | | 59 | +++++++++++++++++++++++++++++++---------------------------- |
| phd-diss.org | | | 73 | +++++++++++++++++++++++++++++++++++++------------------------------------ |
2 files changed, 68 insertions(+), 64 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -1942,8 +1942,9 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
двух слоев: на нижнем слое находятся подпрограммы и классы для приложений,
работающих на одном узле (без сетевых взаимодействий), на верхнем слое --- для
приложений, работающих на произвольном количестве узлов. Модель включает в себя
-два вида сильно связанных друг с другом сущностей --- /управляющие объекты/ и
-/конвейеры/, --- которые используются совместно для написания программы.
+два вида сильно связанных друг с другом сущностей --- /управляющие объекты/ (или
+/ядра/) и /конвейеры/, --- которые используются совместно для написания
+программы.
Управляющие объекты реализуют логику (порядок выполнения) программы в методах
~act~ и ~react~ и хранят состояние текущей ветки исполнения. Как логика так и
@@ -1992,45 +1993,47 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
доступ к полям любого другого управляющего объекта на этом узле. Гарантировать
существование такого объекта может только логика программы.
- Управляющий объект представляет собой /сопрограмму/, которая при вызове
- отправляется в пул задач и затем выполняется планировщиком асинхронно. Тело
- сопрограммы может содержать произвольное количество вызовов других сопрограмм.
- Каждый вызов отправляет соответствующую сопрограммы в пул задач и сразу
- завершается. Управляющие объекты, находящиеся в пуле, могут быть обработаны в
- любом порядке; это используется планировщиком для извлечения максимального
- параллелизма из вычислительной системы путем распределения объектов из пула
- между доступными узлами кластера и ядрами процессора.
+ отправляется в пул управляющих объектов и затем выполняется планировщиком
+ асинхронно. Тело сопрограммы может содержать произвольное количество вызовов
+ других сопрограмм. Каждый вызов отправляет соответствующую сопрограмму в пул и
+ сразу завершается. Управляющие объекты, находящиеся в пуле, могут быть
+ обработаны в любом порядке; это используется планировщиком для извлечения
+ максимального параллелизма из вычислительной системы путем распределения
+ объектов из пула между доступными узлами кластера и ядрами процессора.
- Асинхронное выполнение управляющих объектов позволяет избежать явной
синхронизации после вызова сопрограммы (отправки объекта в очередь);
планировщик возвращает поток управления в родительский управляющий объект
каждый раз когда какой-либо его дочерний объект завершает выполнение. Такое
- /взаимодействие/ превращает сопрограмму в некоторого рода обработчик событий,
- в котором событием является дочерний объект, а обработчиком --- родительский.
-- Механизм обработки событий может быть использован для передачи потока
- управления не только в родительский, но и любой другой объект, адрес которого
- известен; взаимодействие с объектами, осуществляемое вразрез с иерархией
- сильно усложняет поток управления и стек вызовов сопрограмм теряет древовидную
- структуру. Только логика программы может гарантировать существование в памяти
- машины двух взаимодействующих объектов. Один из способов обеспечения такой
- гарантии --- взаимодействие между дочерними объектами одного родительского
- объекта, которое типично для параллельной пакетной обработки данных. Поскольку
- такого рода взаимодействие можно осуществить в рамках иерархии через
- родительский объект, его можно считать оптимизацией, позволяющей избавиться от
- накладных расходов при передаче данных через промежуточный узел. Для программ,
- логика которых полностью основана на событиях (например, для серверов и
- программ с графическим интерфейсом), ситуация иная, и такого рода
+ взаимодействие превращает сопрограмму в некоторого рода обработчик событий, в
+ котором событием является дочерний объект, а обработчиком --- родительский.
+- Сопрограмма может взаимодействовать с произвольным количеством управляющих
+ объектов, адреса которых известны; взаимодействие с объектами, осуществляемое
+ вразрез с иерархией сильно усложняет поток управления и стек вызовов
+ сопрограмм теряет древовидную структуру. Только логика программы может
+ гарантировать существование в памяти машины двух взаимодействующих объектов.
+ Один из способов обеспечения такой гарантии --- взаимодействие между
+ вложенными сопрограммами, вызванными из одной родительской сопрограммы.
+ Поскольку такого рода взаимодействие можно осуществить в рамках иерархии через
+ родительскую сопрограмму, его можно считать оптимизацией, позволяющей
+ избавиться от накладных расходов при передаче данных через промежуточный узел.
+ Для программ, логика которых полностью основана на событиях (например, для
+ серверов и программ с графическим интерфейсом), ситуация иная, и такого рода
взаимодействия являются основными.
-- Также, взаимодействия, идущие вразрез с иерархией, усложняют алгоритмы
- обеспечения отказоустойчивости, применяемый для кластеров машин. Гарантировать
+- Также, взаимодействия, идущие вразрез с иерархией и поверх сети кластера,
+ усложняют разработку алгоритмов обеспечения отказоустойчивости. Гарантировать
нахождение определенного управляющего объекта в памяти соседнего узла
невозможно, поскольку узел может выйти из строя прямо во время выполнения
соответствующей сопрограммы. В результате, при аварийном завершении
- управляющего объекта, все его дочерние объекты должны быть выполнены заново.
- Это подталкивает программиста к созданию
+ сопрограммы, все его вложенные сопрограммы должны быть выполнены заново. Это
+ подталкивает программиста к созданию
- глубоких иерархий сильно связанных управляющих объектов (которые
взаимодействуют между собой на одном уровне иерархии), уменьшающих накладные
расходы на повторное выполнение сопрограмм;
- толстых иерархий слабо связанных управляющих объектов, обеспечивающих
максимальную степень параллелизма.
+ Глубокие иерархии это не только требование технологии, они помогают
+ оптимизировать сетевое взаимодействие большого количества узлов кластера,
+ сводя его к взаимодейсвтвию соседних узлов.
Таким образом, управляющие объекты обладают свойствами как сопрограмм, так и
обработчиков событий одновременно.
diff --git a/phd-diss.org b/phd-diss.org
@@ -1871,8 +1871,8 @@ it transparently to a programmer. The implementation is divided into two layers:
the lower layer consists of routines and classes for single node applications
(with no network interactions), and the upper layer for applications that run on
an arbitrary number of nodes. There are two kinds of tightly coupled entities in
-the model --- /kernels/ and /pipelines/ --- which are used together to compose a
-programme.
+the model --- /control flow objects/ (or /kernels/) and /pipelines/ --- which
+are used together to compose a programme.
Kernels implement control flow logic in theirs ~act~ and ~react~ methods and
store the state of the current control flow branch. Both logic and state are
@@ -1909,50 +1909,51 @@ Pipelines, in turn, allow implementing passive wait, and call correct kernel
methods by analysing their internal state.
*** Governing principles
-- There are no messages in the model, a kernel is itself a message that can be
- sent over network to another node and directly access any kernel on the local
- node. It is responsibility of a programmer to ensure that such kernel exist.
-- A kernel is a /cooperative routine/, which is submitted to task pool upon the
+Data processing pipeline model is based on the following principles, following
+which maximises efficiency of a programme.
+- There is no notion of a message in the model, a kernel is itself a message
+ that can be sent over network to another node and directly access any kernel
+ on the local node. Only programme logic may guarantee the existence of the
+ kernel.
+- A kernel is a /cooperative routine/, which is submitted to kernel pool upon the
call and is executed asynchronously by a scheduler. There can be any number of
calls to other subroutines inside routine body. Every call submits
- corresponding subroutine to task pool and returns immediately. Kernels in the
+ corresponding subroutine to kernel pool and returns immediately. Kernels in the
pool can be executed in any order; this fact is used by a scheduler to exploit
parallelism offered by the computer by distributing kernels from the pool
across available cluster nodes and processor cores.
- Asynchronous execution prevents the use of explicit synchronisation after the
call to subroutine is made; system scheduler returns control flow to the
- routine each time one of its subroutine returns. Such *cooperation* transforms
+ routine each time one of its subroutine returns. Such cooperation transforms
each routine which calls subroutines into event handler, where each event is a
- subroutine and the handler is the routine that called them. In many batch
- processing programmes control flow enters each routine which calls subroutines
- at least twice: the first time it occurs upon the call to the routine and the
- second time happens when control flow returns to the caller after completion
- of a subroutine.
+ subroutine and the handler is the routine that called them.
- The routine may communicate with any number of local kernels, addresses of
- which it knows; communication with routines which are not adjacent in the call
- stack complexifies control flow and call stack looses its tree shape. It is
- responsibility of a programmer to ensure that communicating kernels are
- present in memory. One way to ensure this is to perform communication between
- subroutines which are called from the same routine. Incidentally, it is the
- usual way of writing batch parallel programmes: each such communication
- creates a cycle in the call stack graph, and a cycle between different
- (possibly non-adjacent) layers of kernel hierarchy is redundant, because there
- are other edges that can be used instead. The situation may be different when
- the programme is interactive or event-based.
-- The other disadvantage of communication which does not occur along
- hierarchical links is that it complexifies resiliency algorithms when executed
- across cluster network. Since it is difficult to ensure that a kernel resides
- in memory of a neighbour node, because a node may fail in the middle of its
- execution. Thus, upon failure of a node all of the subroutines which are
- called from the same routine must be restarted. This encourages a programmer
- to construct
- - deep hierarchies of tightly-coupled kernels (which require communication on
- the same level of hierarchy) to reduce overhead of recomputation,
- - fat hierarchies of loosely-coupled kernels.
+ which it knows; communication with kernels which are not adjacent in the call
+ stack complexifies control flow and call stack looses its tree shape. Only
+ programme logic may guarantee presence of communicating kernels in memory. One
+ way to ensure this is to perform communication between subroutines which are
+ called from the same routine. Since such communication is possible within
+ hierarchy through parent routine, it may treated as an optimisation that
+ eliminates overhead of transferring data over intermediate node. The situation
+ is different for interactive or event-based programmes (e.g. servers and
+ programmes with graphical interface) in which this is primary type of
+ communication.
+- In addition to this, communication which does not occur along hierarchical
+ links and executed over cluster network complexify design of resiliency
+ algorithms. Since it is impossible to ensure that a kernel resides in memory
+ 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
+ parallelism.
Deep hierarchy is not only requirement of technology, it helps optimise
- communication of cluster nodes limiting it to adjacent nodes.
-- No explicit synchronisation.
-- Local communications between adjacent nodes in the hierarchy.
+ communication of large number of cluster nodes reducing it to communication of
+ adjacent nodes.
+
+So, control flow objects (or kernels) possess properties of both cooperative
+routines and event handlers.
** SMP implementation
*** Load balancing algorithm
