Используются для создания кэш-памяти

Обновлено: 21.11.2024

Если вы покупали компьютер, то слышали слово "кэш". Современные компьютеры имеют кэши L1 и L2, а многие теперь также имеют кэш L3. Возможно, вы также получили совет по этой теме от благонамеренных друзей, например, что-то вроде «Не покупайте этот чип Celeron, в нем нет кэша!»

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

Простой пример: до кэширования

Кэширование — это технология, основанная на подсистеме памяти вашего компьютера. Основная цель кэш-памяти — ускорить работу вашего компьютера, сохраняя при этом низкую цену компьютера. Кэширование позволяет быстрее выполнять задачи на компьютере.

Чтобы понять основную идею системы кэширования, давайте начнем с очень простого примера, в котором используется библиотекарь для демонстрации принципов кэширования. Давайте представим библиотекаря за своим столом. Он здесь, чтобы дать вам книги, которые вы просите. Для простоты предположим, что вы не можете получить книги сами — вам нужно попросить у библиотекаря любую книгу, которую вы хотите прочитать, и он принесет ее для вас из набора стопок в кладовой (библиотека конгресс в Вашингтоне, округ Колумбия, устроен таким образом). Во-первых, давайте начнем с библиотекаря без кеша.

Приходит первый покупатель. Он просит книгу Моби Дик. Библиотекарь идет в кладовую, берет книгу, возвращается к прилавку и отдает книгу покупателю. Позже клиент возвращается, чтобы вернуть книгу. Библиотекарь берет книгу и возвращает ее в кладовую. Затем он возвращается к своему прилавку, ожидая другого покупателя. Допустим, следующий клиент просит Моби Дика (вы это предвидели. ). Затем библиотекарь должен вернуться в кладовую, чтобы взять книгу, с которой он недавно работал, и отдать ее клиенту. В соответствии с этой моделью библиотекарь должен совершить полный обход, чтобы получить каждую книгу, даже очень популярную, которую часто запрашивают. Есть ли способ улучшить работу библиотекаря?

Да, есть способ — мы можем поставить кеш на библиотекаря. В следующем разделе мы рассмотрим тот же пример, но на этот раз библиотекарь будет использовать систему кэширования.

Простой пример: после кэширования

Дадим библиотекарю рюкзак, в котором он сможет хранить 10 книг (с точки зрения компьютера у библиотекаря теперь есть тайник на 10 книг). В этот рюкзак он будет складывать книги, которые возвращают ему клиенты, максимум до 10. Давайте воспользуемся предыдущим примером, но теперь с нашим новым и улучшенным кэширующим библиотекарем.

День начинается. Рюкзак библиотекаря пуст. Приходит наш первый клиент и просит Моби Дика. Никакого волшебства здесь нет — библиотекарь должен пойти в кладовую, чтобы взять книгу. Он отдает клиенту. Позже клиент возвращается и возвращает книгу библиотекарю. Вместо того, чтобы вернуться в кладовую, чтобы вернуть книгу, библиотекарь кладет книгу в свой рюкзак и стоит там (сначала он проверяет, не полон ли мешок — об этом позже). Приходит другой клиент и просит Моби Дика. Прежде чем отправиться в кладовую, библиотекарь проверяет, нет ли этого названия в его рюкзаке. Он находит! Все, что ему нужно сделать, это взять книгу из рюкзака и отдать клиенту. Нет необходимости заходить на склад, поэтому клиент обслуживается более эффективно.

Что делать, если клиент запросил название не в кеше (в рюкзаке)? В этом случае библиотекарь менее эффективен с тайником, чем без него, потому что сначала библиотекарь тратит время на поиск книги в своем рюкзаке. Одной из задач проектирования кэша является минимизация влияния поиска в кэше, и современное оборудование свело эту задержку практически к нулю. Даже в нашем простом примере с библиотекарем время задержки (время ожидания) поиска в кэше настолько мало по сравнению со временем, которое требуется для возвращения в хранилище, что оно не имеет значения. Тайник небольшой (10 книг), и время, необходимое для того, чтобы заметить промах, составляет лишь ничтожную долю времени, которое занимает путешествие в кладовую.

В этом примере вы можете увидеть несколько важных фактов о кэшировании:

Технология кэширования — это использование более быстрого, но меньшего типа памяти для ускорения более медленного, но большего типа памяти.
При использовании кеша вы должны проверить кеш, чтобы увидеть, есть ли там элемент. Если он есть, это называется попаданием в кеш. В противном случае это называется промахом кеша, и компьютер должен ожидать обращения из более крупной и медленной области памяти.
Кэш имеет некоторый максимальный размер, который намного меньше, чем большая область хранения.
Кэш может иметь несколько уровней.В нашем примере с библиотекарем меньший, но более быстрый тип памяти — это рюкзак, а кладовая представляет собой более крупный и медленный тип памяти. Это одноуровневый кеш. Там может быть еще один уровень тайника, состоящий из полки, которая может вместить 100 книг за прилавком. Библиотекарь может проверить рюкзак, затем полку и затем кладовую. Это будет двухуровневый кеш.

Компьютер — это машина, в которой мы измеряем время очень маленькими шагами. Когда микропроцессор обращается к основной памяти (ОЗУ), он делает это примерно за 60 наносекунд (60 миллиардных долей секунды). Это довольно быстро, но намного медленнее, чем обычный микропроцессор. Микропроцессоры могут иметь время цикла всего 2 наносекунды, поэтому для микропроцессора 60 наносекунд кажутся вечностью.

Что, если мы встроим в материнскую плату специальный банк памяти, небольшой, но очень быстрый (около 30 наносекунд)? Это уже в два раза быстрее, чем доступ к основной памяти. Это называется кешем второго уровня или кешем L2. Что, если мы встроим еще меньшую, но более быструю систему памяти прямо в микросхему микропроцессора? Таким образом, доступ к этой памяти будет осуществляться со скоростью микропроцессора, а не со скоростью шины памяти. Это кэш L1, который на 233-мегагерцовом процессоре Pentium в 3,5 раза быстрее, чем кэш L2, который в два раза быстрее, чем доступ к основной памяти.

