Уровень алгоритма

Участник:Бугаков Юрий/Построение матрицы Адамара произвольной размерности: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 50 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
{{Assignment|Sleo}}
 +
Авторы: [[U:Бугаков Юрий|Бугаков Юрий]] (613 группа), Кужамалиев Ернур (601 группа).
 +
 +
Бугаков Юрий:
 +
 +
* Пункты 1.1, 1.2, 1.9, 1.10, 2.1, 2.7;
 +
* Совместное обсуждение и работа над всей статьей в целом с другим автором.
 +
 +
Кужамалиев Ернур:
 +
 +
* Пункты 1.3, 1.4, 1.5, 1.6, 1.7 (рисунки авториские), 1.8;
 +
* Совместное обсуждение и работа над всей статьей в целом с другим автором.
 +
{{algorithm
 +
| name              = Построение матрицы Адамара
 +
| serial_complexity = <math>O( \left[ \frac{n}{4}\right]\,2^{2n})</math>
 +
| pf_height        = <math>O(1)</math>
 +
| pf_width          = <math>O(2^{2n})</math>
 +
| input_data        = <math>1</math>
 +
| output_data      = <math>2^{2n}</math>
 +
}}
 +
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков Жаком Адамаром (1865-1963). В свое время он дал такое определение матрицы Адамара:
+
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков [https://ru.wikipedia.org/wiki/%D0%90%D0%B4%D0%B0%D0%BC%D0%B0%D1%80,_%D0%96%D0%B0%D0%BA Жаком Адамаром (1865-1963)]. Их применение в науке и технике посвящены тысячи публикаций. Они предоставляют эффективные возможности для организации хранения, обработки и передачи информации.
  
Квадратная матрица Н порядка n с элементами ±1 называется матрицей Адамара, если выполняется условие
+
Квадратная матрица Н порядка ''m'' с элементами ±1 называется матрицей Адамара, если выполняется условие
  
:<math> H_n\,H_n^T = n\,E_n </math>
+
:<math> H_m\,H_m^T = m\,E_m </math>
  
Нетрудно показать, что различные строки матрицы Адамара попарно ортогональны. Также можно увидеть из определения, что n четно и любые две строки совпадают ровно в n/2 позициях и различаются в остальных.
+
Нетрудно заметить, что различные строки матрицы Адамара попарно ортогональны [1]. Также, можно увидеть из определения, что m четно и
 +
:<math>
 +
H_{2m} =
 +
\begin{pmatrix}
 +
H_{m} &  H_{m}\\
 +
H_{m} & -H_{m}\end{pmatrix}
 +
</math>
  
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок n матрицы Адамара при n ≥ 3 может быть лишь четным. Более того, при n ≥ 4 порядок обязан делиться на 4. До сих пор остается открытым вопрос: для любого ли n, кратного 4, существует матрица Адамара порядка n? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
+
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок ''m'' матрицы Адамара при ''m'' ≥ 3 может быть лишь четным. Более того, при ''m'' ≥ 4 порядок обязан делиться на 4. До сих пор остается открытым вопрос: для любого ли ''m'', кратного 4, существует матрица Адамара порядка m? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
  
В настоящее время матрицу Адамара определяют следующим образом:
+
Часто матрицу Адамара нормализуют и рассматривают размерности степени 2 (например [2],[3] и [4]). В дальнейшем будем рассматривать только такие случаи. Переопределим матрицу Адамара следующим образом:
  
Матрица ''H''<sub>''n''</sub> эта матрица размера 2<sup>''n''</sup>&nbsp;&times;&nbsp;2<sup>''n''</sup>, для которой справедливо равенство
+
'''Матрица Адамара ''H''<sub>''n''</sub> - это матрица размера 2<sup>''n''</sup>&nbsp;&times;&nbsp;2<sup>''n''</sup>, для которой справедливо равенство'''
  
:<math>H_n = H_{1} \otimes H_{n-1}</math>
+
:<math>H_n = H_{1} \otimes H_{n-1}</math>,
  
 
:<math>\begin{align}
 
:<math>\begin{align}
Строка 25: Строка 52:
 
     1 & -1
 
     1 & -1
 
   \end{array}\end{pmatrix}
 
   \end{array}\end{pmatrix}
\end{align}</math>
+
\end{align}</math>,
 +
'''где <math> \otimes </math> представляет собой [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BD%D0%B7%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5 тензорное произведение].'''
  
где <math> \otimes </math> представляет собой тензорное произведение матриц.
+
Представим некоторые частные примеры матриц Адамара:
  
Также, матрицу Адамара <math>H_n</math> мы можем представить поэлементным образом.  элемента <math>h_{ij}</math>
+
:<math>
 +
    H_0 = +1,
 +
</math>
  
Equivalently, we can define the Hadamard matrix by its (''k'',&nbsp;''n'')-th entry by writing
+
:<math>
: <math>k = \sum^{m-1}_{i=0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \cdots + k_1 2 + k_0</math>
 
 
 
and
 
: <math>n = \sum^{m-1}_{i=0} {n_i 2^i} = n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \cdots + n_1 2 + n_0</math>
 
 
 
where the ''k''<sub>''j''</sub> and ''n''<sub>''j''</sub> are the binary digits (0 or 1) of ''k'' and ''n'', respectively. Note that for the element in the top left corner, we define: <math>k = n = 0</math>.  In this case, we have:
 
:<math>\left( H_m \right)_{k,n} = \frac{1}{2^\frac{m}{2}} (-1)^{\sum_j k_j n_j}</math>
 
 
 
This is exactly the multidimensional <math>\scriptstyle 2 \,\times\, 2 \,\times\, \cdots \,\times\, 2 \,\times\, 2</math> DFT, normalized to be [[unitary operator|unitary]], if the inputs and outputs are regarded as multidimensional arrays indexed by the ''n''<sub>''j''</sub> and ''k''<sub>''j''</sub>, respectively.
 
 
 
Вот несколько примеров матриц Адамара:
 
:<math>\begin{align}
 
  H_0 = &+1\\
 
 
   H_1 = \frac{1}{\sqrt2}
 
   H_1 = \frac{1}{\sqrt2}
   &\begin{pmatrix}\begin{array}{rr}
+
   \begin{pmatrix}\begin{array}{rr}
 
     1 & 1\\
 
     1 & 1\\
 
     1 & -1
 
     1 & -1
 
   \end{array}\end{pmatrix}
 
   \end{array}\end{pmatrix}
\end{align}</math>
+
</math>,
  
(This ''H''<sub>1</sub> is precisely the size-2 DFT.  It can also be regarded as the [[Fourier transform]] on the two-element ''additive'' group of '''Z'''/(2).)
+
:<math>
:<math>\begin{align}
 
 
   H_2 = \frac{1}{2}
 
   H_2 = \frac{1}{2}
   &\begin{pmatrix}\begin{array}{rrrr}
+
   \begin{pmatrix}\begin{array}{rrrr}
 
     1 &  1 &  1 &  1\\
 
     1 &  1 &  1 &  1\\
 
     1 & -1 &  1 & -1\\
 
     1 & -1 &  1 & -1\\
 
     1 &  1 & -1 & -1\\
 
     1 &  1 & -1 & -1\\
 
     1 & -1 & -1 &  1
 
     1 & -1 & -1 &  1
  \end{array}\end{pmatrix}\\
+
    \end{array}\end{pmatrix}
 +
</math>,
 +
 
 +
:<math>
 
   H_3 = \frac{1}{2^{\frac{3}{2}}}
 
   H_3 = \frac{1}{2^{\frac{3}{2}}}
   &\begin{pmatrix}\begin{array}{rrrrrrrr}
+
   \begin{pmatrix}\begin{array}{rrrrrrrr}
     1 &  1 &  1 &  1 & 1 &  1 &  1 &  1\\
+
     1 &  1 &  1 &  1 & 1 &  1 &  1 &  1\\
     1 & -1 &  1 & -1 & 1 & -1 &  1 & -1\\
+
     1 & -1 &  1 & -1 & 1 & -1 &  1 & -1\\
     1 &  1 & -1 & -1 & 1 &  1 & -1 & -1\\
+
     1 &  1 & -1 & -1 & 1 &  1 & -1 & -1\\
     1 & -1 & -1 &  1 & 1 & -1 & -1 &  1\\  
+
     1 & -1 & -1 &  1 & 1 & -1 & -1 &  1\\
     1 &  1 &  1 & 1 & -1 & -1 & -1 & -1\\
+
     1 &  1 &  1 & -1 & -1 & -1 & -1 & -1\\
     1 & -1 &  1 & -1 & -1 &  1 & -1 &  1\\
+
     1 & -1 &  1 & 1 & -1 &  1 & -1 &  1\\
     1 &  1 & -1 & -1 & -1 & -1 &  1 &  1\\
+
     1 &  1 & -1 & 1 & -1 & -1 &  1 &  1\\
     1 & -1 & -1 &  1 & -1 &  1 &  1 & -1
+
     1 & -1 & -1 &  -1 & -1 &  1 &  1 & -1\\
  \end{array}\end{pmatrix}\\
+
    \end{array}\end{pmatrix}
  (H_n)_{i,j} = \frac{1}{2^{\frac{n}{2}}} &(-1)^{i \cdot j}
+
</math>.
\end{align}</math>
 
  
==== Симметричность и положительная определённость матрицы ====
+
=== Математическое описание алгоритма ===
  
Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций в сравнении с, например, разложением по методу Гаусса. При этом альтернативное (без вычисления квадратных корней) LU-разложение, использующее симметрию матрицы, всё же несколько быстрее метода Холецкого (не использует извлечение квадратных корней), но требует хранения всей матрицы.
+
Основой алгоритма является тот факт, что любую матрицу Адамара <math>H_n</math> размера <math>2^n\times 2^n</math> можно вычислить поэлементно ([3], [4]):
Благодаря тому, что разлагаемая матрица не только симметрична, но и положительно определена, её LU-разложения, в том числе и разложение методом Холецкого, имеют наименьшее ''[[Глоссарий#Эквивалентное возмущение|эквивалентное возмущение]]'' из всех известных разложений матриц.
 
  
==== Режим накопления ====
+
:<math>h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}</math>,
 +
 
 +
где ''k''<sub>''j''</sub> и ''l''<sub>''j''</sub> коэффициенты двоичного разложения чисел ''k'' и ''l'' (1 или 0):
 +
 
 +
: <math>k = \sum^{n}_{i=0} {k_i 2^i} = k_{n} 2^{n} + k_{n-1} 2^{n-1} + \cdots + k_1 2 + k_0</math>
 +
 
 +
и
 +
: <math>l = \sum^{n}_{i=0} {l_i 2^i} = l_{n} 2^{n} + l_{n-1} 2^{n-1} + \cdots + l_1 2 + l_0</math>.
 +
 
 +
Помимо этой формулы чаще всего используется заполнение по определению. В связи с трудностями распараллеливания и постоянного выделения памяти при каждом шаге рекурсивного вызова этого метода, был выбран предыдущий способ вычисления.
 +
 
 +
=== Вычислительное ядро алгоритма ===
  
Алгоритм позволяет использовать так называемый ''режим накопления'', обусловленный тем, что значительную часть вычислений составляют ''вычисления скалярных произведений''.
+
Вычислительное ядро составляют вычисления элементов матрицы <math>h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}</math>.
  
=== Математическое описание алгоритма ===
+
=== Макроструктура алгоритма ===
  
Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>).
+
Основную часть метода составляют вычисления значений степени -1 для каждого элемента:
  
Вычисляемые данные: нижняя треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>).
+
: <math>\sum_{j=0}^n k_j l_j</math>.
  
