С.В. Герасимов, И.В. Машечкин, М.И. Петровский, И.С. Попов, А.Н. Терехин, А.В. Чернов - Организация кэширования (1114662), страница 3
Текст из файла (страница 3)
Он может быть реализован в случаеиспользования параллельных конвейерных процессоров, которыепозволяют командам завершаться не в том порядке, в котором онизапускались, если между ними нет зависимостей по результату. Тогда процессор может не останавливаться в случае промаха в кэш, апродолжать вычисления потока инструкций, если они не требуютобращений к тому же блоку памяти. При этом значительно усложняется логика работы кэш, поскольку ему необходимо параллельно обрабатывать процедуру вытеснения блока после промаха и процедуруобращения к другим блокам. Большинство процессоров, работающих по такой схеме, могут параллельно обрабатывать только одинпромах с множеством последующих попаданий. Если происходитвторой промах, то вычисления останавливаются и обрабатываютсявсе процедуры вытеснения. Но есть архитектуры, работающие с несколькими промахами одновременно. Следует отметить, что такоерешение естественно увеличивает время доступа к кэш за счет использования более сложных алгоритмов поиска и вытеснения.Наиболее популярным методом понижения стоимости промаха является увеличение числа уровней кэш.
В этом случае стоимостьпромаха понижается за счет того, что обращения к более высокомууровню кэш, хотя и дольше чем обращение к кэш первого уровня, но14значительно быстрее, чем к ОП. Большинство современных компьютеров имеет два и более уровней кэш. Как правило, первые двауровня кэш находятся внутри ЦП, при этом их объем и скоростьдоступа к ним могут отличаться на порядок. Для многоядерных процессоров каждое из ядер, по сути, представляет собой отдельныйпроцессор со своими кэш первого и второго уровней.
Кэш третьего ичетвертого уровней используются уже на мощных многопроцессорных серверах, мейнфреймах, специализированных вычислительныхсистемах и находятся на отдельной от ЦП микросхеме, обеспечивающей поддержку необходимых алгоритмов доступа и синхронизации. Поскольку уровни кэш могут быть достаточно разнородными,т.е. иметь разные алгоритмы кэширования и даже разный размерблоков, задача разработки эффективных архитектур с многоуровневым кэш и сами эти архитектуры становятся весьма сложными, причем почти всегда значительное уменьшение стоимости промаха засчет многоуровневости негативно сказывается на времени доступа ивероятности промаха.Самым очевидным решением для сокращения времени доступа является использование кэш с простой организацией и небольшим объемом.
Поэтому кэш первого уровня делают всегда небольшим. Но упрощение и уменьшение размера всего кэш естественноувеличивает вероятность и стоимость промаха.15Кэширование в многопроцессорных архитектурахВсе составляющие процесса кэширования - размещение, адресация, вытеснение и запись - могут существенно влиять на возможность работы в случае параллельных многопроцессорных архитектур. Рассмотрим основные подходы к организации кэширования длясистем с общей и распределенной памятью.
В рамках этих подходовОП является разделяемым ресурсом физически (для общей памяти)или логически (для распределенной). В любом случае возникаетпроблема синхронизации содержимого локальных кэш отдельныхпроцессоров и разделяемой ими ОП. Для описания целостного непротиворечивого состояния локальных кэш используется терминкогерентность кэш. Когерентность определяет порядок чтений изаписей по одному и тому же физическому адресу ОП. Кэш называется когерентным, если выполняются следующие условия:Когерентность выполнения. Если процессор записываетзначение по некоторому физическому адресу в ОП, то приследующем считывании он должен получить ранее записанное значение, если между записью и чтением другойпроцессор не производил запись по этому адресу.Когерентной видимости. Операция чтения процессором,следующая после того, как другой процессор осуществилзапись по некоторому физическому адресу ОП, должна вернуть записанное значение, если другие процессоры не изменяли эту ячейку памяти между двумя операциями.Когерентность записи.
Записи в одну и ту же ячейку ОПдолжны быть последовательными, т.е. если два процессоразаписывают по некоторому адресу в ОП разные значения вопределенном порядке, этот порядок должен сохранятьсяпри считывании любым из процессоров.Для кэш существуют следующие основные подходы поддержаниякогерентности:Справочник (directory). Информация о состоянии блокафизической памяти содержится только в одном месте, называемом справочником (физически справочник можетбыть распределен по вычислительным узлам многопроцессорной системы).Отслеживание (snooping).
Каждый кэш, который содержит копию данных некоторого блока физической памяти,16имеет также соответствующую копию служебной информации о его состоянии. Централизованная система записейотсутствует. Обычно кэш расположены на общей (разделяемой) шине, и контроллеры всех кэш наблюдают за шиной для определения того, не содержат ли они копию блока, с которым производится операция в настоящий момент.Сами процедуры (последовательности действий) поддержания когерентности называются протоколами когерентности. Рассмотримболее детально организацию когерентных кэш для некоторых параллельных архитектур на основе общей памяти. Традиционно по способу организации работы с памятью параллельные архитектуры разделяют на системы:с общей памятью;на основе передачи сообщений.В первом случае все адресное пространство для всех вычислительных узлов параллельной системы представляется единым виртуальным адресным пространством.
Это выполнено даже в случае распределенной общей памяти, когда каждый вычислительный узелимеет свой физически отдельный модуль памяти и предоставляетего полностью или частично в общее пользование. Во втором случае– передачи сообщений - каждый вычислительный модуль функционирует как отдельный компьютер, а весь обмен данными происходитна уровне прикладных программ с помощью аппарата передачи сообщений. Вопрос когерентности кэш для параллельных систем передачи сообщений не актуален, поскольку каждый процесс общейпараллельной программы работает в своем изолированном, физически локальном адресном пространстве.
В то же время, традиционныеалгоритмы решения современных математических задач предполагают массовую обработку больших объемов данных с использованием математических вычислений, организованных в виде последовательностей вложенных циклов. Эффективный перенос таких алгоритмов на системы передачи сообщений достаточно затруднителен,поэтому параллельные системы с общей памятью являются важнейшим компонентом современных вычислительных систем.
Для нихвопрос синхронизации кэш становится особенно актуальным, поскольку в таких системах оперативная память является физическиглобальным разделяемым ресурсом, а память кэш, наоборот, физически локальна и используется только одним процессором.17Кэширование в UMA системахРассмотрение систем с общей оперативной памятью начнем с систем с однородным доступом к памяти (UMA - uniformmemory access) . В данной модели произвольный процессорный элемент имеет доступ к произвольной точке оперативной памяти (доступ с одинаковым временем).
Поэтому характеристики доступа любого процессорного элемента в любую точку ОЗУ не зависят от конкретного элемента и адреса, все процессоры равноценны относительно доступа к памяти. Наиболее популярным представителемUMA-систем является симметричная мультипроцессорная система(SMP - symmetric multiprocessor).ЦПЦПЦПЦПодин или болееуровней кэшодин или болееуровней кэшодин или болееуровней кэшодин или болееуровней кэшобщая шинаОперативная памятьВ этой модели к общей системной шине, или магистрали, подсоединяются несколько процессоров и блок общей оперативной памяти. У данного решения можно отметить следующие недостатки.Во-первых, это централизованная система, и общая шина в ней является «узким горлом», поэтому данная модель накладывает существенные ограничения на количество подключаемых процессорныхэлементов (обычно 2, 4, 8, вплоть до 32).
Во-вторых, возникаютпроблемы синхронизации кэш каждого процессора.В силу особенностей реализаций основным методом организации когерентных кэш для UMA систем является отслеживание(snooping), поскольку в любом случае в системе существует общаявысокоскоростная шина и любые операции работы с оперативнойпамятью проходят через нее. Проблема когерентности кэш возникает только при операции записи. Существуют два базовых протоколаподдержания когерентности:протокол инвалидации кэш при записи;протокол широковещательной записи.Инвалидация при записи является наиболее часто используемым протоколом как для подхода отслеживания (snooping) так и18для подхода на основе справочника. В нем для проведения операцийзаписи процесс захватывает эксклюзивно соответствующий блок памяти. В результате этого все кэш блоки, содержащие данный блокпамяти, становятся невалидными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
