ДС20в10-Кеширование-памятей (1238931)

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

Текст из файла

Кеширование памятейОсновы информатикиКомпьютерные основы программированияu.to/DbCmFAНа основе CMU 15-213/18-243:Introduction to Computer Systemsu.to/XoKmFAЛекция 11, 10 мая, 2020Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Кеширование памятей¢¢Организация и работа кэшаВлияние кэша на быстродействие памяти§ Диаграмма быстродействия памяти§ Реорганизация циклов улучшает пространственную локальность§ Блокирование улучшает временнУю локальность2Пример иерархииL0: РепамятейгистрыL1: Кеш- ур.1(SRAM)Мельче,быстрее,удельно дороже иэнергозатратнееL2: Кеш-п. уровня 2(SRAM)L3:Крупнее,L4:медленнее,удельно дешевлеи энергоэкономичнееL5:L6:Регистры ЦП хранит слова,полученные из кэша уровня 1Кэш уровня 1 хранит кэш-линии,полученные из кэша уровня 2Кеш-память уровня 3(SRAM)Кэш уровня 1 хранит кэш-линии,полученные из кэша уровня 3Основная память(DRAM)Местное постоянное хранение(локальные диски)Кэш уровня 3 хранит кэшлинии, полученные из памятиПамять хранит логическиедисковые блоки, полученныес локального дискаУдалённое постоянное хранение(ленты, сетевые файловые системы, веб сервера)Локальные дискихранят файлыполученныеиздалека3Кэш в общемКэш8493Небольшая, быстрая, дорогая памятькэширует часть кэш-блоковДанные копируютсякэш-блоками104Память14100123456789101112131415Большая, медленная, дешёвая памятьразделена на кэш-блоки4Кэш-памяти¢Кэш-памяти – небольшие, быстрые памяти на основеSRAM, автоматически управляемые аппаратурой.§ Хранит часто используемые блоки основной памяти¢¢Ядро ЦП сначала обращается за данными в кэши, азатем в основную память.

