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

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

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

Carnegie MellonКеширование памятейОсновы информатики.Компьютерные основы программированияgoo.gl/X7evFНа основе CMU 15-213/18-243:Introduction to Computer Systemsgoo.gl/Q7vgWwЛекция 10, 9 апреля, 2018Лектор:Дмитрий Северов, кафедра информатики 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]Блок 101001M[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ГребнивременнОйлокальностиур.320000s1Склоныпростанственнойлокальностиs3s5Основнаяs7128k8ms9Шаг (кратно 8 байт)2m512k32ks11128m32mРазмер рабочего набора (байт)24Кеширование памятей¢¢Организация и работа кэшаВлияние кэша на быстродействие памяти§ Диаграмма быстродействия памяти§ Реорганизация циклов улучшает пространственную локальность§ Блокирование улучшает временнУю локальность25Пример перемножения матриц¢Описание:§ Перемножение матриц NxN§ Всего O(N3) операций§ N чтений каждогоисходного элемента§ Каждый результат - суммаN значений§ может накапливатьсяв регистреПеременная sumнаходитсяв регистре/* 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;}}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 (т.е.

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

Тип файла PDF

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

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

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