Некоторые микропроцессоры имеют два уровня кэш-памяти, встроенные прямо в чип. В этом случае кэш материнской платы — кэш, который существует между микропроцессором и основной системной памятью — становится уровнем 3 или кешем L3.

В компьютере много подсистем; вы можете поместить кеш между многими из них, чтобы улучшить производительность. Вот пример. У нас есть микропроцессор (самая быстрая вещь в компьютере). Кроме того, есть кэш L1, который кэширует кэш L2, который кэширует основную память, которая может использоваться (и часто используется) в качестве кэша для еще более медленных периферийных устройств, таких как жесткие диски и компакт-диски. Жесткие диски также используются для кэширования еще более медленного носителя — вашего интернет-соединения.

Ваше подключение к Интернету является самым медленным каналом на вашем компьютере. Итак, ваш браузер (Internet Explorer, Netscape, Opera и т. д.) использует жесткий диск для хранения HTML-страниц, помещая их в специальную папку на вашем диске. Когда вы впервые запрашиваете HTML-страницу, ваш браузер отображает ее, и ее копия также сохраняется на вашем диске. В следующий раз, когда вы запросите доступ к этой странице, ваш браузер проверит, является ли дата файла в Интернете более новой, чем дата, сохраненная в кэше. Если дата совпадает, ваш браузер использует дату на жестком диске, а не загружает ее из Интернета. В этом случае меньшая, но более быстрая система памяти — это ваш жесткий диск, а большая и медленная — это Интернет.

Кэш также можно создать непосредственно на периферийных устройствах. Современные жесткие диски поставляются с быстрой памятью, около 512 килобайт, жестко подключенной к жесткому диску. Компьютер не использует эту память напрямую — ее использует контроллер жесткого диска. Для компьютера эти микросхемы памяти являются самим диском. Когда компьютер запрашивает данные с жесткого диска, контроллер жесткого диска проверяет эту память, прежде чем перемещать механические части жесткого диска (что очень медленно по сравнению с памятью). Если он найдет данные, запрошенные компьютером в кеше, он вернет данные, хранящиеся в кеше, без фактического доступа к данным на самом диске, что сэкономит много времени.

Вы можете провести эксперимент. Ваш компьютер кэширует дисковод гибких дисков вместе с основной памятью, и вы действительно можете видеть, как это происходит. Получите доступ к большому файлу с дискеты — например, откройте 300-килобайтный текстовый файл в текстовом редакторе. В первый раз вы увидите, как загорается свет на вашей дискете, и вы будете ждать. Дискета работает очень медленно, поэтому загрузка файла займет 20 секунд. Теперь закройте редактор и снова откройте тот же файл. Во второй раз (не ждите 30 минут и не выполняйте большой доступ к диску между двумя попытками) вы не увидите, как загорается свет, и вы не будете ждать. Операционная система проверила в кэше своей памяти дискету и нашла то, что искала. Таким образом, вместо того, чтобы ждать 20 секунд, данные были найдены в подсистеме памяти намного быстрее, чем при первой попытке (один доступ к гибкому диску занимает 120 миллисекунд, а один доступ к основной памяти занимает около 60 наносекунд — это много). Быстрее). Вы могли бы запустить тот же тест на жестком диске, но он более заметен на дисководе, потому что он очень медленный.

Чтобы дать вам общую картину, вот список обычных систем кэширования:

Кэш L1: доступ к памяти осуществляется на полной скорости микропроцессора (10 наносекунд, размер от 4 до 16 килобайт).
Кэш L2 – доступ к памяти типа SRAM (от 20 до 30 наносекунд, размер от 128 до 512 КБ)
Основная память — доступ к памяти типа RAM (около 60 наносекунд, размер от 32 МБ до 128 МБ).
Жесткий диск — механический, медленный (около 12 миллисекунд, размер от 1 ГБ до 10 ГБ)
Интернет – невероятно медленный (от 1 секунды до 3 дней, неограниченный размер)

Как видите, кэш L1 кэширует кэш L2, в котором кэшируется основная память, которую можно использовать для кэширования дисковых подсистем и т. д.

Кэш-память — это специальная память с очень высокой скоростью. Он используется для ускорения и синхронизации с высокоскоростным процессором. Кэш-память дороже, чем основная память или дисковая память, но экономичнее, чем регистры ЦП. Кэш-память — это чрезвычайно быстрый тип памяти, который действует как буфер между оперативной памятью и процессором. Он содержит часто запрашиваемые данные и инструкции, поэтому при необходимости они немедленно доступны ЦП.

Кэш-память используется для сокращения среднего времени доступа к данным из основной памяти. Кэш — это меньшая по размеру и более быстрая память, в которой хранятся копии данных из часто используемых ячеек основной памяти. В процессоре есть различные независимые кэши, в которых хранятся инструкции и данные.

Уровень 1 или регистр.
Это тип памяти, в которой хранятся и принимаются данные, которые немедленно сохраняются в ЦП. Наиболее часто используемые регистры — это аккумулятор, программный счетчик, адресный регистр и т. д.
Уровень 2 или кэш-память.
Это самая быстрая память с более быстрым временем доступа, в которой данные временно сохраняются для более быстрого доступа.
Уровень 3 или основная память.
Это память, в которой компьютер работает в данный момент. Она небольшого размера, и после отключения питания данные больше не остаются в этой памяти.
Уровень 4 или вторичная память.
Это внешняя память, которая не так быстра, как основная память, но данные постоянно остаются в этой памяти.

Производительность кэша.
Когда процессору необходимо прочитать или записать ячейку в основной памяти, он сначала проверяет наличие соответствующей записи в кэше.

Если процессор обнаруживает, что область памяти находится в кеше, происходит попадание в кеш и данные считываются из кеша.
Если процессор не находит область памяти в кэше, это означает, что кэш промахнулся. При промахе кэш выделяет новую запись и копирует данные из основной памяти, после чего запрос выполняется из содержимого кэша.

