Кэш (вычисления) - Cache (computing) - Wikipedia

Схема работы кеш-памяти ЦП

В вычисление, а тайник (/kæʃ/ (Об этом звукеСлушать) каш,[1] или же /ˈkeɪʃ/ кайш в Австралийский английский[2]) - это аппаратный или программный компонент, который хранит данные, чтобы будущие запросы на эти данные могли обслуживаться быстрее; данные, хранящиеся в кэше, могут быть результатом более раннего вычисления или копией данных, хранящихся в другом месте. А попадание в кеш происходит, когда запрошенные данные могут быть найдены в кеше, а промах в кеше происходит, когда это невозможно. Попадания в кэш обслуживаются путем чтения данных из кеша, что быстрее, чем повторное вычисление результата или чтение из более медленного хранилища данных; таким образом, чем больше запросов может быть обработано из кеша, тем быстрее работает система.

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

Мотивация

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

В буферизация предоставляемый кешем, приносит пользу как задержка и пропускная способность (пропускная способность ):

Задержка

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

Пропускная способность

Использование кеша также позволяет повысить пропускную способность базового ресурса за счет объединения нескольких мелкозернистых передач в более крупные и более эффективные запросы. В случае DRAM цепей, это может быть выполнено за счет более широкой шины данных. Например, рассмотрим программу, обращающуюся к байтам в 32-битном адресное пространство, но обслуживается 128-битной внешней шиной данных; доступ к отдельным некэшированным байтам позволит использовать только 1/16 от общей полосы пропускания, а 80% перемещения данных будет осуществляться по адресам памяти, а не самим данным. Чтение больших фрагментов уменьшает долю полосы пропускания, необходимую для передачи адресной информации.

Операция

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

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

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

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

Во время промаха кэша некоторые другие ранее существовавшие записи кэша удаляются, чтобы освободить место для вновь полученных данных. В эвристический используется для выбора записи для замены, известной как политика замены. Одна популярная политика замещения, «наименее недавно использованная» (LRU), заменяет самую старую запись, запись, к которой обращались менее недавно, чем любая другая запись (см. алгоритм кеширования ). Более эффективные алгоритмы кэширования вычисляют частоту использования с учетом размера хранимого содержимого, а также задержки и пропускная способность как для кеша, так и для резервного хранилища. Это хорошо работает для больших объемов данных, больших задержек и более низкой пропускной способности, например, с жесткими дисками и сетями, но неэффективно для использования в кэше ЦП.[нужна цитата ]

Написание политики

Основная статья: Согласованность кеша
Кэш со сквозной записью без выделения для записи
Кэш обратной записи с распределением записи

Когда система записывает данные в кеш, она должна в какой-то момент записать и эти данные в резервное хранилище. Время этой записи контролируется так называемым написать политику. Есть два основных подхода к письму:[3]

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

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

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

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

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

Как политики сквозной записи, так и политики обратной записи могут использовать любую из этих политик пропуска записи, но обычно они объединяются следующим образом:[4]

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

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

Примеры аппаратных кешей

Кэш процессора

Основная статья: Кэш процессора

Небольшие воспоминания на или рядом с ЦПУ может работать быстрее, чем гораздо более крупный основная память. Большинство процессоров с 1980-х годов использовали один или несколько кешей, иногда в каскадных уровнях; современный high-end встроенный, рабочий стол и сервер микропроцессоры может иметь до шести типов кеша (между уровнями и функциями).[5] Примеры кешей с определенной функцией: D-кеш и I-cache и резервный буфер перевода для MMU.

Кэш GPU

Ранее графические процессоры (GPU) часто имели ограниченный доступ только для чтения кеши текстур, и представил Приказ Мортона взбитые текстуры улучшить 2D согласованность кеша. Кеш пропускает резко повлияет на производительность, например если mipmapping не использовался. Кэширование было важно для использования 32-битной (и более широкой) передачи данных текстуры, которая часто составляла всего 4 бита на пиксель, индексированных в сложных шаблонах произвольным образом. УФ-координаты и перспективные преобразования в обратное наложение текстуры.

