Правильный способ преобразования заблокированной матрицы - это не то, что есть в вашей программе. Дополнительные массивы temp1 и temp2 будут бесполезно заполнять ваш кеш. И ваша вторая версия неверна. Чем больше вы выполняете слишком много операций: элементы транспонируются дважды, а диагональные элементы «транспонируются».
Но сначала мы можем сделать простой (и приблизительный) анализ поведения кэша. Я предполагаю, что у вас есть матрица значений типа double, а строки кэша занимают 64 байта (8 значений типа double).
Блокированная реализация эквивалентна наивной реализации, если кэш может полностью содержать матрицу. У вас есть только обязательные пропуски кэша для выборки элементов матрицы. Число пропусков в кеше будет N & times; N / 8 для обработки N & times; N элементов, со средним числом пропусков 1/8 на элемент.
Теперь, для наивной реализации, посмотрите на ситуацию после того, как вы обработали 1 строку в кэше. Предполагая, что ваш кеш достаточно большой, вы будете иметь в своем кеше:
* полная строка A [0] [i]
* первые 8 элементов всех остальных строк матрицы A [i] [0..7]
Это означает, что, если ваш кеш достаточно большой, вы можете обработать 7 последовательных строк без каких-либо промахов кэша, кроме той, которая извлекает строки. Таким образом, если ваша матрица N & times; N, если размер кэша больше чем ~ 2 & times; N & times; 8, у вас будет только 8 & times; N / 8 (строки) + N (столбцы) = 2N пропуски кэша для обработки 8 & times; N элементов, и среднее количество промахов на элемент составляет 1/4. Численно, если размер кэша L1 равен 32 КБ, это произойдет, если N <2 КБ. И если кэш L2 равен 256 КБ, данные останутся в кэше L 2, если N <16 КБ. Я не думаю, что разница между данными в L1 и данными в L2 будет действительно заметна благодаря очень эффективной предварительной выборке в современных процессорах. </p>
Если у вас очень большая матрица, после конца первой строки начало второй строки было извлечено из кэша. Это произойдет, если строка вашей матрицы полностью заполнит кеш. В этой ситуации количество пропущенных кешей будет гораздо важнее. Каждая строка будет иметь N / 8 (чтобы получить строку) + N (чтобы получить первые элементы столбцов) кэш-промахов, и в среднем будет (9 & times; N / 8) / N & приблизительно 1 промах на элемент.
Таким образом, вы можете получить выигрыш при заблокированной реализации, но только для больших матриц.
Вот правильная реализация транспонирования матрицы. Это позволяет избежать двойной обработки элемента A [l] [m] (когда i = l и j = m или i = m и j = l), не транспонировать диагональные элементы и использует регистры для транспонирования.
Наивная версия
for (i=0;i<N;i++)
for (j=i+1;j<N;j++)
{
temp=A[i][j];
A[i][j]=A[j][i];
A[j][i]=temp;
}
И заблокированная версия (мы предполагаем, что размер матрицы кратен размеру блока)
for (ii=0;ii<N;ii+=block)
for (jj=0;jj<N;jj+=block)
for (i=ii;i<ii+block;i++)
for (j=jj+i+1;j<jj+block;j++)
{
temp=A[i][j];
A[i][j]=A[j][i];
A[j][i]=temp;
}