commit 26fdcbce93b4664a873637f91265954650101a3d
parent 2c428126e5b64994b02f9ad1feedc8465d5950f3
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Fri, 24 Mar 2017 17:03:53 +0300
Merge the first and the second sections. Add comparsion to migratable objects model.
Diffstat:
| src/body.tex | | | 48 | ------------------------------------------------ |
| src/head.tex | | | 109 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------ |
2 files changed, 93 insertions(+), 64 deletions(-)
diff --git a/src/body.tex b/src/body.tex
@@ -1,51 +1,3 @@
-\section{Computational kernel hierarchy}
-
-The framework provides classes and methods to simplify development of
-distributed applications and middleware. The focus is to make distributed
-application resilient to failures, i.e.~make it fault tolerant and highly
-available, and do it transparently to a programmer. All classes are divided
-into two layers: the lower layer consists of classes for single node
-applications, and the upper layer consists of classes for applications that run
-on an arbitrary number of nodes. There are two kinds of tightly coupled
-entities in the framework~--- \emph{kernels} and \emph{pipelines}~--- which are
-used together to compose a~programme.
-
-Kernels implement control flow logic in theirs \Method{act} and \Method{react}
-methods and store the state of the current control flow branch. Domain-specific
-logic and state are implemented by a programmer. In~\Method{act} method some
-function is either sequentially computed or decomposed into subtasks
-(represented by another set of kernels) which are subsequently sent to a
-pipeline. In~\Method{react} method subordinate kernels that returned from the
-pipeline are processed by their parent. Calls to \Method{act} and
-\Method{react} methods are asynchronous and are made within threads spawned by
-a pipeline. For each kernel \Method{act} is called only once, and for multiple
-kernels the calls are done in parallel to each other, whereas \Method{react}
-method is called once for each subordinate kernel, and all the calls are made
-in the same thread to prevent race conditions (for different parent kernels
-different threads may be used).
-
-Pipelines implement asynchronous calls to \Method{act} and \Method{react}, and
-try to make as many parallel calls as possible considering concurrency of the
-platform (no.~of cores per node and no.~of nodes in a cluster). A~pipeline
-consists of a kernel pool, which contains all the subordinate kernels sent by
-their parents, and a thread pool that processes kernels in accordance with
-rules outlined in the previous paragraph. A~separate pipeline exists for each
-compute device: There are pipelines for parallel processing, schedule-based
-processing (periodic and delayed tasks), and a proxy pipeline for processing of
-kernels on other cluster nodes.
-
-In principle, kernels and pipelines machinery reflect the one of procedures and
-call stacks, with the advantage that kernel methods are called asynchronously
-and in parallel to each other. The stack, which ordinarily stores local
-variables, is modelled by fields of a kernel. The sequence of processor
-instructions before nested procedure calls is modelled by~\Method{act} method,
-and sequence of processor instructions after the calls is modelled
-by~\Method{react} method. The procedure calls themselves are modelled
-by~constructing and sending subordinate kernels to the pipeline. Two methods
-are necessary because calls are asynchronous and one must wait before
-subordinate kernels complete their work. Pipelines allow circumventing active
-wait, and call correct kernel methods by analysing their internal state.
-
\section{Cluster scheduler architecture}
\subsection{Overview}
diff --git a/src/head.tex b/src/head.tex
@@ -11,24 +11,101 @@ parallel and sequential parts. Using different fault tolerant scenarios based on
hierarchy interactions framework can provide continuous computations in case of
hardware errors or electricity outages.
+The framework provides classes and methods to simplify development of
+distributed applications and middleware. The focus is to make distributed
+application resilient to failures, i.e.~make it fault tolerant and highly
+available, and do it transparently to a programmer. All classes are divided
+into two layers: the lower layer consists of classes for single node
+applications, and the upper layer consists of classes for applications that run
+on an arbitrary number of nodes. There are two kinds of tightly coupled
+entities in the framework~--- \emph{kernels} and \emph{pipelines}~--- which are
+used together to compose a~programme.
+
+Kernels implement control flow logic in theirs \Method{act} and \Method{react}
+methods and store the state of the current control flow branch. Domain-specific
+logic and state are implemented by a programmer. In~\Method{act} method some
+function is either sequentially computed or decomposed into subtasks
+(represented by another set of kernels) which are subsequently sent to a
+pipeline. In~\Method{react} method subordinate kernels that returned from the
+pipeline are processed by their parent. Calls to \Method{act} and
+\Method{react} methods are asynchronous and are made within threads spawned by
+a pipeline. For each kernel \Method{act} is called only once, and for multiple
+kernels the calls are done in parallel to each other, whereas \Method{react}
+method is called once for each subordinate kernel, and all the calls are made
+in the same thread to prevent race conditions (for different parent kernels
+different threads may be used).
+
+Pipelines implement asynchronous calls to \Method{act} and \Method{react}, and
+try to make as many parallel calls as possible considering concurrency of the
+platform (no.~of cores per node and no.~of nodes in a cluster). A~pipeline
+consists of a kernel pool, which contains all the subordinate kernels sent by
+their parents, and a thread pool that processes kernels in accordance with
+rules outlined in the previous paragraph. A~separate pipeline exists for each
+compute device: There are pipelines for parallel processing, schedule-based
+processing (periodic and delayed tasks), and a proxy pipeline for processing of
+kernels on other cluster nodes.
+
+In principle, kernels and pipelines machinery reflect the one of procedures and
+call stacks, with the advantage that kernel methods are called asynchronously
+and in parallel to each other. The stack, which ordinarily stores local
+variables, is modelled by fields of a kernel. The sequence of processor
+instructions before nested procedure calls is modelled by~\Method{act} method,
+and sequence of processor instructions after the calls is modelled
+by~\Method{react} method. The procedure calls themselves are modelled
+by~constructing and sending subordinate kernels to the pipeline. Two methods
+are necessary because calls are asynchronous and one must wait before
+subordinate kernels complete their work. Pipelines allow circumventing active
+wait, and call correct kernel methods by analysing their internal state.
+
\section{Related work}
-Computational models similar to kernel hierarchy are described in a number of
-papers, but none of them includes hierarchy.
+The feature that distingueshes our research with respect to some others, is the
+use of hierarchy as the only possible way of defining depedencies between
+objects, into which a programme is decomposed. The main advantage of hierarchy
+is trivial handling of object failures.
In~\cite{zuckerman2011using} the authors describe codelet model for exascale
machines. This model breaks a programme into small bits of functionality,
-called codelets, and dependencies between them. The programme represents
-directed graph, which is called well-behaved if forward progress of the
-programme is guaranteed. The feature that distingueshes our research with
-respect to some others, is the use of hierarchy as the only possible way of
-defining depedencies between objects, into which a programme is decomposed. The
-main advantage of hierarchy is trivial handling of object failures. In
-contrast, in codelet model hierarchical depedencies are not enforced, and
-resilience to failures is provided by object migration and relies on hardware
-fault detection mechanisms. Furthermore, execution of kernel hierarchiies in
-our model resembles stack-based execution of ordinary programmes: the programme
-finishes only when all subordinate kernels of the main kernel finish. So, there
-is no need to define well-behaved graph to guarantee programme termination.
-
-\cite{meneses2015using}
+called codelets, and dependencies between them. The programme dataflow
+represents directed graph, which is called well-behaved if forward progress of
+the programme is guaranteed. In contrast to our model, in codelet model
+hierarchical depedencies are not enforced, and resilience to failures is
+provided by object migration and relies on hardware fault detection mechanisms.
+Furthermore, execution of kernel hierarchiies in our model resembles
+stack-based execution of ordinary programmes: the programme finishes only when
+all subordinate kernels of the main kernel finish. So, there is no need to
+define well-behaved graph to guarantee programme termination.
+
+In~\cite{meneses2015using} the authors describe migratable objects model for
+parallel programmes. In the framework of this model a programme is decomposed
+into objects that may communicate with each other by sending messages, and can
+be migrated to any cluster node if desired. The authors propose several
+possibilities, how this model may enhance fault-tolerance techniques for
+Charm++ programmes: proactive fault detection, checkpoint/restart and message
+logging. In contrast to our model, migratable objects do not compose a
+hierarchy, but may exchange messages with any object address of which is known
+to the sender. A spanning tree of nodes is used to orchestrate collective
+operations between objects. This tree is similar to tree hierarchy of nodes,
+which is used in our work to distribute kernels between available cluster
+nodes, but we use this hierarchy for any operations that require distribution
+of work, rather than collective ones, and collective operations are typically
+implemented as point-to-point communication between kernels address of which is
+known to each other. Our model does not use techniques described in this paper
+to provide fault-tolerance: upon a failure we re-execute subordinate kernels
+and copy principal kernels to be able to re-execute them as well. Our approach
+blends checkpoint/restart and message logging: each kernel which is sent to
+other cluster node is saved (logged) in memory of the sender, and removed from
+the log upon return. Since subordinate kernels are allowed to communicate only
+with their principals (all other communication may happen only when physical
+location of the kernel is known, if the communicaton fails, then the kernel
+also fails to trigger recovery by the principal), a collection of all logs on
+each cluster nodes consitutes the current state of programme execution, which
+is used to restart failed kernels on the surviving nodes.
+
+To summarise, the feature that distiguishes our model with respect to models
+proposed for improving parallel programme fault-tolerance is the use of kernel
+hierarchy~--- an abstraction which defines strict total order on a set of
+kernels (their execution order) and, consequently, defines for each kernel a
+principal kernel, responsibility of which is to re-executed failed subordinate
+kernels upon a failure.
+