Производительность кэш-памяти часто измеряется показателем, называемым коэффициентом попаданий.

Мы можем улучшить производительность кеша, используя больший размер блока кеша, более высокую ассоциативность, снижение частоты промахов, снижение штрафа за промахи и сокращение времени попадания в кеш.

Для доступа к кешу каждый адрес основной памяти можно рассматривать как состоящий из трех полей. Младшие значащие биты w идентифицируют уникальное слово или байт в блоке основной памяти. В большинстве современных машин адрес находится на уровне байтов. Остальные s битов определяют один из 2 s блоков основной памяти. Логика кэша интерпретирует эти s битов как тег из s-r битов (самая значащая часть) и линейное поле из r битов. Это последнее поле идентифицирует одну из m=2 r строк кэша.

В этом случае кэш состоит из нескольких наборов, каждый из которых состоит из определенного количества строк. Отношения

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

Первичный кэш.
Первичный кэш всегда располагается на микросхеме процессора. Этот кеш небольшой, а время доступа к нему сравнимо со временем доступа к регистрам процессора.
Вторичный кэш.
Вторичный кэш размещается между основным кешем и остальной частью памяти. Он называется кэшем второго уровня (L2).Часто кэш-память 2-го уровня также размещается на микросхеме процессора.

Локальность ссылки –
Поскольку размер кэш-памяти меньше по сравнению с основной памятью. Таким образом, проверка того, какая часть основной памяти должна быть приоритетной и загружена в кеш, решается на основе локальности ссылки.

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

Практические вопросы по GATE –

Очередь-1: компьютер имеет 256-килобайтный, 4-канальный набор ассоциативных кэш-памятей данных обратной записи с размером блока 32 байта. Процессор отправляет 32-битные адреса контроллеру кеша. Каждая запись каталога тегов кэша содержит, помимо адресного тега, 2 допустимых бита, 1 измененный бит и 1 бит замены. Количество битов в поле тега адреса равно

Вопрос-2: рассмотрите данные, приведенные в предыдущем вопросе. Размер каталога тегов кеша

Очередь 3. Кэш прямого отображения с обратной записью объемом 8 КБ организован в виде нескольких блоков, каждый из которых имеет размер 32 байта. Процессор генерирует 32-битные адреса. Контроллер кэша поддерживает информацию тега для каждого блока кэша, состоящую из следующего.

Столько битов, сколько минимум необходимо для идентификации блока памяти, отображаемого в кэше. Каков общий объем памяти, необходимый контроллеру кеша для хранения метаданных (тегов) для кеша?

Статья предоставлена Пуджей Танеджей и Вайшали Бхатиа. Пожалуйста, пишите комментарии, если вы обнаружите что-то неверное или хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

Кэширование памяти (часто называемое просто кэшированием) – это метод, при котором компьютерные приложения временно сохраняют данные в основной памяти компьютера (т. е. в оперативной памяти или ОЗУ), чтобы обеспечить быстрое извлечение этих данных. Оперативная память, используемая для временного хранения, называется кешем. Поскольку доступ к ОЗУ значительно быстрее, чем доступ к другим носителям, таким как жесткие диски или сети, кэширование помогает приложениям работать быстрее благодаря более быстрому доступу к данным. Кэширование особенно эффективно, когда приложение демонстрирует общий шаблон, в котором оно неоднократно обращается к данным, к которым обращались ранее. Кэширование также полезно для хранения вычислений данных, которые в противном случае требуют много времени для вычислений. Сохраняя вычисления в кэше, система экономит время, избегая повторения вычислений.

Обзор кэширования памяти

Как работает кэширование памяти?

При кэшировании памяти сначала выделяется часть оперативной памяти, которая будет использоваться в качестве кэша. Когда приложение пытается прочитать данные, обычно из системы хранения данных, такой как база данных, оно проверяет, существует ли уже нужная запись в кэше. Если это так, то приложение будет считывать данные из кеша, тем самым устраняя более медленный доступ к базе данных. Если нужной записи нет в кеше, то приложение считывает запись из источника. Когда он извлекает эти данные, он также записывает данные в кеш, чтобы, когда приложению потребуются те же данные в будущем, оно могло быстро получить их из кеша.

Поскольку размер кеша ограничен, со временем некоторые данные, уже находящиеся в кеше, придется удалить, чтобы освободить место для новых данных, к которым приложение обращалось последним. Это означает, что системе кэширования нужна стратегия удаления записей для освобождения места. Стратегия будет зависеть от характера доступа к данным приложения и, как правило, будет пытаться удалить записи, к которым не ожидается повторного доступа в ближайшее время. Например, стратегия наименее недавно использованных (LRU) удалит запись, последний доступ к которой был до любой другой записи в кэше. Здесь предполагается, что если с момента доступа к записи прошло много времени, то, скорее всего, к ней скоро не будут обращаться снова. Или, другими словами, записи, которые чаще всего использовались в последнее время, скорее всего, скоро будут использоваться снова. Стратегия наименее часто используемого (LFU) предполагает отслеживание количества обращений к каждой записи в кэше и удаление записи с наименьшим количеством обращений. Здесь предполагается, что редко используемая запись вряд ли будет использоваться снова в ближайшее время.

Проблема с кешем заключается в том, как свести к минимуму «промахи кеша», т. е., попытка чтения приложением записей, которых нет в кеше. Если у вас слишком много промахов, эффективность вашего кеша снижается. Приложение, которое только читает новые данные, не выиграет от кеша и фактически будет демонстрировать более низкую производительность из-за дополнительной работы по проверке кеша, но не находит в нем нужную запись. Одним из способов решения этой проблемы является использование больших кешей. Это часто нецелесообразно на одном компьютере, поэтому распределенные кэши являются популярным выбором для ускорения работы приложений, которым необходим доступ к большим наборам данных. Распределенный кэш-память объединяет оперативную память нескольких компьютеров, подключенных к кластеру, так что вы можете создать больший кэш, который может продолжать расти, добавляя в кластер новые компьютеры. Такие технологии, как Hazelcast IMDG, можно использовать в качестве распределенного кластера для ускорения крупномасштабных приложений.

