|
|
| (не показано 12 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| == Описание свойств и структуры алгоритма ==
| | {{level-p}} |
| === Общее описание алгоритма ===
| |
| === Математическое описание ===
| |
| === Вычислительное ядро алгоритма ===
| |
| === Макроструктура алгоритма ===
| |
| === Описание схемы реализации последовательного алгоритма ===
| |
| === Последовательная сложность алгоритма ===
| |
| === Информационный граф ===
| |
| === Описание ресурса параллелизма алгоритма ===
| |
| === Описание входных и выходных данных ===
| |
| === Свойства алгоритма ===
| |
| == Программная реализация ==
| |
| === Особенности реализации последовательного алгоритма ===
| |
| === Описание локальности данных и вычислений ===
| |
| ==== Описание локальности алгоритма ====
| |
| ==== Описание локальности реализации алгоритма ====
| |
| ===== Описание структуры обращений в память и качественная оценка локальности =====
| |
|
| |
|
| [[file:mv mult 1.PNG|thumb|center|700px|Рисунок 12.1. Умножение плотной матрицы на вектор. Общий профиль обращений в память]]
| | '''Умножение матрицы на вектор''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. |
| | Здесь мы рассмотрим умножение <math>y = Ax</math> плотной неособенной матрицы на вектор<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>, то есть тот вариант, где никак не может использоваться специальный вид матрицы или вектора. |
|
| |
|
| На рисунке 12.1 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.
| | Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), умножаемый на неё вектор <math>x</math> (элементы <math>x_{i}</math>). |
|
| |
|
| Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:
| | Вычисляемые данные: вектор решения <math>y</math> (элементы <math>y_{i}</math>). |
| <source lang="C"> | |
| for(int i = 0; i < size; i++)
| |
| for(int j = 0; j < size; j++)
| |
| vec_out[i] += matrix[i][j] * vec_in[j];
| |
| </source> | |
|
| |
|
| Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.
| | Формулы: |
| | :<math> |
| | \begin{align} |
| | y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}, \quad i \in [1, m]. |
| | \end{align} |
| | </math> |
|
| |
|
| Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора), однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.
| | [[Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант)]] - классический вариант алгоритма, решающего данную задачу. |
|
| |
|
| ===== Количественная оценка локальности ===== | | = Литература = |
| | |
| Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
| |
| | |
| На рисунке 12.2 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность данной программы очень высока, даже немного выше, чем производительность теста Linpack. Одна из основных причин этому – очень высокая локальность обращений к векторам.
| |
| | |
| [[file:mv mult daps ru.PNG|thumb|center|700px|Рисунок 12.2. Сравнение значений оценки daps]]
| |
| | |
| Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
| |
| | |
| На рисунке 12.3 значения приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации умножения матрицы на вектор высока, хотя и не среди первых значений. Однако можно заметить, что полученное значение лишь совсем немного ниже оценки cvg для, например, реализации метода Гаусса или лучших вариантов перемножения матрицы.
| |
| | |
| [[file:mv mult cvg.PNG|thumb|center|700px|Рисунок 12.3. Сравнение значений оценки cvg]]
| |
| | |
| === Возможные способы и особенности реализации параллельного алгоритма ===
| |
| === Масштабируемость алгоритма и его реализации ===
| |
| ==== Описание масштабируемости алгоритма ====
| |
| ==== Описание масштабируемости реализации алгоритма ====
| |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
| === Выводы для классов архитектур ===
| |
| === Существующие реализации алгоритма ===
| |
Умножение матрицы на вектор - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
Здесь мы рассмотрим умножение [math]\displaystyle{ y = Ax }[/math] плотной неособенной матрицы на вектор[1], то есть тот вариант, где никак не может использоваться специальный вид матрицы или вектора.
Исходные данные: плотная матрица [math]\displaystyle{ A }[/math] (элементы [math]\displaystyle{ a_{ij} }[/math]), умножаемый на неё вектор [math]\displaystyle{ x }[/math] (элементы [math]\displaystyle{ x_{i} }[/math]).
Вычисляемые данные: вектор решения [math]\displaystyle{ y }[/math] (элементы [math]\displaystyle{ y_{i} }[/math]).
Формулы:
- [math]\displaystyle{
\begin{align}
y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}, \quad i \in [1, m].
\end{align}
}[/math]
Умножение плотной неособенной матрицы на вектор (последовательный вещественный вариант) - классический вариант алгоритма, решающего данную задачу.
Литература
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