По мере развития графических процессоров (особенно с ГПГПУ вычислить шейдеры ) они разработали все более крупные и все более общие кеши, включая кеши инструкций за шейдеры, демонстрируя все более общие функции с кешами ЦП.[6] Например, GT200 Архитектура графических процессоров не имела кеш-памяти L2, в то время как Ферми GPU имеет 768 КБ кеш-памяти последнего уровня, Кеплер GPU имеет 1536 КБ кеш-памяти последнего уровня,[6] и Максвелл GPU имеет 2048 КБ кэша последнего уровня. Эти тайники выросли, чтобы обрабатывать примитивы синхронизации между потоками и атомарные операции, и интерфейс в стиле ЦП MMU.

DSP

Цифровые сигнальные процессоры аналогичным образом обобщались на протяжении многих лет. Использовались более ранние конструкции блокнотная память питается DMA, но современные DSP, такие как Qualcomm Hexagon часто включают набор кешей, очень похожих на ЦП (например, Измененная архитектура Гарварда с общим L2, разделенным I-кешем L1 и D-кешем).[7]

Резервный буфер перевода

Основная статья: Резервный буфер перевода

А блок управления памятью (MMU), который извлекает записи таблицы страниц из основной памяти, имеет специальный кеш, используемый для записи результатов виртуальный адрес к Физический адрес переводы. Этот специализированный кеш называется резервный буфер перевода (TLB).[8]

Кэш в сети

Информационно-ориентированные сети

Информационно-ориентированные сети (ICN) - это подход к развитию Интернет инфраструктуру вдали от парадигмы, ориентированной на хост, основанной на постоянном подключении и сквозной принцип, к сетевой архитектуре, в которой центральным элементом является информация (или контент, или данные). Из-за присущей узлам в ICN способности кэширования его можно рассматривать как слабо связанную сеть кешей, которая имеет уникальные требования к политикам кэширования. Однако повсеместное кэширование контента создает проблему для защиты контента от несанкционированного доступа, что требует дополнительной осторожности и решений.[9]В отличие от прокси-серверов, в ICN кэш - это решение сетевого уровня. Следовательно, он имеет быстро меняющиеся состояния кеша и более высокую скорость поступления запросов; более того, меньшие размеры кэша дополнительно предъявляют различные требования к политикам вытеснения контента. В частности, политика выселения для ICN должна быть быстрой и легкой. Были предложены различные схемы репликации и вытеснения кэша для различных архитектур и приложений ICN.

Политики

Время с учетом наименее недавно использованного (TLRU)

Время с учетом наименее недавно использованного (TLRU)[10] - это вариант LRU, разработанный для ситуации, когда хранимое в кэше содержимое имеет допустимый срок службы. Алгоритм подходит для приложений сетевого кеширования, таких как информационные сети (ICN), Сети доставки контента (CDN) и распределенные сети в целом. TLRU вводит новый термин: TTU (время использования). TTU - это отметка времени контента / страницы, которая определяет время удобства использования для контента на основе местоположения контента и объявления издателя контента. Благодаря этой метке времени на основе местоположения, TTU предоставляет локальному администратору больше контроля для регулирования в сетевом хранилище. В алгоритме TLRU, когда поступает часть контента, узел кэша вычисляет локальное значение TTU на основе значения TTU, назначенного издатель контента. Локальное значение TTU рассчитывается с использованием локально определенной функции. После вычисления локального значения TTU замена содержимого выполняется на подмножестве общего содержимого, хранящегося в узле кэша. TLRU гарантирует, что менее популярный и небольшой жизненный контент должен быть заменен входящим контентом.

Наименее часто используемые в последнее время (LFRU)

Наименее часто используемые в последнее время (LFRU)[11] Схема замены кеша сочетает в себе преимущества схем LFU и LRU. LFRU подходит для приложений кэширования «в сети», таких как информационные сети (ICN), сети доставки контента (CDN) и распределенные сети в целом. В LFRU кэш разделен на два раздела, которые называются привилегированными и непривилегированными. Привилегированный раздел можно определить как защищенный. Если контент очень популярен, он помещается в привилегированный раздел. Замена привилегированного раздела выполняется следующим образом: LFRU вытесняет контент из непривилегированного раздела, перемещает контент из привилегированного раздела в непривилегированный раздел и, наконец, вставляет новый контент в привилегированный раздел. В приведенной выше процедуре LRU используется для привилегированного раздела, а приближенная схема LFU (ALFU) используется для непривилегированного раздела, отсюда и сокращение LFRU. Основная идея состоит в том, чтобы отфильтровать популярное локально содержимое с помощью схемы ALFU и протолкнуть популярное содержимое в один из привилегированных разделов.

