Назначение и способы организации кэш-памяти; стратегии замещения; принцип локальности; особенности организации кэш-памяти в многоядерных процессорах на примере Intel Core i7.
Как следует из принципов архитектуры фон Неймана, память ЭВМ неоднородна и имеется иерархия запоминающих устройств. Одним из элементов этой иерархии в современных компьютерах является кэш-память процессора.
Кэш-память процессора (Cache) - это особый вид быстрой памяти, которая находится в процессоре и предназначается для хранения данных, активно используемых при выполнении данной программы в текущий момент времени, что позволяет существенно ускорить работу и снизить нагрузку на оперативную память и системную шину.
Размер кэш-памяти существенно меньше и самой оперативной памяти, и той её части, которая выделяется для работы одной программы. Поскольку эта память находится внутри процессора, то ограничения на размеры кремниевой пластины, на которой находится процессор, и различные другие факторы не позволяют сделать эту память достаточно большой. Поэтому по мере выполнения программы данные в кэш-памяти постоянно обновляются (эта процедура называется замещением и будет рассмотрена ниже).
Фактически, современные процессоры не работают напрямую с данными в оперативной памяти, но предварительно загружают их в кэш-память. При этом исполняемая процессором программа не контролирует работу с кэш-памятью и не знает о том, помещены ли туда необходимые данные туда, то есть для неё кэш-память является прозрачной. Cache в переводе с английского означает "тайник", что как раз отражает прозрачность этого вида памяти для прикладной программы.
Обмен данными между оперативной памятью и кэш-памятью осуществляется блоками фиксированного размера. Такой блок будем называть строкой кэш-памяти. Размер одной строки и общий объём являются основными характеристиками кэш-памяти, которые отличаются для разных моделей процессоров. Например, в процессорах Intel Core i7 размер кэш-памяти варьируется от 4 до 12 Mb, а размер строки кэш-памяти составляет 64 байта. При одинаковом общем размере, кэш-память, состоящая из большего количества строк, эффективнее, но сложнее в реализации.
Современные процессоры имеют многоуровневую кэш-память. Можно сказать, в этом случае принцип иерархических запоминающих устройств фон Неймана реализуется следующим образом: уровни с меньшими номерами кэшируют наиболее часто используемые данные в уровнях с бо?льшими номерами, и при этом каждый следующий уровень имеет больший размер и меньшее быстродействие, чем предыдущий.
Чтобы для исполняемой программы кэш-память была прозрачной, используется механизм отображения кэш-памяти. Этот механизм поддерживает соответствие между данными в кэш-памяти и данными в оперативной памяти. Последнее важно, так как в программном коде, в операндах команд, которые работают не с регистрами, а с оперативной памятью (например, команда сложения вида регистр/память), указаны адреса в оперативной памяти, а не в кэш-памяти, и обращения по этим адресам нужно заменить на обращения в кэш-память. Эту подмену и реализует механизм отображения.
Механизм отображения может быть ассоциативным, прямым или гибридным.
Intel x86, используется механизм гибридного отображения: на один и тот же блок оперативной памяти может отображаться не единственная (как в прямом отображении) и не произвольная (как в ассоциативном) строка кэш-памяти, а несколько строк, часто - 4 или 8, в зависимости от модели процессора. Такой механизм значительно более гибок, чем прямое отображение, но при этом не столь сложен в реализации, как механизм ассоциативного отображения.
Поскольку объём кэш-памяти процессора существенно меньше объёма оперативной памяти, уже после непродолжительной работы программы кэш-память оказывается полностью занятой. При необходимости обратиться к блоку оперативной памяти, который не был помещён в кэш-память, он перемещается туда. Но для этого нужно выбрать строку в кэш-памяти, в которую пометить данный блок. Для этого процессор выполняет операцию замещения, состоящую из следующих шагов:
Способ, которым в кэш-памяти выбирается строка для замещения, называется стратегией замещения. При замещении обычно используется принцип Белэди: следует заместить строку, содержащую данные, которые не понадобятся процессору дольше всего. Но однозначно выбрать такую строку нельзя, поэтому используются различные эвристические подходы. Самым распространенным является стратегия LRU (Least Recently Used), которая фиксирует время последнего обращения к каждой строке кэш-памяти и замещает ту из них, к которой процессор дольше всего не обращался. Поясним, как эта стратегия может быть реализована в зависимости от используемого механизма отображения.
LRU непосредственно в том виде, в котором она описана выше.LRU можно реализовать, выбирая из тех строк, которые могут быть связаны с данным блоком оперативной памяти.Несмотря на то, что программа на C/C++, Java, Python и т.д. не может управлять кэш-памятью процессора, при разработке программ иногда её надо учитывать. Например, при работе с данными, превышающими размер кэш-памяти, следует соблюдать принцип локальности.
Принцип локальности. Данные, обрабатываемые в одном фрагменте программы, должны быть расположены в оперативной памяти рядом.
Приведём пример программы на языке C для процессора Intel Core i7 (как было указано выше, кэш-память этого процессоров составляет от 4 до 12 Mb в зависимости от его модели):
int my_array[10000][10000]; ... for(int i = 0; i < 10000; ++i) for (int j = 0; j < 10000; ++j) my_array[i][j] *= 2;
В этом фрагменте объявлен двумерный массив (матрица) целых числе my_array размером 10000*10000. Целое число (int) в современных компиляторах языка C представляется четырьмя байтами. Соответственно, для массива my_array требуется . Очевидно, что этот массив не помещается в кэш-память процессора целиком. Следовательно, по мере того как программа будет работать с этим массивом, в кэш-память процессора будут подгружаются из оперативной памяти все новые и новые фрагменты данного массива. Далее, двумерные массивы языка С хранятся в оперативной памяти построчно: my_array[0][0], ... my_array [0][9999], my_array [1][0], ... my_array [1][9999], ... Отметим, что именно в этом порядке элементы массива обрабатываются в цикле for в программе, представленной выше: то есть, когда в кэш-память из оперативной памяти загружается строка, программа полностью её обрабатывает и больше не обращается к этим данным. Затем в кэш-память загружается следующая строка, и так далее. Очевидно, что в этой программе принцип локальности соблюдается.
Изменим эту программу так: заменим оператор my_array [i][j] *= 2 на my_array [j][i] *= 2. Теперь последовательно обрабатываемые элементы массива расположены в оперативной памяти далеко друг от друга, и программа вынуждена постоянно "прыгать" по массиву, что влечет многократную загрузку/выгрузку одних и тех же строк кэш-памяти. В такой программе принцип локальности не соблюдается, и она будет работать медленнее, чем предыдущая.
Реализация кэш-памяти многоядерных процессоров, да и в целом вычислительных устройств с аппаратной поддержкой многозадачности, сопряжена с рядом трудностей. Одна из наиболее значительных трудностей вызвана необходимостью обеспечить когерентность кэш-памяти.
Когерентность - свойство многоядерного процессора, подразумевающее согласованность данных в кэш-памяти его разных ядер при исполнении программ.
Рассмотрим пример сбоя, который может произойти при использовании кэш-памяти, не обладающей свойством когерентности. Допустим, что в программе на С есть такая строка int x, y. В оперативной памяти эти переменные размещаются рядом и попадают в один блок, который передается в кэш-память и потом, через некоторое время, "возвращается" в оперативную память из кэш-памяти. Далее предположим, что у нас имеется двухъядерный процессор, и каждое из ядер меняет одну из этих переменных - ядро 1 меняет переменную x, а ядро 2 меняет переменную y (это может происходить, например, в разных потоках нашей программы). Таким образом, процессор выполняет следующие действия.
x, записывая в свою кэш-память соответствующий блок оперативной памяти.y, записывая в свою кэш-память тот же блок оперативной памяти (напоминаем, что обе переменные находятся рядом, а кэш-память и оперативная память не могут обмениваться фрагментами памяти, соответствующими только одной переменной, и захватывают лишнее; в этом-то и проблема!).x в своей кэш-памяти.y в своей кэш-памяти.x, так и прежнее значение переменной y.x, так и измененное значение переменной y.Очевидно, что на шаге 6 значение переменной x окажется прежним, которое было до того, как ядро 1 изменило эту переменную. Таким образом результаты действий ядра 1 по изменению переменной x окажутся потерянными, что является ошибкой.
Для того, чтобы избежать таких проблем, сохранив при этом эффективность работы кэш-памяти, в многоядерных процессорах приходится применять сложные технические решения.
Для обеспечения когерентности внутри процессора Intel Core i7 используется внутренняя шина специальной конструкции, которая называется кольцевой сетью. К ней последовательно подключены несколько кэши разных ядер. Получив запрос на предоставление данных, каждый из них решает, обработать ли этот запрос, или передать его дальше. Когда ядро 1 на рис. 11.2 обращается к блоку памяти, копии которого нет в его внутренней кэш-памяти L1, этот запрос обрабатывает его кэш L2. Если требуемые данные нашлись в кэш-памяти L2 ядра 1, то она возвращает их ядру 1. Если же в кэш-памяти L2 ядра 1 не нашлось нужных данных, то запрос кэш-памяти L2 следующего ядра - в данном случае ядра 2. Если в кэш-памяти L2 ядра 1 требуемые данные нашлись, то этот она обрабатывает запрос и возвращает дынные в кэш-память L2 ядра 0. Если ни в одном кэшей L2 ни нашлось требуемых данных, запрос возвращается необработанным ядру 1, и концевая сеть повторно направляет его уже в кэш-память L3 (который в случае промаха обращается уже к оперативной памяти). Как только какое-то из ядер вносит изменения в кэш-данные, кольцевая сеть отправляет остальным ядрам сообщение о том, что копии этих данных в их кэш-памяти потеряли актуальность, и в случае последующих обращений их надо будет запросить у изменившего их ядра. В рассмотренном выше примере с кэшированием двух переменных x и y из разных потоков концевая сеть внесет следующие изменения в действия процессора (в этом примере мы описываем то, как это происходит в процессоре Intel Core i7).
y, ядро 2 запрашивает актуальные данные строки кэш-памяти у ядра 1. Затем меняет значение переменной y. А после изменения сообщает ядру 1, что актуальная копия теперь у него.Intel Core i7 не взаимодействуют c оперативной памятью самостоятельно. Вместо этого в какой-то момент актуальная копия блока памяти попадёт из кэш-памяти ядра 2 в общую кэш-память L3, а ещё позже из L3 - в оперативную память.LRU-стратегию.С.С.Intel Core i7?Назначение и способы организации кэш-памяти; стратегии замещения; принцип локальности; особенности организации кэш-памяти в многоядерных процессорах на примере Intel Core i7.
Как следует из принципов архитектуры фон Неймана, память ЭВМ неоднородна и имеется иерархия запоминающих устройств. Одним из элементов этой иерархии в современных компьютерах является кэш-память процессора.
Кэш-память процессора (Cache) - это особый вид быстрой памяти, которая находится в процессоре и предназначается для хранения данных, активно используемых при выполнении данной программы в текущий момент времени, что позволяет существенно ускорить работу и снизить нагрузку на оперативную память и системную шину.
Размер кэш-памяти существенно меньше и самой оперативной памяти, и той её части, которая выделяется для работы одной программы. Поскольку эта память находится внутри процессора, то ограничения на размеры кремниевой пластины, на которой находится процессор, и различные другие факторы не позволяют сделать эту память достаточно большой. Поэтому по мере выполнения программы данные в кэш-памяти постоянно обновляются (эта процедура называется замещением и будет рассмотрена ниже).
Фактически, современные процессоры не работают напрямую с данными в оперативной памяти, но предварительно загружают их в кэш-память. При этом исполняемая процессором программа не контролирует работу с кэш-памятью и не знает о том, помещены ли туда необходимые данные туда, то есть для неё кэш-память является прозрачной. Cache в переводе с английского означает "тайник", что как раз отражает прозрачность этого вида памяти для прикладной программы.
Обмен данными между оперативной памятью и кэш-памятью осуществляется блоками фиксированного размера. Такой блок будем называть строкой кэш-памяти. Размер одной строки и общий объём являются основными характеристиками кэш-памяти, которые отличаются для разных моделей процессоров. Например, в процессорах Intel Core i7 размер кэш-памяти варьируется от 4 до 12 Mb, а размер строки кэш-памяти составляет 64 байта. При одинаковом общем размере, кэш-память, состоящая из большего количества строк, эффективнее, но сложнее в реализации.
Современные процессоры имеют многоуровневую кэш-память. Можно сказать, в этом случае принцип иерархических запоминающих устройств фон Неймана реализуется следующим образом: уровни с меньшими номерами кэшируют наиболее часто используемые данные в уровнях с бо?льшими номерами, и при этом каждый следующий уровень имеет больший размер и меньшее быстродействие, чем предыдущий.
Чтобы для исполняемой программы кэш-память была прозрачной, используется механизм отображения кэш-памяти. Этот механизм поддерживает соответствие между данными в кэш-памяти и данными в оперативной памяти. Последнее важно, так как в программном коде, в операндах команд, которые работают не с регистрами, а с оперативной памятью (например, команда сложения вида регистр/память), указаны адреса в оперативной памяти, а не в кэш-памяти, и обращения по этим адресам нужно заменить на обращения в кэш-память. Эту подмену и реализует механизм отображения.
Механизм отображения может быть ассоциативным, прямым или гибридным.
Intel x86, используется механизм гибридного отображения: на один и тот же блок оперативной памяти может отображаться не единственная (как в прямом отображении) и не произвольная (как в ассоциативном) строка кэш-памяти, а несколько строк, часто - 4 или 8, в зависимости от модели процессора. Такой механизм значительно более гибок, чем прямое отображение, но при этом не столь сложен в реализации, как механизм ассоциативного отображения.
Поскольку объём кэш-памяти процессора существенно меньше объёма оперативной памяти, уже после непродолжительной работы программы кэш-память оказывается полностью занятой. При необходимости обратиться к блоку оперативной памяти, который не был помещён в кэш-память, он перемещается туда. Но для этого нужно выбрать строку в кэш-памяти, в которую пометить данный блок. Для этого процессор выполняет операцию замещения, состоящую из следующих шагов:
Способ, которым в кэш-памяти выбирается строка для замещения, называется стратегией замещения. При замещении обычно используется принцип Белэди: следует заместить строку, содержащую данные, которые не понадобятся процессору дольше всего. Но однозначно выбрать такую строку нельзя, поэтому используются различные эвристические подходы. Самым распространенным является стратегия LRU (Least Recently Used), которая фиксирует время последнего обращения к каждой строке кэш-памяти и замещает ту из них, к которой процессор дольше всего не обращался. Поясним, как эта стратегия может быть реализована в зависимости от используемого механизма отображения.
LRU непосредственно в том виде, в котором она описана выше.LRU можно реализовать, выбирая из тех строк, которые могут быть связаны с данным блоком оперативной памяти.Несмотря на то, что программа на C/C++, Java, Python и т.д. не может управлять кэш-памятью процессора, при разработке программ иногда её надо учитывать. Например, при работе с данными, превышающими размер кэш-памяти, следует соблюдать принцип локальности.
Принцип локальности. Данные, обрабатываемые в одном фрагменте программы, должны быть расположены в оперативной памяти рядом.
Приведём пример программы на языке C для процессора Intel Core i7 (как было указано выше, кэш-память этого процессоров составляет от 4 до 12 Mb в зависимости от его модели):
int my_array[10000][10000]; ... for(int i = 0; i < 10000; ++i) for (int j = 0; j < 10000; ++j) my_array[i][j] *= 2;
В этом фрагменте объявлен двумерный массив (матрица) целых числе my_array размером 10000*10000. Целое число (int) в современных компиляторах языка C представляется четырьмя байтами. Соответственно, для массива my_array требуется . Очевидно, что этот массив не помещается в кэш-память процессора целиком. Следовательно, по мере того как программа будет работать с этим массивом, в кэш-память процессора будут подгружаются из оперативной памяти все новые и новые фрагменты данного массива. Далее, двумерные массивы языка С хранятся в оперативной памяти построчно: my_array[0][0], ... my_array [0][9999], my_array [1][0], ... my_array [1][9999], ... Отметим, что именно в этом порядке элементы массива обрабатываются в цикле for в программе, представленной выше: то есть, когда в кэш-память из оперативной памяти загружается строка, программа полностью её обрабатывает и больше не обращается к этим данным. Затем в кэш-память загружается следующая строка, и так далее. Очевидно, что в этой программе принцип локальности соблюдается.
Изменим эту программу так: заменим оператор my_array [i][j] *= 2 на my_array [j][i] *= 2. Теперь последовательно обрабатываемые элементы массива расположены в оперативной памяти далеко друг от друга, и программа вынуждена постоянно "прыгать" по массиву, что влечет многократную загрузку/выгрузку одних и тех же строк кэш-памяти. В такой программе принцип локальности не соблюдается, и она будет работать медленнее, чем предыдущая.
Реализация кэш-памяти многоядерных процессоров, да и в целом вычислительных устройств с аппаратной поддержкой многозадачности, сопряжена с рядом трудностей. Одна из наиболее значительных трудностей вызвана необходимостью обеспечить когерентность кэш-памяти.
Когерентность - свойство многоядерного процессора, подразумевающее согласованность данных в кэш-памяти его разных ядер при исполнении программ.
Рассмотрим пример сбоя, который может произойти при использовании кэш-памяти, не обладающей свойством когерентности. Допустим, что в программе на С есть такая строка int x, y. В оперативной памяти эти переменные размещаются рядом и попадают в один блок, который передается в кэш-память и потом, через некоторое время, "возвращается" в оперативную память из кэш-памяти. Далее предположим, что у нас имеется двухъядерный процессор, и каждое из ядер меняет одну из этих переменных - ядро 1 меняет переменную x, а ядро 2 меняет переменную y (это может происходить, например, в разных потоках нашей программы). Таким образом, процессор выполняет следующие действия.
x, записывая в свою кэш-память соответствующий блок оперативной памяти.y, записывая в свою кэш-память тот же блок оперативной памяти (напоминаем, что обе переменные находятся рядом, а кэш-память и оперативная память не могут обмениваться фрагментами памяти, соответствующими только одной переменной, и захватывают лишнее; в этом-то и проблема!).x в своей кэш-памяти.y в своей кэш-памяти.x, так и прежнее значение переменной y.x, так и измененное значение переменной y.Очевидно, что на шаге 6 значение переменной x окажется прежним, которое было до того, как ядро 1 изменило эту переменную. Таким образом результаты действий ядра 1 по изменению переменной x окажутся потерянными, что является ошибкой.
Для того, чтобы избежать таких проблем, сохранив при этом эффективность работы кэш-памяти, в многоядерных процессорах приходится применять сложные технические решения.
Для обеспечения когерентности внутри процессора Intel Core i7 используется внутренняя шина специальной конструкции, которая называется кольцевой сетью. К ней последовательно подключены несколько кэши разных ядер. Получив запрос на предоставление данных, каждый из них решает, обработать ли этот запрос, или передать его дальше. Когда ядро 1 на рис. 11.2 обращается к блоку памяти, копии которого нет в его внутренней кэш-памяти L1, этот запрос обрабатывает его кэш L2. Если требуемые данные нашлись в кэш-памяти L2 ядра 1, то она возвращает их ядру 1. Если же в кэш-памяти L2 ядра 1 не нашлось нужных данных, то запрос кэш-памяти L2 следующего ядра - в данном случае ядра 2. Если в кэш-памяти L2 ядра 1 требуемые данные нашлись, то этот она обрабатывает запрос и возвращает дынные в кэш-память L2 ядра 0. Если ни в одном кэшей L2 ни нашлось требуемых данных, запрос возвращается необработанным ядру 1, и концевая сеть повторно направляет его уже в кэш-память L3 (который в случае промаха обращается уже к оперативной памяти). Как только какое-то из ядер вносит изменения в кэш-данные, кольцевая сеть отправляет остальным ядрам сообщение о том, что копии этих данных в их кэш-памяти потеряли актуальность, и в случае последующих обращений их надо будет запросить у изменившего их ядра. В рассмотренном выше примере с кэшированием двух переменных x и y из разных потоков концевая сеть внесет следующие изменения в действия процессора (в этом примере мы описываем то, как это происходит в процессоре Intel Core i7).
y, ядро 2 запрашивает актуальные данные строки кэш-памяти у ядра 1. Затем меняет значение переменной y. А после изменения сообщает ядру 1, что актуальная копия теперь у него.Intel Core i7 не взаимодействуют c оперативной памятью самостоятельно. Вместо этого в какой-то момент актуальная копия блока памяти попадёт из кэш-памяти ядра 2 в общую кэш-память L3, а ещё позже из L3 - в оперативную память.LRU-стратегию.С.С.Intel Core i7?
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.