Локалност референци — разлика између измена
Садржај обрисан Садржај додат
Ред 71:
Заједнички пример је множење матрица:
for i in 0..n
for j in 0..m
Линија 78 ⟶ 76:
C[i][j] = C[i][j] + A[i][k] * B[k][j];
Када се ради о великим матрицама, овај алгоритам има тенденцију да превише дуплира подаке. Како је потребно помножити сваки члан реда једне матрице са сваким чланом колоне друге долази до вишеструком приступу истим подацима, као и вишеструком добијању истих резултата.
Може се приметити да од ј зависи колона ове матрице C и B и она треба да се врти у унутрашњој петљи(то ће поправити итераторе редова, i и k док се ј креће преко сваке колоне у реду). Ово неће променити математички резултат али се побољшава ефикасност. Преласком ј и к петљи временска захтевност за веће матрице драматично расте. (У овом случају, 'велики' значи, отприлике, више од 100.000 елемената у свакој матрици, или довољно елемената тако да матрице не могу да стану у L1 и L2 кеш.)
Временска захтевност може бити побољшана у претходном примеру, користећи технику која се зове блокирање. Већа матрица се може поделити на равномерно велике суб-матрице, тако да се мањи блокови множе неколико пута док су у меморији.
for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
Линија 86 ⟶ 89:
for (j = jj; j < jj + BLOCK_SIZE && j < SIZE; j++)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
Временска сложеност решења изнад је боље јер блок може да се користи неколико пута пре него што пређете на наредни, тако да мање губимо кад он оде у доње нивое хијерархије . Просторни локалитет је побољшан, јер елементи са суседне меморијске адресе имају тенденцију да се повуку заједно кроз меморијску хијерархију.
== Литература ==
| |||