Кэш (вычисления)

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  "Кэш-вычисления"  -  новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2011 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

Мотивация [ править ]

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

Буферизация обеспечивает кэш преимущества как задержки и пропускной способности ( пропускной способности ):

Задержка [ править ]

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

Пропускная способность [ править ]

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

Операция [ править ]

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

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

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

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

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

Написание политики [ править ]

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

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

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

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

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

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

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

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

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

Примеры аппаратных кешей [ править ]

Кеш процессора [ править ]

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

Кэш графического процессора [ править ]

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

По мере развития графических процессоров (особенно с вычислительными шейдерами GPGPU ) они разрабатывали все более крупные и все более общие кеши, включая кеши инструкций для шейдеров , демонстрируя все более общие функции с кешами ЦП. ^[7] Например, графические процессоры с архитектурой GT200 не имеют кеш-памяти второго уровня, тогда как графический процессор Fermi имеет 768 КБ кеш-памяти последнего уровня, графический процессор Kepler имеет 1536 КБ кеш-памяти последнего уровня, ^[7] а графический процессор Maxwell имеет 2048 КБ. КБ кеша последнего уровня. Эти кеши выросли для обработки примитивов синхронизации между потоками и атомарными операциями.и интерфейс с MMU в стиле ЦП .

DSP [ править ]

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

Резервный буфер перевода [ править ]

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

Сетевой кеш [ править ]

Информационно-ориентированные сети [ править ]

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

Политики [ править ]

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

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

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

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

Программные кеши [ править ]

Дисковый кеш [ править ]

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

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

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

Веб-кеш [ править ]

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

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

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

Мемоизация [ править ]

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

Другие тайники [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• «Что каждый программист должен знать о памяти» по Ulrich Drepper
• «Кэширование в распределенной среде»