Формулы метода:
+
Как видно по формуле, получаемое значение равна количеству единиц в двоичной записи результата побитового умножения ''k'' и ''l''. Существует эффективный метод вычисления количества единиц , сложность которого равна ''m'' операций вычитания и ''m'' операций побитового умножения, где ''m''-искомое количество единиц.
:<math>
 
\begin{align}
 
l_{11} & = \sqrt{a_{11}}, \\
 
l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\
 
l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\
 
l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n].
 
\end{align}
 
</math>
 
  
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
+
=== Схема реализации последовательного алгоритма ===
  
В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>\frac{1}{l_{ii}}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.
+
Последовательность исполнения метода следующая:
  
=== Вычислительное ядро алгоритма ===
+
1. Побитовое умножение <math>k\&l</math>; 
  
Вычислительное ядро последовательной версии метода Холецкого можно составить из множественных (всего их <math>\frac{n (n - 1)}{2}</math>) вычислений скалярных произведений строк матрицы:
+
2. Вычисление количества единиц двоичной записи;
  
:<math>\sum_{p = 1}^{i - 1} l_{ip} l_{jp}</math>
+
3. Определение знака элемента по степени.
  
в режиме накопления или без него, в зависимости от требований задачи. Во многих последовательных реализациях упомянутый способ представления не используется. Дело в том, что в них вычисление сумм типа
+
=== Последовательная сложность алгоритма ===
  