Еще одна проблема кеша — это риск чтения "устаревших" данных, когда данные в кеше не отражают последние данные в базовом источнике. Часто этот риск является приемлемым компромиссом ради производительности приложения. В тех случаях, когда это не так, приложение, которое обновляет базовый источник данных, должно обновить соответствующую запись в кэше.

Примеры использования

Одним из широких вариантов использования кэширования в памяти является ускорение работы приложений баз данных, особенно тех, которые выполняют много операций чтения из базы данных. Заменяя часть операций чтения базы данных операциями чтения из кэша, приложения могут устранить задержку, возникающую при частом доступе к базе данных. Этот вариант использования обычно встречается в средах, где наблюдаются большие объемы доступа к данным, например, на веб-сайте с высоким трафиком, который содержит динамический контент из базы данных.

Другой вариант использования включает ускорение запросов, при котором результаты сложного запроса к базе данных сохраняются в кэше. Выполнение сложных запросов, выполняющих такие операции, как группировка и упорядочивание, может занять значительное время. Если запросы выполняются повторно, как в случае с информационной панелью бизнес-аналитики (BI), к которой обращаются многие пользователи, сохранение результатов в кэше повысит скорость отклика этих информационных панелей.

Кэш-память играет ключевую роль в компьютерах. Фактически, все современные компьютерные системы, включая настольные ПК, серверы в корпоративных центрах обработки данных и облачные вычислительные ресурсы, имеют небольшие объемы очень быстрой статической оперативной памяти (SRAM), расположенной очень близко к центральному процессору (ЦП). Эта память называется кэш-памятью.

Несмотря на свой небольшой размер по сравнению с основной памятью (ОЗУ) или дополнительной памятью (ресурсами хранения), кэш-память оказывает огромное влияние на общую производительность системы.

Что такое кэш-память?

Компьютерные системы оснащены жесткими дисками или твердотельными накопителями (SSD) для обеспечения большой емкости и долговременного хранения данных, а также оперативной памятью, которая используется для хранения данных и программного кода, которые центральный процессор использует или собирается использовать. понадобится в самое ближайшее время. Оперативная память намного быстрее, чем жесткий диск или хранилище SSD. Обычно он состоит из динамической памяти с произвольным доступом (DRAM), которая также дороже в пересчете на гигабайт или сохраненные данные.

Но ЦП работает намного быстрее, чем ОЗУ, поэтому иногда ему приходится ждать, пока инструкции или данные считываются из ОЗУ, прежде чем он сможет продолжить обработку, что снижает общую производительность компьютерной системы.

Чтобы этого не происходило, компьютерные системы обычно оснащаются кэш-памятью: небольшим объемом динамической памяти с произвольным доступом (DRAM), которая является очень быстрой, но очень дорогой и расположена очень близко к самому ЦП.

В этой кэш-памяти хранятся данные или инструкции, которые процессор может использовать в ближайшем будущем. Поскольку это избавляет ЦП от ожидания, для повышения производительности чтения используется кэширование.

Кэш-память и производительность

Кэш-память повышает производительность компьютера. Кэш-память расположена очень близко к ЦП, либо на самом чипе ЦП, либо на материнской плате в непосредственной близости от ЦП и соединена специальной шиной данных. Таким образом, инструкции и данные могут быть прочитаны из него (и записаны в него) гораздо быстрее, чем в случае с обычной оперативной памятью.

Это означает, что процессор с меньшей вероятностью будет вынужден ждать — или время ожидания будет значительно сокращено. В результате очень небольшой объем кэш-памяти может привести к значительному увеличению производительности компьютера.

Как работает кэш-память?

Кэш-память работает, беря данные или инструкции по определенным адресам памяти в ОЗУ и копируя их в кэш-память вместе с записью исходного адреса этих инструкций или данных.

В результате получается таблица, содержащая небольшое количество адресов оперативной памяти и копии инструкций или данных, содержащихся в этих адресах оперативной памяти.

Кэш памяти «сработал»

Когда процессору требуются инструкции или данные из заданного адреса ОЗУ, то, прежде чем извлекать их из ОЗУ, он проверяет, содержит ли кэш-память ссылку на этот адрес ОЗУ. Если это так, то он считывает соответствующие данные или инструкции из кэш-памяти, а не из ОЗУ. Это известно как «попадание в кэш». Поскольку кэш-память быстрее, чем ОЗУ, и поскольку она расположена ближе к центральному процессору, она может получить и начать обработку инструкций и данных намного быстрее.

Та же процедура выполняется, когда данные или инструкции необходимо записать обратно в память. Однако в этом случае есть дополнительный шаг, потому что если что-то записывается в кэш-память, то в конечном итоге это также должно быть записано в ОЗУ.

Как это делается, зависит от политики записи кеша. Простейшая политика называется сквозной записью: при этой политике все, что записывается в кеш памяти, сразу же записывается в ОЗУ.

Альтернативная политика — «обратная запись». Используя политику «обратной записи», данные, записываемые в кэш-память, теперь сразу же записываются и в ОЗУ. Все, что записывается в кэш-память, помечается как «грязное», что означает, что оно отличается от исходных данных или инструкций, которые были считаны из ОЗУ. Когда она удаляется из кэш-памяти, то и только тогда она записывается в оперативную память, заменяя исходную информацию.

Промежуточные политики позволяют ставить «грязную» информацию в очередь и записывать обратно в ОЗУ в пакетном режиме, что может быть более эффективным, чем многократная запись по отдельности.

Кэш памяти «промах»

Если данные или инструкции по заданному адресу оперативной памяти не найдены в кэш-памяти, это называется «промахом кэша». В этом случае ЦП вынужден ждать, пока информация извлекается из ОЗУ.

