Алговики - Вклад [ru]

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-12-08T19:07:23Z

Prokopenko: /* Характеристики программно-аппаратной среды */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-12-08T19:07:07Z

Prokopenko: /* Характеристики программно-аппаратной среды */

Участник:Палионная/Моделирование надежности сложных модифицируемых информационных систем

2016-12-07T19:29:22Z

Prokopenko: /* Характеристики программно-аппаратной среды */

= Свойства и структура алгоритма =

== Общее описание алгоритма ==

В данной задаче рассматривается байесовская рекуррентная модель роста надежности сложных модифицируемых информационных систем.
Так как любая впервые созданная сложная информационная система не обладает требуемой надежностью, она подвергается различным модификациям, целью которых является устранение дефектов, препятствующих правильному функционированию системы. Надежность системы зависит от соотношения параметров, интерпретируемых в теории надежности как показатели <<дефективности>> и <<эффективности>> средства, исправляющего ошибки в системе. При использовании байесовских моделей применительно к задачам теории надежности предполагается, что основные параметры системы не являются заданными, а известны только их априорные распределения. В частности данных алгоритм производит вычисления предельной надежности группы однотипных сложных модифицируемых информационных систем для случая параболического распределения параметров.

== Математическое описание алгоритма ==

Для формализации понятия надежности системы, будем характеризовать ее в каждый момент времени t параметром p(t), при этом время
считаем непрерывным. Так как система подвергается модификациям в случайные моменты времени : <math> 0=Y_0\le~Y_1~\le Y_2~\le\ldots
</math>, параметр <math>p(t)</math> изменяется, принимая соответственно значения <math>p(t) = p(Y_j) = p_j</math> при <math>Y_j~\le~t<~ Y_{j+1}</math> (предполагается, что траектории процесса <math>p(t)</math> непрерывны справа, а модификации происходят мгновенно). Причем при модификациях параметр надежности может как увеличиваться, так и уменьшаться из-за некачественных модификаций.

К числу математических моделей, описывающих изменение надежности модифицируемых информационных систем, относятся рекуррентные модели роста надежности. Рассмотрим, в частности, дискретную экспоненциальную модель, которая определяется следующим образом:
<math>p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).</math>

Здесь <math>\{(\theta_j, \eta_j)\}</math>, <math>j\ge1</math>, -- последовательность независимых одинаково распределенных двумерных случайных векторов таких, что <math>0 < \eta_1 < 1</math>; <math>0 < \theta_1 < 1</math> почти наверное. Начальная надежность <math>p_0</math> считается заданной, случайные величины <math>\eta_j</math> (параметры <<дефективности>>) и <math>\theta_j</math> (параметры <<эффективности>>) описывают соответственно возможное уменьшение и повышение надежности.

Обозначим <math>\lambda = 1 - {E}\theta_j</math>, <math>\mu = {E}\eta_j</math>.
В книге <ref> Королев В. Ю., Соколов И. А. Основы математической теории надежности модифицируемых систем. --- М.: ИПИ РАН, 2006. 102~с. </ref> доказано, что при условии <math>\lambda+\mu\neq1</math>
<math>
p=\lim_{j\to\infty}E p_j = \frac{\mu}{\lambda+\mu}.
</math>
Величина <math>p</math> характеризует асимптотическое значение надежности системы в рамках некоторой рекуррентной модели, задаваемой набором <math>\{(\theta_j, \eta_j)\}</math>.

В рамках байесовского подхода в постановке задач теории надежности можно рассмотреть более сложную ситуацию, где основные параметры системы <math>\lambda </math> и <math>\mu </math> предполагаются случайными. В таком случае наиболее естественной и удобной для изучения характеристикой является усредненное значение предельной надежности, то есть
<math>
p_{average} = Ep = E\frac{\mu}{\lambda+\mu},
</math>
где усреднение ведется по совместному распределению случайных величин <math>\lambda </math> и <math>\mu </math>.

Так как случайные величины <math>\eta_1 </math> и <math>\theta_1 </math> удовлетворяют ограничениям <math>0 < \eta_1 < 1, 0 < \theta_1 < 1 </math>, средние значения <math>\lambda </math> и <math>\mu </math> величин <math>1 - E\theta_j </math> и <math>E\eta_j </math> соответственно также находятся на отрезке [0,1]. В частном случае, рассмотрим независимые случайные параметры <math>\lambda </math> и <math>\mu </math>, имеющие параболические распределения на некоторых (вообще говоря, разных) отрезках, являющихся подмножествами отрезка [0,1].

Итак, пусть средний параметр <<эффективности>> <math>\lambda </math> и средний параметр <<дефективности>> <math>\mu </math> независимы и имеют параболическое распределение <math>P(a_\lambda, b_\lambda) </math>, <math>0\le a_\lambda<b_\lambda\le1 </math>, и <math>P(a_\mu, b_\mu) </math>, <math>0\le a_\mu<b_\mu\le1 </math>, соответственно.

Для плотности <math>f_\xi(x) </math> некоторой случайной величины <math>\xi </math>, имеющей параболическое распределение с параметрами <math>(a_\xi, b_\xi) </math>, справедливо:
<math> f_\xi(x) = \frac{6(x-a_\xi)(b_\xi-x)}{(b_\xi-a_\xi)^3},\ \ \ \ x\in[a_\xi, b_\xi]. </math>

== Вычислительное ядро алгоритма ==
Пусть рассматривается изменение надежности группы однотипных системы на интервале времени [0, T].

'''1.''' Для каждой системы моделируем модификации, происходящие в случайные моменты времени <math>t_j: \sum_{j}t_j <= T</math>, следующим образом:

* Генерируем реализацию случайных величин <math>\lambda </math>, <math>\mu </math> с параболическим распределением на заданных интервалах <math>[a_\lambda, b_\lambda], [a_\mu, b_\mu]</math> соответственно. Задаем начальную надежность системы, как реализацию случайной величины с равномерным на [0,1] распределением.

* Пока <math> \sum_{j}t_j <= T </math>, моделируем поступления модификаций в систему в момент времени <math>t_j</math>: генерируем реализацию случайных величин <math>\theta_j </math>, <math>\eta_j </math> таких, что <math>\lambda = 1 - {E}\theta_j</math>, <math>\mu = {E}\eta_j</math>, изменяем надежность системы по формуле <math> p_{j+1} = \eta_{j+1}p_j + \theta_{j+1}(1-p_j).</math>

'''2.''' Вычисляем усредненную надежность группы однотипных систем после всех модификаций.

== Макроструктура алгоритма ==
Основную часть алгоритма составляет расчет надежности модифицируемых объектов после каждой модификации. Могут быть рассмотрены другие априорные распределения параметров <math>\lambda</math> и <math>\mu</math> в рамках данной модели или совершенно другие математические модели, описывающие изменение надежности сложных модифицируемых систем.

== Схема реализации последовательного алгоритма ==

