commit bc5daf10dec26a2d5f86acf221c91f2989817d66
parent a0c1b4a00678e05717dfb1e0442384b95d9a8d59
Author: Ivan Gankevich <igankevich@ya.ru>
Date: Mon, 13 Feb 2017 13:39:31 +0300
Merge pipeline section into Mapping of generation algorithm.
Diffstat:
| phd-diss-ru.org | | | 39 | ++++++++++++++++++++++++++++++--------- |
| phd-diss.org | | | 83 | +++++++++++++++++++++++++------------------------------------------------------ |
2 files changed, 56 insertions(+), 66 deletions(-)
diff --git a/phd-diss-ru.org b/phd-diss-ru.org
@@ -1929,6 +1929,13 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
путем передачи данных между звеньев параллельно с вычислениями, в то время как в
модели BSP глобальная синхронизация происходит после каждого шага.
+Конвейер объектов ускоряет программу путем параллельного выполнения блоков кода,
+работающих с разными вычислительными устройствами: в то время как текущая часть
+взолнованной поверхности генерируется на процессоре, предыдущая часть
+записывается на диск. Такой подход позволяет получить ускорение, потому что
+различные вычислительные устройства работают асинхронно, и их параллельное
+использование увеличивает производительность программы.
+
Поскольку передача данных между звеньями конвейера происходит параллельно с
вычислениями, то на одном и том же конвейере можно запустить сразу несколько
копий приложения с разными параметрами (генерировать сразу несколько
@@ -1942,6 +1949,29 @@ cite:malewicz2010pregel,seo2010hama. Конвейер позволяет иск
минимизирует время простоя процессора и других устройств компьютера и повышает
общую пропускную способность кластера.
+Конвейеризация шагов программы, которые в противном случае последовательны,
+выгодно не только для кода, работающего с различными устройствами, но и для
+кода, различные ветки которого могут быть запущены на нескольких аппаратных
+потоках одного процессорного ядра, т.е. ветки, осуществляющие доступ к различным
+блокам памяти или использующие смешанную арифметику (целочисленную и с плавающей
+точкой). Ветки кода, которые используют различные модули процессора, являются
+хорошими кандидатами для параллельного запуска на процессорном ядре с
+несколькими аппаратными потоками.
+
+Таким образом, вычислительную модель на основе конвейера можно рассматривать как
+/массивно асинхронную модель/ (bulk-asynchronous model) из-за параллельной
+природы шагов программы. Эта модель является основой модели отказоустойчивости,
+которая будет описана далее.
+
+**** Программная реализация.
+Из соображений эффективности конвейер объектов и методы обеспечения
+отказоустойчивости (которые будут описаны далее) были реализованы во фреймворке
+на языке C++: с точки зрения автора язык C слишком низкоуровневый для написания
+распределенных программ, а использование языка Java влечет за собой накладные
+расходы, и не популярно в высокопроизводительных вычислениях. На данный момент
+фреймворк запускает сервис и приложение в одном процессе. Фреймворк называется
+"Фабрика" и находится на этапе проверки концепции.
+
*** Обзор вычислительной модели
Основное назначение модели состоит в упрощении разработки распределенных
приложений для пакетной обработки данных и промежуточного программного
@@ -2781,15 +2811,6 @@ $\mathbb{O}$. Поскольку вызов функции может пород
использует оперативную память другого узла кластера, а не диск.
**** Обеспечение высокой доступности.
-**** Программная реализация.
-Из соображений эффективности методы обеспечения отказоустойчивости были
-реализованы во фреймворке на языке C++: с точки зрения автора язык C слишком
-низкоуровневый для написания распределенных программ, а использование языка Java
-влечет за собой накладные расходы, и не популярно в высокопроизводительных
-вычислениях. На данный момент фреймворк запускает сервис и приложение в одном
-процессе. Фреймворк называется "Фабрика" и находится на этапе проверки
-концепции.
-
**** Результаты тестирования.
Методы отказоустойчивости были протестированы на физическом кластере
(см. [[tab:cluster]]) на примере программы, генерирующей взволнованную
diff --git a/phd-diss.org b/phd-diss.org
@@ -1859,6 +1859,12 @@ cite:malewicz2010pregel,seo2010hama. Pipeline eliminates global synchronisation
transfer between joints in parallel to computations, whereas in BSP model global
synchronisation occurs after each step.
+Object pipeline speeds up the programme by parallel execution of code blocks
+that work with different compute devices: while the current part of wavy surface
+is generated by a processor, the previous part is written to a disk. This
+approach allows getting speed-up because compute devices operate asynchronously,
+and their parallel usage increases the whole programme performance.
+
Since data transfer between pipeline joints is done in parallel to computations,
the same pipeline may be used to run several copies of the application but with
different parameters (generate several ocean wavy surfaces having different
@@ -1871,6 +1877,26 @@ to a file, the other do computations on the processor in parallel. This
minimises downtime of the processor and other computer devices and increases
throughput of the computer cluster.
+Pipelining of otherwise sequential steps is beneficial not only for code work
+with different devices, but for code different branches of which are suitable
+for execution by multiple hardware threads of the same processor core, i.e.
+branches accessing different memory blocks or performing mixed arithmetic
+(integer and floating point). Code branches which use different modules of
+processor are good candidates to run in parallel on a processor core with
+multiple hardware threads.
+
+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.
+
+**** Software implementation.
+For efficiency reasons object pipeline and fault tolerance techniques (which
+will be described later) are implemented in the C++ framework: From the authors'
+perspective C language is deemed low-level for distributed programmes, and Java
+incurs too much overhead and is not popular in HPC community. As of now, the
+framework runs in the same process as an parallel application that uses it. The
+framework is called Factory, it is now in proof-of-concept development stage.
+
*** Computational model overview
The main purpose of the model is to simplify development of distributed batch
processing applications and middleware. The main focus is to make application
@@ -2582,55 +2608,6 @@ of a master node per superstep. The paper does not answer the question of how to
determine if a node failed, it assumes a failure when the network connection to
a node is prematurely closed.
-**** Pipelining.
-To infer fault tolerance model which is suitable for big data applications we
-use bulk-synchronous parallel model cite:valiant1990bridging as the basis. This
-model assumes that a parallel programme is composed of several sequential steps
-that are internally parallel, and global synchronisation of all parallel
-processes occurs after each step. In our model all sequential steps are
-pipelined where it is possible. The evolution of the computational model is
-described as follows.
-
-Given a programme that is sequential and large enough to be decomposed into
-several sequential steps, the simplest way to make it run faster is to exploit
-data parallelism. Usually it means finding multi-dimensional arrays and loops
-that access their elements and trying to make them parallel. After transforming
-several loops the programme will still have the same number of sequential steps,
-but every step will (ideally) be internally parallel.
-
-After that the only possibility to speedup the programme is to overlap execution
-of code blocks that work with different hardware devices. The most common
-pattern is to overlap computation with network I/O or disk I/O. This approach
-makes sense because all devices operate with little synchronisation, and issuing
-commands in parallel makes the whole programme perform better. This behaviour
-can be achieved by allocating a separate task queue for each device and
-submitting tasks to these queues asynchronously with execution of the main
-thread. So, after this optimisation, the programme will be composed of several
-steps chained into the pipeline, each step is implemented as a task queue for a
-particular device.
-
-Pipelining of otherwise sequential steps is beneficial not only for code
-accessing different devices, but for code different branches of which are
-suitable for execution by multiple hardware threads of the same core, i.e.
-branches accessing different regions of memory or performing mixed arithmetic
-(floating point and integer). In other words, code branches which use different
-modules of processor are good candidates to run in parallel on a processor core
-with multiple hardware threads.
-
-Even though pipelining may not add parallelism for a programme that uses only
-one input file (or a set of input parameters), it adds parallelism when the
-programme can process multiple input files: each input generates tasks which
-travel through the whole pipeline in parallel with tasks generated by other
-inputs. With a pipeline an array of files is processed in parallel by the same
-set of resources allocated for a batch job, and possibly with greater efficiency
-for busy HPC clusters compared to executing a separate job for each input file,
-because the time that each subsequent job after the first spends in a queue is
-eliminated.
-
-Computational model with a pipeline can be seen as /bulk-asynchronous model/,
-because of the parallel nature of otherwise sequential execution steps. This
-model is the basis of the fault-tolerance model developed here.
-
**** Hierarchy.
Although, fault-tolerance and high-availability are different terms, in essence
they describe the same property---an ability of a system to switch processing
@@ -2755,14 +2732,6 @@ checkpoints. The advantage is that they
is low,
- they save only relevant data,
- and they use memory of a subordinate node instead of stable storage.
-**** Software implementation.
-For efficiency reasons fault tolerance techniques described above are
-implemented in the C++ framework: From the authors' perspective C language is
-deemed low-level for distributed programmes, and Java incurs too much overhead
-and is not popular in HPC community. As of now, the framework runs in the same
-process as an parallel application that uses it. The framework is called
-Factory, it is now in proof-of-concept development stage.
-
**** Evaluation.
Factory framework is evaluated on physical cluster (Table [[tab:cluster]]) on
the example of hydrodynamics HPC application which was developed