На самом деле данные или инструкции извлекаются из ОЗУ и записываются в кэш-память, а затем отправляются в ЦП. Причина этого в том, что данные или инструкции, которые недавно использовались, скорее всего, снова потребуются в ближайшем будущем. Таким образом, все, что ЦП запрашивает из ОЗУ, всегда копируется в кэш-память.

(Есть исключение. Некоторые данные редко используются повторно, их можно пометить как некэшируемые. Это предотвращает ненужное занятие ценного пространства кэш-памяти данными.)

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

Если необходимо принять решение, кэш памяти применит «политику замены», чтобы решить, какая информация будет вытеснена.

Существует несколько возможных политик замены. Одной из наиболее распространенных является политика наименее использовавшихся (LRU). В этой политике используется принцип, согласно которому, если данные или инструкции не использовались в последнее время, то они с меньшей вероятностью потребуются в ближайшем будущем, чем данные или инструкции, которые потребовались совсем недавно.

Ключевое значение кэш-памяти

Кэш-память необходима для устранения узких мест производительности между ОЗУ и ЦП. Его использование аналогично использованию оперативной памяти в качестве дискового кеша. В этом случае часто используемые данные, хранящиеся во вторичных системах хранения (таких как жесткие диски или твердотельные накопители), временно помещаются в оперативную память, где ЦП может получить к ним доступ гораздо быстрее.

Поскольку ОЗУ дороже (но быстрее), чем вторичное хранилище, дисковые кэши меньше, чем жесткие диски или твердотельные накопители. Поскольку SRAM дороже (но быстрее), чем DRAM, кэши памяти меньше, чем RAM.

Типы кэш-памяти

Первичный кэш Большая часть кэш-памяти физически расположена на том же кристалле, что и сам ЦП, а часть, ближайшая к ядрам ЦП, иногда называется первичным кэшем, хотя этот термин больше не используется.

Вторичная кэш-память Часто это относится к дополнительной части кэш-памяти, расположенной на отдельной микросхеме материнской платы рядом с процессором. Этот термин также больше не используется, поскольку большая часть кэш-памяти теперь расположена на самом кристалле ЦП.

Уровни кэш-памяти

Современные компьютерные системы имеют более одной части кэш-памяти, и эти кэши различаются по размеру и близости к ядрам процессора, а значит, и по скорости. Они известны как уровни кэша.

Самая маленькая и самая быстрая кэш-память — это кэш-память 1-го уровня, или кэш-память L1, а следующей является кэш-память L2. Большинство систем теперь имеют кэш-память L3, а с момента появления чипов Skylake Intel также добавила кэш-память L4 в некоторые из своих процессоров.

Уровень 1

Кэш L1 — это кэш-память, встроенная в сам ЦП. Он работает на той же тактовой частоте, что и процессор. Это самый дорогой тип кэш-памяти, поэтому его размер крайне ограничен.Но поскольку он очень быстрый, это первое место, где процессор будет искать данные или инструкции, которые могли быть буферизованы там из ОЗУ.

На самом деле в большинстве современных процессоров кэш L1 разделен на две части: раздел данных (L1d) и раздел инструкций (L1i). Они содержат данные и инструкции соответственно.

Современный ЦП может иметь размер кэша порядка 32 КБ L1i и L1d на ядро.

Уровень 2

Кэш L2 также может располагаться в микросхеме ЦП, хотя и не так близко к ядру, как кэш L1. Или, что реже, он может быть расположен на отдельном чипе рядом с процессором. Кэш L2 дешевле и больше, чем кэш L1, поэтому размер кэша L2, как правило, больше и может составлять порядка 256 КБ на ядро.

Уровень 3

Кэш уровня 3, как правило, намного больше, чем кэш L1 или L2, но он также отличается еще одним важным аспектом. В то время как кэши L1 и L2 являются частными для каждого ядра процессора, кэш L3, как правило, является общим кешем, общим для всех ядер. Это позволяет ему играть важную роль в обмене данными и межъядерной связи. Кэш L3 может иметь размер порядка 2 МБ на ядро.

Отображение кэша

Кэш-память, как уже говорилось, чрезвычайно быстра, то есть ее можно очень быстро считывать.

Но существует потенциальное узкое место: прежде чем данные можно будет считать из кэш-памяти, их необходимо найти. Процессор знает адрес оперативной памяти данных или инструкции, которую он хочет прочитать. Он должен искать в кеше памяти, чтобы увидеть, есть ли ссылка на этот адрес ОЗУ в кеше памяти вместе со связанными данными или инструкциями.

Существует несколько способов отображения данных или инструкций из ОЗУ в кэш памяти, и они напрямую влияют на скорость, с которой их можно найти. Но есть компромисс: минимизация времени поиска также сводит к минимуму вероятность попадания в кеш, а максимизация вероятности попадания в кеш увеличивает вероятное время поиска.

Обычно используются следующие методы сопоставления кеша:

Прямое сопоставление

При использовании кеша с прямым отображением существует только одно место в кэш-памяти, в котором может храниться данный блок данных из ОЗУ.

Это означает, что ЦП должен заглянуть только в одно место в кэше памяти, чтобы увидеть, присутствуют ли данные или инструкции, которые он ищет, и если это так, они будут найдены очень быстро. Недостаток кэша с прямым отображением заключается в том, что он сильно ограничивает объем данных или инструкций, которые могут храниться в кэше памяти, поэтому попадания в кэш случаются редко.

Ассоциативное сопоставление

Также известное как полностью связанное сопоставление, оно противоположно прямому сопоставлению. При ассоциативной схеме отображения любой блок данных или инструкций из ОЗУ можно поместить в любой блок кэш-памяти. Это означает, что ЦП должен просмотреть всю кэш-память, чтобы увидеть, содержит ли она то, что он ищет, но вероятность попадания в кеш гораздо выше.

Набор-ассоциативное сопоставление

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

Поиск в двухсторонней системе занимает в два раза больше времени, чем в системе с прямым сопоставлением, поскольку ЦП должен искать в двух местах, а не только в одном, но вероятность попадания в кеш гораздо выше.