Схема реализации последовательного алгоритма приведена в [[#Вычислительное ядро алгоритма|описании вычислительного ядра алгоритма]].

== Последовательная сложность алгоритма ==
* <math>[0;T]</math> - рассматриваемый временной интервал;
* <math>N</math> - количество модифицируемых систем.
Тогда для вычисления средней надежности <math>N</math> модифицируемых объектов за время <math>T</math> в последовательном (наиболее медленном) варианте требуется:
* <math>N(34+6T)+1</math> сложений (вычитаний),
* <math>N(51+5T)</math> умножений.

== Информационный граф ==
[[Файл:инф_граф.png]]

Описание информационного графа:

* Красная вершина графа обозначает начальный блок программы, в котором задаются входные данные и вычисляются общие для всех модифицируемых объектов характеристики.

* Желтые вершины графа обозначают выполнение одной модификации для одной модифицируемой системы. Так как для разных объектов количество модификаций, вообще говоря, различно, количество желтых вершин в параллельных нитях графа различно.

* Зеленые вершины графа обозначают заключительный этап вычислений для каждого модифицируемого объекта. На этом этапе происходит вычисление надежности объекта после последней модификации.

* Синяя вершина графа обозначает заключительный участок выполнения программы, на котором происходит вычисление усредненной надежности по всем модифицируемым объектам.

== Ресурс параллелизма алгоритма ==
Ресурс параллелизма алгоритма заключается в независимости модифицируемых объектов. Таким образом на разных процессах могут происходить вычисления для разных объектов независимо друг от друга.

== Входные и выходные данные алгоритма ==
'''Входные параметры:'''
* <math>N</math> - количество объектов в рассматриваемой группе;
* <math>T</math> - временной интервал, <math>T>0 ;</math>
* <math>a_l, b_l</math> - интервалы параболического распределения для случайной величины <math>\lambda, a_l >= 0, b_l <=1 ;</math>
* <math>a_m, b_m</math> - интервалы параболического распределения для случайной величины <math>\mu, a_m >= 0, b_m <=1 .</math>
Выходные параметры: усредненная надежность группы однотипных объектов.
== Свойства алгоритма ==

= Программная реализация алгоритма =

Алгоритм реализован на C++, код программы приведен здесь [https://github.com/SofiaPalionnaya/Parallelism].
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
=== Масштабируемость алгоритма ===
{| class="wikitable"
|-
! Количество процессов
! Время выполнения
|-
|1
|2.36
|-
|2
|2.41
|-
|4
|2.12
|-
|8
|2.03
|-
|16
|1.98
|-
|32
|1.65
|-
|64
|1.4
|-
|128
|1.04
|-
|}

=== Характеристики программно-аппаратной среды ===
Результаты тестов были получены на машине со следующими характеристиками:
{| class="wikitable"
|-
! Характеристики
!
|-
|Операционная система
|Ubuntu 14.04
|-
|Компиляторы С++
|gcc version 4.8.4
|-
|CPU
|AMD Athlon Neo X2 Dual Core Processor L325
|-
|RAM
|3Gb SO-DIMM DDR3
|-
|-
|}

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Для данной постановки задачи существующих реализаций не найдено.

= Литература =
<references />
2. Кудрявцев А. А. Байесовские модели массового обслуживания и надежности: априорные распределения с компактным носителем //
Информатика и ее применения, 2016. Т. 10. Вып. 1.

3. Кудрявцев А. А., Палионная С.И. Байесовская рекуррентная модель роста надежности: параболическое распределение параметров // Информатика и ее применения. — 2016. Т. 10, выпуск 2, страницы 80–83.

[[en:Description of algorithm properties and structure]]

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-12-07T19:27:01Z

Prokopenko: /* Программная реализация алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:30:09Z

Prokopenko: /* Литература */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:28:19Z

Prokopenko: /* Существующие реализации алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:13:52Z

Prokopenko: /* Существующие реализации алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:13:34Z

Prokopenko: /* Существующие реализации алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:08:24Z

Prokopenko: /* Масштабируемость алгоритма и его реализации */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:07:47Z

Prokopenko: /* Реализация с помощью MPI */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T19:07:06Z

Prokopenko: /* Масштабируемость алгоритма и его реализации */

Участник:Vlamakarenko/Трассировка лучей

2016-11-30T19:06:42Z

Prokopenko: Отмена правки 19733, сделанной участником Prokopenko (обс.)

авторы: [[Участник:vlamakarenko|В.А.Макаренко]], [[Участник:Rgabdullin|Р.А.Габдуллин]]

= Свойства и структура алгоритма =

== Общее описание алгоритма ==

'''Трассировка лучей''' - это технология визуализации трехмерных сцен путем отслеживания обратной траектории лучей света (от наблюдателя к источнику).
Достоинствами данного метода являются реалистичность итоговых изображений, возможность визуализации гладких объектов без аппроксимации полигональными поверхностями, простота реализации отражений, преломлений, взятия в фокус, реалистичного освещения; возможность параллельной обработки лучей.

== Математическое описание алгоритма ==

=== Некоторые понятия из радиометрии ===

[[file: Radiance_raytracer.png|thumb|right|300px|Энергетическая яркость]]
[[file: BRDF Diagram.svg|thumb|right|300px|BRDF]]

'''Энергия излучения''' - энергия, переносимая оптическим излучением. Обозначается через  <math>Q</math>.

'''Поток излучения''' - мощность, переносимая оптическим излучением через какую-либо поверхность.  <math>\Phi = \frac{dQ}{dt}</math>.

'''Плотность потока излучения''' - отношение потока излучения, проходящего через малый участок поверхности, к площади этой поверхности.   <math>\frac{d\Phi}{dA}</math>,   где   <math>dA</math> - дифференциал поверхности.

'''Облученность''' - отношение потока излучения, падающего на малый участок поверхности, к площади этой поверхности.   <math>E=\frac{d\Phi}{dA}</math>,   где   <math>dA</math> - дифференциал поверхности.

'''Энергетическая светимость''' - отношение потока излучения, испускаемого малым участком поверхности, к площади этой поверхности.  <math>M=\frac{d\Phi}{dA}</math>,   где   <math>dA</math> - дифференциал поверхности.

'''Сила излучения''' - мощность излучения источника света в некотором направлении. Равна отношению потока излучения, исходящего от источника, к малому телесному углу.   <math>I=\frac{d\Phi}{d\omega}</math>.

'''Энергетическая яркость''' - отношение потока излучения через малую площадку поверхности и распространяющегося в малом телесном угле, к площади проекции этой площадки на плоскость, перпендикулярную направлению распространения, и величине телесного угла.  <math>L=\frac{d^2\Phi}{dA\cdot d\omega \cdot \cos \theta}</math>

Энергетическую яркость, падающую на элемент поверхности, будем назвать '''падающей яркостью''' и обозначать <math>L_i</math>. Энергетическую яркость, отраженную элементом поверхности, будем называть '''отраженной яркостью''' и обозначать <math>L_o</math>.

Из определений следует, что:

1) <math>dE_i(\overline{p}, \overline{\omega}_i) = L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i \, d\omega_i</math> 
2) <math>E(\overline{p}) = \int_{\Omega_i} L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i \, d\omega_i</math>,  где интегрирование проводится по направлениям <math>\overline{\omega}_i</math> таким, что <math>(\overline{n}, \overline{\omega}_i)</math> > 0,  то есть по полусфере. (<math>\overline{n}</math> - нормаль к поверхности в точке <math>\overline{p}</math>,   <math>\Omega_i = 2\pi^{+}</math>).

Пусть <math>\overline{p}</math> - точка поверхности, <math>\overline{n}</math> - нормаль в этой точке, <math>\overline{\omega}_i, \overline{\omega}_o</math> - единичные вектора такие, что <math>(\overline{n}, \overline{\omega}_i) > 0, \,\, (\overline{n}, \overline{\omega}_o) > 0 </math> 
Будем считать, что   <math>dL_o(\overline{p}, \overline{\omega}_o)</math> пропорционален   <math>dE_i(\overline{p},\overline{\omega}_i)</math>: 
<math>dL_o(\overline{p}, \overline{\omega}_o) \sim dE_i(\overline{p},\overline{\omega}_i)</math>. 
Функция   <math>f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) = \frac{dL_o(\overline{p}, \overline{\omega}_o)}{dE_i(\overline{p},\overline{\omega}_i)} = \frac{dL_o(\overline{p}, \overline{\omega}_o)}{L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i d\omega_i}</math>   называется '''двулучевой функцией отражательной способности (BRDF)'''. 
В точке <math>\overline{p}</math> может быть задано несколько BRDF - множество <math>\{f_{r_k}(\overline{p}, \overline{\omega}_i, \overline{\omega}_o)\}</math>. 
Тогда итоговая BRDF просто равна сумме BRDF из этого множества: <math>f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) = \sum_k f_{r_k}(\overline{p}, \overline{\omega}_i, \overline{\omega}_o)</math>. 
<math>L_o(\overline{p}, \overline{\omega}_o) = \int_{\Omega_i} f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i d\omega_i</math>.   - уравнение отражений. 
Важная часть алгоритма трассировки лучей - определить отраженную яркость по падающим яркостям, то есть посчитать этот интеграл. Обычно для вычисления интеграла применяют метод Монте-Карло.

==== Уравнение рендеринга ====

Уравнение рендеринга - это интегральное уравнение, которое определяет количество излученного в определенном направлении света как сумму отраженного и собственного излучения. Физической основой для уравнения рендеринга является закон сохранения энергии.

Уравнение отражений является частью уравнения рендеринга, поэтому остается только добавить собственное излучение объектов <math>L_e(\overline{p}, \overline{\omega}_o)</math>.

Уравнение рендеринга имеет вид <math>L_o(\overline{p}, \overline{\omega}_o) = L_e(\overline{p}, \overline{\omega}_o) + \int_{\Omega_i} f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i d\omega_i</math>.

По сути, алгоритмы рендеринга, в том числе и трассировка лучей, занимаются поиском приближенного решения уравнения рендеринга.

==== Поиск приближенного решения уравнения рендеринга ====

Введем оператор поиска первого пересечения.
<math>r_c(\overline{p}, \overline{\omega})</math> - оператор, который находит точку первого пересечения с объектами луча, выпускаемого из точки <math>\overline{p}</math> по направлению <math>\overline{\omega}</math>.

Воспользуемся предположением, что количество излучения, распространяющегося вдоль одной прямой одинаково в любой точке прямой. Тогда:

<math> L_i(\overline{p},\overline{\omega}_i) = L_o(r_c(\overline{p}, \overline{\omega}_i), -\overline{\omega}_i) </math>.

и уравнение рендеринга превратится в ''уравнение Фредгольма второго рода''

<math>
L_o(\overline{p},\overline{\omega}_o) = L_e(\overline{p},\overline{\omega}_o) + \int_{\Omega_i} f_{r}(\overline{p},\overline{\omega}_i,\overline{\omega}_o)L_o(r_c(\overline{p}, \overline{\omega}_i), -\overline{\omega}_i) \cos\theta_i d\omega_i
</math>.

Обозначим интеграл в правой части как <math> K \circ L_o </math>.
Тогда уравнение рендеринга перепишется, как

<math> L_o = L_e + K \circ L_o </math>.

Искать решение будем итерационным методом: выберем какое-либо начальное приближение <math> L_{o}^{(0)} </math>. Найдем значение правой части <math>L_o^{(1)} = L_e + K \circ L_o^{(0)}</math>, воспользуемся им для поиска следующего приближенного решения <math>L_o^{(2)} = L_e + K \circ L_o^{(1)} = L_e + K \circ ( L_e + L_o^{(0)} ) = L_e + K \circ L_e + K^2 \circ L_o^{(0)} </math> и т.д.

В конечном итоге получим, что <math>L_o = \sum \limits_{n=0}^\infty K^n \circ L_o^{(0)}</math>.

Этот метод называется ''методом последовательных приближений''.

=== Определения ===

[[file: Ray trace diagram.svg|thumb|right|300px|Камера и видовая плоскость]]

'''Объект''' - поверхность в трехмерном пространстве. 
'''Материал объекта''' - множество BRDF. 
'''Сцена''' - четверка '''{камера, объекты, источники света, видовая плоскость}'''.

==== Камера ====

'''Камера''' - "виртуальный глаз", через который мы видим объекты сцены.

Камера задается положением в пространстве и ортонормированным базисом <math>(\overline{u}_c, \overline{v}_c, \overline{w}_c)</math> (локальная система координат). <math>\overline{u}_c</math> направлен вправо относительно наблюдателя, <math>\overline{v}_c</math> - вверх, <math>\overline{w}_c</math> - на наблюдателя. Таким образом, <math>(\overline{u}_c, \overline{v}_c, \overline{w}_c)</math> - правая тройка векторов. Вектор направления камеры в своей системе координат: <math>(0, 0, -1)</math>.

==== Видовая плоскость ====

Перед камерой на расстоянии <math>d</math> поставим пиксельную сетку <math>w \times h</math> с размером пикселя <math>s \times s</math> так, чтобы камера была направлена в ее центр. Итоговое изображение будет получено из этой сетки покраской пикселей в нужный цвет.

<math>p(i, j)</math>, где <math>i=\overline{0,h-1}, \quad j=\overline{0,w-1}</math> - пиксел <math>i</math>-ой строки снизу <math>j</math>-го столбца слева.

Заметим, что с увеличением <math>d</math> уменьшается угол обзора, а <math>s</math> влияет на масштаб.

==== Источники света ====

Типы источников света: 
1) '''Point light''' - точка, излучающая свет одиноково во всех направлениях. 
2) '''Directional light''' - бесконечно удаленный источник света, задается единичным направлением на себя. 
3) '''Area light''' - объект, излучающий свет одинаково во всех направлениях.

=== Алгоритм трассировки лучей ===

==== Генерация луча ====

Перед камерой на расстоянии <math>d</math> поставим пиксельную сетку <math>w \times h</math> с размером пикселя <math>s \times s</math> так, чтобы камера была направлена в центр сетки. Итоговое изображение будет получено из этой сетки покраской пикселей в нужный цвет.

Пусть <math>p(i, j)</math>, где <math>i=\overline{0,h-1}, \quad j=\overline{0,w-1}</math> - пиксел <math>i</math>-ой строки снизу <math>j</math>-го столбца слева. Проведем пучок лучей из камеры через пиксел в локальной системе координат камеры. Начало каждого луча в точке <math>\overline{pos}=(0,0,0)</math>.
Найдем вектора направления <math>\overline{dir}_n</math>:

<math>\overline{dir}_n.x = s \cdot (j + \delta_n.x -\frac{w}{2} + \frac{1}{2}) </math>

<math>\overline{dir}_n.y = s \cdot (i + \delta_n.y -\frac{h}{2} + \frac{1}{2}) </math>

<math>\overline{dir}_n.z = d</math>,

где <math> \delta_n = (\delta_n.x, \delta_n.y) \in [0;1]^2</math> - смещения начала n-ого луча.

Нормируем вектора <math>\overline{dir}_n</math> и переведем лучи в глобальную систему координат.

==== Пересечение луча с объектами сцены ====

