ДС18в10-Кеширование-памятей (1238913), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

100%)28Перемножение матриц (ijk)/* ijk */for (i=0; i<n; i++) {for (j=0; j<n; j++) {sum = 0.0;for (k=0; k<n; k++)sum += a[i][k] * b[k][j];c[i][j] = sum;}}Внутренний цикл:(*,j)(i,*)(i,j)ABCПострокеПостолбцуОдинэлементПромахов в итерации внутреннего цикла:ABC0.251.00.029Перемножение матриц (jik)/* jik */for (j=0; i<n; i++) {for (i=0; j<n; j++) {sum = 0.0;for (k=0; k<n; k++)sum += a[i][k] * b[k][j];c[i][j] = sum;}}Внутренний цикл:(*,j)(i,*)(i,j)ABCПострокеПостолбцуОдинэлементПромахов в итерации внутреннего цикла:ABC0.251.00.030Перемножение матриц (kij)/* kij */for (k=0; k<n; k++) {for (i=0; i<n; i++) {r = a[i][k];for (j=0; j<n; j++)c[i][j] += r * b[k][j];}}Внутренний цикл:(i,k)(k,*)(i,*)ABCОдинэлементПострокеПострокеПромахов в итерации внутреннего цикла:ABC0.00.250.2531Перемножение матриц (ikj)/* ikj */for (i=0; k<n; k++) {for (k=0; i<n; i++) {r = a[i][k];for (j=0; j<n; j++)c[i][j] += r * b[k][j];}}Внутренний цикл:(i,k)(k,*)(i,*)ABCОдинэлементПострокеПострокеПромахов в итерации внутреннего цикла:ABC0.00.250.2532Перемножение матриц (jki)/* jki */for (j=0; j<n; j++) {for (k=0; k<n; k++) {r = b[k][j];for (i=0; i<n; i++)c[i][j] += a[i][k] * r;}}Внутренний цикл:(*,k)(*,j)(k,j)ABCПостолбцуОдинэлементПостолбцуПромахов в итерации внутреннего цикла:ABC1.00.01.033Перемножение матриц (kji)/* kji */for (k=0; j<n; j++) {for (j=0; k<n; k++) {r = b[k][j];for (i=0; i<n; i++)c[i][j] += a[i][k] * r;}}Внутренний цикл:(*,k)(*,j)(k,j)ABCПостолбцуОдинэлементПостолбцуПромахов в итерации внутреннего цикла:ABC1.00.01.034Сводка перемножений матрицfor (i=0; i<n; i++) {for (j=0; j<n; j++) {sum = 0.0;for (k=0; k<n; k++)sum += a[i][k] * b[k][j];c[i][j] = sum;}}for (k=0; k<n; k++) {for (i=0; i<n; i++) {r = a[i][k];for (j=0; j<n; j++)c[i][j] += r * b[k][j];}}for (j=0; j<n; j++) {for (k=0; k<n; k++) {r = b[k][j];for (i=0; i<n; i++)c[i][j] += a[i][k] * r;}}ijk и jik:• 2 чтения, 0 записей• промахов в итерации = 1.25kij и ikj:• 2 чтения, 1 запись• промахов в итерации = 0.5jki и kji:• 2 чтения, 1 запись• промахов в итерации = 2.035Скорость перемножения матриц на Core i7Тактов на итерацию внутр.

цикла100jki / kjiijk / jikjkikjiijkjikkijikj10kij / ikj150100150200250300350400450500550600650700Размер массива (N)36Кеширование памятей¢¢Организация и работа кэшаВлияние кэша на быстродействие памяти§ Диаграмма быстродействия памяти§ Реорганизация циклов улучшает пространственную локальность§ Блокирование улучшает временнУю локальность37Пример: Перемножение матрицc = (double *) calloc(sizeof(double), n*n);/* Перемножение a и b - матриц размерами n x n */void mmm(double *a, double *b, double *c, int n) {int i, j, k;for (i = 0; i < n; i++)for (j = 0; j < n; j++)for (k = 0; k < n; k++)c[i*n + j] += a[i*n + k] * b[k*n + j];}jc=iab*38Анализ промахов кеша¢Допустим:§ Элементы матриц – double§ Блок кэша = 8 double (64 байта)§ Размер кэша C << n (много меньше n)¢nПервая итерация:§ n/8 + n = 9n/8 промахов=*=*§ После итерации в кэше:(схематично)ширина8 байт39Анализ промахов кеша¢Допустим:§ Элементы матриц – double§ Блок кэша = 8 double (64 байта)§ Размер кэша C << n (много меньше n)¢nВторая итерация:§ Опять:n/8 + n = 9n/8 промахов¢Всего промахов:=*ширина8 байт§ 9n/8 * n2 = (9/8) * n340Блочное перемножение матрицc = (double *) calloc(sizeof(double), n*n);/* Перемножение a и b - матриц размерами n x n */void mmm(double *a, double *b, double *c, int n) {int i, j, k;for (i = 0; i < n; i+=B)for (j = 0; j < n; j+=B)for (k = 0; k < n; k+=B)/* Перемножение мини-матриц размерами B x B */for (i1 = i; i1 < i+B; i++)for (j1 = j; j1 < j+B; j++)for (k1 = k; k1 < k+B; k++)c[i1*n+j1] += a[i1*n + k1]*b[k1*n + j1];}j1c= i1ab*+Размер блока B x Bc41Анализ промахов кеша¢Допустим:§ Блок кэша = 8 doubles§ Размер кэша C << n (много меньше n)§ Четыре блока умещаются в кеш : 4B2 < C¢n/B blocksПервая (блочная) итерация:§ B2/8 промахов в блоке§ 2n/B * B2/8 = nB/4(не считая матрицу c)=Размер блока B x B§ То, что осталось в кэше(схематично)*=*42Анализ промахов кеша¢Допустим:§ Блок кэша = 8 doubles§ Размер кэша C << n (много меньше n)§ Четыре блока умещаются в кеш : 4B2 < C¢Вторая (блочная) итерация:§ Как и на первой итерации§ 2n/B * B2/8 = nB/4¢n/B blocksВсего промахов:§ nB/4 * (n/B)2 = n3/(4B)=*Размер блока B x B43Сводка блокирования¢¢¢¢Без блокирования: (9/8) * n3С блокированием: 1/(4B) * n3Предполагается наибольший размер блока B,ограниченный как 4B2 < C!Причины существенной разницы:§ Матрице присуща временная локальность:3n2 входных данных, 2n3 операций§ Каждый элемент массивов используется O(n) раз!§ При условии, что программа написана правильно§44Сводка кеширования¢Кеш-памяти могут сильно влиять на быстродействие¢В можете использовать это в своих программах§ Фокусируйтесь на внутренних циклах, где возникаетбольшая часть вычислений и обращений в память.§ Старайтесь улучшать пространственную локальность,обращаясь к данным с минимальным шагом 1.§ Старайтесь улучшать временнУю локальность,максимально используя повторно данные,однажды считанные из основной памяти.45.

Характеристики

Список файлов лекций