Целью этого модуля является обсуждение основ кэш-памяти. Мы обсудим различные политики сопоставления, а также обсудим политики чтения/записи. По сути, будут даны ответы на четыре основных вопроса, касающихся размещения блоков, идентификации блоков, замены блоков и стратегии записи.

Скорость основной памяти очень низкая по сравнению со скоростью современных процессоров. Для обеспечения хорошей производительности процессор не должен тратить много времени на ожидание доступа к инструкциям и данным в основной памяти. Следовательно, важно разработать схему, которая сокращает время, необходимое для доступа к необходимой информации. Поскольку скорость блока основной памяти ограничена электронными и корпусными ограничениями, решение необходимо искать в другой архитектурной компоновке. Эффективным решением является использование быстрой кэш-памяти, благодаря которой основная память кажется процессору более быстрой, чем она есть на самом деле. Кэш — это меньшая по размеру и более быстрая память, в которой хранятся копии данных из наиболее часто используемых ячеек основной памяти. Поскольку большинство обращений к памяти осуществляется в области кэшированной памяти, средняя задержка доступа к памяти будет ближе к задержке кэша, чем к задержке основной памяти.

Эффективность механизма кэширования основана на свойстве компьютерных программ, которое называется локальность ссылки. Анализ программ показывает, что большая часть времени их выполнения тратится на подпрограммы, в которых многие инструкции выполняются многократно.Эти инструкции могут представлять собой простой цикл, вложенные циклы или несколько процедур, которые многократно вызывают друг друга. Фактическая подробная схема последовательности инструкций не важна — дело в том, что многие инструкции в локализованных областях программы выполняются многократно в течение некоторого периода времени, а к остальной части программы обращаются относительно редко. Это называется локальностью ссылки. Она проявляется двумя способами: временным и пространственным. Первый означает, что недавно выполненная инструкция, скорее всего, будет выполнена снова очень скоро. Пространственный аспект означает, что инструкции, находящиеся в непосредственной близости от недавно выполненной инструкции (относительно адресов инструкций), также могут быть выполнены в ближайшее время.

Если активные сегменты программы можно разместить в быстрой кэш-памяти, то общее время выполнения можно значительно сократить. Концептуально работа с кэш-памятью очень проста. Схема управления памятью предназначена для использования преимущества локальности ссылок. Временной аспект локальности ссылки предполагает, что всякий раз, когда информационный элемент (инструкция или данные) требуется впервые, этот элемент должен быть помещен в кэш, где он, как мы надеемся, останется до тех пор, пока он снова не понадобится. Пространственный аспект предполагает, что вместо того, чтобы извлекать только один элемент из основной памяти в кэш, полезно извлекать несколько элементов, которые также находятся по соседним адресам. Мы будем использовать термин блок для обозначения набора смежных адресов определенного размера. Другой термин, который часто используется для обозначения блока кеша, – кэш-строка

Кэш-память, включенная в иерархию памяти, может быть разделенной или объединенной/двойной. Разделенный кеш — это тот, в котором у нас есть отдельный кеш данных и отдельный кеш инструкций. Здесь два кеша работают параллельно, один передает данные, а другой передает инструкции. Двойной или унифицированный кеш — это когда данные и инструкции хранятся в одном и том же кеше. Комбинированный кеш с общим размером, равным сумме двух разделенных кешей, обычно имеет более высокую частоту попаданий. Эта более высокая скорость возникает из-за того, что комбинированный кэш не разделяет жестко количество записей, которые могут использоваться инструкциями, от тех, которые могут использоваться данными. Тем не менее, многие процессоры используют разделенный кэш инструкций и данных для увеличения пропускной способности кэша.

Когда от процессора поступает запрос на чтение, содержимое блока слов памяти, содержащих указанное местоположение, передается в кэш. Впоследствии, когда программа обращается к любому из мест в этом блоке, желаемое содержимое считывается непосредственно из кэша. Обычно кэш-память может хранить разумное количество блоков в любой момент времени, но это число мало по сравнению с общим количеством блоков в основной памяти. Соответствие между блоками основной памяти и блоками в кэше задается функцией сопоставления. Когда кэш заполнен и имеется ссылка на слово памяти (инструкцию или данные), которого нет в кэше, Аппаратное обеспечение управления кешем должно решить, какой блок следует удалить, чтобы освободить место для нового блока, содержащего указанное слово. Набор правил для принятия этого решения составляет алгоритм замены

Поэтому три основные проблемы, которые должны решаться в кэш-памяти:

· Размещение кеша – куда вы помещаете блок в кеше?

· Идентификация кеша – как определить, доступна ли запрошенная информация в кеше или нет?

· Замена кеша — какой блок будет заменен в кеше, освобождая место для входящего блока?

На эти вопросы даны ответы и пояснения на примере размера основной памяти 1 МБ (адрес основной памяти — 20 бит), кэш-памяти размером 2 КБ и размера блока 64 байта. Поскольку размер блока составляет 64 байта, сразу видно, что в основной памяти 214 блоков, а в кэше 25 блоков. То есть 16 КБ блоков основной памяти должны быть сопоставлены с 32 блоками кэша. Существует три различных политики сопоставления: прямое сопоставление, полностью ассоциативное сопоставление и ассоциативное сопоставление с n-путями, которые используются. Они обсуждаются ниже.

