arma-thesis

git clone https://git.igankevich.com/arma-thesis.git
Log | Files | Refs | LICENSE

commit c8a2f01a6e87aa6545fb28323f47247f7b60b44b
parent c601cf1214430870e0c9ee06c0e91c9eed4a1b1a
Author: Ivan Gankevich <igankevich@ya.ru>
Date:   Mon, 13 Feb 2017 16:59:22 +0300

Sync kernel hierarchy.

Diffstat:
phd-diss-ru.org | 100++++++++++++++++++++++++++++++++++++-------------------------------------------
phd-diss.org | 84++++++++++++++++++++++++++++++++++++++++---------------------------------------
2 files changed, 88 insertions(+), 96 deletions(-)

diff --git a/phd-diss-ru.org b/phd-diss-ru.org @@ -2416,6 +2416,9 @@ arma.plot_factory_vs_openmp_overlap( ** Реализация для систем с распределенной памятью (MPP) *** Алгоритм обнаружения узлов кластера +:PROPERTIES: +:CUSTOM_ID: sec:node-discovery +:END: **** Введение. Многие распределенные системы построены по принципу /субординации/: в каждом кластере выбирается главный (руководящий) узел, который управляет очередью @@ -2715,42 +2718,30 @@ digraph { переменных. **** Иерархия управляющих объектов. -Для распределения нагрузки узлы кластера объединяются в -древовидную иерархию. Нагрузка распределяется между непосредственными соседями -узла, так что при запуске задачи на подчиненном узле главный узел также -получают часть нагрузки. Это делает систему симметричной и легкой в -обслуживании: на каждом узле установлен один и тот же набор программного -обеспечения, что позволяет заменить один узел другим при выходе из строя -первого. Похожее архитектурное решение используется в хранилищах типа -"ключ-значение" cite:anderson2010couchdb,lakshman2010cassandra для -обеспечения отказоустойчивости при выходе из строя одного из узлов, однако -автору неизвестны планировщики задач, которые используют данный подход. - -Каждая программа, запущенная поверх иерархии узлов состоит из -/вычислительных объектов/ --- объектов, которых содержат данные и код для -их обработки. Для эффективного использования параллелизма, предоставляемого -кластером и многопроцессорной машиной, объект может создать подчиненные -(дочерние) объекты, которые система автоматически распределит сначала между -доступными процессорными ядрами, затем между подчиненными узлами кластера. Сама -программа также является вычислительным объектом, который либо решает -прикладную задачу последовательно, либо создает подчиненные объекты для -параллельного решения. +Для распределения нагрузки узлы кластера объединяются в древовидную иерархию +(см. раздел [[#sec:node-discovery]]), и нагрузка распределяется между +непосредственными соседями узла, так что при запуске управляющего объекта на +подчиненном узле главный узел также получают часть его подчиненных объектов. Это +делает систему симметричной и легкой в обслуживании: на каждом узле установлен +один и тот же набор программного обеспечения, что позволяет заменить один узел +другим при выходе из строя первого. Похожее архитектурное решение используется в +хранилищах типа ключ-значение cite:anderson2010couchdb,lakshman2010cassandra для +обеспечения отказоустойчивости, однако автору неизвестны планировщики задач, +которые используют данный подход. В отличие от функции ~main~ в программах на основе библиотеки передачи -сообщений, первый вычислительный объект выполняется только на одном узле, а -дополнительные узлы используются либо при переполнении очереди объектов -текущего узла, либо при явном указании в коде программы. Такая архитектура -позволяет использовать произвольное количество узлов для запуска задачи и -динамически менять это количество во время ее выполнения. Похожий принцип -выполнения задач используется в системах обработки больших объемов -данных cite:dean2008mapreduce,vavilapalli2013yarn --- при запуске задаче не -требуется указывать количество узлов, вместо этого система сама выбирает узлы, -на которых будет выполняться задача, в зависимости физического расположения -входных файлов. - -С математической точки зрения вычислительный объект $K$ может быть определен -как векторнозначный функционал, отображающий один вычислительный объект на -\(n\)-компонентный вектор вычислительных объектов: +сообщений, первый (главный) управляющий объект выполняется только на одном узле, +а дополнительные узлы используются по необходимости. Такое решение позволяет +использовать произвольное количество узлов для запуска задачи и динамически +менять это количество во время ее выполнения. Похожее решение используется в +системах обработки больших объемов данных +cite:dean2008mapreduce,vavilapalli2013yarn --- пользователь, запускающий задачу +на кластере, не указывает количество узлов, фактические узлы --- это узлы, на +которых расположены входные файлы. + +С математической точки зрения управляющий объект $K$ может быть определен как +векторнозначный функционал, отображающий один управляющий объект на +\(n\)-компонентный вектор управляющих объектов: \begin{equation*} K(f): \mathbb{K} \rightarrow \mathbb{K}^n \qquad @@ -2758,30 +2749,29 @@ digraph { \end{equation*} Специальный объект $\mathbb{O}: \mathbb{K} \rightarrow \mathbb{K}^0$ используется для остановки рекурсии, и передается в качестве аргумента главному -(первому созданному) объекту программы. Аргумент функционала интерпретируется +управляющему объекту программы. Аргумент управляющего объекта интерпретируется следующим образом. -- Если текущий объект является только что созданным объектом, то аргумент - функционала --- это главенствующий над ним объект (родитель). -- Если текущий объект является родителем объекта, который его породил или - родителем какого-либо другого объекта, то аргумент функционала --- объект, - которые его породил. - -Объекты обрабатываются в цикле, который начинается с вызова функции главного -объекта программы, затем вызываются функции всех порожденных им объектов. Цикл -продолжается до тех пор пока функция какого-либо объекта не вернет -$\mathbb{O}$. Поскольку вызов функции может породить сразу несколько объектов, -они выполняются параллельно, что приводит к быстрому заполнению пула объектов, -которые можно выполнять в произвольном порядке. Несколько потоков одновременно -выбирают из пула объекты для обработки, и при переполнении пула объекты могут -быть переданы на другие узлы кластера без явного указания в исходном коде -программы. - -Вычислительные объекты реализованы в виде замыканий (функторов) --- +- Если объект является только что созданным объектом, то аргумент --- это его + родительский объект. +- В остальных случаях аргументом может являться любой объект (чаще всего + дочерний по отношению к текущему). + +Объекты обрабатываются в цикле, который начинается с выполнением главного +объекта, затем внутри главного объекта создаются и асинхронно выполняются другие +объекты. Цикл продолжается до тех пор пока какой-либо объекта не вернет +\(\mathbb{O}\). Поскольку вызов функции может породить сразу несколько объектов, +они выполняются параллельно, что приводит к быстрому заполнению пула объектов. +Поскольку объекты из пула могут выполняться в произвольном порядке, несколько +потоков одновременно выбирают объекты для обработки, и при переполнении +пула объекты могут быть переданы на другие узлы кластера без явного указания в +исходном коде программы. + +Вычислительные объекты реализованы в виде замыканий (функторы в C++) --- объектов-функций, которые сохраняют в себе аргументы, ссылку на породивший их объект и данные из предметной области задачи. Данные обрабатываются либо при -выполнении объекта, либо для параллельной обработки создаются дочерние объекты. -Когда обработка завершена, родительский объект вызывается с дочерним объектов в -качестве аргумента для сбора результатов обработки. +выполнении объекта, либо для параллельной обработки создаются подчиненные +объекты. Когда обработка завершена, родительский объект вызывается с дочерним +объектом в качестве аргумента для сбора результатов обработки. **** Выход из строя одного узла. Наиболее распространенная стратегия при выходе из строя подчиненного узла --- diff --git a/phd-diss.org b/phd-diss.org @@ -1423,7 +1423,7 @@ elevation by skew-normal distribution: f(z; \alpha) & = \frac{e^{-\frac{z^2}{2}}}{\sqrt{2 \pi }} \mathrm{erfc}\left[-\frac{\alpha z}{\sqrt{2}}\right], \end{align} -where $T$ --- Owen $T$-function cite:owen1956tables. Using this formula it is +where $T$ --- Owen \(T\)-function cite:owen1956tables. Using this formula it is impossible to specify skewness and kurtosis separately --- both values are adjusted via $\alpha$ parameter. The only advantage of the formula is its relative computational simplicity: this function is available in some programmes @@ -2268,6 +2268,9 @@ devices other than disks may be used as well. ** MPP implementation *** Cluster node discovery algorithm +:PROPERTIES: +:CUSTOM_ID: sec:node-discovery +:END: **** Introduction. Many distributed systems are built on the principle of /subordination/: there is principal node in each cluster which manages job queue, schedules their @@ -2619,55 +2622,54 @@ determine if a node failed, it assumes a failure when the network connection to a node is prematurely closed. **** Hierarchy of control flow objects -Each programme that runs on top of the tree hierarchy is composed of -computational kernels---objects that contain data and code to process it. To -exploit parallelism a kernel may create arbitrary number of subordinate kernels -which are automatically spread first across available processor cores, second -across subordinate nodes in the tree hierarchy. The programme is itself a kernel -(without a parent as it is executed by a user), which either solves the problem -sequentially on its own or creates subordinate kernels to solve it in parallel. - -Unlike main function in programmes based on message passing library, the first -computational kernel is initially run only on one node, and remote nodes are -used only when the local queue is overflown by kernels. This design choice -allows to have arbitrary number of nodes throughout execution of a programme, -and take more nodes for highly parallel parts of the code. Somewhat similar -choice was made in the design of MapReduce framework +For load balancing purposes cluster nodes are combined into tree hierarchy (see +section [[#sec:node-discovery]]), and the load is distributed between direct +neighbours: when one runs the kernel on the subordinate node, the principal node +also receive some of its subordinate kernels. This makes the system symmetrical +and easy to maintain: each node have the same set of software that allows +replacing one node with another in case of failure of the former. Similar +architectural solution used in key-value stores +cite:anderson2010couchdb,lakshman2010cassandra to provide fault tolerance, but +author does not know any task schedulers that use this approach. + +Unlike ~main~ function in programmes based on message passing library, the first +(the main) kernel is initially run only on one node, and remote nodes are used +on-demand. This design choice allows having arbitrary number of nodes throughout +execution of a programme, and use more nodes for highly parallel parts of the +code. Similar choice is made in the design of big data frameworks cite:dean2008mapreduce,vavilapalli2013yarn --- a user submitting a job does not -specify the number of hosts to run its job on, and effective hosts are the hosts +specify the number of hosts to run its job on, and actual hosts are the hosts where input files are located. From mathematical point of view kernel $K$ can be described as a vector-valued -functional which recursively maps a kernel to $n$-component vector of kernels: +functional which recursively maps a kernel to \(n\)-component vector of kernels: \begin{equation*} K(f): \mathbb{K} \rightarrow \mathbb{K}^n \qquad \mathbb{K}^n = \left\{ f: \mathbb{K} \rightarrow \mathbb{K}^n \right\}. \end{equation*} -Dummy kernel $\mathbb{O}: \mathbb{K} \rightarrow \mathbb{K}^0$, which stops -recursion, is used to call the first kernel and finish execution of the -programme. An argument to each kernel is interpreted using the following rules. -\begin{enumerate} - \item If a kernel is a new kernel, then its argument is its parent kernel. - \item If a kernel is a parent of the kernel that produced it or some other - existing kernel, then the argument is the kernel that produced it. -\end{enumerate} - -Engine that executes kernels is implemented as a simple loop. It starts with -calling the first kernel with a dummy kernel as an argument, then calls each -kernel that was produced by this call and so forth. The loop finishes when a -dummy kernel is returned as a result of the call. - -Since kernel call may return multiple kernels they are executed in parallel. -Parallel execution quickly produces a pool of kernels which permit execution in -an unspecified order. Several threads concurrently retrieve kernels from the -pool and may "spill" the remaining kernels to neighbouring cluster nodes. - -Kernels are implemented as closures --- function objects containing all their -arguments, a reference to parent kernel and user-supplied data. The data is -either processed upon kernel call, or subordinate kernels are created to process -it in parallel. When the processing is complete a parent kernel closure with its -subordinate kernel as an argument is called to collect data from it. +Special kernel $\mathbb{O}: \mathbb{K} \rightarrow \mathbb{K}^0$ is used to stop +the recursion and is passed as an argument to the main kernel. An argument to a +kernel is interpreted as follows. +- If a kernel is a newly created kernel, then its argument is its parent kernel. +- In other cases the argument is an arbitrary kernel (often a child of the + current kernel). + +Kernels are processed in a loop which starts with executing the main kernel, +then inside the main kernel other kernels are created and executed +asynchronously. The loop continues until some kernel returns \(\mathbb{O}\). +Since kernel may return multiple kernels they are executed in parallel, which +quickly fills kernel pool. Since kernels from the pool may be executed in +unspecified order, several concurrent threads retrieve kernels from the pool and +may send the remaining kernels to neighbouring cluster nodes if the pool +overflows. + +Kernels are implemented as closures (functors in C++) --- function objects +containing all their arguments, a reference to parent kernel and application +domain data. The data is either processed upon kernel call, or subordinate +kernels are created to process it in parallel. When the processing is complete a +parent kernel closure with its subordinate kernel as an argument is called to +collect the resulting data from it. **** Fault tolerance. **** Handling single node failures.