Все точки луча <math>ray(\overline{p}, \overline{d})</math> можно представить в виде:

<math>h(x,y,z)=\overline{p}+t \cdot \overline{d}, \quad t \in [0;\infty) </math>.

Луч пересекает объект <math>O_i</math> тогда и только тогда, когда <math>t_i = \inf\{t > 0 \, | \quad \overline{p}+t \cdot \overline{d} \in O_i\} \, < \infty</math>

Если луч пересекает объект <math>O_i</math>, то <math>h_i(x,y,z) = \overline{p}+t_i \cdot \overline{d}</math> - их первое пересечение, <math>t_i</math> - расстояние от начала луча до точки пересечения.

==== Вычисление энергитической яркости <math>L_o</math>, выходящей из точки пересечения ====

Найдем <math>T = \{t_i\}</math> - параметры пересечения с объектами (см. предыдущий пункт).

<math>t_{min} = \min \{t_i\}, \quad O_{min} = \{O_i | t_i = t_{min}\}</math>

Если <math>t_{min} = \infty</math>, то луч не пересекает ни один объект и нужно покрасить соответствующий пиксел в черный цвет (цвет фона).

Если <math>t_{min} < \infty</math>, то нужно найти выходящее излучение (цвет) из точки пересечения в камеру. Выходящее излучение зависит от свойств материала объекта и входящего излучения в точку пересечения.

Чтобы вычислить входящее излучение, находится приближенное значение интеграла <math> \int_{\Omega_i} f_{r}(\overline{p},\overline{\omega}_i,\overline{\omega}_o)L_o(r_c(\overline{p}, \overline{\omega}_i), -\overline{\omega}_i) \cos\theta_i d\omega_i </math> методом Монте-Карло.

Заметим, что каждый луч необходимо продолжить в некотором направлении(а не создавать новый пучок), так как необходимое количество лучей для численного интегрирования можно заранее сгенерировать в камере.

Таким образом, алгоритм моделирует обратное движение пучка лучей света, который пришел в камеру. Пучок лучей движется из камеры и, сталкиваясь с объектами, распространяется в пространство в случайных направлениях, согласно свойствам материалов объектов.

=== Улучшение визуальных качеств изображения ===

Заметим, что чем больше лучей выпускается через каждый пиксел изображения, тем лучше получается картинка.

== Вычислительное ядро алгоритма ==

Основные вычисления связаны с поиском пересечения луча с объектами сцены.

== Макроструктура алгоритма ==

Для каждого пикселя изображения генерируется пучок лучей, проходящих через этот пиксел. 

Для каждого луча находится точка первого пересечения с объектами сцены, расчитывается входящие излучения и на основе этого - итоговое выходящее. 
Для упрощения модели разобьем входящее излучение на ''прямое'' и ''непрямое''. 
Прямое излучение - излучение, приходящее в точку непосредственно от источников света. 
Непрямое излучение состоит из отраженного от других объектов сцены света.

После этого цвет усредняется по всем лучам, проходящим через данный пиксел.

== Схема реализации последовательного алгоритма ==

Здесь приведен псевдокод ключевых моментов алгоритма.

<source lang="c++">
//Покраска пикселей изображения

for (uint r = 0; r < h; r++) //строки
{
for (uint c = 0; c < w; c++) //столбцы
{
image(r,c) = renderPixel(r, c); //вычисляем цвет в пикселе
}
}
</source>

<source lang="c++">
//renderPixel(r, c)

pixel_color = {0,0,0};

for (uint j = 0; j < num_rays_per_pixel; j++)
{
pp = generatePoint(); //генерируем произвольное смещение внутри пикеля

//вычисляем координаты точки на полотне
x = s * (c - 0.5 * w + pp.x);
y = s * (r - 0.5 * h + pp.y);

//cоздаем луч
Ray ray({0,0,0}, normalize({x,y,-d}));
Ray worldRay = convertToWorldCoords(ray);

pixel_color += traceRay(worldRay, 0) * 1.0 / num_rays_per_pixel; //вычисляем цвет для каждого луча и усредняем
}
</source>

<source lang="c++">
//traceRay(ray, depth)

if (depth > max_depth) //превысили максимальную глубину луча, дальше не идем
{
return black; //возвращаем черный цвет
}

Intersection is = hitObjects(ray); //нашли первое пересечение с объектами сцены и записали информацию о нем в is:
//материал объекта, расстояние, нормаль и т. п.

if (is) //если есть пересечение
{
is.ray = ray; //запомнили луч
is.depth = depth; // и глубину

return shade(is); //расчитали цвет в точке пересечения в зависимости
//от материала объекта, используя информацию о пересечении

}

return getBackgroundColor(ray); //вернули цвет фона
</source>

<source lang="c++">
//shade(is)

//цвета
direct_illumination = {0,0,0}; //прямое излучение
indirect_illumintaion = {0,0,0}; //непрямое излучение

for (uint i = 0; i < light_count; i++)
{
if (light[i].isVisible(is)) //если источник света виден из точки пересечения
{
direct_illumination = getIllumination(light[i], is); //рассчитываем прямое излучение от i-го источника света
}
}

if (isReflective(is.object))
{
indirect_illumination = traceRay(reflecedRay(is.ray), is.depth + 1);
}

//зная входящее излучение, расчитываем выходящее в зависимости от свойств материала объекта
//...
</source>

== Последовательная сложность алгоритма ==
Вычислим последовательную сложность алгоритма в терминах пересечения луча с объектами сцены.

<math>w</math> - ширина полотна

<math>h</math> - высота полотна

<math>depth_{max}</math> - максимальная глубина луча в рекурсии

<math>N_{obj}</math> - количество объектов сцены

<math>N_{lights}</math> - количество источников света сцены

<math>N_{rays}</math> - число лучей на один пиксел

На каждой итерации ищется пересечение луча со всеми объектами: <math>O(N_{obj})</math>

После нахождения точки пересечения, выясняется, виден ли каждый источник света из этой точки. Для этого нужно найти первое пересечение теневого луча (начало в точке пересечения, направлен к источнику света) и сравнить расстояние до точки пересечения с расстоянием до источника света. Для всего этого требуется <math>O(N_{lights} \cdot N_{obj})</math> операций.

Для каждого луча понадобится <math>O(depth_{max}(N_{obj} + N_{obj} \cdot N_{lights})) = O(depth_{max}\cdot N_{obj} \cdot N_{lights})</math> операций.

Всего лучей, выходящих из камеры <math>w \cdot h \cdot N_{rays}</math>.

В итоге получаем <math>O(depth_{max}\cdot N_{obj} \cdot N_{lights} \cdot w \cdot h \cdot N_{rays})</math> операций.

== Информационный граф ==

[[file: Raytracer_graph.png|400px]]

Зеленые вершины - генерация лучей для данного пикселя. 
Желтые вершины - трассировка лучей данного пикселя.

== Ресурс параллелизма алгоритма ==

Из информационного графа видно, что обработка каждого пикселя происходит независимо от других, а затем происходит соединение всех пикселей в итоговое изображение. Пусть <math>N_p \geqslant 2</math> - количество процессов. Всем процессам, кроме первого поручим обработать свою часть изображения (каждый процесс обработает <math>\Big[\frac{w \cdot h}{N_p - 1}\Big] </math> пикселей, а оставшуюся часть работы поручим произвольному процессу). Первому процессу поручим принять работу и собрать итоговое изображение (используем MPI_Gatherv).

Время работы: <math>O\Big(\frac{depth_{max}\cdot N_{obj} \cdot N_{lights} \cdot w \cdot h \cdot N_{rays}}{N_p}\Big)</math>.

== Входные и выходные данные алгоритма ==

На вход алгоритму подается описание сцены (описание камеры, видовой плоскости, объектов и их материалов, источников света). 
Выходные данные алгоритма - готовое изображение.

== Свойства алгоритма ==

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==

=== Реализация с помощью MPI ===
1) 
Размер изображения 700 на 700 пикселей, 256 лучей на пиксел, глубина рекурсии 3. 
Сцена: 
[[file: Raytracer_scene5.jpeg|300px]]

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|1
|479.915
|-
|2
|492.614
|-
|4
|313.172
|-
|8
|170.866
|-
|16
|82.375
|-
|32
|43.812
|-
|64
|22.318
|-
|128
|12.195
|-
|256
|8.793
|-
|512
|6.954
|-
|1024
|6.741
|-
|}

2) 
Размер изображения 1340 на 1340 пикселей, 1024 лучей на пиксел, глубина рекурсии 5. 
Сцена: 
[[file: Raytracer_scene8.jpeg|300px]]

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|1
|600.270
|-
|2
|610.583
|-
|4
|243.261
|-
|8
|136.025
|-
|16
|67.517
|-
|32
|33.467
|-
|64
|17.234
|-
|128
|9.361
|-
|}

Алгоритм перестает масштабироваться, когда время работы параллельной части алгоритма (визуализация) мало по сравнению с накладными расходами MPI и временем, которое расходуется на инициализацию сцены (загрузка сцены из файла, построение оптимизирующих структур данных для ускорения визуализации 3d-моделей).

=== Реализация с помощью NVIDIA CUDA ===

В программной реализации на CUDA изображение делится на окна меньшего размера.
Затем происходит отрисовка каждого окна, при этом цвета пикселей в каждом окне вычисляются параллельно.

[[File:CudaRaytracer_scene1.png | 500px]] [[File:CudaRaytracerPerformance.png| 500px]]

{| class="wikitable"
|-
! Лучей в окне
! GTX 1070
! GT 640m
|-
|512
|29.8 c
|58.0 c
|-
|1024
|15.2 c
|35.5 c
|-
|2048
|8.2 c
|25.2 c
|-
|4096
|4.6 c
|24.5 c
|-
|8192
|3.0 c
|23.5 c
|-
|16384
|3.1 c
|23.4 c
|-
|32768
|2.8 c
|23.2 c
|-
|65536
|2.5 c
|23.1 c
|-
|131072
|2.4 c
|23.0 c
|-
|}
Видно, что с ростом размера окна "исчезает" рост производительности. Это связано с накладными расходами на хранение данных в памяти GPU.

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