Прямое сопоставление. Это самый простой метод сопоставления. В этом методе блок i основной памяти сопоставляется с блоком j по модулю (количество блоков в кэше) кэша. В нашем примере это блок j mod 32. То есть первые 32 блока основной памяти отображаются на соответствующие 32 блока кэша, 0 на 0, 1 на 1, … и 31 на 31. И помните, что у нас есть всего 32 блока в кеше. Таким образом, следующие 32 блока основной памяти также отображаются на те же соответствующие блоки кэша. Таким образом, 32 снова сопоставляется с блоком 0 в кеше, 33 — с блоком 1 в кеше и так далее. То есть блоки основной памяти сгруппированы в группы по 32 блока, и каждая из этих групп будет отображаться на соответствующие блоки кэша.Например, всякий раз, когда один из блоков основной памяти 0, 32, 64, … загружается в кэш, он сохраняется только в блоке кэша 0. Таким образом, в любой момент времени, если какой-либо другой блок занимает блок кэша, который удаляется, а другой блок сохраняется. Например, если мы хотим ввести блок 64, а блок 0 уже доступен в кэше, блок 0 удаляется и вставляется блок 64. Точно так же блоки 1, 33, 65, … хранятся в блоке кэша 1, и скоро. Вы можете легко увидеть, что 29 блоков основной памяти будут отображены на один и тот же блок в кеше. Поскольку на данную позицию блока кэша отображается более одного блока памяти, может возникнуть конкуренция за эту позицию, даже если кэш не заполнен. То есть блоки, имеющие право занимать один и тот же блок кэша, могут конкурировать за блок. Например, если процессор попеременно обращается к инструкциям из блоков 0 и 32, возникнут конфликты, даже если кэш-память не заполнена. Конфликт разрешается, позволяя новому блоку перезаписывать текущий резидентный блок. Таким образом, в этом случае алгоритм замены тривиален. Другого места для размещения блока нет. Таким образом, он должен заменить только текущий резидентный блок.

Размещение блока в кеше определяется по адресу памяти. Адрес памяти можно разделить на три поля, как показано на рис. 26.1. Младшие 6 бит выбирают одно из 64 слов в блоке. Когда новый блок поступает в кеш, 5-битное поле блока кеша определяет позицию кеша, в которой должен храниться этот блок. Старшие 9 бит адреса памяти блока хранятся в 9 битах тега, связанных с его расположением в кэше. Они определяют, какой из 29 блоков, которые могут быть отображены в эту позицию кэша, в настоящее время находится в кэше. Поскольку адрес основной памяти сгенерирован, в первую очередь проверьте поле блока. Это укажет на блок, который вы должны проверить. Теперь проверьте поле тега. Если они совпадают, блок доступен в кеше и считается попаданием. В противном случае это промах. Затем блок, содержащий искомое слово, должен быть сначала прочитан из основной памяти и загружен в кэш. Как только блок будет идентифицирован, используйте поле слова, чтобы выбрать одно из 64 слов. Обратите внимание, что поле слова не участвует в отображении.

Рисунок 26.1 Прямое сопоставление

Рассмотрите адрес 78F28, который равен 0111 1000 1111 0010 1000. Теперь, чтобы проверить, находится ли блок в кеше или нет, разделите его на три поля: 011110001 11100 101000. Поле блока указывает, что вы должны проверить блок 28. Теперь проверьте поле девятибитного тега. Если они совпадают, это попадание.

Технику прямого сопоставления легко реализовать. Количество проверяемых записей тега равно только одному, и длина поля тега также меньше. Алгоритм замены очень прост. Однако он не очень гибкий. Даже если кеш не заполнен, вам, возможно, придется много переключаться между основной памятью и кешем из-за жесткой политики сопоставления.

Полностью ассоциативное сопоставление: это гораздо более гибкий метод сопоставления, при котором блок основной памяти может быть помещен в любую позицию блока кэша. Это указывает на то, что нет необходимости в блочном поле. В этом случае для идентификации блока памяти, когда он находится в кэше, требуется 14 бит тега. Это показано на рисунке 5.8. Биты тега адреса, полученного от процессора, сравниваются с битами тега каждого блока кэша, чтобы увидеть, присутствует ли желаемый блок. Это называется методом ассоциативного сопоставления. Это дает полную свободу в выборе места кэш-памяти для размещения блока памяти. Таким образом, пространство в кеше можно использовать более эффективно. Новый блок, который должен быть помещен в кеш, должен заменить (извлечь) существующий блок только в том случае, если кеш заполнен. В этом случае нам нужен алгоритм выбора блока для замены. Обычно используются случайные алгоритмы, FIFO и LRU. Случайная замена делает случайный выбор удаляемого блока. FIFO удаляет самый старый блок без учета шаблонов доступа к памяти. Значит, это не очень эффективно. С другой стороны, наименее используемый метод учитывает шаблоны доступа и удаляет блок, на который не ссылались в течение самого длительного периода. Это очень эффективно.

Таким образом, ассоциативное сопоставление является полностью гибким. Но стоимость ассоциативного кеша выше, чем стоимость кеша с прямым отображением, из-за необходимости искать все шаблоны тегов, чтобы определить, находится ли данный блок в кеше. Это должен быть ассоциативный поиск, как обсуждалось в предыдущем разделе. Также обратите внимание, что длина тега увеличивается. То есть увеличивается как количество тегов, так и длина тега. Замена тоже сложная. Следовательно, это практически невозможно.

Рис. 26.2. Полностью ассоциативное сопоставление

Установить ассоциативное сопоставление: это компромисс между двумя вышеупомянутыми методами.Блоки кэша сгруппированы в наборы, состоящие из n блоков, и отображение позволяет блоку основной памяти находиться в любом блоке определенного набора. Это также называется ассоциативным отображением n-way set. Следовательно, проблема конкуренции прямого метода облегчается наличием нескольких вариантов размещения блоков. При этом стоимость оборудования снижается за счет уменьшения размера ассоциативного поиска. В нашем примере адрес основной памяти для метода ассоциативного отображения наборов показан на рис. 26.3 для кэша с двумя блоками на набор (двустороннее ассоциативное отображение наборов). В тайнике 16 наборов. В этом случае блоки памяти 0, 16, 32... отображаются в набор кэш-памяти 0, и они могут занимать любую из двух позиций блоков в этом наборе. Наличие 16 наборов означает, что 4-битное поле набора адреса определяет, какой набор кэша может содержать нужный блок. Затем 11-битное поле тега адреса необходимо ассоциативно сравнить с тегами двух блоков набора, чтобы проверить, присутствует ли нужный блок. Этот двусторонний ассоциативный поиск прост в реализации и сочетает в себе преимущества обоих других методов. На самом деле это можно рассматривать как общий случай; когда n равно 1, оно становится прямым отображением; когда n — количество блоков в кеше, это ассоциативное сопоставление.

