Последовательный обход памяти

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

float A[N][N];

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

┘

A0,0

A0,1

A0,2

┘

A0,N-1

A1,0

A1,1

A1,2

┘

A1,N-1

┘

AN-1,0

AN-1,1

AN-1,2

┘

AN-1,N-1

┘

Получается два варианта перебора элементов массива:

Быстро: for (i=0;i<N;i++) for (j=0;j<N;j++) A[i][j]=x;

Медленно: for (j=0;j<N;j++) for (i=0;i<N;i++) A[i][j]=x;

В -ортране многомерные массивы располагаются в памяти по столбцам, поэтому циклы по i и по j в -ортране следовало бы поменять местами. Почти любой произвольный обход элементов в памяти, отличный от последовательного, будет работать медленнее. Тот непоследовательный обход, который работает быстрее, является архитектурно зависимым, и для общего случая трудно применим.

Рассмотрим задачу перемножения двух квадратных матриц N×N. Если напрямую запрограммировать известную формулу: , например, на языке Си, получим следующий фрагмент программы:

for (i=0;i<N;i++)

for (k=0;k<N;k++)

for (j=0;j<N;j++) C[i][k]+=A[i][j]*B[j][k];

Заметим, что в этом случае массив A перебирается по строкам, а массив B - по столбцам (смотрим на внутренний цикл). Зная, что массивы в языке Си хранятся по строкам, приходим к выводу, что элементы массива A перебираются последовательно, а элементы массива B - нет. В данном случае порядок обхода массива C практически не важен, поскольку между обращениями к различным его элементам проходит довольно много времени.

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

for (i=0;i<N;i++)

for (j=0;j<N;j++)

for (k=0;k<N;k++) C[i][k]+=A[i][j]*B[j][k];

Время перемножения матриц 1000×1000 (double)

Процессор	Обычный способ	Последовательный способ	Ускорение
Alpha 667 MHz	120,67 с	6,24 с	19,34
Opteron 1800 MHz	16, 67 с	6,3 с	2,65