[https://ru.wikipedia.org/wiki/RenderMan RenderMan] — очень известный пакет программ для рендеринга 3D-анимации, который был создан компанией Pixar в 1986 году.
Данный пакет использовался во множестве известных фильмов и мультфильмов, например: [https://en.wikipedia.org/wiki/Avatar_(2009_film) Аватар](2009), [https://en.wikipedia.org/wiki/Harry_Potter_and_the_Order_of_the_Phoenix_(film) Гарри Поттер и Орден Феникса](2007), [https://en.wikipedia.org/wiki/Finding_Nemo В поисках Немо](2003).

[https://ru.wikipedia.org/wiki/V-Ray V-Ray] — система рендеринга, разработанная компанией Chaos Group в 2000 году.
VRay — это рейтрейсный рендерер, в котором присутствует несколько алгоритмов просчета глобального освещения.

[http://www.nvidia.com/object/nvidia-iray.html NVIDIA IRay] — технология создания фотореалистичных изображений с использованием графических ускорителей, созданная компанией NVIDIA.

[https://ru.wikipedia.org/wiki/Mental_ray mental ray] — профессиональная система рендеринга и визуализации изображений, разработанная компанией mental images(является дочерней компанией NVIDIA) в 1986 году.
Использован в фильмах [https://en.wikipedia.org/wiki/Terminator_3:_Rise_of_the_Machines Терминатор 3: Восстание машин](2003), [https://en.wikipedia.org/wiki/Tron:_Legacy Трон: Наследие](2010).

[http://www.raytracing.ru/ Hydra Renderer] — это плагин для рендера реалистичных изображений в 3D Studio Max. Разработан при поддержке Лаборатории компьютерной графики и мультимедиа факультета ВМК МГУ.

= Литература =

1. [http://www.raytracegroundup.com/ Suffern, Kevin G. "Ray Tracing from the Ground Up / Kevin G. Suffern", 2007]

2. [http://www.scratchapixel.com/ Scratchapixel 2.0. Learn Computer Graphics From Scratch!]

3. Параллельные вычисления на GPU. Архитектура и программная модель CUDA: Учеб. пособие / А.В. Боресков и др. - М.: Издательство Московского университета, 2012. - 336 с.

= Полученные изображения =

<gallery>
File:Raytracer_scene1.jpeg
File:Raytracer_scene2.jpeg
File:Raytracer_scene3.jpeg
File:Raytracer_scene4.jpeg
File:Raytracer_scene5.jpeg
File:Raytracer_scene6.jpeg
File:Raytracer_scene7.jpeg
File:CudaRaytracer_scene1.png
</gallery>

Участник:Vlamakarenko/Трассировка лучей

2016-11-30T19:04:46Z

Prokopenko: /* Реализация с помощью MPI */

авторы: [[Участник:vlamakarenko|В.А.Макаренко]], [[Участник:Rgabdullin|Р.А.Габдуллин]]

= Свойства и структура алгоритма =

== Общее описание алгоритма ==

'''Трассировка лучей''' - это технология визуализации трехмерных сцен путем отслеживания обратной траектории лучей света (от наблюдателя к источнику).
Достоинствами данного метода являются реалистичность итоговых изображений, возможность визуализации гладких объектов без аппроксимации полигональными поверхностями, простота реализации отражений, преломлений, взятия в фокус, реалистичного освещения; возможность параллельной обработки лучей.

== Математическое описание алгоритма ==

=== Некоторые понятия из радиометрии ===

[[file: Radiance_raytracer.png|thumb|right|300px|Энергетическая яркость]]
[[file: BRDF Diagram.svg|thumb|right|300px|BRDF]]

'''Энергия излучения''' - энергия, переносимая оптическим излучением. Обозначается через  <math>Q</math>.

'''Поток излучения''' - мощность, переносимая оптическим излучением через какую-либо поверхность.  <math>\Phi = \frac{dQ}{dt}</math>.

'''Плотность потока излучения''' - отношение потока излучения, проходящего через малый участок поверхности, к площади этой поверхности.   <math>\frac{d\Phi}{dA}</math>,   где   <math>dA</math> - дифференциал поверхности.

'''Облученность''' - отношение потока излучения, падающего на малый участок поверхности, к площади этой поверхности.   <math>E=\frac{d\Phi}{dA}</math>,   где   <math>dA</math> - дифференциал поверхности.

'''Энергетическая светимость''' - отношение потока излучения, испускаемого малым участком поверхности, к площади этой поверхности.  <math>M=\frac{d\Phi}{dA}</math>,   где   <math>dA</math> - дифференциал поверхности.

'''Сила излучения''' - мощность излучения источника света в некотором направлении. Равна отношению потока излучения, исходящего от источника, к малому телесному углу.   <math>I=\frac{d\Phi}{d\omega}</math>.

'''Энергетическая яркость''' - отношение потока излучения через малую площадку поверхности и распространяющегося в малом телесном угле, к площади проекции этой площадки на плоскость, перпендикулярную направлению распространения, и величине телесного угла.  <math>L=\frac{d^2\Phi}{dA\cdot d\omega \cdot \cos \theta}</math>

Энергетическую яркость, падающую на элемент поверхности, будем назвать '''падающей яркостью''' и обозначать <math>L_i</math>. Энергетическую яркость, отраженную элементом поверхности, будем называть '''отраженной яркостью''' и обозначать <math>L_o</math>.

Из определений следует, что:

1) <math>dE_i(\overline{p}, \overline{\omega}_i) = L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i \, d\omega_i</math> 
2) <math>E(\overline{p}) = \int_{\Omega_i} L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i \, d\omega_i</math>,  где интегрирование проводится по направлениям <math>\overline{\omega}_i</math> таким, что <math>(\overline{n}, \overline{\omega}_i)</math> > 0,  то есть по полусфере. (<math>\overline{n}</math> - нормаль к поверхности в точке <math>\overline{p}</math>,   <math>\Omega_i = 2\pi^{+}</math>).

Пусть <math>\overline{p}</math> - точка поверхности, <math>\overline{n}</math> - нормаль в этой точке, <math>\overline{\omega}_i, \overline{\omega}_o</math> - единичные вектора такие, что <math>(\overline{n}, \overline{\omega}_i) > 0, \,\, (\overline{n}, \overline{\omega}_o) > 0 </math> 
Будем считать, что   <math>dL_o(\overline{p}, \overline{\omega}_o)</math> пропорционален   <math>dE_i(\overline{p},\overline{\omega}_i)</math>: 
<math>dL_o(\overline{p}, \overline{\omega}_o) \sim dE_i(\overline{p},\overline{\omega}_i)</math>. 
Функция   <math>f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) = \frac{dL_o(\overline{p}, \overline{\omega}_o)}{dE_i(\overline{p},\overline{\omega}_i)} = \frac{dL_o(\overline{p}, \overline{\omega}_o)}{L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i d\omega_i}</math>   называется '''двулучевой функцией отражательной способности (BRDF)'''. 
В точке <math>\overline{p}</math> может быть задано несколько BRDF - множество <math>\{f_{r_k}(\overline{p}, \overline{\omega}_i, \overline{\omega}_o)\}</math>. 
Тогда итоговая BRDF просто равна сумме BRDF из этого множества: <math>f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) = \sum_k f_{r_k}(\overline{p}, \overline{\omega}_i, \overline{\omega}_o)</math>. 
<math>L_o(\overline{p}, \overline{\omega}_o) = \int_{\Omega_i} f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i d\omega_i</math>.   - уравнение отражений. 
Важная часть алгоритма трассировки лучей - определить отраженную яркость по падающим яркостям, то есть посчитать этот интеграл. Обычно для вычисления интеграла применяют метод Монте-Карло.

==== Уравнение рендеринга ====

Уравнение рендеринга - это интегральное уравнение, которое определяет количество излученного в определенном направлении света как сумму отраженного и собственного излучения. Физической основой для уравнения рендеринга является закон сохранения энергии.

Уравнение отражений является частью уравнения рендеринга, поэтому остается только добавить собственное излучение объектов <math>L_e(\overline{p}, \overline{\omega}_o)</math>.

Уравнение рендеринга имеет вид <math>L_o(\overline{p}, \overline{\omega}_o) = L_e(\overline{p}, \overline{\omega}_o) + \int_{\Omega_i} f_r(\overline{p}, \overline{\omega}_i, \overline{\omega}_o) L_i(\overline{p}, \overline{\omega}_i)\cos \theta_i d\omega_i</math>.

По сути, алгоритмы рендеринга, в том числе и трассировка лучей, занимаются поиском приближенного решения уравнения рендеринга.

==== Поиск приближенного решения уравнения рендеринга ====

Введем оператор поиска первого пересечения.
<math>r_c(\overline{p}, \overline{\omega})</math> - оператор, который находит точку первого пересечения с объектами луча, выпускаемого из точки <math>\overline{p}</math> по направлению <math>\overline{\omega}</math>.

Воспользуемся предположением, что количество излучения, распространяющегося вдоль одной прямой одинаково в любой точке прямой. Тогда:

<math> L_i(\overline{p},\overline{\omega}_i) = L_o(r_c(\overline{p}, \overline{\omega}_i), -\overline{\omega}_i) </math>.

и уравнение рендеринга превратится в ''уравнение Фредгольма второго рода''

<math>
L_o(\overline{p},\overline{\omega}_o) = L_e(\overline{p},\overline{\omega}_o) + \int_{\Omega_i} f_{r}(\overline{p},\overline{\omega}_i,\overline{\omega}_o)L_o(r_c(\overline{p}, \overline{\omega}_i), -\overline{\omega}_i) \cos\theta_i d\omega_i
</math>.

Обозначим интеграл в правой части как <math> K \circ L_o </math>.
Тогда уравнение рендеринга перепишется, как

<math> L_o = L_e + K \circ L_o </math>.

Искать решение будем итерационным методом: выберем какое-либо начальное приближение <math> L_{o}^{(0)} </math>. Найдем значение правой части <math>L_o^{(1)} = L_e + K \circ L_o^{(0)}</math>, воспользуемся им для поиска следующего приближенного решения <math>L_o^{(2)} = L_e + K \circ L_o^{(1)} = L_e + K \circ ( L_e + L_o^{(0)} ) = L_e + K \circ L_e + K^2 \circ L_o^{(0)} </math> и т.д.

В конечном итоге получим, что <math>L_o = \sum \limits_{n=0}^\infty K^n \circ L_o^{(0)}</math>.

Этот метод называется ''методом последовательных приближений''.

=== Определения ===

[[file: Ray trace diagram.svg|thumb|right|300px|Камера и видовая плоскость]]

'''Объект''' - поверхность в трехмерном пространстве. 
'''Материал объекта''' - множество BRDF. 
'''Сцена''' - четверка '''{камера, объекты, источники света, видовая плоскость}'''.

==== Камера ====

'''Камера''' - "виртуальный глаз", через который мы видим объекты сцены.

Камера задается положением в пространстве и ортонормированным базисом <math>(\overline{u}_c, \overline{v}_c, \overline{w}_c)</math> (локальная система координат). <math>\overline{u}_c</math> направлен вправо относительно наблюдателя, <math>\overline{v}_c</math> - вверх, <math>\overline{w}_c</math> - на наблюдателя. Таким образом, <math>(\overline{u}_c, \overline{v}_c, \overline{w}_c)</math> - правая тройка векторов. Вектор направления камеры в своей системе координат: <math>(0, 0, -1)</math>.

==== Видовая плоскость ====

Перед камерой на расстоянии <math>d</math> поставим пиксельную сетку <math>w \times h</math> с размером пикселя <math>s \times s</math> так, чтобы камера была направлена в ее центр. Итоговое изображение будет получено из этой сетки покраской пикселей в нужный цвет.

<math>p(i, j)</math>, где <math>i=\overline{0,h-1}, \quad j=\overline{0,w-1}</math> - пиксел <math>i</math>-ой строки снизу <math>j</math>-го столбца слева.

Заметим, что с увеличением <math>d</math> уменьшается угол обзора, а <math>s</math> влияет на масштаб.

==== Источники света ====

Типы источников света: 
1) '''Point light''' - точка, излучающая свет одиноково во всех направлениях. 
2) '''Directional light''' - бесконечно удаленный источник света, задается единичным направлением на себя. 
3) '''Area light''' - объект, излучающий свет одинаково во всех направлениях.

=== Алгоритм трассировки лучей ===

==== Генерация луча ====

Перед камерой на расстоянии <math>d</math> поставим пиксельную сетку <math>w \times h</math> с размером пикселя <math>s \times s</math> так, чтобы камера была направлена в центр сетки. Итоговое изображение будет получено из этой сетки покраской пикселей в нужный цвет.

Пусть <math>p(i, j)</math>, где <math>i=\overline{0,h-1}, \quad j=\overline{0,w-1}</math> - пиксел <math>i</math>-ой строки снизу <math>j</math>-го столбца слева. Проведем пучок лучей из камеры через пиксел в локальной системе координат камеры. Начало каждого луча в точке <math>\overline{pos}=(0,0,0)</math>.
Найдем вектора направления <math>\overline{dir}_n</math>:

<math>\overline{dir}_n.x = s \cdot (j + \delta_n.x -\frac{w}{2} + \frac{1}{2}) </math>

<math>\overline{dir}_n.y = s \cdot (i + \delta_n.y -\frac{h}{2} + \frac{1}{2}) </math>

<math>\overline{dir}_n.z = d</math>,

где <math> \delta_n = (\delta_n.x, \delta_n.y) \in [0;1]^2</math> - смещения начала n-ого луча.

Нормируем вектора <math>\overline{dir}_n</math> и переведем лучи в глобальную систему координат.

==== Пересечение луча с объектами сцены ====

Все точки луча <math>ray(\overline{p}, \overline{d})</math> можно представить в виде:

<math>h(x,y,z)=\overline{p}+t \cdot \overline{d}, \quad t \in [0;\infty) </math>.

Луч пересекает объект <math>O_i</math> тогда и только тогда, когда <math>t_i = \inf\{t > 0 \, | \quad \overline{p}+t \cdot \overline{d} \in O_i\} \, < \infty</math>

Если луч пересекает объект <math>O_i</math>, то <math>h_i(x,y,z) = \overline{p}+t_i \cdot \overline{d}</math> - их первое пересечение, <math>t_i</math> - расстояние от начала луча до точки пересечения.

==== Вычисление энергитической яркости <math>L_o</math>, выходящей из точки пересечения ====

Найдем <math>T = \{t_i\}</math> - параметры пересечения с объектами (см. предыдущий пункт).

<math>t_{min} = \min \{t_i\}, \quad O_{min} = \{O_i | t_i = t_{min}\}</math>

Если <math>t_{min} = \infty</math>, то луч не пересекает ни один объект и нужно покрасить соответствующий пиксел в черный цвет (цвет фона).

Если <math>t_{min} < \infty</math>, то нужно найти выходящее излучение (цвет) из точки пересечения в камеру. Выходящее излучение зависит от свойств материала объекта и входящего излучения в точку пересечения.

Чтобы вычислить входящее излучение, находится приближенное значение интеграла <math> \int_{\Omega_i} f_{r}(\overline{p},\overline{\omega}_i,\overline{\omega}_o)L_o(r_c(\overline{p}, \overline{\omega}_i), -\overline{\omega}_i) \cos\theta_i d\omega_i </math> методом Монте-Карло.

Заметим, что каждый луч необходимо продолжить в некотором направлении(а не создавать новый пучок), так как необходимое количество лучей для численного интегрирования можно заранее сгенерировать в камере.

Таким образом, алгоритм моделирует обратное движение пучка лучей света, который пришел в камеру. Пучок лучей движется из камеры и, сталкиваясь с объектами, распространяется в пространство в случайных направлениях, согласно свойствам материалов объектов.

=== Улучшение визуальных качеств изображения ===

Заметим, что чем больше лучей выпускается через каждый пиксел изображения, тем лучше получается картинка.

== Вычислительное ядро алгоритма ==

Основные вычисления связаны с поиском пересечения луча с объектами сцены.

== Макроструктура алгоритма ==

Для каждого пикселя изображения генерируется пучок лучей, проходящих через этот пиксел. 

Для каждого луча находится точка первого пересечения с объектами сцены, расчитывается входящие излучения и на основе этого - итоговое выходящее. 
Для упрощения модели разобьем входящее излучение на ''прямое'' и ''непрямое''. 
Прямое излучение - излучение, приходящее в точку непосредственно от источников света. 
Непрямое излучение состоит из отраженного от других объектов сцены света.

После этого цвет усредняется по всем лучам, проходящим через данный пиксел.

== Схема реализации последовательного алгоритма ==

Здесь приведен псевдокод ключевых моментов алгоритма.

<source lang="c++">
//Покраска пикселей изображения

for (uint r = 0; r < h; r++) //строки
{
for (uint c = 0; c < w; c++) //столбцы
{
image(r,c) = renderPixel(r, c); //вычисляем цвет в пикселе
}
}
</source>

<source lang="c++">
//renderPixel(r, c)

pixel_color = {0,0,0};

for (uint j = 0; j < num_rays_per_pixel; j++)
{
pp = generatePoint(); //генерируем произвольное смещение внутри пикеля

//вычисляем координаты точки на полотне
x = s * (c - 0.5 * w + pp.x);
y = s * (r - 0.5 * h + pp.y);

//cоздаем луч
Ray ray({0,0,0}, normalize({x,y,-d}));
Ray worldRay = convertToWorldCoords(ray);

pixel_color += traceRay(worldRay, 0) * 1.0 / num_rays_per_pixel; //вычисляем цвет для каждого луча и усредняем
}
</source>

<source lang="c++">
//traceRay(ray, depth)

if (depth > max_depth) //превысили максимальную глубину луча, дальше не идем
{
return black; //возвращаем черный цвет
}

Intersection is = hitObjects(ray); //нашли первое пересечение с объектами сцены и записали информацию о нем в is:
//материал объекта, расстояние, нормаль и т. п.

if (is) //если есть пересечение
{
is.ray = ray; //запомнили луч
is.depth = depth; // и глубину

return shade(is); //расчитали цвет в точке пересечения в зависимости
//от материала объекта, используя информацию о пересечении

}

return getBackgroundColor(ray); //вернули цвет фона
</source>

<source lang="c++">
//shade(is)

//цвета
direct_illumination = {0,0,0}; //прямое излучение
indirect_illumintaion = {0,0,0}; //непрямое излучение

for (uint i = 0; i < light_count; i++)
{
if (light[i].isVisible(is)) //если источник света виден из точки пересечения
{
direct_illumination = getIllumination(light[i], is); //рассчитываем прямое излучение от i-го источника света
}
}

if (isReflective(is.object))
{
indirect_illumination = traceRay(reflecedRay(is.ray), is.depth + 1);
}

//зная входящее излучение, расчитываем выходящее в зависимости от свойств материала объекта
//...
</source>

== Последовательная сложность алгоритма ==
Вычислим последовательную сложность алгоритма в терминах пересечения луча с объектами сцены.

<math>w</math> - ширина полотна

<math>h</math> - высота полотна

<math>depth_{max}</math> - максимальная глубина луча в рекурсии

<math>N_{obj}</math> - количество объектов сцены

<math>N_{lights}</math> - количество источников света сцены

<math>N_{rays}</math> - число лучей на один пиксел

На каждой итерации ищется пересечение луча со всеми объектами: <math>O(N_{obj})</math>

После нахождения точки пересечения, выясняется, виден ли каждый источник света из этой точки. Для этого нужно найти первое пересечение теневого луча (начало в точке пересечения, направлен к источнику света) и сравнить расстояние до точки пересечения с расстоянием до источника света. Для всего этого требуется <math>O(N_{lights} \cdot N_{obj})</math> операций.

Для каждого луча понадобится <math>O(depth_{max}(N_{obj} + N_{obj} \cdot N_{lights})) = O(depth_{max}\cdot N_{obj} \cdot N_{lights})</math> операций.

Всего лучей, выходящих из камеры <math>w \cdot h \cdot N_{rays}</math>.

В итоге получаем <math>O(depth_{max}\cdot N_{obj} \cdot N_{lights} \cdot w \cdot h \cdot N_{rays})</math> операций.

== Информационный граф ==

[[file: Raytracer_graph.png|400px]]

Зеленые вершины - генерация лучей для данного пикселя. 
Желтые вершины - трассировка лучей данного пикселя.

== Ресурс параллелизма алгоритма ==

Из информационного графа видно, что обработка каждого пикселя происходит независимо от других, а затем происходит соединение всех пикселей в итоговое изображение. Пусть <math>N_p \geqslant 2</math> - количество процессов. Всем процессам, кроме первого поручим обработать свою часть изображения (каждый процесс обработает <math>\Big[\frac{w \cdot h}{N_p - 1}\Big] </math> пикселей, а оставшуюся часть работы поручим произвольному процессу). Первому процессу поручим принять работу и собрать итоговое изображение (используем MPI_Gatherv).

Время работы: <math>O\Big(\frac{depth_{max}\cdot N_{obj} \cdot N_{lights} \cdot w \cdot h \cdot N_{rays}}{N_p}\Big)</math>.

== Входные и выходные данные алгоритма ==

На вход алгоритму подается описание сцены (описание камеры, видовой плоскости, объектов и их материалов, источников света). 
Выходные данные алгоритма - готовое изображение.

== Свойства алгоритма ==

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==

=== Реализация с помощью MPI ===
Рассматривается система , на сетке 1024 узла, система стабилизируется на 900 кванте времени, расчет и вывод останавливается на 1000 кванте времени.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.234
|-
|64
|0.24
|-
|32
|0.248
|-
|16
|0.254
|-
|8
|0.272
|-
|4
|0.29
|-
|2
|0.323
|-
|1
|0.34
|-
|}

Очевидно, что система плохо масштабируема за счет того, что вывод результатов довольно трудоемкий, но осуществлять его приходится часто.

=== Реализация с помощью NVIDIA CUDA ===

В программной реализации на CUDA изображение делится на окна меньшего размера.
Затем происходит отрисовка каждого окна, при этом цвета пикселей в каждом окне вычисляются параллельно.

[[File:CudaRaytracer_scene1.png | 500px]] [[File:CudaRaytracerPerformance.png| 500px]]

{| class="wikitable"
|-
! Лучей в окне
! GTX 1070
! GT 640m
|-
|512
|29.8 c
|58.0 c
|-
|1024
|15.2 c
|35.5 c
|-
|2048
|8.2 c
|25.2 c
|-
|4096
|4.6 c
|24.5 c
|-
|8192
|3.0 c
|23.5 c
|-
|16384
|3.1 c
|23.4 c
|-
|32768
|2.8 c
|23.2 c
|-
|65536
|2.5 c
|23.1 c
|-
|131072
|2.4 c
|23.0 c
|-
|}
Видно, что с ростом размера окна "исчезает" рост производительности. Это связано с накладными расходами на хранение данных в памяти GPU.

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

[https://ru.wikipedia.org/wiki/RenderMan RenderMan] — очень известный пакет программ для рендеринга 3D-анимации, который был создан компанией Pixar в 1986 году.
Данный пакет использовался во множестве известных фильмов и мультфильмов, например: [https://en.wikipedia.org/wiki/Avatar_(2009_film) Аватар](2009), [https://en.wikipedia.org/wiki/Harry_Potter_and_the_Order_of_the_Phoenix_(film) Гарри Поттер и Орден Феникса](2007), [https://en.wikipedia.org/wiki/Finding_Nemo В поисках Немо](2003).

[https://ru.wikipedia.org/wiki/V-Ray V-Ray] — система рендеринга, разработанная компанией Chaos Group в 2000 году.
VRay — это рейтрейсный рендерер, в котором присутствует несколько алгоритмов просчета глобального освещения.

[http://www.nvidia.com/object/nvidia-iray.html NVIDIA IRay] — технология создания фотореалистичных изображений с использованием графических ускорителей, созданная компанией NVIDIA.

[https://ru.wikipedia.org/wiki/Mental_ray mental ray] — профессиональная система рендеринга и визуализации изображений, разработанная компанией mental images(является дочерней компанией NVIDIA) в 1986 году.
Использован в фильмах [https://en.wikipedia.org/wiki/Terminator_3:_Rise_of_the_Machines Терминатор 3: Восстание машин](2003), [https://en.wikipedia.org/wiki/Tron:_Legacy Трон: Наследие](2010).

[http://www.raytracing.ru/ Hydra Renderer] — это плагин для рендера реалистичных изображений в 3D Studio Max. Разработан при поддержке Лаборатории компьютерной графики и мультимедиа факультета ВМК МГУ.

= Литература =

1. [http://www.raytracegroundup.com/ Suffern, Kevin G. "Ray Tracing from the Ground Up / Kevin G. Suffern", 2007]

2. [http://www.scratchapixel.com/ Scratchapixel 2.0. Learn Computer Graphics From Scratch!]

3. Параллельные вычисления на GPU. Архитектура и программная модель CUDA: Учеб. пособие / А.В. Боресков и др. - М.: Издательство Московского университета, 2012. - 336 с.

= Полученные изображения =

<gallery>
File:Raytracer_scene1.jpeg
File:Raytracer_scene2.jpeg
File:Raytracer_scene3.jpeg
File:Raytracer_scene4.jpeg
File:Raytracer_scene5.jpeg
File:Raytracer_scene6.jpeg
File:Raytracer_scene7.jpeg
File:CudaRaytracer_scene1.png
</gallery>

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:50:44Z

Prokopenko: /* Программная реализация алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:49:47Z

Prokopenko: /* Входные и выходные данные алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:49:20Z

Prokopenko: /* Входные и выходные данные алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:40:43Z

Prokopenko: /* Ресурс параллелизма алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:34:36Z

Prokopenko: /* Схема реализации последовательного алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:34:03Z

Prokopenko: /* Информационный граф */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:33:34Z

Prokopenko: /* Информационный граф */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:29:51Z

Prokopenko: /* Схема реализации последовательного алгоритма */

Файл:Inf graph.png

2016-11-30T18:27:29Z

Prokopenko: Prokopenko загрузил новую версию Файл:Inf graph.png

Файл:Inf graph.png

2016-11-30T18:23:21Z

Prokopenko:

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T18:01:05Z

Prokopenko: /* Последовательная сложность алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:58:51Z

Prokopenko: /* Математическое описание алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:57:50Z

Prokopenko: /* Вычислительное ядро алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:55:48Z

Prokopenko: /* Схема реализации последовательного алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:54:45Z

Prokopenko: /* Схема реализации последовательного алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:50:36Z

Prokopenko: /* Схема реализации последовательного алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:49:39Z

Prokopenko: /* Схема реализации последовательного алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:48:05Z

Prokopenko: /* Макроструктура алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T17:47:37Z

Prokopenko: /* Вычислительное ядро алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T10:40:16Z

Prokopenko: /* Программная реализация алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T10:38:45Z

Prokopenko: /* Свойства и структура алгоритма */

= Свойства и структура алгоритма =

== Общее описание алгоритма ==
Алгоритм предназначен для графического изображения смены возможных динамических режимов системы при изменении значений бифуркационных параметров.

== Математическое описание алгоритма ==
Рассматривается динамическая система: <math>u_{t+1} = f(u_t, \ldots, u_{t - k}, r_0, \ldots, r_l), u_0 = u^0 = const, \ldots, u_k = u^k = const, r_0 = const > 0, \ldots, r_l = const > 0</math>. Для построения бифуркационной диаграммы системы необходимо:

1. Выбрать подпространство значений параметров, на котором будет рассматриваться поведение системы.

2. Для каждого набора значений параметров вычислить N последовательных состояний системы, начиная с начального состояния, где N - достаточно большое число квантов времени. Этот шаг выполняется для стабилизации системы, в случае если для данного значения параметров система не ведет себя хаотично (имеет устойчивую точку, цикл, аттрактор и т.п.).

3. Вычислить еще K состояний системы, начиная с N-го состояния и вывести соответствующие результаты вместе со значениями параметров в файл. Чем больше число K, тем точнее будет бифуркационная диаграмма.

4. Отобразить полученные результаты графически.

== Вычислительное ядро алгоритма ==
В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.

== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.

Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.

== Схема реализации последовательного алгоритма ==
Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.

Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.

Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.

== Последовательная сложность алгоритма ==
В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.

Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].

Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).

== Информационный граф ==
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.

Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.

В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.

Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.

В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.

На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]

== Ресурс параллелизма алгоритма ==
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.

== Входные и выходные данные алгоритма ==
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

== Свойства алгоритма ==

= Программная реализация алгоритма =
Вторая часть описания алгоритмов в рамках AlgoWiki рассматривает все составные части процесса их реализации. Рассматривается как последовательная реализация алгоритма, так и параллельная. Описывается взаимосвязь свойств программ, реализующих алгоритм, и особенностей архитектуры компьютера, на которой они выполняются. Исследуется работа с памятью, локальность данных и вычислений, описывается масштабируемость и эффективность параллельных программ, производительность компьютеров, достигаемая на данной программе. Обсуждаются особенности реализации для разных классов архитектур компьютеров, приводятся ссылки на реализации в существующих библиотеках.

== Особенности реализации последовательного алгоритма ==
Здесь описываются особенности и варианты реализации алгоритма в виде последовательной программы, которые влияют на [[глоссарий#Эффективность реализации|''эффективность ее выполнения'']]. В частности, в данном разделе имеет смысл ''сказать о существовании блочных вариантов реализации алгоритма'', дополнительно описав потенциальные преимущества или недостатки, сопровождающие такую реализацию. Важный вопрос - это ''возможные варианты организации работы с данными'', варианты структур данных, наборов временных массивов и другие подобные вопросы. Для различных вариантов реализации следует оценить доступный ресурс параллелизма и объем требуемой памяти.

Важным нюансом является ''описание необходимой разрядности выполнения операций алгоритма'' (точности). На практике часто нет никакой необходимости выполнять все арифметические операции над вещественными числами с двойной точностью, т.к. это не влияет ни на устойчивость алгоритма, ни на точность получаемого результата. В таком случае, если значительную часть операций можно выполнять над типом float, и лишь в некоторых фрагментах необходим переход к типу double, это обязательно нужно отметить. Это прямое указание не только на правильную реализацию с точки зрения устойчивости по отношению к ошибкам округления, но и на более эффективную.

Опираясь на информацию из [[#Описание ресурса параллелизма алгоритма|п.1.8]] (описание ресурса параллелизма алгоритма), при описании последовательной версии стоит сказать про возможности [[глоссарий#Эквивалентное преобразование|''эквивалентного преобразования программ'']], реализующих данных алгоритм. В дальнейшем, это даст возможность простого использования доступного параллелизма или же просто покажет, как использовать присущий алгоритму параллелизм на практике. Например, параллелизм на уровне итераций самого внутреннего цикла обычно используется для векторизации. Однако, в некоторых случаях этот параллелизм можно поднять "вверх" по структуре вложенности объемлющих циклов, что делает возможной и эффективную реализацию данного алгоритма на многоядерных SMP-компьютерах.

С этой же точки зрения, в данном разделе весьма полезны соображения по реализации алгоритма на различных параллельных вычислительных платформах. Высокопроизводительные кластеры, многоядерные узлы, возможности для векторизации или использования ускорителей - особенности этих архитектур не только опираются на разные свойства алгоритмов, но и по-разному должны быть выражены в программах, что также желательно описать в данном разделе.

== Локальность данных и вычислений ==
Вопросы локальности данных и вычислений не часто изучаются на практике, но именно локальность определяет эффективность выполнения программ на современных вычислительных платформах <ref>Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.</ref><ref>Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.</ref>. В данном разделе приводятся оценки степени [[глоссарий#Локальность использования данных|''локальности данных'']] и [[глоссарий#Локальность вычислений|вычислений]] в программе, причем рассматривается как [[глоссарий#Временная локальность|''временна́я'']], так и [[глоссарий#Пространственная локальность|''пространственная'']] локальность. Отмечаются позитивные и негативные факты, связанные с локальностью, какие ситуации и при каких условиях могут возникать. Исследуется, как меняется локальность при переходе от последовательной реализации к параллельной. Выделяются ключевые шаблоны взаимодействия программы, реализующей описываемый алгоритм, с памятью. Отмечается возможная взаимосвязь между используемыми конструкциями языков программирования и степенью локальности, которыми обладают результирующие программы.

Отдельно приводятся профили взаимодействия с памятью для вычислительных ядер и ключевых фрагментов. Если из-за большого числа обращений по общему профилю сложно понять реальную специфику взаимодействия программ с памятью, то проводится последовательная детализация и приводится серия профилей более мелкого масштаба.

На рис.3 и рис.4 показаны профили обращения в память для программ, реализующих разложение Холецкого и быстрое преобразование Фурье, по которым хорошо видна разница свойств локальности у данных алгоритмов.

[[file:Cholesky_locality1.jpg|thumb|center|700px|Рис.3 Реализация метода Холецкого. Общий профиль обращений в память]]
[[file:fft 1.PNG|thumb|center|700px|Рис.4 Нерекурсивная реализация БПФ для степеней двойки. Общий профиль обращений в память]]

== Возможные способы и особенности параллельной реализации алгоритма ==
Раздел довольно обширный, в котором должны быть описаны основные факты и положения, формирующие параллельную программу. К их числу можно отнести:
* представленный иерархически ресурс параллелизма, опирающийся на структуру циклических конструкций и на граф вызовов программы;
* комбинацию (иерархию) массового параллелизма и параллелизма конечного;
* возможные способы распределения операций между процессами/нитями;
* возможные способы распределения данных;
* оценку количества операций, объёма и числа пересылок данных (как общего числа, так и в пересчёте на каждый параллельный процесс);

и другие.

В этом же разделе должны быть даны рекомендации или сделаны комментарии относительно реализации алгоритма с помощью различных технологий параллельного программирования: MPI, OpenMP, CUDA или использования директив векторизации.

== Масштабируемость алгоритма и его реализации ==
Задача данного раздела - показать пределы [[глоссарий#Масштабируемость|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость|''сильной'']] и [[глоссарий#Слабая масштабируемость|''слабой'']] масштабируемости алгоритма и его реализаций.

Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).

Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи <ref>Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.</ref>. При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.

На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.
[[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рис.5 Масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи]]

== Динамические характеристики и эффективность реализации алгоритма ==
Это объемный раздел AlgoWiki, поскольку оценка эффективности реализации алгоритма требует комплексного подхода <ref>Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.</ref>, предполагающего аккуратный анализ всех этапов от архитектуры компьютера до самого алгоритма. Основная задача данного раздела заключается в том, чтобы оценить степень эффективности параллельных программ, реализующих данный алгоритм на различных платформах, в зависимости от числа процессоров и размера задачи. Эффективность в данном разделе понимается широко: это и [[глоссарий#Эффективность распараллеливания|''эффективность распараллеливания'']] программы, это и [[глоссарий#Эффективность реализации|''эффективность реализации'']] программ по отношению к пиковым показателям работы вычислительных систем.

Помимо собственно показателей эффективности, нужно описать и все основные причины, из-за которых эффективность работы параллельной программы на конкретной вычислительной платформе не удается сделать выше. Это не самая простая задача, поскольку на данный момент нет общепринятой методики и соответствующего инструментария, с помощью которых подобный анализ можно было бы провести. Требуется оценить и описать эффективность работы с памятью (особенности профиля взаимодействия программы с памятью), эффективность использования заложенного в алгоритм ресурса параллелизма, эффективность использования коммуникационной сети (особенности коммуникационного профиля), эффективность операций ввода/вывода и т.п. Иногда достаточно интегральных характеристик по работе программы, в некоторых случаях полезно показать данные мониторинга нижнего уровня, например, по загрузке процессора, кэш-промахам, интенсивности использования сети Infiniband и т.п. Хорошее представление о работе параллельной MPI-программы дают данные трассировки, полученные, например, с помощью системы Scalasca.

== Выводы для классов архитектур ==
В данный раздел должны быть включены рекомендации по реализации алгоритма для разных классов архитектур. Если архитектура какого-либо компьютера или платформы обладает специфическими особенностями, влияющими на эффективность реализации, то это здесь нужно отметить.

На практике это сделать можно по-разному: либо все свести в один текущий раздел, либо же соответствующие факты сразу включать в предшествующие разделы, где они обсуждаются и необходимы по смыслу. В некоторых случаях, имеет смысл делать отдельные варианты всей [[#ЧАСТЬ. Программная реализация алгоритмов|части II]] AlgoWiki применительно к отдельным классам архитектур, оставляя общей машинно-независимую [[#ЧАСТЬ. Свойства и структура алгоритмов|часть I]]. В любом случае, важно указать и позитивные, и негативные факты по отношению к конкретным классам. Можно говорить о возможных вариантах оптимизации или даже о "трюках" в написании программ, ориентированных на целевые классы архитектур.

== Существующие реализации алгоритма ==
Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T10:37:07Z

Prokopenko: /* Свойства алгоритма */

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T10:34:47Z

Prokopenko: /* Математическое описание алгоритма */

= Свойства и структура алгоритма =

== Общее описание алгоритма ==
Алгоритм предназначен для графического изображения смены возможных динамических режимов системы при изменении значений бифуркационных параметров.

== Математическое описание алгоритма ==
Рассматривается динамическая система: <math>u_{t+1} = f(u_t, \ldots, u_{t - k}, r_0, \ldots, r_l), u_0 = u^0 = const, \ldots, u_k = u^k = const, r_0 = const > 0, \ldots, r_l = const > 0</math>. Для построения бифуркационной диаграммы системы необходимо:

1. Выбрать подпространство значений параметров, на котором будет рассматриваться поведение системы.

2. Для каждого набора значений параметров вычислить N последовательных состояний системы, начиная с начального состояния, где N - достаточно большое число квантов времени. Этот шаг выполняется для стабилизации системы, в случае если для данного значения параметров система не ведет себя хаотично (имеет устойчивую точку, цикл, аттрактор и т.п.).

3. Вычислить еще K состояний системы, начиная с N-го состояния и вывести соответствующие результаты вместе со значениями параметров в файл. Чем больше число K, тем точнее будет бифуркационная диаграмма.

4. Отобразить полученные результаты графически.

== Вычислительное ядро алгоритма ==
В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.

== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.

Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.

== Схема реализации последовательного алгоритма ==
Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.

Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.

Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.

== Последовательная сложность алгоритма ==
В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.

Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].

Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).

== Информационный граф ==
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.

Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.

В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.

Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.

В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.

На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]

== Ресурс параллелизма алгоритма ==
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.

== Входные и выходные данные алгоритма ==
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

== Свойства алгоритма ==
Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.

Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.

[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.

Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.

''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.

На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.

Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.

Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.

[[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.

''"Длинные" дуги в информационном графе'' <ref name="VVVVVV" /> говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.

Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' <ref name="VVVVVV" />, которые также имеет смысл привести в данном разделе.

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T10:33:29Z

Prokopenko: /* Математическое описание алгоритма */

= Свойства и структура алгоритма =

== Общее описание алгоритма ==
Алгоритм предназначен для графического изображения смены возможных динамических режимов системы при изменении значений бифуркационных параметров.

== Математическое описание алгоритма ==
Рассматривается динамическая система: <math>u_{t+1} = f(u_t, \ldots, u_{t - k}, r_0, \ldots, r_l), u_0 = u^0 = const, \ldots, u_k = u^k = const, r_0 = const > 0, \ldots, r_l = const > 0</math>. Для построения бифуркационной диаграммы системы необходимо:\\
1. Выбрать подпространство значений параметров, на котором будет рассматриваться поведение системы.\\
2. Для каждого набора значений параметров вычислить N последовательных состояний системы, начиная с начального состояния, где N - достаточно большое число квантов времени. Этот шаг выполняется для стабилизации системы, в случае если для данного значения параметров система не ведет себя хаотично (имеет устойчивую точку, цикл, аттрактор и т.п.).\\
3. Вычислить еще K состояний системы, начиная с N-го состояния и вывести соответствующие результаты вместе со значениями параметров в файл. Чем больше число K, тем точнее будет бифуркационная диаграмма.\\
4. Отобразить полученные результаты графически.

== Вычислительное ядро алгоритма ==
В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.

== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.

Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.

== Схема реализации последовательного алгоритма ==
Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.

Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.

Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.

== Последовательная сложность алгоритма ==
В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.

Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].

Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).

== Информационный граф ==
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.

Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.

В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.

Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.

В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.

На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]

== Ресурс параллелизма алгоритма ==
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.

== Входные и выходные данные алгоритма ==
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

== Свойства алгоритма ==
Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.

Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.

[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.

Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.

''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.

На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.

Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.

Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.

[[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.

''"Длинные" дуги в информационном графе'' <ref name="VVVVVV" /> говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.

Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' <ref name="VVVVVV" />, которые также имеет смысл привести в данном разделе.

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-30T10:22:12Z

Prokopenko: /* Свойства и структура алгоритма */

= Свойства и структура алгоритма =

== Общее описание алгоритма ==
Алгоритм предназначен для графического изображения смены возможных динамических режимов системы при изменении значений бифуркационных параметров.

== Математическое описание алгоритма ==
Рассматривается динамическая система: <math>u_{t+1} = f(u_t, \ldots, u_{t - k}, r_0, \ldots, r_l), u_0 = u^0 = const, \ldots, u_k = u^k = const, r_0 = const > 0, \ldots, r_l = const > 0</math>. Для построения бифуркационной диаграммы системы необходимо:
1. Выбрать подпространство значений параметров, на котором будет рассматриваться поведение системы.
2. Для каждого набора значений параметров вычислить последующее состояние
== Вычислительное ядро алгоритма ==
В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.

== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.

Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.

== Схема реализации последовательного алгоритма ==
Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.

Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.

Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.

== Последовательная сложность алгоритма ==
В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.

Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].

Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).

== Информационный граф ==
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.

Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.

В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.

Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.

В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.

На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]

== Ресурс параллелизма алгоритма ==
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.

== Входные и выходные данные алгоритма ==
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

== Свойства алгоритма ==
Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.

Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.

[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.

Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.

''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.

На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.

Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.

Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.

[[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.

''"Длинные" дуги в информационном графе'' <ref name="VVVVVV" /> говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.

Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' <ref name="VVVVVV" />, которые также имеет смысл привести в данном разделе.

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-13T12:23:16Z

Prokopenko: /* Математическое описание алгоритма */

= Свойства и структура алгоритма =

== Общее описание алгоритма ==
Алгоритм предназначен для графического изображения смены возможных динамических режимов системы при изменении значений бифуркационных параметров.

== Математическое описание алгоритма ==
Рассматривается динамическая система: <math>u_{t+1} = f(u_t, r), u_0 = u^0 = const, r = const > 0</math>

== Вычислительное ядро алгоритма ==
В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.

== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.

Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.

== Схема реализации последовательного алгоритма ==
Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.

Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.

Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.

== Последовательная сложность алгоритма ==
В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.

Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].

Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).

== Информационный граф ==
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.

Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.

В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.

Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.

В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.

На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]

== Ресурс параллелизма алгоритма ==
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.

== Входные и выходные данные алгоритма ==
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

== Свойства алгоритма ==
Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.

Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.

[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.

Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.

''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.

На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.

Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.

Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.

[[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.

''"Длинные" дуги в информационном графе'' <ref name="VVVVVV" /> говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.

Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' <ref name="VVVVVV" />, которые также имеет смысл привести в данном разделе.

Участник:Prokopenko/Алгоритм построения бифуркационной диаграммы динамической системы

2016-11-13T12:22:55Z

Prokopenko: Новая страница: «= Свойства и структура алгоритма = == Общее описание алгоритма == Алгоритм предназначен дл…»

= Свойства и структура алгоритма =

== Общее описание алгоритма ==
Алгоритм предназначен для графического изображения смены возможных динамических режимов системы при изменении значений бифуркационных параметров.

== Математическое описание алгоритма ==
Рассматривается динамическая система: <math>u_{t+1} = f(u_t, r), u_0 = u^0 = \const, r = \const > 0</math>

== Вычислительное ядро алгоритма ==
В описываемом алгоритме выделяется и описывается [[глоссарий#Вычислительное ядро|''вычислительное ядро'']], т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.

== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.

Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.

== Схема реализации последовательного алгоритма ==
Здесь описываются все шаги, которые нужно выполнить при последовательной реализации данного алгоритма. В некотором смысле, данный раздел является избыточным, поскольку математическое описание уже содержит всю необходимую информацию. Однако он, несомненно, полезен: схема реализации алгоритма выписывается явно, помогая однозначной интерпретации приводимых далее оценок и свойств.

Описание может быть выполнено в виде блок-схемы, последовательности математических формул, обращений к описанию других алгоритмов, фрагмента кода на Фортране, Си или другом языке программирования, фрагмента кода на псевдокоде и т.п. Главное - это сделать схему реализации последовательного алгоритма полностью понятной. Совершенно не обязательно все шаги детализировать до элементарных операций, отдельные шаги могут соответствовать макрооперациям, отвечающим другим алгоритмам.

Описание схемы реализации вполне может содержать и словесные пояснения, отражающие какие-либо тонкие нюансы самого алгоритма или его реализации. Уже в данном разделе можно сказать про возможный компромисс между объемом требуемой оперативной памяти и временем работы алгоритма, между используемыми структурами данных и степенью доступного параллелизма. В частности, часто возникает ситуация, когда можно ввести дополнительные временные массивы или же отказаться от использования специальных компактных схем хранения данных, увеличивая степень доступного параллелизма.

== Последовательная сложность алгоритма ==
В данном разделе описания свойств алгоритма приводится оценка его [[глоссарий#Последовательная сложность|''последовательной сложности'']], т.е. числа операций, которые нужно выполнить при последовательном исполнении алгоритма (в соответствии с [[#Описание схемы реализации последовательного алгоритма|п.1.5]]). Для разных алгоритмов понятие операции, в терминах которой оценивается его сложность, может существенно различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, обновления элементов массива, элементарные функции, макрооперации и другие. В LU-разложении преобладают арифметические операции над вещественными числами, а для транспонирования матриц важны лишь обращения к памяти: это и должно найти отражение в описании.

Если выбор конкретного типа операций для оценки сложности алгоритма не очевиден, то нужно привести обоснование возможных вариантов. В некоторых случаях можно приводить оценку не всего алгоритма, а лишь его вычислительного ядра: в таком случае это нужно отметить, сославшись [[#Общее описание алгоритма|на п.1.1]].

Например, сложность алгоритма суммирования элементов вектора сдваиванием равна <math>n-1</math>. Сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки – <math>n\log_2n</math> операций комплексного сложения и <math>(n\log_2n)/2</math> операций комплексного умножения. Сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> вычислений квадратного корня, <math>n(n-1)/2</math> операций деления, по <math>(n^3-n)/6</math> операций умножения и сложения (вычитания).

== Информационный граф ==
Это очень важный раздел описания. Именно здесь можно показать (увидеть) как устроена параллельная структура алгоритма, для чего приводится описание и изображение его информационного графа ([[глоссарий#Граф алгоритма|''графа алгоритма'']] <ref name="VVVVVV">Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. </ref>). Для рисунков с изображением графа будут составлены рекомендации по их формированию, чтобы все информационные графы, внесенные в энциклопедию, можно было бы воспринимать и интерпретировать одинаково. Дополнительно можно привести полное параметрическое описание графа в терминах покрывающих функций <ref name="VVVVVV" />.

Интересных вариантов для отражения информационной структуры алгоритмов много. Для каких-то алгоритмов нужно показать максимально подробную структуру, а иногда важнее макроструктура. Много информации несут разного рода проекции информационного графа, выделяя его регулярные составляющие и одновременно скрывая несущественные детали. Иногда оказывается полезным показать последовательность в изменении графа при изменении значений внешних переменных (например, размеров матриц): мы часто ожидаем "подобное" изменение информационного графа, но это изменение не всегда очевидно на практике.

В целом, задача изображения графа алгоритма весьма нетривиальна. Начнем с того, что это потенциально бесконечный граф, число вершин и дуг которого определяется значениями внешних переменных, а они могут быть весьма и весьма велики. В такой ситуации, как правило, спасают упомянутые выше соображения подобия, делающие графы для разных значений внешних переменных "похожими": почти всегда достаточно привести лишь один граф небольшого размера, добавив, что графы для остальных значений будут устроены "точно также". На практике, увы, не всегда все так просто, и здесь нужно быть аккуратным.

Далее, граф алгоритма - это потенциально многомерный объект. Наиболее естественная система координат для размещения вершин и дуг информационного графа опирается на структуру вложенности циклов в реализации алгоритма. Если глубина вложенности циклов не превышает трех, то и граф размещается в привычном трехмерном пространстве, однако для более сложных циклических конструкций с глубиной вложенности 4 и больше необходимы специальные методы представления и изображения графов.

В данном разделе AlgoWiki могут использоваться многие интересные возможности, которые еще подлежат обсуждению: возможность повернуть граф при его отображении на экране компьютера для выбора наиболее удобного угла обзора, разметка вершин по типу соответствующим им операций, отражение [[глоссарий#Ярусно-параллельная форма графа алгоритма|''ярусно-параллельной формы графа'']] и другие. Но в любом случае нужно не забывать главную задачу данного раздела - показать информационную структуру алгоритма так, чтобы стали понятны все его ключевые особенности, особенности параллельной структуры, особенности множеств дуг, участки регулярности и, напротив, участки с недерминированной структурой, зависящей от входных данных.

На рис.1 показана информационная структура алгоритма умножения матриц, на рис.2 - информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]
[[file:Fig2.svg|thumb|center|300px|Рис.2. Информационная структура одного из вариантов алгоритма решения систем линейных алгебраических уравнений с блочно-двухдиагональной матрицей]]

== Ресурс параллелизма алгоритма ==
Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы <ref name="VVVVVV" />. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.

Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне может быть использован и для отражения ресурса параллелизма.

Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.

Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения.

== Входные и выходные данные алгоритма ==
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

== Свойства алгоритма ==
Описываются прочие свойства алгоритма, на которые имеет смысл обратить внимание на этапе реализации. Как и ранее, никакой привязки к конкретной программно-аппаратной платформе не предполагается, однако вопросы реализации в проекте AlgoWiki всегда превалируют, и необходимость обсуждения каких-либо свойств алгоритмов определяется именно этим.

Весьма полезным является ''соотношение последовательной и параллельной сложности'' алгоритма. Оба понятия мы рассматривали ранее, но здесь делается акцент на том выигрыше, который теоретически может дать параллельная реализация алгоритма. Не менее важно описать и те сложности, которые могут возникнуть в процессе получения параллельной версии алгоритма.

[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма равна отношению числа операций к суммарному объему входных и выходных данных. Она показывает, сколько операций приходится на единицу переданных данных. Несмотря на простоту данного понятия, это значение исключительно полезно на практике: чем выше вычислительная мощность, тем меньше накладных расходов вызывает перемещение данных для их обработки, например, на сопроцессоре, ускорителе или другом узле кластера. Например, вычислительная мощность скалярного произведения двух векторов равна всего лишь <math>1</math>, а вычислительная мощность алгоритма умножения двух квадратных матриц равна <math>2n/3</math>.

Вопрос первостепенной важности на последующем этапе реализации - это [[глоссарий#Устойчивость|''устойчивость'']] алгоритма. Все, что касается различных сторон этого понятия, в частности, оценки устойчивости, должно быть описано в данном разделе.

''Сбалансированность'' вычислительного процесса можно рассматривать с разных сторон. Здесь и сбалансированность типов операций, в частности, арифметических операций между собой (сложение, умножение, деление) или же арифметических операций по отношению к операциям обращения к памяти (чтение/запись). Здесь и сбалансированность операций между параллельными ветвями алгоритма. С одной стороны, балансировка нагрузки является необходимым условием эффективной реализации алгоритма. Вместе с этим, это очень непростая задача, и в описании должно быть отмечено явно, насколько алгоритм обладает этой особенностью. Если обеспечение сбалансированности не очевидно, желательно описать возможные пути решения этой задачи.

На практике важна [[глоссарий#Детерминированность|''детерминированность алгоритмов'']], под которой будем понимать постоянство структуры вычислительного процесса. С этой точки зрения, классическое умножение плотных матриц является детерминированным алгоритмом, поскольку его структура при фиксированном размере матриц никак не зависит от элементов входных матриц. Умножение разреженных матриц, когда матрица хранятся в одном из специальных форматов, свойством детерминированности уже не обладает: его свойства, например, степень локальности данных зависит от структуры разреженности входных матриц. Итерационный алгоритм с выходом по точности также не является детерминированным: число итераций, а значит и число операций, меняется в зависимости от входных данных. В этом же ряду стоит использование датчиков случайных чисел, меняющих вычислительный процесс для различных запусков программы. Причина выделения свойства детерминированности понятна: работать с детерминированным алгоритмом проще, поскольку один раз найденная структура и будет определять качество его реализации. Если детерминированность нарушается, то это должно быть здесь описано вместе с описанием того, как недетерминированность влияет на структуру вычислительного процесса.

Серьезной причиной недетерминированности работы параллельных программ является изменение порядка выполнения ассоциативных операций. Типичный пример - это использование глобальных MPI-операций на множестве параллельных процессов, например, суммирование элементов распределенного массива. Система времени исполнения MPI сама выбирает порядок выполнения операций, предполагая выполнение свойства ассоциативности, из-за чего ошибки округления меняются от запуска программы к запуску, внося изменения в конечный результат ее работы. Это очень серьезная проблема, которая сегодня встречается часто на системах с массовым параллелизмом и определяет отсутствие повторяемости результатов работы параллельных программ. Данная особенность характерна для [[#ЧАСТЬ. Программная реализация алгоритмов|второй части AlgoWiki]], посвященной реализации алгоритмов, но вопрос очень важный, и соответствующие соображения, по возможности, должны быть отмечены и здесь.

Заметим, что, в некоторых случаях, недетерминированность в структуре алгоритмов можно "убрать" введением соответствующих макроопераций, после чего структура становится не только детерминированной, но и более понятной для восприятия. Подобное действие также следует отразить в данном разделе.

[[глоссарий#Степень исхода|''Степень исхода вершины информационного графа'']] показывает, в скольких операциях ее результат будет использоваться в качестве аргумента. Если степень исхода вершины велика, то на этапе реализации алгоритма нужно позаботиться об эффективном доступе к результату ее работы. В этом смысле, особый интерес представляют рассылки данных, когда результат выполнения одной операции используется во многих других вершинах графа, причем число таких вершин растет с увеличением значения внешних переменных.

''"Длинные" дуги в информационном графе'' <ref name="VVVVVV" /> говорят о потенциальных сложностях с размещением данных в иерархии памяти компьютера на этапе выполнения программы. С одной стороны, длина дуги зависит от выбора конкретной системы координат, в которой расположены вершины графа, а потому в другой системе координат они попросту могут исчезнуть (но не появится ли одновременно других длинных дуг?). А с другой стороны, вне зависимости от системы координат их присутствие может быть сигналом о необходимости длительного хранения данных на определенном уровне иерархии, что накладывает дополнительные ограничения на эффективность реализации алгоритма. Одной из причин возникновения длинных дуг являются рассылки скалярных величин по всем итерациям какого-либо цикла: в таком виде длинные дуги не вызывают каких-либо серьезных проблем на практике.

Для проектирования специализированных процессоров или реализации алгоритма на ПЛИС представляют интерес ''компактные укладки информационного графа'' <ref name="VVVVVV" />, которые также имеет смысл привести в данном разделе.