< /tr>

Тег	Set	Word
11	4	6

Рисунок 26.3. Установка ассоциативного сопоставления

Еще один управляющий бит, называемый верным битом, должен быть предоставлен для каждого блока. Этот бит указывает, содержит ли блок допустимые данные. Его не следует путать с модифицированным или грязным битом, упомянутым ранее. Грязный бит, который указывает, был ли блок изменен во время его пребывания в кэше, необходим только в системах, которые не используют метод сквозной записи. Все действительные биты устанавливаются в 0 при первоначальном включении питания в систему или при загрузке основной памяти новыми программами и данными с диска. Передачи с диска в оперативную память осуществляются по механизму прямого доступа к памяти. Обычно они обходят кеш как по соображениям стоимости, так и по соображениям производительности. Действительный бит конкретного блока кэша устанавливается равным 1 при первой загрузке этого блока из основной памяти. Всякий раз, когда блок основной памяти обновляется источником, который обходит кэш, выполняется проверка, чтобы определить, загружается ли блок сейчас находится в кэше. Если это так, его допустимый бит сбрасывается до 0. Это гарантирует, что устаревшие данные не будут существовать в кэше.

Аналогичная трудность возникает, когда DMA-передача производится из основной памяти на диск, а кеш использует протокол обратной записи. В этом случае данные в памяти могут не отражать изменения, внесенные в кэшированную копию. Одним из решений этой проблемы является очистка кеша путем принудительной записи грязных данных обратно в память до передачи DMA. Операционная система может это сделать легко, и это не сильно влияет на производительность, потому что такие переносы диска происходят не часто. Необходимость обеспечения того, чтобы два разных объекта (в данном случае процессор и подсистема прямого доступа к памяти) использовали одни и те же копии данных, называется проблемой когерентности кэша.

Политики чтения/записи. Наконец, нам нужно также обсудить применяемые политики чтения/записи. Процессору не нужно явно знать о существовании кеша. Он просто выдает запросы на чтение и запись, используя адреса, которые относятся к ячейкам в памяти. Схема управления кешем определяет, существует ли запрошенное слово в данный момент в кеше. Если это так, операция чтения или записи выполняется в соответствующем месте кэша. В этом случае считается, что произошло чтение или запись. При операции чтения не происходит никаких изменений, поэтому основная память не затрагивается. При попадании записи система может действовать двумя способами. В первом методе, называемом протоколом сквозной записи, местоположение кэша и местоположение основной памяти обновляются одновременно. Второй метод заключается в обновлении только местоположения кеша и пометке его как обновленного соответствующим битом флага, часто называемым битом dirty или modified. Местоположение слова в основной памяти обновляется позже, когда блок, содержащий это отмеченное слово, должен быть удален из кэша, чтобы освободить место для нового блока. Этот метод известен как протокол обратной записи или обратного копирования. Протокол сквозной записи проще, но он приводит к ненужным операциям записи в основную память, когда данное слово кэша обновляется несколько раз в течение его пребывания в кэше.Обратите внимание, что протокол обратной записи также может привести к ненужным операциям записи, потому что, когда блок кеша записывается обратно в память, все слова блока записываются обратно, даже если было изменено только одно слово, пока блок находился в кеше. . Этого можно избежать, если поддерживать большее количество грязных битов на блок. Если во время операции записи адресованное слово отсутствует в кэше, происходит промах записи. Затем, если используется протокол сквозной записи, информация записывается непосредственно в основную память. В случае протокола обратной записи блок, содержащий адресованное слово, сначала помещается в кэш, а затем требуемое слово в кэше перезаписывается новой информацией.

Когда происходит промах записи, мы используем политику выделения памяти для записи или политику запрета записи. То есть, если мы используем политику обратной записи для обращений по записи, то блок все равно попадает в кеш (write allocate) и устанавливается грязный бит. С другой стороны, если используется политика сквозной записи, то блок не выделяется в кеш, и изменения происходят сразу в основной памяти.

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

Подводя итог, мы обсудили потребность в кэш-памяти. Мы рассмотрели различные вопросы, связанные с кэш-памятью, а именно, политики размещения, политики замены и политики чтения/записи. Прямое отображение является самым простым в реализации. В кэше с прямым отображением блок кэша доступен до того, как будет определено, является ли это попаданием или промахом, поскольку можно предположить попадание, продолжить и восстановить позже, если это промах. Также требуется только один компаратор по сравнению с N компараторами для ассоциативного отображения n-путей. В случае заданного ассоциативного сопоставления для данных возникает дополнительная задержка MUX, и данные поступают только после определения того, попали они или нет. Однако операцию можно ускорить, параллельно сравнивая все теги в наборе и выбирая данные на основе результата тега. Ассоциативное сопоставление множеств более гибко, чем прямое сопоставление. Полное ассоциативное сопоставление является наиболее гибким, но и наиболее сложным в реализации и редко используется.

Веб-ссылки/вспомогательные материалы

Компьютерная организация и дизайн — аппаратно-программный интерфейс, Дэвид А. Паттерсон и Джон Л. Хеннесси, 4-е издание, Морган Кауфманн, Elsevier, 2009 г.
Компьютерная архитектура — количественный подход, Джон Л. Хеннесси и Дэвид А. Паттерсон, 5-е издание, Морган Кауфманн, Elsevier, 2011 г.
Computer Organization, Carl Hamacher, Zvonko Vranesic and Safwat Zaky, 5th. Edition, McGraw-Hill Higher Education, 2011.

Основы работы с кэш-памятью доктора А. П. Шанти распространяются по лицензии Creative Commons Attribution-NonCommercial 4.0 International License, если не указано иное.

Читайте также: