С.В. Герасимов, И.В. Машечкин, М.И. Петровский, И.С. Попов, А.Н. Терехин, А.В. Чернов - Организация кэширования (1114662), страница 2
Текст из файла (страница 2)
стратегия обратная LRU, эффек7тивна при обработке программой последовательно большихобъемов памяти;Комбинированные методы – могут сочетать случайный поиск с LRU и LFU.Основное достоинство метода случайного вытеснения заключается в простоте его аппаратной реализации. С увеличением степени ассоциативности алгоритмам LRU, LFU и MRU требуется всебольше времени для поиска блока-кандидата на вытеснение. Поэтому для частично или полностью ассоциативных кэш большого объема, как правило, используются методы случайного вытеснения илиприближенные алгоритмы типа LRU, в которых выбирается не самый редко используемый блок, а один из нескольких редко используемых, возможно не самый редкий.Стратегии записиОтдельно следует обратить внимание на организацию работы скэш при записи данных.
В целом, количество операций чтения данных преобладает, а в случае использования кэш команд чтение –единственная операция. Поэтому основная оптимизация производительности кэш ориентирована на повышения эффективности чтения.В частности, для операций чтения данные из блока кэш могут считываться параллельно с анализом тега этого блока. Если анализ показывает, что произошло попадание, то экономия времени возникаетза счет параллельного считывания. Если же произошел промах, тосчитанные данные просто игнорируются. При этом выигрыша поскорости нет, но нет и проигрыша по сравнению с подходом, при котором анализ тэга и считывания блока происходят строго параллельно. Но такой подход не годится для операций записи, посколькуизменение данных можно производить только в случае попадания вправильный блок, т.е. строго после завершения анализа тэга.
Крометого, обычно операция записи изменяет не весь блок, а одно машинное слово или меньше. Поэтому операции записи требуют большеговремени.Существуют две стратегии организации записи при использовании кэш:сквозная запись – информация пишется сразу и в кэш, ив ОП;отложенная запись – информация пишется только вкэш, данный блок помечается специальным флагом, апри выполнении вытеснения обновленный блок передается в ОП целиком.8Оба подхода имеют свои достоинства и недостатки. В частности, при отложенной записи число обращений к оперативной памятиуменьшается за счет аккумуляции всех изменений блока до моментаего вытеснения из кэш. С другой стороны, при сквозной записи операции чтения не приводят к необходимости записи блока в оперативную память, а данные в оперативной памяти всегда консистентны, что особенно важно для архитектур с параллельными вычислениями – многоядерных и многопроцессорных.Еще одной особенностью организации кэш является алгоритмработы в случае промахапри операции записи, т.е.
отсутствия в кэшблока памяти в который осуществляется запись. В этом случае возможны два подхода:загрузка при записи (fetch on write) - загрузка из оперативной памяти в кэш блока, в который производиласьзапись;прямая запись (write around) – в этом случае загрузкаблока в кэш не производится.Любой из данных подходов может использоваться совместно с любой из стратегий записи, но обычно стратегия «сквозная запись» используется с алгоритмом «прямая запись», а «отложенная запись»совместно с «загрузкой при записи».Многоуровневый кэшДальнейшим развитием подхода кэширования является организация многоуровневой или иерархической структуры кэш памяти. В этом случае добавляется несколько промежуточных уровнейкэш памяти между процессором и основной оперативной памятью.Поскольку аппаратная реализация быстрой памяти на единицу хранимой информации дороже, чем аппаратная реализация более медленной, то размер памяти каждого уровня увеличивается по направлению от процессора к оперативной памяти, а скорость доступа, соответственно, убывает.
При этом, как правило, уровни вложены, т.е.данные, содержащиеся в более быстром и менее объемном уровне,содержатся и в следующем, более медленном и более объемном.9Кэшуровня 1КэшуровняN0 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 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7Как и в случае одноуровневого кэш, эффективность многоуровневой организации обеспечивается принципом локальностипрограмм. При этом создается эффект того, что вся память доступнасо скоростью самого быстрого, нижнего уровня иерархии, и имеетобъем самого большого уровня иерархии.
Важным моментом приорганизации многоуровневых кэш является стратегия размещенияодних и тех же блоков в разных уровнях. Такое размещение можетбыть:инклюзивным – каждый блок нижнего уровня содержится вблоке верхнего, и при вытеснении происходит замещениеблоков по всей цепочке уровней;эксклюзивным – блок, находящийся в одном из уровней, гарантированно отсутствует в других, при этом операция вытеснения менее трудоемка;смешанным – жестких правил размещения блоков нет, вытеснение происходит в соответствии с работой алгоритмоввытеснения каждого из уровней.10Производительность кэш и методы ее повышенияИспользование кэш-памяти позволяет повысить эффективность работы с оперативной памятью. Во-первых, сокращается количество обращений к ОЗУ, как по выборке команд, так и по выборке операндов.
Во-вторых, существенно увеличивается скорость доступа к памяти в случае использования ОП с «расслоением», так какобмены блоков с памятью проходят практически параллельно (когдамы работаем с группой подряд идущих слов). В-третьих, посколькуразмещение и команд, и данных в одном кэш может приводить к тому, что блоки кода и данные начинают вытеснять друг друга, увеличивая при этом обращения к оперативной памяти, современные компьютеры имеют два независимых кэш: кэш данных и кэш команд,каждый из которых работает со своим потоком информации, т.е.первых хранит только блока памяти с данными, второй только с кодом.Естественно, при использовании кэш возникают и проблемы,связанные с усложнением логики работы процессора: при выборкеочередных команд, получении операндов команд и записи результатов выполнения команд в ОЗУ добавляются схемы организации использования кэш-памяти.
Производительность кэш обычно оценивается по следующей формуле, где элементы формулы могут оцениваться либо в абсолютных временных единицах, например, наносекундах, либо в циклах ЦП:T ОП = T кэш + P промах × C промахT ОП – среднее время доступа к ОП,T кэш - время доступа к кэш,P промах – вероятность промаха в кэш,C промах – стоимость промаха в кэш.В формуле есть три составляющие T кэш, P промах, C промах, за счетуменьшения которых можно повышать эффективность работы кэш.Кратко рассмотрим некоторые популярные методы повышения эффективности кэш. Следует отметить, что стратегии увеличения производительности кэш, как правило, ориентированы на оптимизациюпо одному из трех параметров формулы, при этом бывает, что другие параметры могут ухудшаться.
Кроме того, повышение эффективности работы кэш может достигаться как за счет аппаратных решений, так и программных. Пользователь компьютера или программист может (и должен) использовать программные средства, на аппаратные он влиять не может. Далее рассмотрим некоторые показа11тельные и простые программные и аппаратные методы повышенияэффективности работы с кэш.Программные методы повышения эффективности работы кэшБольшинство программных средств повышения эффективности работы с кэш сводятся к тому, чтобы за счет правильной организации использования программой алгоритмов и структур данных вней выполнялся принцип локальности. Примером таких средств способов организации работы программы могут служить объединениемассивов и объединение циклов.Многие программы требуют одновременного обхода двух иболее массивов по одному общему индексу.
Это создает угрозу того,что обращения к разным массивам будет приводить к конфликтам ипостоянному вытеснению и возврату блоков в кэш. Например://до оптимизацииint a[100000];int b[100000];int c[100000];for (int i = 0; i < 100000; i++){c[i] = a[i]+b[i];}Поэтому целесообразно объединять массивы в общий массив структур.//после оптимизацииstruct i2{int a;int b;}i2 ab[100000];int c[100000];for (int i = 0; i < 100000; i++){c[i] = ab[i].a+ab[i].b;}12Часто программа имеет отдельные участки кода для доступа кодним и тем же массивам по одним и тем же индексам, но с различными вычислениями внутри цикла. Например://до оптимизацииfor (int i = 0; i < 100000; i++){for (int j = 0; j < 100000; j++){a[i][j] = b[i][j]*c[i][j];}}for (int k = 0; k < 100000; k++){for (int l = 0; l < 100000; l++){d[i][j] = a[i][j]+c[i][j];}}В этом случае, за счет объединения вычислений в общий цикл, данные могут повторно использоваться (считываться) из кэш до их записи в случае кэш с отложенной записью.//после оптимизацииfor (int i = 0; i{for (int j ={a[i][j]d[i][j]}}< 100000; i++)0; j < 100000; j++)= b[i][j]*c[i][j];= a[i][j]+c[i][j];Существуют различные программные возможности повышения эффективности использования кэш, в том числе, встроенные в компиляторы.
Но для правильного использования средств оптимизациипрограмм важно знать, какая именно организация кэш имеется нацелевой архитектуре. В частности, последний пример с объединением циклов не даст положительного эффекта в случае сквозной записи, поскольку потребует выгрузки блока из кэш в оперативную память после каждой операции записи.13Аппаратные методы повышения эффективности работы кэшСамым простым методом повышения производительности кэшза счет понижения вероятности промаха является увеличение размера блока памяти. Действительно, чем больше блок, тем выше вероятность того, что программа последовательно будет обращаться кодному и тому же блоку памяти, если выполняется принцип локальности.
Кроме того, чем больше размер блока, тем меньше нужноблоков для того же суммарного объема памяти, а, значит, быстреебудут работать алгоритмы поиска, что также несколько уменьшаетвремя доступа к кэш. Но, с другой стороны, с увеличением размераблока возрастают накладные расходы на его вытеснение, что можетпривести к сильному увеличению стоимость промаха.Наиболее популярным методом понижения вероятности промаха является повышение ассоциативности кэш. Чем выше ассоциативность, тем больше возможностей у алгоритма кэширования привытеснении оставить нужный блок, который будет использоваться вближайшем времени.
Но с другой стороны, как уже обсуждалосьвыше, при высоком уровне ассоциативности, неслучайные алгоритмы поиска становятся вычислительно сложными, что значительноувеличивает время доступа к кэш.Одним из подходов к понижению стоимости промаха за счетаппаратных решений является организация так называемого не блокирующего при промахе кэш.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
