|
|
| (не показано 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]]
| |
| − | | |
| − | === Возможные способы и особенности реализации параллельного алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | ==== Описание масштабируемости алгоритма ====
| |
| − | ==== Описание масштабируемости реализации алгоритма ====
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