:<math>a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}</math><nowiki/>
+
Для построения матрицы Адамара порядка <math>N=2^n</math> в первом шаге потребуется <math>N^2</math> побитовых умножений ''k&l''.
 +
Во втором шаге, как говорилось выше, сложность метода вычисления количества единиц  числа в двоичном представлении равна удвоенному количеству единиц. В наихудшем случае сложность равна <math>2log_2N</math>, при ''k=l=N-1'', а в наилучшем 0. Для нахождения  степени всех элементов матрицы потребуются <math> 2N^2\left[\frac{log_2N}{4}\right]</math> операций. В третьем шаге для определения знака потребуется <math>N^2</math> операций, то есть сложность алгоритма <math> T(n) = 2\,(1+\left[\frac{n}{4}\right])\,2^{2n}. </math>
  
в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений
+
=== Информационный граф ===
  
:<math>a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}</math>
+
На рисунке ниже изображен информационный граф алгоритма.
  
в ''режиме накопления'' или без него.
+
*<math>k\&l</math> - операция побитового умножения, где <math>k</math> и <math>l</math> соответствующие координаты элемента <math>h_{kl}</math>;
 +
* OP - вычисление количества единиц числа в двоичной системе. Состоит из последовательного применения операций вычитания и побитового умножения;
 +
* SGN - определение знака соответствующего элемента. Если результат предыдущего шага четное, то знак положительный, иначе отрицательный. 
  
Тем не менее, в популярных зарубежных реализациях точечного метода Холецкого, в частности, в библиотеках LINPACK и LAPACK, основанных на BLAS, используются именно вычисления скалярных произведений в виде вызова соответствующих подпрограмм BLAS (конкретно — функции SDOT). На последовательном уровне это влечёт за собой дополнительную операцию суммирования на каждый из <math>\frac{n (n + 1)}{2}</math> вычисляемый элемент матрицы <math>L</math> и некоторое замедление работы программы (о других следствиях рассказано ниже в разделе «[[#Существующие реализации алгоритма|Существующие реализации алгоритма]]»). Поэтому в данных вариантах ядром метода Холецкого будут вычисления этих скалярных произведений.
+
[[file:Hadamar.png|thumb|center|1400px|Рисунок 1. Граф алгоритма.]]
 +
[[file:OP3.png|thumb|center|1400px|Рисунок 2. Граф OP.]]
  
=== Макроструктура алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют множественные (всего <math>\frac{n (n - 1)}{2}</math>) вычисления сумм
+
Для построения матрицы порядка <math>N=2^n</math> требуется последовательно выполнить следующие шаги:
 +
* <math>N^2</math>  вычислений побитового умножения,
 +
* для каждого элемента от <math>2</math> до <math>2n</math> операций вычитания и побитового умножения, в зависимости от результата предыдущего шага,
 +
* <math>N^2</math>  для определения знака значения элемента.
 +
 +
Таким образом для построения необходимы лишь простые операции вычитания и побитового умножения выполняемые с целыми положительными числами. Стоит заметить что вычисления для каждого элемента не зависят друг от друга. Также можно воспользоваться либо симметричностью матрицы Адамара либо закономерностью областей показанная в пункте 1.1.
 +
Таким образом, основной вклад в высотe ЯПФ вносит операция вычисления количества единиц. Ширина ЯПФ будет равна <math>O(2^{2n})</math>.
  
:<math>a_{ji}-\sum_{p=1}^{i-1}l_{ip} l_{jp}</math>
+
=== Входные и выходные данные алгоритма ===
  
в режиме накопления или без него.
+
'''Входные данные''': натуральное число <math> n \in \N </math> - размерность матрицы Адамара <math>H_n</math>.
  
=== Схема реализации последовательного алгоритма ===
+
'''Объём входных данных''': 1 (натуральное число <math> n </math>).
  
Последовательность исполнения метода следующая:
+
'''Выходные данные''': матрица Адамара <math>H_n</math> размера <math>2^n\times 2^n</math> (элементы <math>h_{ij}</math>).
  
1. <math>l_{11}= \sqrt{a_{11}}</math>
+
'''Объём выходных данных''': <math>2^{2n}</math>, где <math> n </math> - размерность матрицы Адамара. Стоит заметить, что в силу симметричности или самого определения матрицы Адамара, достаточно хранить не все элементы матрицы, а только их часть.
  
2. <math>l_{j1}= \frac{a_{j1}}{l_{11}}</math> (при <math>j</math> от <math>2</math> до <math>n</math>).
+
=== Свойства алгоритма ===
  
Далее для всех <math>i</math> от <math>2</math> до <math>n</math> по нарастанию выполняются
+
* Соотношение последовательной и параллельной сложности:
 +
Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Рассматривается некоторое фиксированное число процессов <math>P\in \mathbb{N}</math>. Считается, что каждый процесс ''P'' обрабатывает не более чем <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> элементов. Тогда качественная формула может быть записана таким образом: <math>T(n,P)=2\,(1+\left[ \frac{n}{4} \right])\,\frac{2^{2n}}{P}</math>.
  
3. <math>l_{ii} = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}</math> и
+
Неравенство <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> можно переписать, как <math>log_2\,\sqrt{P}\leq n</math>.
  
4. (кроме <math>i = n</math>): <nowiki/><math>l_{ji} = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}</math> (для всех <math>j</math> от <math>i + 1</math> до <math>n</math>).
+
Легко увидеть, что минимум функции ''T(n,P)'' будет при максимально возможном ''P'' : <math>log_2\,\sqrt{P}\leq n</math>. Такое ''P'' будет оптимальным числом процессов для алгоритма. В частности, для <math>P=2^p,\,p\in\mathbb{N}</math> оптимальное <math>P = 2^{2n}</math>.
 +
:<math>\frac{T(n)}{T(n,P)}=P</math>.
 +
То есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>;
  
После этого (если <math>i < n</math>) происходит переход к шагу 3 с бо́льшим <math>i</math>.
+
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
 +
:<math>\,\frac{2^{2n}(2+[\frac{n}{4}])}{1+2^{2n}}\left( \sim [\frac{n}{4}],\,n\to+\infty \right)</math>;
  
Особо отметим, что вычисления сумм вида <math>a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}</math> в обеих формулах производят в режиме накопления вычитанием из <math>a_{ji}</math> произведений <math>l_{ip} l_{jp}</math> для <math>p</math> от <math>1</math> до <math>i - 1</math>, c нарастанием <math>p</math>.
+
* Алгоритм построения матрицы Адамара является ''не детерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размера 2<sup>''n''</sup>&nbsp;&times;&nbsp;2<sup>''n''</sup>);
  
