commit 71a2f1095e1b86a0b931c876c2f2c2795eaf6d90
parent 73dfeff75d34cb125ec7e9e3e4297387bd7dc4ac
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Fri, 3 Nov 2017 10:17:06 +0300
Remove old section.
Diffstat:
| arma-thesis-ru.org | | | 84 | +++++++++++++++---------------------------------------------------------------- |
| arma-thesis.org | | | 47 | ----------------------------------------------- |
2 files changed, 16 insertions(+), 115 deletions(-)
diff --git a/arma-thesis-ru.org b/arma-thesis-ru.org
@@ -2661,59 +2661,6 @@ graph G {
расходы, и не популярно в высокопроизводительных вычислениях. Фреймворк
называется Bscheduler и находится на этапе проверки концепции.
-**** Основополагающие принципы модели. :noexport:
-Модель конвейера обработки данных строится по следующим принципам, следование
-которым обеспечивает максимальную эффективность программы.
-- В модели отсутствует понятие сообщения, роль сообщения выполняет сам
- управляющий объект: он может быть передан по сети на другой узел и получить
- доступ к полям любого другого управляющего объекта на этом узле. Гарантировать
- существование такого объекта может только логика программы.
-- Управляющий объект представляет собой /сопрограмму/, которая при вызове
- отправляется в пул управляющих объектов и затем выполняется планировщиком
- асинхронно. Тело сопрограммы может содержать произвольное количество вызовов
- других сопрограмм. Каждый вызов отправляет соответствующую сопрограмму в пул и
- сразу завершается. Управляющие объекты, находящиеся в пуле, могут быть
- обработаны в любом порядке; это используется планировщиком для извлечения
- максимального параллелизма из вычислительной системы путем распределения
- объектов из пула между доступными узлами кластера и ядрами процессора.
-- Асинхронное выполнение управляющих объектов позволяет избежать явной
- синхронизации после вызова сопрограммы (отправки объекта в очередь);
- планировщик возвращает поток управления в родительский управляющий объект
- каждый раз когда какой-либо его дочерний объект завершает выполнение. Такое
- взаимодействие превращает сопрограмму в некоторого рода обработчик событий, в
- котором событием является дочерний объект, а обработчиком\nbsp{}--- родительский.
-- Сопрограмма может взаимодействовать с произвольным количеством управляющих
- объектов, адреса которых известны; взаимодействие с объектами, осуществляемое
- вразрез с иерархией сильно усложняет поток управления и стек вызовов
- сопрограмм теряет древовидную структуру. Только логика программы может
- гарантировать существование в памяти машины двух взаимодействующих объектов.
- Один из способов обеспечения такой гарантии\nbsp{}--- взаимодействие между
- вложенными сопрограммами, вызванными из одной родительской сопрограммы.
- Поскольку такого рода взаимодействие можно осуществить в рамках иерархии через
- родительскую сопрограмму, его можно считать оптимизацией, позволяющей
- избавиться от накладных расходов при передаче данных через промежуточный узел.
- Для программ, логика которых полностью основана на событиях (например, для
- серверов и программ с графическим интерфейсом), ситуация иная, и такого рода
- взаимодействия являются основными.
-- Также, взаимодействия, идущие вразрез с иерархией и поверх сети кластера,
- усложняют разработку алгоритмов обеспечения отказоустойчивости. Гарантировать
- нахождение определенного управляющего объекта в памяти соседнего узла
- невозможно, поскольку узел может выйти из строя прямо во время выполнения
- соответствующей сопрограммы. В результате, при аварийном завершении
- сопрограммы, все его вложенные сопрограммы должны быть выполнены заново. Это
- подталкивает программиста к созданию
- - глубоких древовидных иерархий сильно связанных управляющих объектов (которые
- взаимодействуют между собой на одном уровне иерархии), уменьшающих накладные
- расходы на повторное выполнение сопрограмм;
- - толстых древовидных иерархий слабо связанных управляющих объектов,
- обеспечивающих максимальную степень параллелизма.
- Глубокие иерархии это не только требование технологии, они помогают
- оптимизировать сетевое взаимодействие большого количества узлов кластера,
- сводя его к взаимодейсвтвию соседних узлов.
-
-Таким образом, управляющие объекты обладают свойствами как сопрограмм, так и
-обработчиков событий одновременно.
-
**** Программный интерфейс.
Каждый управляющий объект имеет четыре типа полей (перечисленных в
табл.\nbsp{}[[tab-kernel-fields]]):
@@ -2796,21 +2743,22 @@ downstream-объектов. Это означает, что если решае
выходным данным предыдущего звена. Звенья конвейера распределяются по узлам
вычислительного кластера, чтобы сделать возможным параллелизм по операциям, а
затем данные, перемещающиеся между звеньями конвейера распределяются между
-ядрами процессора, чтобы сделать возможным параллелизм по данным. На рис.\nbsp{}[[fig-pipeline]] представлена схема конвейера обработки данных, в которой
+ядрами процессора, чтобы сделать возможным параллелизм по данным. На
+рис.\nbsp{}[[fig-pipeline]] представлена схема конвейера обработки данных, в которой
прямоугольниками со скругленными углами обозначены звенья конвейера, обычными
-прямоугольниками\nbsp{}--- массивы объектов из предметной области задачи, передаваемые
-от одного звена к другому, а стрелками\nbsp{}--- направление передачи данных.
-Некоторые звенья разделены на /секции/, каждая из которых обрабатывает отдельную
-часть массива. Если звенья соединены без использования /барьера/ (горизонтальная
-или вертикальная полоса), то передача отдельных объектов между такими звеньями
-происходит параллельно с вычислениями, по мере их готовности. Секции работают
-параллельно на нескольких ядрах процессора (нескольких узлах кластера). Таким
-образом, между множеством ядер процессора, секций звеньев конвейера и объектами
-устанавливается сюръективное отображение, т.е. на одном ядре процессора может
-работать несколько секций звеньев конвейера, каждая из которых может
-обрабатывать несколько объектов последовательно, но одна секция не может
-работать сразу на нескольких ядрах, а объект не может обрабатываться сразу
-несколькими секциями конвейера.
+прямоугольниками\nbsp{}--- массивы объектов из предметной области задачи,
+передаваемые от одного звена к другому, а стрелками\nbsp{}--- направление
+передачи данных. Некоторые звенья разделены на /секции/, каждая из которых
+обрабатывает отдельную часть массива. Если звенья соединены без использования
+/барьера/ (горизонтальная или вертикальная полоса), то передача отдельных
+объектов между такими звеньями происходит параллельно с вычислениями, по мере их
+готовности. Секции работают параллельно на нескольких ядрах процессора
+(нескольких узлах кластера). Таким образом, между множеством ядер процессора,
+секций звеньев конвейера и объектами устанавливается сюръективное отображение,
+т.е. на одном ядре процессора может работать несколько секций звеньев конвейера,
+каждая из которых может обрабатывать несколько объектов последовательно, но одна
+секция не может работать сразу на нескольких ядрах, а объект не может
+обрабатываться сразу несколькими секциями конвейера.
#+name: fig-pipeline
#+begin_src dot :exports results :file build/pipeline-ru.pdf
@@ -2923,7 +2871,7 @@ digraph {
Parallel)\nbsp{}cite:valiant1990bridging, применяемой в системах обработки
графов\nbsp{}cite:malewicz2010pregel,seo2010hama. Конвейер позволяет исключить
глобальную синхронизацию (где это возможно) между последовательно идущим этапами
-вычислений путем передачи данных между звеньев параллельно с вычислениями, в то
+вычислений путем передачи данных между звеньями параллельно с вычислениями, в то
время как в модели BSP глобальная синхронизация происходит после каждого шага.
Конвейер объектов ускоряет программу путем параллельного выполнения блоков кода,
diff --git a/arma-thesis.org b/arma-thesis.org
@@ -2738,53 +2738,6 @@ So, computational model with a pipeline can be seen as /bulk-asynchronous
model/, because of the parallel nature of programme steps. This model is the
basis of the fault-tolerance model which will be described later.
-*** Computational model :noexport:
-**** Governing principles.
-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 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
- each routine which calls subroutines into event handler, where each event is a
- 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 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 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
- adjacent nodes.
-
-So, control flow objects (or kernels) possess properties of both cooperative
-routines and event handlers.
*** Cluster node discovery algorithm
:PROPERTIES:
:CUSTOM_ID: sec-node-discovery
