Алгоритмы, для которых увеличение кэш памяти и количества вычислительных ядер не дают ускорения
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Пример 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.