Пример 1. Скалярное произведение векторов.

For I = 1 to N do

X(i) = X(i)+A(i)*B(i)

Вычисление содержит 2*N чтений из памяти и 2*N арифметических операций (сложений и умножений).

T = (N/M) * (C₁ * M + C₂ * M/p) = N * (C₁ + C₂/p)

M – объем кэш памяти

n = M/2 длина части векторов, которые размещается в кэш памяти.

 C₂ * M/p = C₂ *2*n/p время выполнения скалярного произведения частей векторов в кэш памяти на p процессорах

N/M – количество частей, на которые делятся данные для закачивания в кэш память.

C₁ * M – время закачивания части матрицы из оперативной памяти в кэш.

Увеличение количества процессоров ведет к увеличению быстродействия, хотя, при C₁ > C₂ = 15, это увеличение незначительно. Объем кэш памяти должен быть достаточен для загрузки процессорных ядер, а большее увеличение объема кэш-памяти бесполезно.

Конвейерное вычисление (одновременное выполнение операций чтения данных и арифметических операций).

Рассмотрим модель вычислений, при которой, как только в кэш память попадают первые части векторов, они сразу же перемножаются, а в это же время закачиваются следующие части векторов. В этом случае, поскольку на современных процессорах C₁ >> C₂ , время работы равно

T = N * C₁

Время выполнения программы не зависит от объема кэш памяти и лучшее быстродействие достигается на одном процессоре.

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

Стандартный алгоритм сводится к n² алгоритмам вычисления скалярного произведения векторов длины n. Если L – длина кэш линейки, то обращений к памяти порядка n³ / L.

Время выполнения программы не зависит от объема кэш памяти и от количества процессоров.

В данном примере в кэш память попадают строка (или часть строки) матрицы A и столбец (часть столбца) матрицы B – 2*n чисел. С ними выполняется n умножений и n-1 сложений – всего тоже 2*n операций. Следовательно, если время выполнения арифметической операции в 15 раз быстрее считывания данных из оперативной памяти в кэш память, то процессор загружен на 1/15 часть своей мощности.

Сложность (по количеству арифметических операций) всего алгоритма равна O(n³), где n – размерность матрицы, или, O((N/2)^3/2), где N – количество входных данных (N – количество элементов двух матриц размера n²). А сложность части алгоритма, которая выполняется в кэш памяти, равна O(N).

Таким образом, исходный алгоритм неэффективно разрезан на части.

Алгоритмы, увеличение быстродействия которых зависит от объема кэш памяти и не зависит от количества процессоров.

Пример 2. Сортировка.

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

T = (n/M) * (C₁ *M + C₂ * M*log(M)/p) + C₃ *(n/M)*log(n/M) = n * (C₁ + C₂ * log(M)/p) + C₃ *(n/M)*log(n/M) =

= n * (C₁ + C₂ * P₀ *log M / (S – M) ) + C₃ *(n/M)*log(n/M) 

M – часть исходного массива, которая сортируется в кэш памяти.

(n/M) – количество частей исходного массива, которые сортируются в кэш памяти.

C₁ *M – время закачки части массива объема M в кэш память.

C₂ * M*log(M)/p – время сортировки порции (части) данных в кэш памяти.

C₃ * (n/M)*log(n/M) – время слияния частей.

Получить формулу оптимального соотношения величины объема M кэш памяти и количества процессоров затруднительно. Такое оптимальное соотношение легко вычислить на компьютере перебором всех возможных значений количества процессоров p. При больших n второе слагаемое становится существенно больше первого и определяет время работы всего алгоритма. Второе слагаемое убывает с ростом M . Поэтому, для задачи сортировки больших массивов, чем больше кэш память, тем быстрее эта задача выполняется и следует на кристалле иметь только один процессор.