ДС18в09-иерархия-памятей (1238912)
Текст из файла
Carnegie MellonИерархия памятейОсновы информатики.Компьютерные основы программированияgoo.gl/X7evFНа основе CMU 15-213/18-243:Introduction to Computer Systemsgoo.gl/Q7vgWwЛекция 9, 2 апреля, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Иерархия памятей¢¢¢Технологии и трендыЛокальность обращенияКеширование в иерархии памятей2Память с произвольным доступомRandom-Access Memory (RAM)¢Ключевые особенности§ RAM обычно изготавливается в виде (части) интегральной схемы.§ Базовая единица хранения - ячейка (1 бит в ячейке).§ Несколько ИС RAM образуют память.¢2 классических вида памяти с произвольным доступом§ Статическая RAM (SRAM)§ Динамическая RAM (DRAM)3Сводка по свойствам SRAM и DRAMТранз.на битВремя Регене- Коррек- Стоидоступа рация ция?мостьПримененияSRAM4 или 6 1XНетНе обяз.
100xКэш-памятьDRAM1ДаДаОсновная память,видео-память10X1X4Постоянная память¢DRAM и SRAM – непостоянная память§ Теряют информацию при выключении электропитания¢Постоянная память сохраняет значение при выключени觧§§§¢Read-only memory (ROM): программируется при изготовленииProgrammable ROM (PROM): однократно-программируемаяEraseable PROM (EPROM): может стираться целиком (УФ, рентген)Electrically eraseable PROM (EEPROM): электрически стираемаяFlash memory: EEPROM с частичным (секторным) стиранием§ Выходит из строя после 0.1-1М стираний.Применение постоянной памяти§ «Встроенные» программы, хранимые в *ROM (BIOS, модули/платырасширения, подсистемы безопасности…)§ Твердотельные диски Solid state disks (замена вращающихся дисковв «брелках», смартфонах, плеерах, планшетах, ноутбуках…)§ Дисковые кеши5Традиционное подключение ЦП к ОЗУ¢¢Шина набор параллельных проводников, несущихсигналы адреса, данных и управления.Обычно к шине подключаются несколько устройствИнтегральная схема CPUРегистровый блокАЛУСистемная шинаШинный интерфейсМоств/вШина памятиОсновнаяпамять6Чтение из памяти - 1¢ЦП выставляет адрес A на шине памятиИнтегральная схема CPUБлок регистров%eaxОперация чтения: movq A, %raxАЛУМост в/вШинный интерфейсAОсновная память0xA7Чтение из памяти - 2¢Основная память принимает A с шины памяти,выбирает слово x, и выставляет его на шинуИнтегральная схема CPUБлок регистров%eaxОперация чтения: movq A, %raxАЛУМост в/вШинный интерфейсAОсновная память0xA8Чтение памяти - 3¢ЦП считывает слово x с шины и помещает в регистр %eax.Интегральная схема CPUБлок регистров%eaxОперация чтения: movq A, %raxАЛУМост в/вШинный интерфейсAОсновная память0xA9Запись в память - 1¢ЦП выставляет на шину адрес A.
Основная памятьсчитывает его и ожидает слова данных.Интегральная схема CPUБлок регистров%eaxОперация записи: movq %rax, AАЛУМост в/вШинный интерфейсAОсновная память0A10Запись в память – 2¢ЦП CPU выставляет на шину слово данных y.Интегральная схема CPUБлок регистров%eaxyОперация записи: movq %rax, AАЛУМост в/вШинный интерфейсAОсновная память0A11Запись в память - 3¢Память считывает с шины слово данных y иразмещает по адресу A.Интегральная схема CPUБлок регистров%eaxyОперация записи: movq %rax, AАЛУМост в/вШинный интерфейсAОсновная память0yA12Что внутри жёсткого диска?ДержательВалПластиныПриводРазъёмЭлектроника(включаяпроцессори память!)Seagate Technology13Геометрия диска - 1¢¢¢Диск состоит из пластин, по две поверхности на каждойКаждая поверхность состоит из концентрических дорожекКаждая дорожка состоит из секторов разделённыхзазорамиДорожкиПоверхностьДорожка kЗазорыВалСекторы14Геометрия диска - 2¢Одинаковые дорожки образуют цилиндрЦилиндр kПоверхность 0Пластина 0Поверхность 1Поверхность 2Пластина 1Поверхность 3Поверхность 4Пластина 2Поверхность 5Вал15Ёмкость диска¢Ёмкость: максимальное количество хранимых байт§ Изготовители считают ёмкость в (GB), где 1 GB = 109 байт.¢Ёмкость определяется технологией:§ Плотность записи (бит/дюйм): количество бит в 1-дюймовомсегменте дорожки§ Плотность дорожек (дорожек/дюйм): количество дорожекпересекающих 1 дюйм радиуса§ Поверхностная плотность (бит/кв.дюйм): произведениеплотностей записи и дорожек.16Зоны записиСовременные диски разделяютвсё множество дорожекна зоны записи§ В каждой дорожке одной зоны –одинаковое количество секторовопределяемое самой внутреннейдорожкой.§ В каждой зоне своё своё значениесекторов/дорожку.§ во внешних – больше,§ во внутренних – меньше§ Для вычисления ёмкостииспользуется среднее значение…¢Вал17Вычисление ёмкости дискаЁмкость = (к-во байт/сектор) x (среднее к-во секторов/дорожку) x(к-во дорожек/поверхность) x (2 поверхности/пластину) x(к-во пластин/диск)Пример:§ 512 байт в секторе§ 300 секторов на дорожке (в среднем)§ 20 000 дорожек на поверхность§ 2 поверхности на пластине§ 5 пластин в дискеЁмкость = 512 x 300 x 20000 x 2 x 5= 30,720,000,000= 30.72 GB18Работа диска - 1Поверхностивращаются спостояннойугловойскоростьюГоловки чтения/записина держателях «плавают»над поверхностью на прослойкевоздухавалвалвалвалСмещаясь по радиусудержатель может разместитьголовки над любой дорожкой19Работа диска - 2Головки чтения записьперемещаются вместепо цилиндрамДержательВал20Структура диска – вид на пластинуПоверхность делится надорожкиДорожки делятся на сектора21Доступ к диску - 1Головка размещается наддорожкой22Доступ к диску - 2Вращение против часовойстрелки23Доступ к диску - 3Перед чтением синегосектора24Доступ к диску - 4После чтенияСИНЕГОДанные переданы25Очередной запросПосле чтенияСИНЕГОСледующим требуетсяпрочитать красный26ПодводПосле чтенияСИНЕГОПодвод кКРАСНОМУПодвод головки к дорожке красного27ДоворотПосле чтенияСИНЕГОПодвод кКРАСНОМУДоворот кКРАСНОМУОжидание красного сектора28ЧтениеПосле чтенияСИНЕГОПодвод кКРАСНОМУДоворот кКРАСНОМУПосле чтенияКРАСНОГОЧтение и передача данных29Составляющие времени выполненияПосле чтенияСИНЕГОПодвод кКРАСНОМУДоворот кКРАСНОМУВремяПодводаВремядоворотаПосле чтенияКРАСНОГОВремяпередачи30Время доступа к диску¢Среднее время доступа к сектору :§ T доступа ср.
= T подвода ср. + T доворота ср. + T чтения ср.¢Время подвода головок (T подвода ср.)§ Типичное T подвода ср. = 3—9 мс¢Время доворота пластин (T доворота ср.)§ T доворота ср. = 1/2 x 1/(частота вращения) x 60 сек/мин§ Типичная частота вращения = 5400-15000 об/мин¢Время чтения сектора (T чтения ср.)§ Time to read the bits in the target sector.§ T чтения ср. = 1/(частота вращения) x 1/(ср. к-во секторов/дорожку)x 60 сек/мин31Время доступа к диску: Пример¢Дано:§ Скорость вращения = 7,200 об/мин§ Среднее время подвода = 9 мс§ Среднее количество секторов/дорожку = 400.¢Считаем:§ T доворота ср.= 1/2 x (60/7200) x 1000 ms/sec = 4 мс§ T чтения ср.
= 60/7200 x 1/400 x 1000 = 0.02 мс§ T доступа ср. = 9 мс + 4 мс + 0.02 мс¢Важно:§ Основные затраты времени на подвод и доворот§ Доступ к первому биту в секторе – дорого, к остальным - даром.§ Время доступа к SRAM - 4 нс, DRAM - 60 нс§§Диск в 40 000 раз медленнее SRAM,В 2 500 раз медленнее DRAM.32Логические блоки диска¢Современные диски предлагают более простойабстрактный вид геометрии :§ Набор доступных секторов представляется последовательностьюлогических блоков (0, 1, 2, ...)¢Отображение логических блоков на физические сектора§ Выполняется отдельным устройством – дисковым контроллером§ Преобразуется запрос логического блока в физическую триаду(поверхность, дорожка, сектор)¢Контроллер резервирует несколько цилиндров в каждойзоне§ Различаются «форматированная» и «максимальная» ёмкости33Шина ввода/выводаИнтегральная схема ЦПБлок регистров%eaxАЛУМост в/вОсновнаяпамятьШинный интерфейсШина в/вКонтроллерUSBМышь КлавиатураГрафическийадаптерДисковыйконтроллерСлоты расширениядля других устройств.Например,сетевого адаптера.МониторДиск34Чтение сектора диска - 1Интегральная схема ЦПБлок регистров%eaxАЛУЦП инициирует чтение диска записьюкоманды, номера блока, и целевогоадреса памяти в порт (адрес)дискового контроллера.Мост в/вОсновнаяпамятьШинный интерфейсШина в/вКонтроллерUSBМышь КлавиатураГрафическийадаптерДисковыйконтроллерМониторДиск35Чтение сектора диска - 2Интегральная схема ЦПБлок регистров%eaxАЛУДисковый контроллер читаетсектор и выполняет процедурупрямого доступа в память (ПДП,DMA).Мост в/вОсновнаяпамятьШинный интерфейсШина в/вКонтроллерUSBМышь КлавиатураГрафическийадаптерДисковыйконтроллерМониторДиск36Чтение сектора диска - 3Интегральная схема ЦПБлок регистров%eaxАЛУДисковый контроллер уведомляетЦП о завершении ПДП(DMA)прерыванием (т.e., передачейсигнала на специальный выводпрерывания ЦП)Мост в/вОсновнаяпамятьШинный интерфейсШина в/вКонтроллерUSBМышь КлавиатураГрафическийадаптерДисковыйконтроллерМониторДиск37Твердотельные диски (SSDs)Шина в/вSolid State Disk (SSD)УровеньинтерпретацииFlash - памятьБлок 0Стр.
0¢¢¢¢Стр. 1Блок B-1…Стр.P-1…Стр.0Стр.1…Стр.P-1Страницы: 512B - 4KB, Блоки: 32 - 128 страницЧтение/запись страницамиСтраница м.б. записана только после стирания блокаБлок изнашивается после 100 000 повторных записей38Быстродействие SSDПоследоват. чтениеПроизвольное чтениеДоступ к посл. чтению¢¢550 MБ/сек365 MБ/сек50 мксПоследоват. ЗаписьПроизвольная записьДоступ к посл.
записи470 MБ/сек303 MБ/сек60 мксПоследовательный доступ быстрее случайногоСлучайная запись немного медленнее чтения§ Блок стирается медленно (~1 ms)§ Запись в страницу вызывает копирование всех остальных страницблока в новый§ В ранних SSD различия в скоростях записи и чтения много большеИсточник: спецификация Intel SSD 73039Особенности твердотельных дисков¢Преимущества§ Без движущихся частей à быстрее, экономнее, устойчивее¢Недостатки§ ИзнашиваниеНивелируется “логикой равномерного износа” на уровнеинтерпретации§ Например Intel SSD 730 гарантирует 128 петабайт (128x1015)байт) записей до износа§ В 2015, удельная стоимость в ~30 раз выше§¢Применения§ MP3 плееры, смартфоны, планшеты, ноутбуки§ Высокопроизводительные настольные ПК и сервера40Пропасть ЦП-памятьРастёт пропасть между скоростями DRAM, диска, и ЦП100 000 000,0Диск10 000 000,01 000 000,0SSD100 000,0Disk seek timeFlash SSD access timeDRAM access timeSRAM access timeCPU cycle timeEffective CPU cycle timeнс10 000,01 000,0DRAM100,010,01,0ЦП0,10,019801985199019952000Годы20032005201041Спасение в локальности!Ключ к переходу через пропасть памятьпроцессор – это фундаментальноесвойство компьютерных программизвестное как локальность42Иерархия памятей¢¢¢Технологии и трендыЛокальность обращенияКеширование в иерархии памятей43Локальность¢¢Принцип локальности : Программы чаще обращаютсяк данным и командам, чьи адреса близкие к темкоторые недавно использовалисьВременнАя локальность:§ Недавно использованные ячейки вероятновскоре будут использованы вновь¢Пространственная локальность:§ К ячейкам с ближайшими адресамиобращения произойдут в ближайшее время44Пример локальностиsum = 0;for (i = 0; i < n; i++)sum += a[i];return sum;¢Обращение к данным§ Последовательная выборка элементовмассива§ Обращение к sum в каждой итерации¢ПространсвеннаяВременнАяОбращение к командам§ Последовательная выборка команд§ Повторение команд циклаПространственнаяВременнАя45Качественная оценка локальности¢¢Утверждение: Способность взглянув на код получитькачественную оценку его локальности – ключевойнавык профессионального программиста.Вопрос: Эта функция имеет хорошую локальность вотношении массива a?int sum_array_rows(int a[M][N]){int i, j, sum = 0;for (i = 0; i < M; i++)for (j = 0; j < N; j++)sum += a[i][j];return sum;}46Пример локальности¢Вопрос: Эта функция имеет хорошую локальность вотношении массива a?int sum_array_cols(int a[M][N]){int i, j, sum = 0;for (j = 0; j < N; j++)for (i = 0; i < M; i++)sum += a[i][j];return sum;}47Пример локальности¢Вопрос: Вы можете переставить циклы так, чтобыфункция сканировала 3-мерный массив a такжеэффективно как одномерный? С хорошейпространственной локальностью.int sum_array_3d(int a[M][N][N]){int i, j, k, sum = 0;for (i = 0; i < M; i++)for (j = 0; j < N; j++)for (k = 0; k < N; k++)sum += a[k][i][j];return sum;}48Иерархия хранения данных¢Некоторые фундаментальные и стабильные свойствааппаратуры и ПО:§ Более быстрые технологии хранения удельно дороже, менееёмкие, и более энергоёмкие (нагрев!).§ Пропасть «процессор-память» растёт.§ Хороший код демонстрирует хорошую локальность.¢¢Эти фундаментальные свойства замечательнодополняют друг другаЭто подсказывает подход к организации подсистемыпамяти известный как иерархия хранения данных.49Иерархия памятей¢¢¢Технологии и трендыЛокальность обращенияКеширование в иерархии памятей50Пример иерархииL0: РепамятейL1:Мельче,быстрее,удельно дороже иэнергозатратнееL2:L3:Крупнее,L4:медленнее,удельно дешевлеи энергоэкономичнееL5:L6:гистрыКеш ур.1(SRAM)Регистры ЦП хранит слова,полученные из кэша уровня 1Кеш уровня 2(SRAM)Кеш уровня 3(SRAM)Кэш уровня 1 хранит кэш-линии,полученные из кэша уровня 2Кэш уровня 1 хранит кэш-линии,полученные из кэша уровня 3Основная память(DRAM)Местное постоянное хранение(локальные диски)Кэш уровня 3 хранит кэшлинии, полученные из памятиПамять хранит логическиедисковые блоки, полученныес локального дискаУдалённое постоянное хранение(ленты, сетевые файловые системы, веб сервера)Локальные дискихранят файлыполученныеиздалека51Кеши¢¢Кеш(Cache): Устройство хранения меньшей ёмкости ибольшего быстродействия, действующее каквспомогательное для доступа к части данных болеекрупного и медленного устройства.Фундаментальная идея иерархии:§ Устройство уровня k служит кешем для устройства уровня k+1.¢Почему работает иерархия хранения данных?§ Благодаря локальности программы к данным уровня k доступпроисходит чаще, чем к данным уровня k+1.§ Значит уровень хранения k+1 может быть медленнее, а значитбольше и дешевле (на единицу хранения)¢Идеально: Иерархия предоставляет большой объёмхранения по цене экономичного нижнего уровня сскоростью доступа верхнего уровня для программ.52Кэш в общемКэш8493Небольшая, быстрая, дорогая памятькэширует часть кэш-блоковДанные копируютсякэш-блоками104Память14100123456789101112131415Большая, медленная, дешёвая памятьразделена на кэш-блоки53Кэш в общем: ПопаданиеЗапрос: 14КэшПамять891430123456789101112131415Нужен блок данных bБлок b в кэше есть:Попадание!54Кэш в общем: ПромахЗапрос: 12Кэш81293Запрос: 1212Память140123456789101112131415Нужен блок данных bБлока b в кэше нет:Промах!Блок b поступаетиз памятиБлок b помещается в кеше•Политика размещения:определяет, где b в кэше•Политика замещения:определяет удаляемый блок(жертву)55Кэш в общем: типы промахов¢Холодный промах§ Кеш пуст.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