Программные кеши

Дисковый кеш

Основная статья: Кеш страницы

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

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

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

Веб-кеш

Основная статья: Веб-кеш

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

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

Другой вид кеша - P2P кеширование, где файлы, наиболее востребованные пиринговый заявки хранятся в Интернет-провайдер кеш для ускорения передачи P2P. Точно так же существуют децентрализованные эквиваленты, которые позволяют сообществам выполнять ту же задачу для P2P-трафика, например, Corelli.[13]

Мемоизация

Основная статья: Мемоизация

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

Другие тайники

BIND DNS демон кэширует отображение доменных имен на IP-адреса, как и библиотека преобразователя.

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

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

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

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

А распределенный кеш[14] использует сетевые хосты для обеспечения масштабируемости, надежности и производительности приложения.[15] Хосты могут быть совмещены или распределены по разным географическим регионам.

Буфер против кеша

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ "Кэш". Оксфордские словари. Оксфордские словари. Получено 2 августа 2016.
  2. ^ "Кэш". Словарь Macquarie. Macmillan Publishers Group, Австралия, 2015 г.. Получено 21 июля 2015.[постоянная мертвая ссылка ]
  3. ^ Боттомли, Джеймс (1 января 2004 г.). «Понимание кеширования». Linux журнал. Получено 1 октября 2019.
  4. ^ Джон Л. Хеннесси; Дэвид А. Паттерсон (2011). Компьютерная архитектура: количественный подход. Эльзевир. С. B – 12. ISBN  978-0-12-383872-8.
  5. ^ "Intel Wide Well Core i7 с кэш-памятью L4 128 МБ".Упоминает кеш L4. В сочетании с отдельными I-Cache и TLB это увеличивает общее количество кешей (уровней + функций) до 6
  6. ^ а б С. Миттал "Обзор методов управления и использования кешей в графических процессорах ", JCSC, 23 (8), 2014.
  7. ^ "Обзор qualcom Hexagon DSP SDK".
  8. ^ Фрэнк Уеда (2009). «Лекция 7: Управление памятью» (PDF). CSE 120: Принципы операционных систем. Калифорнийский университет в Сан-Диего. Получено 4 декабря 2013.
  9. ^ Билал, Мухаммед; и другие. (2019). «Безопасное распространение защищенного контента в информационно-ориентированных сетях». Системный журнал IEEE: 1–12. arXiv:1907.11717. Bibcode:2019arXiv190711717B. Дои:10.1109 / JSYST.2019.2931813.
  10. ^ Билал, Мухаммед; и другие. (2017). «Политика управления кэшем с учетом времени с учетом наименее недавнего использования (TLRU) в ICN». IEEE 16-я Международная конференция по передовым коммуникационным технологиям (ICACT): 528–532. arXiv:1801.00390. Bibcode:2018arXiv180100390B. Дои:10.1109 / ICACT.2014.6779016. ISBN  978-89-968650-3-2.
  11. ^ Билал, Мухаммед; и другие. (2017). «Схема управления кешем для эффективного вытеснения и репликации контента в кэш-сетях». Доступ IEEE. 5: 1692–1701. arXiv:1702.04078. Bibcode:2017arXiv170204078B. Дои:10.1109 / ACCESS.2017.2669344.
  12. ^ Множественный (вики). «Кэширование веб-приложений». Докфорж. Получено 24 июля 2013.
  13. ^ Гарет Тайсон; Андреас Мауте; Себастьян Кауне; Му Му; Томас Плагеманн. Corelli: служба динамической репликации для поддержки содержимого, зависящего от задержки, в сетях сообщества (PDF). MMCN'09. Архивировано из оригинал (PDF) 18 июня 2015 г.
  14. ^ Пол, S; З. Фэй (1 февраля 2001 г.). «Распределенное кеширование с централизованным управлением». Компьютерные коммуникации. 24 (2): 256–268. CiteSeerX  10.1.1.38.1094. Дои:10.1016 / S0140-3664 (00) 00322-4.
  15. ^ Хан, Икбал (июль 2009 г.). «Распределенное кэширование на пути к масштабируемости». MSDN. 24 (7).

дальнейшее чтение