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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 45 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Свойства и структура алгоритма ==
+
{{Assignment|Sleo}}
 +
Авторы: [[U:Бугаков Юрий|Бугаков Юрий]] (613 группа), Кужамалиев Ернур (601 группа).
  
=== Общее описание алгоритма ===
+
Бугаков Юрий:
  
 +
* Пункты 1.1, 1.2, 1.9, 1.10, 2.1, 2.7;
 +
* Совместное обсуждение и работа над всей статьей в целом с другим автором.
  
 +
Кужамалиев Ернур:
  
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков Жаком Адамаром (1865-1963). Их применение в науке и технике посвящены тысячи публикаций. Они предоставляют эффективные возможности для организации хранения, обработки и передачи информации.
+
* Пункты 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>
 +
}}
  
Квадратная матрица Н порядка ''n'' с элементами ±1 называется матрицей Адамара, если выполняется условие
+
== Свойства и структура алгоритма ==
  
:<math> H_n\,H_n^T = n\,E_n </math>
+
=== Общее описание алгоритма ===
  
Нетрудно показать, что различные строки матрицы Адамара попарно ортогональны. Также можно увидеть из определения, что n четно и любые две строки совпадают ровно в n/2 позициях и различаются в остальных.
+
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков [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)]. Их применение в науке и технике посвящены тысячи публикаций. Они предоставляют эффективные возможности для организации хранения, обработки и передачи информации.
  
Матрицу Адамара можно определить эквивалентным образом:
+
Квадратная матрица Н порядка ''m'' с элементами ±1 называется матрицей Адамара, если выполняется условие
  
:<math>
+
:<math> H_m\,H_m^T = m\,E_m </math>
H_{n} = H_1\otimes H_{n-1}
 
</math>
 
  
 +
Нетрудно заметить, что различные строки матрицы Адамара попарно ортогональны [1]. Также, можно увидеть из определения, что m четно и
 
:<math>
 
:<math>
\begin{align}
+
H_{2m} =
  H_1 =
 
  &\begin{pmatrix}\begin{array}{rr}
 
    1 & 1\\
 
    1 & -1
 
  \end{array}\end{pmatrix}
 
\end{align}
 
</math>
 
где <math> \otimes </math> представляет собой тензорное произведение, то есть
 
 
 
:<math>
 
H_{n} =
 
 
\begin{pmatrix}
 
\begin{pmatrix}
H_{n-1} &  H_{n-1}\\
+
H_{m} &  H_{m}\\
H_{n-1} & -H_{n-1}\end{pmatrix}
+
H_{m} & -H_{m}\end{pmatrix}
 
</math>
 
</math>
  
:<math>
+
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок ''m'' матрицы Адамара при ''m'' ≥ 3 может быть лишь четным. Более того, при ''m'' ≥ 4 порядок обязан делиться на 4. До сих пор остается открытым вопрос: для любого ли ''m'', кратного 4, существует матрица Адамара порядка m? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
\begin{align}
 
  H_1 =
 
  &\begin{pmatrix}\begin{array}{rr}
 
    1 & 1\\
 
    1 & -1
 
  \end{array}\end{pmatrix}
 
\end{align}
 
</math>
 
  
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок n матрицы Адамара при n ≥ 3 может быть лишь четным. Более того, при n ≥ 4 порядок обязан делиться на 4. До сих пор остается открытым вопрос: для любого ли n, кратного 4, существует матрица Адамара порядка n? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
+
Часто матрицу Адамара нормализуют и рассматривают размерности степени 2 (например [2],[3] и [4]). В дальнейшем будем рассматривать только такие случаи. Переопределим матрицу Адамара следующим образом:
  
Часто размерность матрицы Адамара считают равной степени 2 и нормализируют её. Определение принимает следующий вид:
+
'''Матрица Адамара ''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}
Строка 61: Строка 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>. Для этого представим порядковые номера ''k'' и ''l'' элемента <math>h_{kl}</math> в виде двоичного разложения
+
:<math>
 +
    H_0 = +1,
 +
</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>
+
:<math>
 
 
и
 
: <math>l = \sum^{m-1}_{i=0} {l_i 2^i} = l_{m-1} 2^{m-1} + l_{m-2} 2^{m-2} + \cdots + l_1 2 + l_0</math>
 
 
 
где ''k''<sub>''j''</sub> и ''l''<sub>''j''</sub> коэффициенты двоичного разложения чисел ''k'' и ''l'' (1 или 0).
 
 
 
Тогда каждый элемент матрицы Адамара <math>H_n</math> имеет вид
 
:<math>h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}</math>
 
 
 
Представим некоторые частные примеры матриц Адамара:
 
:<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>,
:<math>\begin{align}
+
 
 +
:<math>
 
   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}
\end{align}</math>
+
</math>.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
  
Исходные данные: положительно определённая симметрическая матрица <math>A</math> (элементы <math>a_{ij}</math>).
+
Основой алгоритма является тот факт, что любую матрицу Адамара <math>H_n</math> размера <math>2^n\times 2^n</math> можно вычислить поэлементно ([3], [4]):
  
Вычисляемые данные: нижняя треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>).
+
:<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>
 
\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>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>\frac{1}{l_{ii}}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</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>.
 +
 
 +
Помимо этой формулы чаще всего используется заполнение по определению. В связи с трудностями распараллеливания и постоянного выделения памяти при каждом шаге рекурсивного вызова этого метода, был выбран предыдущий способ вычисления.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 131: Строка 112:
 
Вычислительное ядро составляют вычисления элементов матрицы <math>h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}</math>.
 
Вычислительное ядро составляют вычисления элементов матрицы <math>h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}</math>.
  
Помимо этой формулы чаще всего используется метод тензорного произведения. Но в связи с трудностями распараллеливания и постоянного выделения памяти при каждом шаге рекурсивного вызова, мы решили выбрать первый способ вычисления
+
=== Макроструктура алгоритма ===
  
=== Макроструктура алгоритма ===
+
Основную часть метода составляют вычисления значений степени -1 для каждого элемента:
  
Как записано выше основную часть метода составляют множественные вычисления элементов
+
: <math>\sum_{j=0}^n k_j l_j</math>.
  
: <math>h_{k,l} = \frac{1}{2^\frac{n}{2}} (-1)^{\sum_j k_j l_j}</math>.
+
Как видно по формуле, получаемое значение равна количеству единиц в двоичной записи результата побитового умножения ''k'' и ''l''. Существует эффективный метод вычисления количества единиц , сложность которого равна ''m'' операций вычитания и ''m'' операций побитового умножения, где ''m''-искомое количество единиц.
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
Строка 143: Строка 124:
 
Последовательность исполнения метода следующая:
 
Последовательность исполнения метода следующая:
  
1. <math>l_{11}= \sqrt{a_{11}}</math>
+
1. Побитовое умножение <math>k\&l</math>
 +
 
 +
2. Вычисление количества единиц двоичной записи;
  
2. <math>l_{j1}= \frac{a_{j1}}{l_{11}}</math> (при <math>j</math> от <math>2</math> до <math>n</math>).
+
3. Определение знака элемента по степени.
  
Далее для всех <math>i</math> от <math>2</math> до <math>n</math> по нарастанию выполняются
+
=== Последовательная сложность алгоритма ===
  
3. <math>l_{ii} = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}</math> и
+
Для построения матрицы Адамара порядка <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>
  
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>).
+
=== Информационный граф ===
  
После этого (если <math>i < n</math>) происходит переход к шагу 3 с бо́льшим <math>i</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>.
+
*<math>k\&l</math> - операция побитового умножения, где <math>k</math> и <math>l</math> соответствующие координаты элемента <math>h_{kl}</math>;
 +
* OP - вычисление количества единиц числа в двоичной системе. Состоит из последовательного применения операций вычитания и побитового умножения;
 +
* SGN - определение знака соответствующего элемента. Если результат предыдущего шага четное, то знак положительный, иначе отрицательный.
  
=== Последовательная сложность алгоритма ===
+
[[file:Hadamar.png|thumb|center|1400px|Рисунок 1. Граф алгоритма.]]
 +
[[file:OP3.png|thumb|center|1400px|Рисунок 2. Граф OP.]]
  
Для разложения матрицы порядка 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> умножений.
 
  
Умножения и сложения (вычитания) составляют ''основную часть алгоритма''.
+
Для построения матрицы порядка <math>N=2^n</math> требуется последовательно выполнить следующие шаги:
 +
* <math>N^2</math>  вычислений побитового умножения,
 +
* для каждого элемента от <math>2</math> до <math>2n</math> операций вычитания и побитового умножения, в зависимости от результата предыдущего шага,
 +
* <math>N^2</math>  для определения знака значения элемента.
 
   
 
   
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.
+
Таким образом для построения необходимы лишь простые операции вычитания и побитового умножения выполняемые с целыми положительными числами. Стоит заметить что вычисления для каждого элемента не зависят друг от друга. Также можно воспользоваться либо симметричностью матрицы Адамара либо закономерностью областей показанная в пункте 1.1.
 +
Таким образом, основной вклад в высотe ЯПФ вносит операция вычисления количества единиц. Ширина ЯПФ будет равна <math>O(2^{2n})</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>).
 +
 
 +
'''Объём выходных данных''': <math>2^{2n}</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>.
 +
 
 +
Неравенство <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, которое формирует матрицу размера 2<sup>''n''</sup>&nbsp;&times;&nbsp;2<sup>''n''</sup>);
 +
 
 +
* Степень исхода вершины информационного графа равна 1;
 +
 
 +
* Алгоритм построения матрицы Адамара является ''сбалансированным''. Так как количество вершин на разных процессорах одинаково, то алгоритм является сбалансированным по числу операций на каждом процессоре.
  
При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам ''с кубической сложностью''.
+
=ЧАСТЬ Программная реализация алгоритма =
  
=== Информационный граф ===
+
== Особенности реализации последовательного алгоритма ==
  
Опишем [[глоссарий#Граф алгоритма|граф алгоритма]]<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);
  
'''Первая''' группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию SQRT.
+
    for(i=0;i<N;++i)
Единственная координата каждой из вершин <math>i</math> меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.
+
    {
 +
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>
  
Аргумент этой функции
+
Также существует рекурсивная реализация метода построения матрицы Адамара
 
* при <math>i = 1</math> — элемент ''входных данных'', а именно  <math>a_{11}</math>;
 
* при <math>i > 1</math> — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами <math>i - 1</math>, <math>i</math>, <math>i - 1</math>.
 
Результат срабатывания операции является ''выходным данным'' <math>l_{ii}</math>.
 
  
'''Вторая''' группа вершин расположена в двумерной области, соответствующая ей операция <math>a / b</math>.
+
<source lang="C">
Естественно введённые координаты области таковы:
+
void adamar_recursion(int** H, int N, int i, int j, int h) // h - нормализующий множитель
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>n-1</math>, принимая все целочисленные значения;
+
{
* <math>j</math> — меняется в диапазоне от <math>i+1</math> до <math>n</math>, принимая все целочисленные значения.
+
    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);
 +
    }
 +
}
 +
</source>
  
Аргументы операции следующие:
+
Или эквивалентный безрекурсивный вариант:
*<math>a</math>:
 
** при <math>i = 1</math> — элементы ''входных данных'', а именно <math>a_{j1}</math>;
 
** при <math>i > 1</math> — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами <math>i - 1, j, i - 1</math>;
 
* <math>b</math> — результат срабатывания операции, соответствующей вершине из первой группы, с координатой <math>i</math>.
 
  
Результат срабатывания операции является ''выходным данным'' <math>l_{ji}</math>.
+
<source lang="C">
 +
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;
 +
    }
 +
}
 +
</source>
  
'''Третья''' группа вершин расположена в трёхмерной области, соответствующая ей операция  <math>a - b * c</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>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>;
 
  
Результат срабатывания операции является ''промежуточным данным'' алгоритма.
+
== Возможные способы и особенности параллельной реализации алгоритма ==
  
Описанный граф можно посмотреть на рис.1 и рис.2, выполненных для случая <math>n = 4</math>. Здесь вершины первой группы обозначены жёлтым цветом и буквосочетанием sq, вершины второй — зелёным цветом и знаком деления, третьей — красным цветом и буквой f. Вершины, соответствующие операциям, производящим выходные данные алгоритма, выполнены более крупно. Дублирующие друг друга дуги даны как одна. На рис.1 показан граф алгоритма согласно классическому определению , на рис.2 к графу алгоритма добавлены вершины , соответствующие входным (обозначены синим цветом) и выходным (обозначены розовым цветом) данным.
+
== Масштабируемость алгоритма и его реализации ==
 +
Исследование проводилось на суперкомпьютере "Blue Gene".
  
[[file:Cholesky full.png|thumb|center|1400px|Рисунок 1. Граф алгоритма без отображения входных и выходных данных. SQ - вычисление квадратного корня, F - операция a-bc, Div - деление.]]
+
Набор и границы значений изменяемых  параметров запуска реализации алгоритма:  
[[file:Cholesky full_in_out.png|thumb|center|1400px|Рисунок 2. Граф алгоритма с отображением входных и выходных данных. SQ - вычисление квадратного корня, F - операция a-bc, Div - деление, In - входные данные, Out - результаты.]]
 
  
=== Ресурс параллелизма алгоритма ===
+
* число процессоров [1, 2, 4, 8,..., 1024] ;
 +
* размер матрицы [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] Воронцов К.В.. Математические методы обучения по прецедентам (теория обучения машин)