Пример 1. Скалярное произведение векторов.
For I = 1 to N do
X(i) = X(i)+A(i)*B(i)
Вычисление содержит 2*N чтений из памяти и 2*N арифметических операций (сложений и умножений).
T = (N/M) * (C1 * M + C2 * M/p) = N * (C1 + C2/p)
M – объем кэш памяти
n = M/2 длина части векторов, которые размещается в кэш памяти.
C2 * M/p = C2 *2*n/p время выполнения скалярного произведения частей векторов в кэш памяти на p процессорах
N/M – количество частей, на которые делятся данные для закачивания в кэш память.
C1 * M – время закачивания части матрицы из оперативной памяти в кэш.
Увеличение количества процессоров ведет к увеличению быстродействия, хотя, при C1 > C2 = 15, это увеличение незначительно. Объем кэш памяти должен быть достаточен для загрузки процессорных ядер, а большее увеличение объема кэш-памяти бесполезно.
Конвейерное вычисление (одновременное выполнение операций чтения данных и арифметических операций).
Рассмотрим модель вычислений, при которой, как только в кэш память попадают первые части векторов, они сразу же перемножаются, а в это же время закачиваются следующие части векторов. В этом случае, поскольку на современных процессорах C1 >> C2 , время работы равно
T = N * C1
Время выполнения программы не зависит от объема кэш памяти и лучшее быстродействие достигается на одном процессоре.
Пример 1а. Стандартное перемножение квадратных матриц размера n.
For i = 1 to N do
For j = 1 to N do
For k = 1 to N do
C(i,j) = C(i,j)+A(i,k)*B(k,j)
Стандартный алгоритм сводится к n2 алгоритмам вычисления скалярного произведения векторов длины n. Если L – длина кэш линейки, то обращений к памяти порядка n3 / L.
Время выполнения программы не зависит от объема кэш памяти и от количества процессоров.
В данном примере в кэш память попадают строка (или часть строки) матрицы A и столбец (часть столбца) матрицы B – 2*n чисел. С ними выполняется n умножений и n-1 сложений – всего тоже 2*n операций. Следовательно, если время выполнения арифметической операции в 15 раз быстрее считывания данных из оперативной памяти в кэш память, то процессор загружен на 1/15 часть своей мощности.
Сложность (по количеству арифметических операций) всего алгоритма равна O(n3), где n – размерность матрицы, или, O((N/2)3/2), где N – количество входных данных (N – количество элементов двух матриц размера n2). А сложность части алгоритма, которая выполняется в кэш памяти, равна O(N).
Таким образом, исходный алгоритм неэффективно разрезан на части.
Алгоритмы, увеличение быстродействия которых зависит от объема кэш памяти и не зависит от количества процессоров.
Пример 2. Сортировка.
Имеет смысл использовать следующий алгоритм. Сортируемый массив нарезается на части, которые могут поместиться в кэш памяти. Для сортировки этих частей используется алгоритм, требующий мало дополнительной памяти (квиксорт), чтобы не выходить за пределы кэш памяти. Затем, отсортированные части массива сливаются (сортировка слиянием).
T = (n/M) * (C1 *M + C2 * M*log(M)/p) + C3 *(n/M)*log(n/M) = n * (C1 + C2 * log(M)/p) + C3 *(n/M)*log(n/M) =
= n * (C1 + C2 * P0 *log M / (S – M) ) + C3 *(n/M)*log(n/M)
M – часть исходного массива, которая сортируется в кэш памяти.
(n/M) – количество частей исходного массива, которые сортируются в кэш памяти.
C1 *M – время закачки части массива объема M в кэш память.
C2 * M*log(M)/p – время сортировки порции (части) данных в кэш памяти.
C3 * (n/M)*log(n/M) – время слияния частей.
Получить формулу оптимального соотношения величины объема M кэш памяти и количества процессоров затруднительно. Такое оптимальное соотношение легко вычислить на компьютере перебором всех возможных значений количества процессоров p. При больших n второе слагаемое становится существенно больше первого и определяет время работы всего алгоритма. Второе слагаемое убывает с ростом M . Поэтому, для задачи сортировки больших массивов, чем больше кэш память, тем быстрее эта задача выполняется и следует на кристалле иметь только один процессор.
Дата: 2018-12-21, просмотров: 425.