|
|
| (не показано 10 промежуточных версий 2 участников) |
| Строка 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]]
| |
| − | | |
| − | === Возможные способы и особенности реализации параллельного алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | ==== Описание масштабируемости алгоритма ====
| |
| − | ==== Описание масштабируемости реализации алгоритма ====
| |
| − | [[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рисунок 1. Параллельная реализация произведения матриц Максимальная производительность. ]]
| |
| − | [[file:Масштабируемость перемножения матрицы на вектор эффективность.png|thumb|center|700px|Рисунок 2. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
| |
| − | Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
| |
| − | * число процессоров [4 : 1024]
| |
| − | * размерность матрицы [1024 : 20480]
| |
| − | Эффективность выполнения реализации алгоритма
| |
| − | * Минимальная эффективность 4,71%
| |
| − | * Максимальная эффективность 31,72%
| |
| − | Оценка масштабируемости
| |
| − | * По числу процессов: -0.0436 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
| |
| − | * По размеру задачи: -0.0255 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
| |
| − | * По двум направлениям: -0.000968 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 25% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.
| |
| − | | |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