=== Последовательная сложность алгоритма ===
+
* Степень исхода вершины информационного графа равна 1;
  
Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется:
+
* Алгоритм построения матрицы Адамара является ''сбалансированным''. Так как количество вершин на разных процессорах одинаково, то алгоритм является сбалансированным по числу операций на каждом процессоре.
 
* <math>n</math> вычислений квадратного корня,
 
* <math>\frac{n(n-1)}{2}</math> делений,
 
* <math>\frac{n^3-n}{6}</math> сложений (вычитаний),
 
* <math>\frac{n^3-n}{6}</math> умножений.
 
  
Умножения и сложения (вычитания) составляют ''основную часть алгоритма''.
+
=ЧАСТЬ Программная реализация алгоритма =
 
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.
 
  
При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''.
+
== Особенности реализации последовательного алгоритма ==
  
=== Информационный граф ===
+
В простейшем варианте генерацию матрицы Адамара для нашего алгоритма можно записать так:
  
Опишем [[глоссарий#Граф алгоритма|граф алгоритма]]<ref>Воеводин В.В.  Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> как аналитически, так и в виде рисунка.
+
<source lang="C">
 +
void adamar(int** H, int n) // N = 2^n - размерность матрицы
 +
{   
 +
    int i,j,N;
 +
    float h;
 +
    h = pow(1/2,n/2); // h - нормализующий множитель
 +
    N = pow(2,n);
  
Граф алгоритма состоит из трёх групп вершин, расположенных в целочисленных узлах трёх областей разной размерности.
+
    for(i=0;i<N;++i)
 +
    {
 +
for(j=0;j<N;++j)
 +
{
 +
ij = i & j;
 +
    for (l=0;ij;++l) ij&=ij-1; // l - количество единиц бинарного представления ij
 +
if(l%2==0) H[i][j] = h;
 +
else H[i][j] = -h;
 +
}
 +
    }
 +
}
 +
</source>
  
'''Первая''' группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию SQRT.
+
Также существует рекурсивная реализация метода построения матрицы Адамара
Единственная координата каждой из вершин <math>i</math> меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.
 
  
Аргумент этой функции
+
<source lang="C">
+
void adamar_recursion(int** H, int N, int i, int j, int h) // h - нормализующий множитель
* при <math>i = 1</math> — элемент ''входных данных'', а именно  <math>a_{11}</math>;  
+
{
* при <math>i > 1</math> — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами <math>i - 1</math>, <math>i</math>, <math>i - 1</math>.
+
    if(n==1) H[i][j] = h;
Результат срабатывания операции является ''выходным данным'' <math>l_{ii}</math>.
+
    else
 +
    {
 +
        adamar(H, N/2, i, j, h);
 +
        adamar(H, N/2, i, N/2+j, h);
 +
        adamar(H, N/2, N/2+i, j, h);
 +
        adamar(H, N/2, N/2+i, N/2+j, -h);
 +
    }
 +
}
 +
</source>
  
'''Вторая''' группа вершин расположена в двумерной области, соответствующая ей операция <math>a / b</math>.
+
Или эквивалентный безрекурсивный вариант:
Естественно введённые координаты области таковы:  
 
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>n-1</math>, принимая все целочисленные значения;
 
* <math>j</math> — меняется в диапазоне от <math>i+1</math> до <math>n</math>, принимая все целочисленные значения.
 
  
Аргументы операции следующие:
+
<source lang="C">
*<math>a</math>:
+
void adamar_not_recursion(int** H, int n) // N = 2^n - размерность матрицы
** при <math>i = 1</math> — элементы ''входных данных'', а именно <math>a_{j1}</math>;
+
{   
** при <math>i > 1</math> — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами <math>i - 1, j, i - 1</math>;
+
    int i,j,N;
* <math>b</math> — результат срабатывания операции, соответствующей вершине из первой группы, с координатой <math>i</math>.
+
    float h;
 +
    h = pow(1/2,n/2);
 +
    N = pow(2,n);
 +
    k=2;
 +
    H[0][0] = h;
 +
 +
    while(k<=N)
 +
    {
 +
for (i=0; i<k; ++i)
 +
{
 +
for (j=0; j<k; ++j)
 +
{
 +
if (i<k/2 && j<k/2)
 +
{
 +
}
 +
else
 +
{
 +
if(i>=k/2 && j>=k/2)
 +
{
 +
H[i][j] = -(H[i-k/2][j-k/2]);
 +
}
 +
else
 +
{
 +
if (i>j)
 +
{
 +
H[i][j] = H[i-k/2][j];
 +
}
 +
else
 +
{
 +
H[i][j] = H[i][j-k/2];
 +
}
 +
}
 +
}
 +
}
 +
}
 +
 +
        k=k*2;
 +
    }
 +
}
 +
</source>
  
Результат срабатывания операции является ''выходным данным'' <math>l_{ji}</math>.
+
Для данного случая, рекурсия является менее эффективной для генерации матрицы Адамара ([https://habrahabr.ru/post/256351/ Хабрахабр. О бедной рекурсии замолвите слово, или всё, что вы не знали и не хотите о ней знать.]). С точки зрения последовательной реализации, генерация матрицы Адамара с помощью adamar_not_recursion будет выигрывать у adamar, так как adamar_not_recursion будет выполнять меньшее количество операций. С точки зрения параллельной реализации adamar имеет 100% парализацию и при определенных условиях будет выигрывать по времени у распараллелинной adamar_not_recursion (пусть в adamar и будет выполняться большее количество операций, но они являются [https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8 битовыми операциями]).
  
'''Третья''' группа вершин расположена в трёхмерной области, соответствующая ей операция  <math>a - b * c</math>.
+
== Локальность данных и вычислений ==
Естественно введённые координаты области таковы:
 
* <math>i</math> — меняется в диапазоне от <math>2</math> до <math>n</math>, принимая все целочисленные значения;
 
* <math>j</math> — меняется в диапазоне от <math>i</math> до <math>n</math>, принимая все целочисленные значения;
 
* <math>p</math> — меняется в диапазоне  от <math>1</math> до <math>i - 1</math>, принимая все целочисленные значения.
 
  
Аргументы операции следующие:
+
== Возможные способы и особенности параллельной реализации алгоритма ==
*<math>a</math>:
 
** при <math>p = 1</math> элемент входных данных <math>a_{ji}</math>;
 
** при <math>p > 1</math> — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами <math>i, j, p - 1</math>;
 
*<math>b</math> — результат срабатывания операции, соответствующей вершине из второй группы, с координатами <math>p, i</math>;
 
*<math>c</math> — результат срабатывания операции, соответствующей вершине из второй группы, с координатами <math>p, j</math>;
 
  
Результат срабатывания операции является ''промежуточным данным'' алгоритма.
+
== Масштабируемость алгоритма и его реализации ==
 +
Исследование проводилось на суперкомпьютере "Blue Gene".
  
Описанный граф можно посмотреть на рис.1 и рис.2, выполненных для случая <math>n = 4</math>. Здесь вершины первой группы обозначены жёлтым цветом и буквосочетанием sq, вершины второй — зелёным цветом и знаком деления, третьей — красным цветом и буквой f. Вершины, соответствующие операциям, производящим выходные данные алгоритма, выполнены более крупно. Дублирующие друг друга дуги даны как одна. На рис.1 показан граф алгоритма согласно классическому определению , на рис.2 к графу алгоритма добавлены вершины , соответствующие входным (обозначены синим цветом) и выходным (обозначены розовым цветом) данным.
+
Набор и границы значений изменяемых  параметров запуска реализации алгоритма:
  
[[file:Cholesky full.png|thumb|center|1400px|Рисунок 1. Граф алгоритма без отображения входных и выходных данных. SQ - вычисление квадратного корня, F - операция a-bc, Div - деление.]]
+
* число процессоров [1, 2, 4, 8,..., 1024] ;
[[file:Cholesky full_in_out.png|thumb|center|1400px|Рисунок 2. Граф алгоритма с отображением входных и выходных данных. SQ - вычисление квадратного корня, F - операция a-bc, Div - деление, In - входные данные, Out - результаты.]]
+
* размер матрицы [2, 4, 8,..., 2048].
  
=== Ресурс параллелизма алгоритма ===
+
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
  
Для разложения матрицы порядка <math>n</math> методом Холецкого в параллельном варианте требуется последовательно выполнить следующие ярусы:
+
* минимальная эффективность реализации 0.0121%;
* <math>n</math> ярусов с вычислением квадратного корня (единичные вычисления в каждом из ярусов),
+
* максимальная эффективность реализации 3.3003%.
* <math>n - 1</math> ярус делений (в каждом из ярусов линейное количество делений, в зависимости от яруса — от <math>1</math> до <math>n - 1</math>),
 
* по <math>n - 1</math> ярусов умножений и сложений/вычитаний (в каждом из ярусов — квадратичное количество операций, от <math>1</math> до <math>\frac{n^2 - n}{2}</math>.
 
 
Таким образом, в параллельном варианте, в отличие от последовательного, вычисления квадратных корней и делений будут определять довольно значительную долю требуемого времени. При реализации на конкретных архитектурах наличие в отдельных ярусах [[глоссарий#Ярусно-параллельная форма графа алгоритма|ЯПФ]] отдельных вычислений квадратных корней может породить и другие проблемы. Например, при реализации на ПЛИСах остальные вычисления (деления и тем более умножения и сложения/вычитания) могут быть конвейеризованы, что даёт экономию и по ресурсам на программируемых платах; вычисления же квадратных корней из-за их изолированности приведут к занятию ресурсов на платах, которые будут простаивать большую часть времени. Таким образом, общая экономия в 2 раза, из-за которой метод Холецкого предпочитают в случае симметричных задач тому же методу Гаусса, в параллельном случае уже имеет место вовсе не по всем ресурсам, и главное - не по требуемому времени.
 
  
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения метода Холецкого в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает увеличение требуемой памяти почти в 2 раза.
+
На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.
  
При классификации по высоте ЯПФ, таким образом, метод Холецкого относится к алгоритмам со сложностью <math>O(n)</math>. При классификации по ширине ЯПФ его сложность будет <math>O(n^2)</math>.
+
[[file:Prois1.jpg|thumb|center|700px|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
 +
[[file:Effec1.jpg|thumb|center|700px|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]
  
=== Входные и выходные данные алгоритма ===
+
Построим оценки масштабируемости выбранной реализации:
 +
* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.
 +
* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени <math>n</math> размера матрицы <math>N=2^{n}</math>.  При увеличении размера матрицы эффективность также увеличивается, но скорость возрастания уменьшается.
 +
По двум направлениям: При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая.
  
'''Входные данные''': плотная матрица <math>A</math> (элементы <math>a_{ij}</math>).
+
== Динамические характеристики и эффективность реализации алгоритма ==
Дополнительные ограничения:
 
* <math>A</math> – симметрическая матрица, т. е. <math>a_{ij}= a_{ji}, i, j = 1, \ldots, n</math>.
 
* <math>A</math> – положительно определённая матрица, т. е. для любых ненулевых векторов <math>\vec{x}</math> выполняется <math>\vec{x}^T A \vec{x} > 0</math>.
 
  
'''Объём входных данных''': <math>\frac{n (n + 1)}{2}</math> (в силу симметричности достаточно хранить только диагональ и над/поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом. Например, в библиотеке, реализованной в НИВЦ МГУ, матрица A хранилась в одномерном массиве длины <math>\frac{n (n + 1)}{2}</math> по строкам своего нижнего треугольника.
+
== Выводы для классов архитектур ==
  
'''Выходные данные''': нижняя треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>).
+
== Существующие реализации алгоритма ==
  
'''Объём выходных данных''': <math>\frac{n (n + 1)}{2}</math>  (в силу треугольности достаточно хранить только ненулевые элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом. Например, в той же  библиотеке, созданной в НИВЦ МГУ, матрица <math>L</math> хранилась в одномерном массиве длины <math>\frac{n (n + 1)}{2}</math> по строкам своей нижней части.
+
Примеры вычислительных пакетов, содержащих функции генерации матриц Адамара:
  
=== Свойства алгоритма ===
+
# [http://www.exponenta.ru/soft/matlab/potemkin/book2/chapter5/hadamard.asp MATLAB];
 +
# [https://reference.wolfram.com/language/ref/HadamardMatrix.html WOLFRAM];
 +
# [http://pydoc.net/Python/rogues/0.3.0/rogues.matrices.hadamard/ Python];
 +
# [http://www.obihiro.ac.jp/~suzukim/masuda/octave/html3/octave_97.html Octave].
  
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''квадратичным'' (отношение кубической к линейной).  
+
Стоит отметить, что во многих вычислительных пакетах встроена операция тензорного произведения матриц, которая позволяет строить матрицу Адамара по определению. Этот факт позволяет использовать матрицу Адамара в этих вычислительных пакетах:
 +
# [https://ru.wikipedia.org/wiki/Maple MAPLE];
 +
# [https://ru.wikipedia.org/wiki/Mathcad MATCATH].
  
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''линейна''.
+
= Литература =
 +
[1] Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки: Пер. с англ. — М: Связь, 1979. — 744 с.
  
При этом алгоритм почти полностью детерминирован, это гарантируется теоремой о единственности разложения. Использование другого порядка выполнения ассоциативных операций может привести к накоплению ошибок округления, однако это влияние в используемых вариантах алгоритма не так велико, как, скажем, отказ от использования режима накопления.
+
[2] Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — Алгебраический аппарат квантовой информатики 2
  
Дуги информационного графа, исходящие из вершин, соответствующих операциям квадратного корня и деления, образуют пучки т. н. рассылок линейной мощности (то есть степень исхода этих вершин и мощность работы с этими данными — линейная функция от порядка матрицы и координат этих вершин). При этом естественно наличие в этих пучках «длинных» дуг. Остальные дуги локальны.  
+
[3] Kunz H.O.. On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms. IEEE Transactions on Computers. 28 (3): 267–8. [https://en.wikipedia.org/wiki/Digital_object_identifier doi]:[http://ieeexplore.ieee.org/document/1675334/ 10.1109/TC.1979.1675334]
  
Наиболее известной является компактная укладка графа — его проекция на треугольник матрицы, который перевычисляется укладываемыми операциями. При этом «длинные» дуги можно убрать, заменив более дальнюю пересылку комбинацией нескольких ближних (к соседям).
+
[4] Википедия – свободная энциклопедия [Электронный ресурс]. -  https://en.wikipedia.org/wiki/Hadamard_transform. - (дата обращения: 15.10.2016).
  
[[Глоссарий#Эквивалентное возмущение|Эквивалентное возмущение]] <math>M</math> у метода Холецкого всего вдвое больше, чем возмущение <math>\delta A</math>, вносимое в матрицу при вводе чисел в компьютер:
+
[5] Воеводин В.В.. Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
<math>
 
||M||_{E} \leq 2||\delta A||_{E}
 
</math>
 
  
Это явление обусловлено положительной определённостью матрицы. Среди всех используемых разложений матриц это наименьшее из эквивалентных возмущений.
+
[6] Воронцов К.В.. Математические методы обучения по прецедентам (теория обучения машин)

Текущая версия на 21:50, 20 ноября 2016

Symbol wait.svgЭта работа прошла предварительную проверку
Дата последней правки страницы:
20.11.2016
Данная работа соответствует формальным критериям.
Проверено Sleo.

Авторы: Бугаков Юрий (613 группа), Кужамалиев Ернур (601 группа).

Бугаков Юрий:

  • Пункты 1.1, 1.2, 1.9, 1.10, 2.1, 2.7;
  • Совместное обсуждение и работа над всей статьей в целом с другим автором.

Кужамалиев Ернур:

  • Пункты 1.3, 1.4, 1.5, 1.6, 1.7 (рисунки авториские), 1.8;
  • Совместное обсуждение и работа над всей статьей в целом с другим автором.


Построение матрицы Адамара
Последовательный алгоритм
Последовательная сложность [math]O( \left[ \frac{n}{4}\right]\,2^{2n})[/math]
Объём входных данных [math]1[/math]
Объём выходных данных [math]2^{2n}[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(1)[/math]
Ширина ярусно-параллельной формы [math]O(2^{2n})[/math]


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

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

Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков Жаком Адамаром (1865-1963). Их применение в науке и технике посвящены тысячи публикаций. Они предоставляют эффективные возможности для организации хранения, обработки и передачи информации.

Квадратная матрица Н порядка m с элементами ±1 называется матрицей Адамара, если выполняется условие

[math] H_m\,H_m^T = m\,E_m [/math]

Нетрудно заметить, что различные строки матрицы Адамара попарно ортогональны [1]. Также, можно увидеть из определения, что m четно и

[math] H_{2m} = \begin{pmatrix} H_{m} & H_{m}\\ H_{m} & -H_{m}\end{pmatrix} [/math]

С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок m матрицы Адамара при m ≥ 3 может быть лишь четным. Более того, при m ≥ 4 порядок обязан делиться на 4. До сих пор остается открытым вопрос: для любого ли m, кратного 4, существует матрица Адамара порядка m? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).

Часто матрицу Адамара нормализуют и рассматривают размерности степени 2 (например [2],[3] и [4]). В дальнейшем будем рассматривать только такие случаи. Переопределим матрицу Адамара следующим образом:

Матрица Адамара Hn - это матрица размера 2n × 2n, для которой справедливо равенство

[math]H_n = H_{1} \otimes H_{n-1}[/math],
[math]\begin{align} H_1 = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}[/math],

где [math] \otimes [/math] представляет собой тензорное произведение.

Представим некоторые частные примеры матриц Адамара:

[math] H_0 = +1, [/math]
[math] H_1 = \frac{1}{\sqrt2} \begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} [/math],
[math] H_2 = \frac{1}{2} \begin{pmatrix}\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\end{pmatrix} [/math],
[math] H_3 = \frac{1}{2^{\frac{3}{2}}} \begin{pmatrix}\begin{array}{rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1\\ 1 & 1 & 1 & -1 & -1 & -1 & -1 & -1\\ 1 & -1 & 1 & 1 & -1 & 1 & -1 & 1\\ 1 & 1 & -1 & 1 & -1 & -1 & 1 & 1\\ 1 & -1 & -1 & -1 & -1 & 1 & 1 & -1\\ \end{array}\end{pmatrix} [/math].

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

Основой алгоритма является тот факт, что любую матрицу Адамара [math]H_n[/math] размера [math]2^n\times 2^n[/math] можно вычислить поэлементно ([3], [4]):

[math]h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}[/math],

где kj и lj коэффициенты двоичного разложения чисел k и l (1 или 0):

[math]k = \sum^{n}_{i=0} {k_i 2^i} = k_{n} 2^{n} + k_{n-1} 2^{n-1} + \cdots + k_1 2 + k_0[/math]

и

[math]l = \sum^{n}_{i=0} {l_i 2^i} = l_{n} 2^{n} + l_{n-1} 2^{n-1} + \cdots + l_1 2 + l_0[/math].

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

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

Вычислительное ядро составляют вычисления элементов матрицы [math]h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}[/math].

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

Основную часть метода составляют вычисления значений степени -1 для каждого элемента:

[math]\sum_{j=0}^n k_j l_j[/math].

Как видно по формуле, получаемое значение равна количеству единиц в двоичной записи результата побитового умножения k и l. Существует эффективный метод вычисления количества единиц , сложность которого равна m операций вычитания и m операций побитового умножения, где m-искомое количество единиц.

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

Последовательность исполнения метода следующая:

1. Побитовое умножение [math]k\&l[/math];

2. Вычисление количества единиц двоичной записи;

3. Определение знака элемента по степени.

1.6 Последовательная сложность алгоритма

Для построения матрицы Адамара порядка [math]N=2^n[/math] в первом шаге потребуется [math]N^2[/math] побитовых умножений k&l. Во втором шаге, как говорилось выше, сложность метода вычисления количества единиц числа в двоичном представлении равна удвоенному количеству единиц. В наихудшем случае сложность равна [math]2log_2N[/math], при k=l=N-1, а в наилучшем 0. Для нахождения степени всех элементов матрицы потребуются [math] 2N^2\left[\frac{log_2N}{4}\right][/math] операций. В третьем шаге для определения знака потребуется [math]N^2[/math] операций, то есть сложность алгоритма [math] T(n) = 2\,(1+\left[\frac{n}{4}\right])\,2^{2n}. [/math]

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

На рисунке ниже изображен информационный граф алгоритма.

  • [math]k\&l[/math] - операция побитового умножения, где [math]k[/math] и [math]l[/math] соответствующие координаты элемента [math]h_{kl}[/math];
  • OP - вычисление количества единиц числа в двоичной системе. Состоит из последовательного применения операций вычитания и побитового умножения;
  • SGN - определение знака соответствующего элемента. Если результат предыдущего шага четное, то знак положительный, иначе отрицательный.
Рисунок 1. Граф алгоритма.
Рисунок 2. Граф OP.

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

Для построения матрицы порядка [math]N=2^n[/math] требуется последовательно выполнить следующие шаги:

  • [math]N^2[/math] вычислений побитового умножения,
  • для каждого элемента от [math]2[/math] до [math]2n[/math] операций вычитания и побитового умножения, в зависимости от результата предыдущего шага,
  • [math]N^2[/math] для определения знака значения элемента.

Таким образом для построения необходимы лишь простые операции вычитания и побитового умножения выполняемые с целыми положительными числами. Стоит заметить что вычисления для каждого элемента не зависят друг от друга. Также можно воспользоваться либо симметричностью матрицы Адамара либо закономерностью областей показанная в пункте 1.1. Таким образом, основной вклад в высотe ЯПФ вносит операция вычисления количества единиц. Ширина ЯПФ будет равна [math]O(2^{2n})[/math].

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

Входные данные: натуральное число [math] n \in \N [/math] - размерность матрицы Адамара [math]H_n[/math].

Объём входных данных: 1 (натуральное число [math] n [/math]).

Выходные данные: матрица Адамара [math]H_n[/math] размера [math]2^n\times 2^n[/math] (элементы [math]h_{ij}[/math]).

Объём выходных данных: [math]2^{2n}[/math], где [math] n [/math] - размерность матрицы Адамара. Стоит заметить, что в силу симметричности или самого определения матрицы Адамара, достаточно хранить не все элементы матрицы, а только их часть.

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

  • Соотношение последовательной и параллельной сложности:

Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Рассматривается некоторое фиксированное число процессов [math]P\in \mathbb{N}[/math]. Считается, что каждый процесс P обрабатывает не более чем [math]\left[\frac{2^{2n}}{P}\right]\geq 1[/math] элементов. Тогда качественная формула может быть записана таким образом: [math]T(n,P)=2\,(1+\left[ \frac{n}{4} \right])\,\frac{2^{2n}}{P}[/math].

Неравенство [math]\left[\frac{2^{2n}}{P}\right]\geq 1[/math] можно переписать, как [math]log_2\,\sqrt{P}\leq n[/math].

Легко увидеть, что минимум функции T(n,P) будет при максимально возможном P : [math]log_2\,\sqrt{P}\leq n[/math]. Такое P будет оптимальным числом процессов для алгоритма. В частности, для [math]P=2^p,\,p\in\mathbb{N}[/math] оптимальное [math]P = 2^{2n}[/math].

[math]\frac{T(n)}{T(n,P)}=P[/math].

То есть, отношение последовательной и параллельной сложности будет линейно зависеть от [math]P[/math];

  • Вычислительная мощность алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
[math]\,\frac{2^{2n}(2+[\frac{n}{4}])}{1+2^{2n}}\left( \sim [\frac{n}{4}],\,n\to+\infty \right)[/math];
  • Алгоритм построения матрицы Адамара является не детерминированным, так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размера 2n × 2n);
  • Степень исхода вершины информационного графа равна 1;
  • Алгоритм построения матрицы Адамара является сбалансированным. Так как количество вершин на разных процессорах одинаково, то алгоритм является сбалансированным по числу операций на каждом процессоре.

2 ЧАСТЬ Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

В простейшем варианте генерацию матрицы Адамара для нашего алгоритма можно записать так:

void adamar(int** H, int n) // N = 2^n - размерность матрицы
{     
    int i,j,N;
    float h;
    h = pow(1/2,n/2); // h - нормализующий множитель
    N = pow(2,n);

    for(i=0;i<N;++i) 
    {
	for(j=0;j<N;++j)
	{
		ij = i & j;
    		for (l=0;ij;++l) ij&=ij-1; // l - количество единиц бинарного представления ij
		if(l%2==0) H[i][j] = h;
		else H[i][j] = -h;
	}
    }
}

Также существует рекурсивная реализация метода построения матрицы Адамара

void adamar_recursion(int** H, int N, int i, int j, int h) // h - нормализующий множитель
{
    if(n==1) H[i][j] = h;
    else
    {
        adamar(H, N/2, i, j, h);
        adamar(H, N/2, i, N/2+j, h);
        adamar(H, N/2, N/2+i, j, h);
        adamar(H, N/2, N/2+i, N/2+j, -h);
    }
}

Или эквивалентный безрекурсивный вариант:

void adamar_not_recursion(int** H, int n) // N = 2^n - размерность матрицы
{     
    int i,j,N;
    float h;
    h = pow(1/2,n/2);
    N = pow(2,n);
    k=2;
    H[0][0] = h;
	
    while(k<=N)
    {
	for (i=0; i<k; ++i)
	{
		for (j=0; j<k; ++j)
		{
			if (i<k/2 && j<k/2)
			{
			}
			else
			{
				if(i>=k/2 && j>=k/2)
				{
					H[i][j] = -(H[i-k/2][j-k/2]);
				}
				else
				{
					if (i>j)
					{
						H[i][j] = H[i-k/2][j];
					}
					else
					{
						H[i][j] = H[i][j-k/2];
					}
				}
			}
		}
	}
		
        k=k*2;
    }
}

Для данного случая, рекурсия является менее эффективной для генерации матрицы Адамара (Хабрахабр. О бедной рекурсии замолвите слово, или всё, что вы не знали и не хотите о ней знать.). С точки зрения последовательной реализации, генерация матрицы Адамара с помощью adamar_not_recursion будет выигрывать у adamar, так как adamar_not_recursion будет выполнять меньшее количество операций. С точки зрения параллельной реализации adamar имеет 100% парализацию и при определенных условиях будет выигрывать по времени у распараллелинной adamar_not_recursion (пусть в adamar и будет выполняться большее количество операций, но они являются битовыми операциями).

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

Исследование проводилось на суперкомпьютере "Blue Gene".

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

  • число процессоров [1, 2, 4, 8,..., 1024] ;
  • размер матрицы [2, 4, 8,..., 2048].

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

  • минимальная эффективность реализации 0.0121%;
  • максимальная эффективность реализации 3.3003%.

На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.

Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.
Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.

Построим оценки масштабируемости выбранной реализации:

  • При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.
  • При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени [math]n[/math] размера матрицы [math]N=2^{n}[/math]. При увеличении размера матрицы эффективность также увеличивается, но скорость возрастания уменьшается.

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

Примеры вычислительных пакетов, содержащих функции генерации матриц Адамара:

  1. MATLAB;
  2. WOLFRAM;
  3. Python;
  4. Octave.

Стоит отметить, что во многих вычислительных пакетах встроена операция тензорного произведения матриц, которая позволяет строить матрицу Адамара по определению. Этот факт позволяет использовать матрицу Адамара в этих вычислительных пакетах:

  1. MAPLE;
  2. MATCATH.

3 Литература

[1] Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки: Пер. с англ. — М: Связь, 1979. — 744 с.

[2] Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — Алгебраический аппарат квантовой информатики 2

[3] Kunz H.O.. On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms. IEEE Transactions on Computers. 28 (3): 267–8. doi:10.1109/TC.1979.1675334

[4] Википедия – свободная энциклопедия [Электронный ресурс]. - https://en.wikipedia.org/wiki/Hadamard_transform. - (дата обращения: 15.10.2016).

[5] Воеводин В.В.. Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[6] Воронцов К.В.. Математические методы обучения по прецедентам (теория обучения машин)