Если потребуется.Типичная структура системы:ИС ЦПБлок регистровКэшпамятьШинный интерфейсАЛУСистемная шина Шина памятиМоств/вОсновнаяпамять5Общая организация кэша (S, E, B)E = 2e линий в наборенаборлинияS = 2sнаборовРазмер кэша:C = S x E x B байт данныхvметкаБит актуальности0 1 2B-1B = 2b байт в кэш-блоке6Чтение кэшаE = 2e линий в наборе• Выбрать набор• Проверить на совпадениеметки линий в наборе• Есть + актуальна: попадание!• Выбрать данные начинаяот смещенияАдрес данных в памяти:t битS = 2sнаборовs битb битметка индекс смещение внабора кэш-блокеначало данных по этому смещениюvметкаБит актуальности0 1 2B-1B = 2b байт в кэш-блоке7Пример: Кэш прямого отображения (E = 1)Прямое отображение: одна линия в набореДопустим: размер кэш-блока - 8 байтS = 2sнаборовvметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7Адрес int:t бит0…01100выбор набора8Пример: Кэш прямого отображения (E = 1)Прямое отображение: одна линия в набореДопустим: размер кэш-блока - 8 байтактуально? + совпала: допустим да = попадание!vметкаАдрес int:t бит0…011000 1 2 3 4 5 6 7смещение в линии9Пример: Кэш прямого отображения (E = 1)Прямое отображение: одна линия в набореДопустим: размер кэш-блока - 8 байтактуально? + совпала: допустим да = попадание!vметкаАдрес int:t бит0…011000 1 2 3 4 5 6 7смещение в линииЗдесь int (4 байта)Если не совпала, то старая линия освобождается и замещается10Имитирование кэша прямого отображенияt=1xs=2xxb=1xM=16 адресов байтов, B=2 байта в кэш-блоке,S=4 набора, E=1 линия в набореТрассировка адресов (чтения, по одному байту):промах0[00002],попадание1[00012],промах7[01112],промах8[10002],промах0[00002]Набор 0Набор 1Набор 2Набор 3v метка011?010кеш-блок?M[8-9]M[0-1]M[6-7]11E-канальный наборно-ассоциативныйкэш (здесь: E = 2)E = 2: Две линии в набореДопустим: размер кэш-блока – 8 байтАдрес short int:t битvметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 70…01100выборнабора12E-канальный наборно-ассоциативныйкэш (здесь: E = 2)E = 2: Две линии в набореДопустим: размер кэш-блока – 8 байтАдрес short int:сравнить метки обеих линийt бит0…01100актуально + совпала = попадание!vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7смещение в кеш-блоке13E-канальный наборно-ассоциативныйкэш (здесь: E = 2)E = 2: Две линии в набореДопустим: размер кэш-блока – 8 байтАдрес short int:сравнить метки обеих линийt бит0…01100актуально + совпала = попадание!vметка0 1 2 3 4 5 6 7vметка0 1 2 3 4 5 6 7смещение в линииздесь short int (2 байта)Если не совпала, то…•Одна линия в наборе освобождается и замещается•Политики замещения: случайно, least recently used (LRU), …14Имитирование 2-канальногонаборно-ассоциативного кэшаt=2xxs=1xb=1xM=16 байтовых адресов, B=2 байта в кэш-блоке,S=2 набора, E=2 линии в наборТрассировка адресов (чтения, по одному байту):промах0[00002],попадание1[00012],промах7[01112],промах8[10002],попадание0[00002]v метка кэш-блок0??00M[0-1]Блок 0 10110M[8-9]01Блок 1001M[6-7]15Немного о записи¢Присутствуют несколько копий данных:§ Кэши памяти, основная память, диск¢Что делать при записи с попаданием?§ Write-through (запись непосредственно в память )§ Write-back (запись в память задерживается до замены линии)§¢Нужен бит несоответствия (линия совпадает с памятью или нет)Что делать при записи с промахом?§ Write-allocate (загрузка в кэш, изменение линии кэша)Хорошо если ожидаются ещё записи§ No-write-allocate (запись непосредственно в память)§¢Типичные политики§ Write-through + No-write-allocate§ Write-back + Write-allocate16Иерархия кэшей Intel Core i7Интегральная схема процессораЯдро 0Ядро 3регистрыКэш ур.1данныерегистрыКэш ур.1команды…Общий кэшуровня 2Кэш ур.1данныеКэш ур.1командыОбщий кэшуровня 2Общий кэш уровня 3(разделяемый всеми ядрами)Кэш команд и кэшданных уровня 1:32 KБ, 8-каналов,Доступ: 4 циклаОбщий кэш уровня 2:256 KБ, 8-каналов,Доступ: 11 цикловОбщий кэш уровня 3:8 MБ, 16-каналов,Доступ: 30-40цикловРазмер кеш-блока: 64байта для всех кэшейОсновная память17Характеристики эффективности кэша¢Вероятность промахов§ Доля обращений в память не обнаруженных к кэше(промахов / доступов) = 1 – вероятность попаданий§ Типичные значения (в процентах):§ 3-10% для кэша уровня 1§ Может быть весьма малым (< 1%) для кэша уровня 2, в зависимостиот размера¢Продолжительность доступа в кэш§ Время доставки данных из кэша в процессорВключая время определение наличия данных в кэше§ Типичные величины:§ 1-2 такта для кэша уровня 1§ 5-20 тактов для кэша уровня 2§¢Продолжительность промаха§ Дополнительное время необходимое при промахе§обычно 50-200 тактов для основной памяти (и будет расти!)18Некоторые мысли о характеристикахэффективности кэша¢Громадная разница между попаданиями и промахами§ До 100 раз, для кэша первого уровня и основной памяти¢Верно ли что 99% попаданий в два раза лучше чем 97%?§ Допустим:продолжительность доступа в кэш – 1 тактпродолжительность промаха – 100 тактов§ Среднее время доступа:97% попаданий: 1 такт + 0.03 * 100 тактов = 4 такта99% попаданий: 1 такт + 0.01 * 100 тактов = 2 такта¢Поэтому в основном используется термин“вероятность промаха”, и не “вероятность попадания”19Создание программ дружелюбных к кэшу¢Ускорение наиболее часто исполняемых участков§ Сосредоточение на внутренних циклах основных функций¢Минимизация промахов во внутренних циклах§ Повторные обращение к переменным (временнАя локальность)§ Доступ с единичным шагом (пространственная локальность)Ключевая идея: благодаря пониманию кэш-памятикачественное теоретическое понятие локальностиполучает практическую количественную меру20Кеширование памятей¢¢Организация и работа кэшаВлияние кэша на быстродействие памяти§ Диаграмма быстродействия памяти§ Реорганизация циклов улучшает пространственную локальность§ Блокирование улучшает временнУю локальность21«Гора» (быстродействия) памяти¢Скорость чтения (пропускная способность чтения)§ К-во байт считываемых из памяти за секунду (MБ/сек)¢Диаграмма быстродействия памятей «Гора» :Измеренная пропускная способность чтения какфункция временной и пространственной локальности.§ Компактный способ охарактеризовать быстродействиеподсистемы памяти.22Функция измерения «горы»long data[MAXELEMS]; /* Глобальный читаемый массив *//* test – Читаем первые "elems" элементов*массива “data” c шагом "stride",*разворачивая цикл 4x4.*/int test(int elems, int stride) {long i, sx2=stride*2, sx3=stride*3, sx4=stride*4;long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;long length = elems, limit = length - sx4;/* Накапливаем 4 4 элемента за итерацию */for (i = 0; i < limit; i += sx4) {acc0 = acc0 + data[i];acc1 = acc1 + data[i+stride];acc2 = acc2 + data[i+sx2];acc3 = acc3 + data[i+sx3];}/* Подбираем оставшиеся элементы */for (; i < length; i++) {acc0 = acc0 + data[i];}return ((acc0 + acc1) + (acc2 + acc3));Многократно вызыватьtest() варьируяelemsи stride.Для каждого elemsи stride:1.

Для заполнениякеша вызватьtest().2. Вызвать test()снова и измеритьagain and скоростьчтения(МБ/с)}mountain/mountain.c23Core i7 Haswell 2.1 ГГцРазмеры кеш-памятей:• 64 Б блок• 32 КБ ур.1 данные• 256 КБ ур.2 общий• 8 МБ ур.3 общий«Гора» памятиАгрессивнаяпредвыборкаСкорость чтения (МБ/с)16000ур.11400012000100008000ур.260004000ГребнивременнОйлокальностиур.320000s1s3Склоныпростанственнойлокальностиs5Основнаяs7Шаг (кратно 8 байт)8ms9s11128m32m2m512k128k32kРазмер рабочего набора (байт)24Кеширование памятей¢¢Организация и работа кэшаВлияние кэша на быстродействие памяти§ Диаграмма быстродействия памяти§ Реорганизация циклов улучшает пространственную локальность§ Блокирование улучшает временнУю локальность25Пример перемножения матриц¢Описание:§§§§Переменная sumнаходитсяв регистре/* ijk */Перемножение матриц N x N for (i=0; i<n; i++) {for (j=0; j<n; j++) {Всего O(N3) операцийsum = 0.0;N чтений каждого исходногоfor (k=0; k<n; k++)элементаsum += a[i][k] * b[k][j];Каждый результат - сумма Nc[i][j] = sum;значений}§ может накапливаться в}регистре26Анализ вероятности промаха дляматричного умножения¢Допустим:§ Размер линии = 32 байта (достаточно для 4-х 64-битных слов)§ Размер матрицы (N) очень большой1/N приблизительно представляется 0.0§ Кэш недостаточно велик, чтобы содержать несколько строк матрицы§¢Метод анализа:§ Посмотрим на схему доступа во внутреннем циклеjk*iAj=kBiC27Расположение в памяти массивов Си¢Массивы Си хранятся в памяти по строкам§ строки располагаются друг за другом¢Проход по столбцам в одной строке:§ for (i = 0; i < N; i++)sum += a[0][i];§ доступ к последовательно расположенным элементам§ Если размер кэш-блока (B) > 4 байт, действуетпространственная локальность§ вероятность вынужденного промаха = 4 байта / B¢Проход по строкам в одном столбце:§ for (i = 0; i < n; i++)sum += a[i][0];§ Доступ к разнесённым в памяти элементам§ Пространственная локальность отсутствует!§ вероятность вынужденного промаха = 1 (т.е.

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.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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