С.В. Герасимов, И.В. Машечкин, М.И. Петровский, И.С. Попов, А.Н. Терехин, А.В. Чернов - Организация кэширования (1114662)
Текст из файла
Московский Государственный Университет имени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиС.В.Герасимов, И.В.Машечкин, М.И.Петровский,И.С.Попов, А.Н.Терехин, А.В.ЧерновОрганизация кэширования(учебно-методическое пособие)Москва20111УДК 004.254ББК 32.973-018.2C40Пособие посвящено базовым аспектам реализации процессакэширования в современных вычислительных архитектурах. В пособии рассматриваются вопросы работы ассоциативного кэш и кэшпрямого доступа, алгоритмов вытеснения, стратегии записи, организации многоуровнего кэш. Отдельное внимание уделено оценкампроизводительности кэш, методам повышения производительности,а также организации кэширования в многопроцессорных архитектурах типа UMA и NUMA.
Пособие издано в поддержку курса "Операционные системы", читаемого студентам второго курса на факультете ВМК МГУ имени М.В. Ломоносова. Материал рассчитан наширокий круг читателей: студентов, аспирантов, преподавателей, атакже всех интересующихся.УДК 004.254ББК 32.973-018.2Рецензенты:доцентдоцентИ.А.ВолковаЕ.А.КузьменковаС.В.Герасимов, И.В.Машечкин, М.И.Петровский, И.С.Попов,А.Н.Терехин, А.В.ЧерновС40 Организация кэширования: учебно-методическое пособие.Издательский отдел факультета ВМК МГУ 2011, - 26 c.Печатается по решению Редакционно-издательского Совета факультета вычислительной математики и кибернетики МГУ им.М.В. ЛомоносоваISBN 978-5-89407-468-9© Издательский отдел факультета вычислительной математики икибернетики МГУ имени М.В. Ломоносова, 2011© С.В.Герасимов, И.В.Машечкин, М.И.Петровский, И.С.Попов,А.Н.Терехин, А.В.Чернов2Основы кэширования _______________________________________ 4Понятие кэширования ___________________________________________ 4Ассоциативность кэш, организация адресации ______________________ 5Алгоритмы вытеснения __________________________________________ 7Стратегии записи ________________________________________________ 8Многоуровневый кэш ____________________________________________ 9Производительность кэш и методы ее повышения _____________ 11Программные методы повышения эффективности работы кэш ______ 12Аппаратные методы повышения эффективности работы кэш _______ 14Кэширование в многопроцессорных архитектурах _____________ 16Кэширование в UMA системах ___________________________________ 18Кэширование в NUMA системах __________________________________ 203Основы кэшированияПонятие кэшированияОдной из проблем производительности компьютеров являетсянесоответствие скорости работы центрального процессора и скорости доступа к информации, размещенной в оперативной памяти.Процессору приходится простаивать при обращении к оперативнойпамяти в ожидании получения или записи данных.
Причем тенденция увеличения скорости работы центрального процессора и увеличения скорости работы ОЗУ говорит о том, что данная проблема будет в будущем увеличиваться, поскольку с момента появления вычислительной техники производительность центральных процессоров росла экспоненциально, а скорость доступа ОЗУ линейно.Для сглаживания данной проблемы используется Кэш (от фр.cacher — «прятать») — специальный промежуточный буфер высокоскоростной памяти небольшого размера.
Такой буфер содержит тучасть информации из ОЗУ, которая потенциально может быть запрошена с наибольшей вероятностью. Это достигается за счет использования принципа локальности программ, суть которого состоит в предположении о том, что большинство программ в каждыймомент времени использует те же участки кода и данных, которыеиспользовались недавно, и, таким образом, не обращаются случайнои равномерно ко всему коду и всему объему данных.Кэш состоит из набора блоков памяти, каждый из которых ассоциирован с блоком данных в основной памяти. Каждый блок имеет идентификатор - тэг, определяющий соответствие между блокамиданных в кэш и их копиями в основной памяти. Таким образом, кэшявляется частным случаем ассоциативной памяти, т.е. памяти адресуемой по содержимому.
При использовании кэш обмен даннымипри выполнении программы (чтение команд, чтение значений операндов, запись результатов) происходит не с ячейками оперативнойпамяти, а с кэш. Когда центральный процессор обращается к даннымсначала проверяется кэш. Если в нем необходимые данные присутствуют, т.е. найден блок, совпадающий с блоком затребованногоэлемента данных в ОЗУ, то используется информация в кэш.
Такойслучай называется попаданием кэш. Если в кэш не найдена необходимая информация, то содержащий ее блок данных читается из основной памяти в кэш, и становится доступным для последующихобращений. Такой случай называется промахом кэш. Процент обращений к кэш, когда в нём найден результат, называется уровнемпопаданий или коэффициентом попаданий в кэш. Поскольку кэшимеет размер заметно меньший по сравнению с ОЗУ, то при промахенужно отбросить некоторый блок для освобождения пространства.4Для выбора отбрасываемого блока используются алгоритмы вытеснения.
При записи данных в кэш выполняется их обновление в основной памяти. Порядок во времени между изменением данных вкэш и обновлением данных в ОЗУ определяется стратегией записи.Ассоциативность кэш, организация адресацииСуществуют три основных подхода к организации отображения блоков оперативной памяти в кэш:Полностью ассоциативный кэш. Блок ОП может быть размещенв любой позиции в кэш.Кэш прямого отображения (direct mapping).
В этом случае каждый блок ОП может быть размещен в единственной позиции вкэш, заданной формулой:А кэш= АОП MOD N кэшА кэш – адрес блока в кэш,АОП - адрес блока в ОП,N кэш - число блоков в кэш.Частично ассоциативный кэш. В этом случае множество блоковкэш разделяется на несколько непересекающихся подмножеств, иблок ОП может быть отображен в любой блок кэш из строго заданного подмножества:А п/м кэш = АОП MOD N п/м кэшА п/м кэш – адрес подмножества блоков в кэш,АОП - адрес блока в ОП,N п/м кэш – число подмножеств блоков в кэш.Данные подходы представлены на рисунке.5Полностьюассоциативный.Прямое отображение.Блок 13 может быть влюбой позицииБлок 13может бытьтолько в позиции5 = (13 mod 8)Ассоциативный с 4подмножествамиБлок 13может быть впозициях 2 или 3Set 2 = (13 mod 4)0 1 2 3 4 5 6 70 1 2 3 4 5 6 70 1 2 3 4 5 6 7КэшSet1 Set2 Set3 Set40 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7ОПБлок 13Если число подмножеств частично ассоциативного кэш обозначитьm, а число блоков в нем n, то такой кэш называют m-ассоциативныйкэш.
Таким образом, прямое отображение и полностью ассоциативный кэш являются частными случаями частично ассоциативногокэш (1- и n- ассоциативные кэш соответственно).Адрес блокаТэгПонижениеассоциативностиИндексСмещениевнутриблокаПовышениеассоциативностиАдрес в кэш содержит две позиции: смещение в блоке и тэг. Вслучае частично ассоциативного кэш добавляется еще позиция индекс, который нужен для выбора подмножества в частично ассоциативном кэш. Тэг – уникальный для каждого блока спецификатор. Втеге находится служебная информация, характеризующая данныйблок кэш.
В нем может содержаться информация о том, какому блоку ОП соответствует содержимое данного блока кэш, занят или свободен блок, производились изменения в данном блоке или нет, идругая информация. Когда процессору нужно обратиться за командой или за данными в ОП, сначала происходит обращение к кэш, ипоиск по всем тегам происходит параллельно в рамках подмножества тегов, заданного индексом. Следует отметить, что увеличение6степени ассоциативности частично ассоциативного кэш увеличиваетчисло блоков в подмножестве, таким образом, уменьшая размерность индекса в адресе и увеличивая размер тэга.
Полностью ассоциативный кэш не имеет поля индекс, а вся информация содержитсяв теге. Но в этом случае и поиск осуществляется дольше, посколькупроисходит по всем тегам, а не по определенному их подмножеству.С другой стороны, в кэш прямого отображения индексом однозначно определяется номер блока в кэш, а тэг содержит только информацию о состоянии этого блока.Анализ тэгов блоков кэш производится аппаратно. После вычисления исполнительного адреса операнда или команды устройствоуправления может определить, находится ли соответствующая информация в одном из блоков кэш-памяти и является она актуальнойили нет.Алгоритмы вытесненияПри возникновении промаха происходит вытеснение – обновление содержимого кэш. Для этого в кэш выбирается блокпретендент на вытеснение, т.е.
блок, содержимое которого будет заменено на содержимое нового блока из ОП. Стратегия этого выборазависит от конкретной организации процессора и от используемогоподхода к отображению. В частности, в кэш прямого отображенияопределение кандидата на вытеснение происходит быстро и однозначно, поскольку адрес вытесняемого блока однозначно связан садресом загружаемого блока.Для частично или полностью ассоциативных кэш вытеснениеблоков может осуществляться одним из следующих способов:случайный выбор - номер вытесняемого блока определяетсявстроенным генератором случайных чисел в соответствии сравномерным распределением;LRU (Least-Recently Used) - вытеснение неиспользуемогодольше всех блока, в этом случае сохраняется информация о«возрасте» блока кэш, т.е. метки последнего обращения,причем каждое обращение влечет пересчет «возраста» длявсех блоков;LFU (Least Frequently Used) – вытеснение наиболее редкоиспользуемого блока, аналогично LRU, но при этом считается и хранится число обращений к блоку, что, в отличие отLRU, не требует обновления информации во всех блокахпри каждом обращении;MRU (Most-Recently Used) – достаточно экзотический подход, при котором происходит вытеснение последнего использованного блока, т.е.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
