Равномерная норма вектора, вещественная версия, последовательный вариант

Материал из Алговики
Перейти к: навигация, поиск

Содержание

1 Описание свойств и структуры алгоритма

1.1 Словесное описание алгоритма

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

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

Исходные данные: одномерный массив [math]n[/math] чисел. Вычисляемые данные: максимум абсолютной величины элементов массива. Формулы метода: для вектора [math]\vec{a}[/math] из [math]n[/math] элементов вычисляется выражение [math]\max\limits_i |a_i|[/math].

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

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

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

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

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

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

Формулы метода описаны выше. Последовательность исполнения может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

Для вычисления равномерной нормы массива, состоящего из [math]N[/math] элементов, количество операций вычисления модуля неизменно и равно [math]N[/math], а количество операций вычисления максимума равно [math]N-1[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

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

Опишем граф алгоритма в виде рисунка. Изображен граф для случая [math]n = 6[/math].

Вычисление с нормы вектора с экономией вызовов функции максимума

Однако следует отметить, что в большинстве случаев программисты не экономят на одном вызове функции максимума, а инициализируют начальное значение переменной нулём. В этом случае граф становится таким, как на втором рисунке ([math]n = 6[/math]).

Упрощенная реализация вычисления нормы вектора

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

Последовательный вариант вычисления равномерной нормы массива, несмотря на название, имеет ресурс параллелизма степени 2. Дело в том, что, если рассматривать отдельно вычисления модуля и максимума, то видно, что при выполнении очередного выбора максимума «подготовительное» отбрасывание знака к следующему можно выполнить заранее. В принципе, можно, если использовать дополнительную память для хранения всех модулей, вообще выполнить все отбрасывания знаков параллельно, а потом последовательно выполнить выбор максимального из вычисленных абсолютных величин. Таким образом, в получившемся алгоритме высота параллельной формы будет равна 1 операции вычисления функции ABS плюс [math]N-1[/math] операций выбора максимума. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности как по высоте, так и по ширине параллельной формы. Однако если мы будем последовательно выполнять и вычисления абсолютных величин, то ширина параллельной формы может быть уменьшена до 2, что даёт нам постоянную сложность по ширине параллельной формы.

1.9 Описание входных и выходных данных

Входные данные: массив [math]a[/math] (элементы [math]a_i[/math]).

Дополнительные ограничения: отсутствуют.

Объём входных данных: [math]n[/math].

Выходные данные: максимум модулей элементов массива.

Объём выходных данных: один скаляр.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является константой (2). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных почти столько же, сколько операций; если точнее — даже больше на 2). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. Важной особенностью алгоритма является то, что его видоизменение и переход к другому графу никак не повлияет на ошибки округления результата, поскольку функция максимума, в отличие от базовой арифметики (сложения и умножения) остаётся ассоциативной и в условиях действия машинного округления.

2 Программная реализация

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

В простейшем (входные данные — вектор) варианте на Фортране можно записать так:

	NORMX = ABS(A(1))
	DO I = 2,N
		NORMX = MAX( NORMX, ABS(A(I)) )
	END DO

В варианте с «холостым» выбором максимума запись такая:

	NORMX = 0.
	DO I = 1,N
		NORMX = MAX( NORMX, ABS(A(I)) )
	END DO

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

2.2.1 Описание локальности алгоритма

2.2.2 Описание локальности реализации алгоритма

2.2.2.1 Описание структуры обращений в память и качественная оценка локальности
2.2.2.2 Количественная оценка локальности
2.2.2.3 Анализ на основе теста Apex-Map

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

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

2.4.1 Описание масштабируемости алгоритма

2.4.2 Описание масштабируемости реализации алгоритма

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

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

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

Помимо выписанных выше простейших реализаций, существуют более сложные коды, реализующие тот же алгоритм. Это объясняется тем, что порой чисто программистскими приёмами оптимизируют работу с регистрами, с кэшем и т. п. В частности, даже в Линпаке есть разные реализации кода — из BLAS или другие варианты. Большинство их сводится к сведению одинарного цикла длиной [math]n[/math] к двойному циклу либо к одинарному с меньшим числом итераций, но более длинной операцией в теле цикла. Между тем, разбиения циклов на группы могут быть полезны и для лучшего использования кэша на отдельных узлах, когда самих равномерных норм вычисляется сразу много и распараллеливание программы состоит в их распределении между узлами.