• Главная
  •  > 
  • Ошибки в Windows 10
  •  > 
  • Увеличение производительности кэш-памяти. Почему не нужно использовать программы для оптимизации памяти

Увеличение производительности кэш-памяти. Почему не нужно использовать программы для оптимизации памяти

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

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

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

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

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

На написание этой статьи меня вдохновила шестая глава из книги Computer Systems: A Programmer"s Perspective . В другой статье из этой серии, «Оптимизация кода: процессор» , мы также боремся за такты процессора.

Память тоже имеет значение

Рассмотрим две функции, которые суммируют элементы матрицы. Они практически одинаковы, только первая функция обходит элементы матрицы построчно, а вторая - по столбцам.

Int matrixsum1(int size, int M) { int sum = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { sum += M[i][j]; // обходим построчно } } return sum; } int matrixsum2(int size, int M) { int sum = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { sum += M[j][i]; // обходим по столбцам } } return sum; }

Обе функции выполняют одно и то же количество инструкций процессора. Но на машине с Core i7 Haswell первая функция выполняется в 25 раз быстрее для больших матриц. Этот пример хорошо демонстрирует, что память тоже имеет значение . Если вы будете оценивать эффективность программ только в терминах количества выполняемых инструкций, вы можете писать очень медленные программы.

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

Иерархия памяти

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

На вершине иерархии находятся регистры процессора. Доступ к ним занимает 0 тактов, но их всего несколько штук. Далее идёт несколько килобайт кэш-памяти первого уровня, доступ к которой занимает примерно 4 такта. Потом идёт пара сотен килобайт более медленной кэш-памяти второго уровня. Потом несколько мегабайт кэш-памяти третьего уровня. Она гораздо медленней, но всё равно быстрее оперативной памяти. Далее расположена относительно медленная оперативная память.

Оперативную память можно рассматривать как кэш для локального диска. Диски это рабочие лошадки среди устройств хранения. Они большие, медленные и стоят дёшево. Компьютер загружает файлы с диска в оперативную память, когда собирается над ними работать. Разрыв во времени доступа между оперативной памятью и диском колоссальный. Диск медленнее оперативной памяти в десятки тысяч раз, и медленнее кэша первого уровня в миллионы раз. Выгоднее обратиться несколько тысяч раз к оперативной памяти, чем один раз к диску. На это знание опираются такие структуры данных, как B-деревья , которые стараются разместить больше информации в оперативной памяти, пытаясь избежать обращения к диску любой ценой.

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

Современная система имеет примерно такие характеристики:

Быстрая память стоит очень дорого, а медленная очень дёшево. Это великая идея архитекторов систем совместить большие размеры медленной и дешёвой памяти с маленькими размерами быстрой и дорогой. Таким образом система может работать на скорости быстрой памяти и иметь стоимость медленной. Давайте разберёмся как это удаётся.

Допустим, ваш компьютер имеет 8 ГБ оперативной памяти и диск размером 1000 ГБ. Но подумайте, что вы не работаете со всеми данными на диске в один момент. Вы загружаете операционную систему, открываете веб-браузер, текстовый редактор, пару-тройку других приложений и работаете с ними несколько часов. Все эти приложения помещаются в оперативной памяти, поэтому вашей системе не нужно обращаться к диску. Потом, конечно, вы закрываете одно приложение и открываете другое, которое приходится загрузить с диска в оперативную память. Но это занимает пару секунд, после чего вы несколько часов работаете с этим приложением, не обращаясь к диску. Вы не особо замечаете медленный диск, потому что в один момент вы работаете только с небольшим бъёмом данных, которые кэшируются в оперативной памяти. Вам нет смысла тратить огромные деньги на установку 1024 ГБ оперативной памяти, в которую можно было бы загрузить содержимое всего диска. Если бы вы это сделали, вы бы почти не заметили никакой разницы в работе, это было бы «деньги на ветер».

Так же дело обстоит и с маленькими кэшами процессора. Допустим вам нужно выполнить вычисления над массивом, который содержит 1000 элементов типа int . Такой массив занимает 4 КБ и полностью помещается в кэше первого уровня размером 32 КБ. Система понимает, что вы начали работу с определённым куском оперативной памяти. Она копирует этот кусок в кэш, и процессор быстро выполняет действия над этим массивом, наслаждаясь скоростью кэша. Потом изменённый массив из кэша копируется назад в оперативную память. Увеличение скорости оперативной памяти до скорости кэша не дало бы ощутимого прироста в производительности, но увеличило бы стоимость системы в сотни и тысячи раз. Но всё это верно только если программы имеют хорошую локальность.

Локальность

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

Рассмотрим, программу, которая суммирует элементы массива:

Int sum(int size, int A) { int i, sum = 0; for (i = 0; i < size; i++) sum += A[i]; return sum; }

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

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

Перемещение данных между уровнями иерархии осуществляется блоками определённого размера. К примеру, процессор Core i7 Haswell перемещает данные между своими кэшами блоками размером в 64 байта. Рассмотрим конкретный пример. Мы выполняем программу на машине с вышеупомянутым процессором. У нас есть массив v , содержащий 8-байтовые элементы типа long . И мы последовательно обходим элементы этого массива в цикле. Когда мы читаем v , его нет в кэше, процессор считывает его из оперативной памяти в кэш блоком размером 64 байта. То есть в кэш отправляются элементы v –v . Далее мы обходим элементы v , v , ..., v . Все они будут в кэше и доступ к ним мы получим быстро. Потом мы читаем элемент v , которого в кэше нет. Процессор копирует элементы v –v в кэш. Мы быстро обходим эти элементы, но не находим в кэше элемента v . И так далее.

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

Желательно обходить массив последовательно, читая его элементы один за другим. Если нужно обойти элементы матрицы, то лучше обходить матрицу построчно, а не по столбцам. Это даёт хорошую пространственную локальность. Теперь вы можете понять, почему функция matrixsum1 работала медленнее функции matrixsum2 . Двумерный массив расположен в памяти построчно: сначала расположена первая строка, сразу за ней идёт вторая и так далее. Первая функция читала элементы матрицы построчно и двигалась по памяти последовательно, будто обходила один большой одномерный массив. Эта функция в основном читала данные из кэша. Вторая функция переходила от строки к строке, читая по одному элементу. Она как бы прыгала по памяти слева-направо, потом возвращалась в начало и опять начинала прыгать слева-направо. В конце каждой итерации она забивала кэш последними строками, так что в начале следующей итерации первых строк кэше не находила. Эта функция в основном читала данные из оперативной памяти.

Дружелюбный к кэшу код

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

Вычисления над матрицами очень важны в приложениях анализа сигналов и научных вычислениях. Если перед программистами встанет задача написать функцию перемножения матриц, то 99.9% из них напишут её примерно так:

Void matrixmult1(int size, double A, double B, double C) { double sum; for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) { sum = 0.0; for (int k = 0; k < size; k++) sum += A[i][k]*B[k][j]; C[i][j] = sum; } }

Этом код дословно повторяет математическое определение перемножения матриц. Мы обходим все элементы окончательной матрицы построчно, вычисляя каждый из них один за другим. В коде есть одна неэффективность, это выражение B[k][j] в самом внутреннем цикле. Мы обходим матрицу B по стобцам. Казалось бы, ничего с этим не поделаешь и придётся смириться. Но выход есть. Можно переписать то же вычисление по другому:

Void matrixmult2(int size, double A, double B, double C) { double r; for (int i = 0; i < size; i++) for (int k = 0; k < size; k++) { r = A[i][k]; for (int j = 0; j < size; j++) C[i][j] += r*B[k][j]; } }

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

Блокинг

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

Можно продемонстрировать это на примере. Допустим у вас есть ориентированный граф, представленный в виде матрицы смежности. Это такая квадратная матрица из нулей и единиц, так что если элемент матрицы с индексом (i, j) равен единице, то существует грань от вершины графа i к вершине j. Вы хотите превратить этот ориентированный граф в неориентированный. То есть, если есть грань (i, j), то должна появиться противоположная грань (j, i). Обратите внимание, что если представить матрицу визуально, то элементы (i, j) и (j, i) являются симметричными относительно диагонали. Эту трансформацию нетрудно осуществить в коде:

Void convert1(int size, int G) { for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) G[i][j] = G[i][j] | G[j][i]; }

Блокинг появляется естественным образом. Представьте перед собой большую квадратную матрицу. Теперь иссеките эту матрицу горизонтальными и вертикальными линиями, чтобы разбить её, скажем, на 16 равных блока (четыре строки и четыре столбца). Выберите два любых симметричных блока. Обратите внимание, что все элементы в одном блоке имеют симметричные элементы в другом блоке. Это наводит на мысль, что ту же операцию можно совершать над каждым блоком поочерёдно. В этом случае на каждом этапе мы будем работать только с двумя блоками. Если блоки сделать достаточно маленького размера, то они поместятся в кэше высокого уровня. Выразим эту идею в коде:

Void convert2(int size, int G) { int block_size = size / 12; // разбить на 12*12 блоков // представим, что делится без остатка for (int ii = 0; ii < size; ii += block_size) { for (int jj = 0; jj < size; jj += block_size) { int i_start = ii; // индекс i для блока принимает значения [j] = G[i][j] | G[j][i]; } } }

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

На машине с процессором Core i7 Haswell вторая функция не выполняется быстрее. На машине с более простым процессором Pentium 2117U вторая функция выполняется в 2 раза быстрее . На машинах, которые не выполняют предвыборку, производительность улучшилась бы ещё сильнее.

Какие алгоритмы быстрее

Все знают из курсов по алгоритмам, что нужно выбирать хорошие алгоритмы с наименьшей сложностью и избегать плохих алгоритмов с высокой сложностью. Но эти сложности оценивают выполнение алгоритма на теоретической машине, созданной нашей мыслью. На реальных машинах теоретически плохой алгоритм может выполнятся быстрее теоретически хорошего. Вспомните, что получить данные из оперативной памяти занимает 200 тактов, а из кэша первого уровня 4 такта - это в 50 раз быстрее. Если хороший алгоритм часто трогает память, а плохой алгоритм размещает свои данные в кэше, хороший может выполняться медленнее плохого. Также хороший алгоритм может хуже выполняться на процессоре, чем плохой. К примеру, хороший алгоритм вносит зависимость данных и не может загрузить конвеер, а плохой лишён этой проблемы и на каждом такте отправляет в конвеер новую инструкцию. Иными словами, сложность алгоритма это ещё не всё. То, как алгоритм будем выполняться на конкретной машине с конкретными данными, имеет значение.

Представим, что вам нужно реализовать очередь целых чисел, и новые элементы могут добавляться в любую позицию очереди. Вы выбираете между двумя реализациями: массив и связный список. Чтобы добавить элемент в середину массива, нужно сдвинуть вправо половину массива, что занимает линейное время. Чтобы добавить элемент в середину списка, нужно дойти по списку до середины, что также занимает линейное время. Вы думаете, что раз сложности у них одинаковые, то лучше выбрать список. Тем более у списка есть одно хорошее свойство. Список может расти без ограничения, а массив придётся расширять, когда он заполнится. Давайте представим что длина очереди 1000 элементов и нам нужно вставить элемент в середину очереди. Элементы списка хаотично разбросаны по памяти, а получить данные из памяти занимает 200 тактов. Поэтому чтобы обойти 500 элементов, нам понадобится 500*200=100"000 тактов. Массив расположен в памяти последовательно, что позволит нам наслаждаться скоростью кэша первого уровня с временем доступа 4 такта. Используя несколько оптимизаций, мы можем двигать элементы, тратя 1-4 такта на элемент. Мы сдвинем половину массива максимум за 500*4=2000 тактов. Это быстрее в 50 раз .

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

Заключение

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

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

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

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

Тем не менее, если вы будете «правильно» записывать данные в память и удалять оттуда ненужную информацию, ничто не сможет помешать вам насладиться высокими скоростями работы оперативной памяти:

  • С помощью утилиты Dataram RAMDisk вы можете использовать часть вашей оперативной памяти в качестве жесткого диска.
  • В нашей пошаговой инструкции ниже «Настраиваем бесплатный RAMDisk » мы показываем, как вы можете создать и настроить небольшого размера флеш-диск в оперативной памяти. О том, как вы можете использовать такой диск, например, для хранения кэша браузера Firefox, мы расскажем в нижеприведенной инструкции «Размещаем в RAM-диске кэш браузера ».
  • С помощью бесплатной программы CleanMEM вы можете автоматизированно или вручную удалять более ненужные данные из вашей оперативной памяти.

Увеличиваем размеры оперативной памяти

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

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

Размещаем в RAM-диске кэш браузера:

Настраиваем бесплатный RAMDisk

1 Бесплатная утилита


С помощью Starwind RAMDisk вы можете бесплатно настроить под Windows один или несколько RAM-дисков. Единственное ограничение: размеры каждого такого RAM-диска не могут превышать 1 Гбайт.

2 Может понадобиться драйвер


Windows должна думать, что в случае с RAM-диском речь идет как бы о жестком диске. Этого программное обеспечение добивается с помощью нового драйвера.

3 Обзор RAM-дисков


Windows может работать даже с несколькими RAM-дисками. Утилита представит вам обзор всех имеющихся в системе RAM-дисков.

4 Добавляем RAM-диск


Для добавления и настройки нового RAM-диска кликните на пункт «Add Device».

5 При настройке поможет ассистент


Сразу же вам на помощь приходит «ассистент», который поможет пройти самые важные шаги.

6 Ограничение в 1 Гбайт


В случае со свободно распространяемой версией программы размеры RAM-диска не могут превышать 1 Гбайт. Тем не менее, в большинстве случаев этого должно быть достаточно. Для разных действий вы можете использовать разные RAM-диски. Важно: обязательно поставьте галочку перед «Automount this Device», чтобы при каждой перезагрузке системы RAM-диск появлялся в «Проводнике» автоматически.

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

Мы все «немного читали» об оптимизации работы с памятью, и у нас отложилось, что полезно, когда «кэш остается горячим», то есть данные, к которым часто обращаются потоки, должны быть компактными и находиться в ближайшем к процессорному ядру кэше. Все так, но когда дело доходит до того, чтобы делиться доступом, потоки становятся злейшими врагами [производительности], а кэш не просто горячий, он аж «горит адским огнем » – такая во круг него разворачивается борьба.

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

Рассмотрим случай, который хорошо описан в Intel64 and IA-32 Architectures Optimization Manual , однако про который программисты часто забывают, работая со массивами структур в могопоточном режиме. Они допускают обращение (с модификацией) потоков к данным структур, расположенных очень близко друг к другу, а именно в блоке, равном длине одной кэш-линии (64 байт). Мы это называем Сache line sharing . Существует два типа разделения кэш-линий: true sharing и false sharing .
True sharing (истинное разделение) – это когда потоки имеют доступ к одному и тому же объекту памяти, например, общей переменной или примитиву синхронизации. False sharing (от лукавого) – это доступ к разным данным, но по каким-то причинам, оказавшимся в одной кэш-линии процессора. Сразу отметим, что и тот, и другой случай вредит производительности из-за необходимости аппаратной синхронизации кэш-памяти процессора, однако если первый случай часто неизбежен, то второй можно и нужно исключать.

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


Условия для возниконовения проблемы:
Два или более потока пишут в одну кэш-линию;
Один поток пишет, остальные читают из кэш-линии;
Один поток пишет, в остальных ядрах стработал HW prefetcher.

Может оказаться, что переменные в полях разных структур так расположились в памяти, что будучи считанными в L1 кэш процессора, находятся в одной кэш-линии, как на рисунке. При этом, если один из потоков модифицирует поле своей структуры, то вся кэш-линия в соответствии с cache coherency протоколом объявляется невалидной для остальных ядер процессора. Другой поток уже не сможет пользоваться своей структурой, несмотря на то, что она уже лежит в L1 кэше его ядра. В старых процессорах типа P4 в такой ситуации потребовалась бы долгая синхронизация с основной памятью, то есть модифицированные данные были бы отправлены в основную память и потом считаны в L1 кэш другого ядра. В текущем поколении процессоров (кодовое имя Sandy Bridge) синхронизационным механизмом используется общий кэш третьего уровня (или LLC – Last Level Cache), который является инклюзивным для подсистемы кэш-памяти и в котором располагаются все данные, находящиеся как в L2, так и в L1 всех ядер процессора. Таким образом, синхронизация происходит не с основной памятью, а с LLC, являющегося частью реализации протокола механизма когерентности кэшей, что намного быстрее. Но она все равно происходит, и на это требуется время, хотя и измеряемое всего несколькими десятками тактов процессора. А если данные в кэш-линии разделяются между потоками, которые выполняются в разных физических процессорах? Тогда уже придется синхнонизироваться между LLC разных чипов, а это намного дольше - уже сотни тактов. Теперь представим, что программа только и занимается тем, что в цикле обрабатывает поток данных, получаемых из какого-либо источника. Теряя сотни тактов на каждой итерации цикла, мы рискуем «уронить» свою производительность в разы.

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

Потоковая функция в цикле пробегает по двум массивам float a[i] и b[i], перемножает их значения по индексу массива и складывает в локальные переменные потоков localSum. Для усиления эффекта эта операция делается несколько (ITERATIONS) раз.

< ITERATIONS; j++){ for (i = tid; i < MAXSIZE; i+= NUM_PROCS){ a[i] = i + a[i] * b[i]; localSum += a[i];}} }

Беда в том, что для разделения данных между потоками выбран способ перемежевания индексов цикла. То есть, если у нас работают два потока, первый будет обращаться к элементам массивов a и b, второй - к элементам a и b, первый - a и b, второй - a и b, и так далее. При этом элементы массива a[i] модифицируются потоками. Не трудно видеть, что в одну кэш-линию попадут 16 элементов массива, и потоки будут одновременно доступаться к соседним элементам, «сводя с ума» механизм синхрониции кэшей процессора.

Самое неприятное в том, что мы даже не заметим по работе программы существование этой проблемы. Она будет просто работать медленнее, чем может, вот и все. Как оценить эффективность программы с помощью профилировщика VTune Amplifier XE, я уже описывал в одном из постов на Хабре. Используя профиль General Exploration , о котором я там упоминал, можно увидеть описываемую проблему, которая будет «подсвечена» инструментом в результатах профилировки в колонке Contested Access . Эта метрика как раз и измеряет соотношение циклов, потраченых на синхронизацию кэшей процессора при их модификации потоками.

Если кому-то интересно, что стоит за этой метрикой, то во время комплексной профилировки инструмент среди других аппаратных счетчиков собирает и данные счетчика:
MEM_LOAD_UOPS_LLC_HIT_RETIRED.XSNP_HITM_PS – Точный счетчик(PS) выполненной(RETIRED) операции(OUPS) загрузки(LOAD) данных(MEM), которые оказалиcь(HIT) в LLC и модифицированны(M). «Точный» счетчик означает, что данные, собранные таким счетчиком в семплировании, относятся к указателю инструкции (IP), следующему после инструкции, которая была той самой загрузкой, приведшей к синхронизации кэшей. Набрав статистику по этой метрике, мы можем с определенной точностью указать адрес инструкции, и, соответственно, строку исходного кода, где производилось чтение. VTune Amplifier XE может показать, какие потоки читали эти данные, а дальше мы уже должны сами сориентироваться, как реализован многопоточный доступ к данным и как исправить ситуацию.

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

Int work(void *pArg) { int j = 0, i = 0; int tid = (int) pArg; for (j = 0; j < ITERATIONS; j++){ chunks = MAXSIZE / NUM_PROCS; for (i = tid * chunks; i < (tid + 1) * chunks; i++){ a[i] = i + a[i] * b[i]; localSum += a[i];}} }

False sharing

No False sharing

Сравнение доступа потоков к элементам массива в случае False sharing и в исправленном коде

В нашем простом случае данные используются всего один раз, и даже если они будут вытеснены из кэш-памяти, они нам уже не понадобятся. А о том, чтобы данные обоих массивов a[i] и b[i], расположенные далеко друг от друга в адресном пространстве, вовремя оказались в кэше позаботится аппаратный prefetcher – механизм подкачки данных из основной памяти, реализованный в процессоре. Он отлично работает, если доступ к элементам массива последовательный.

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

Если вы работаете со структурами данных в многопоточном режиме, уделите внимание их размеру. Используйте «подкладки» (padding), чтобы нарастить размер структуры до 64 байт:
struct data_packet { int address; int data; int attribute; int padding; }
Выделяйте память под структуры по выровненному адресу:
__declspec(align(64)) struct data_packet sendpack
Используйте массивы структур вместо структур массивов:
data_packet sendpack;
вместо
struct data_packet { int address; int data; int attribute; }
Как видно, в последнем случае потоки, модифицирующие одно из полей, приведут к запуску механизма синхронизации кэш-памяти.

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

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

P.S. Попробуйте мой примерчик, и расскажите, на сколько процентов увеличилось быстродействие теста на вашей платформе.

Теги: Добавить метки

Увеличение производительности кэш-памяти

Формула для среднего времени доступа к памяти в системах с кэш-памятью выглядит следующим образом:

Среднее время доступа = Время обращения при попадании + Доля промахов x Потери при промахе

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

Зачем увеличивать кэш?

Первичная причина увеличения объема встроенного кэша может заключаться в том, что кэш-память в современных процессорах работает на той же скорости, что и сам процессор. Частота процессора в этом случае никак не меньше 3200 MГц. Больший объем кэша позволяет процессору держать большие части кода готовыми к выполнению. Такая архитектура процессоров сфокусирована на уменьшении задержек, связанных с простоем процессора в ожидании данных. Современные программы, в том числе игровые, используют большие части кода, который необходимо извлекать из системной памяти по первому требованию процессора. Уменьшение промежутков времени, уходящих на передачу данных от памяти к процессору, - это надежный метод увеличения производительности приложений, требующих интенсивного взаимодействия с памятью. Кэш L3 имеет немного более высокое время ожидания, чем L 1 и 2, это вполне естественно. Хоть он и медленнее, но все-таки он значительно более быстрый, чем обычная память. Не все приложения выигрывают от увеличения объема или скорости кэш-памяти. Это сильно зависит от природы приложения.

Если большой объем встроенного кэша - это хорошо, тогда что же удерживало Intel и AMD от этой стратегии ранее? Простым ответом является высокая себестоимость такого решения. Резервирование пространства для кэша очень дорого. Стандартный 3.2GHz Northwood содержит 55 миллионов транзисторов. Добавляя 2048 КБ кэша L3, Intel идет на увеличение количества транзисторов до 167 миллионов. Простой математический расчет покажет нам, что EE - один из самых дорогих процессоров.

Сайт AnandTech провел сравнительное тестирование двух систем, каждая из которых содержала два процессора - Intel Xeon 3,6 ГГц в одном случае и AMD Opteron 250 (2,4 ГГц) - в другом. Тестирование проводилось для приложений ColdFusion MX 6.1, PHP 4.3.9, и Microsoft .NET 1.1. Конфигурации выглядели следующим образом:

Dual Opteron 250;

2 ГБ DDR PC3200 (Kingston KRX3200AK2);

Системная плата Tyan K8W;

Dual Xeon 3.6 ГГц;

Материнская плата Intel SE7520AF2;

ОС Windows 2003 Server Web Edition (32 бит);

1 жесткий IDE 40 ГБ 7200 rpm, кэш 8 МБ

На приложениях ColdFusion и PHP, не оптимизированных под ту или иную архитектуру, чуть быстрее (2,5-3%) оказались Opteron"ы, зато тест с.NET продемонстрировал последовательную приверженность Microsoft платформе Intel, что позволило паре Xeon"ов вырваться вперед на 8%. Вывод вполне очевиден: используя ПО Microsoft для веб-приложений, есть смысл выбрать процессоры Intel, в других случаях несколько лучшим выбором будет AMD.

Больше - не всегда лучше

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

Один из способов обойти эти трудности -- передача логики управления кэш-памятью от аппаратного обеспечения к программному.

«Компилятор потенциально в состоянии анализировать поведение программы и генерировать команды по переносу данных между уровнями памяти», -- отметил Шен.

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

Формула для среднего времени доступа к памяти в системах с кэш-памятью выглядит следующим образом:

Среднее время доступа = Время обращения при попадании + Доля промахов x Потери при промахе

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

Метод Доля промахов Потери при промахеВремя обраще-ния при попадании Слож-ность аппаратуры Примечания
Увеличение размера блока + -
Повышение степени ассоциативности + - 1
Кэш-память с вспомогательным кэшем +
Псевдоассоциативные кэши +
Аппаратная предварительная выборка команд и данных + 2 Предварительная выборка данных затруднена
Предварительная выборка под управлением компилятора + 3 Требует также неблокируемой кэш-памяти
Специальные методы для уменьшения промахов + 0 Вопрос ПО
Установка приоритетов промахов по чтению над записями + 1 Просто для однопроцессорных систем
Использование подблоков ++ 1 Сквозная запись + подблок на 1 слово помогают записям
Пересылка требуемого слова первым +
Неблокируемые кэши +
Кэши второго уровня + 2 Достаточно дорогое оборудование
Простые кэши малого размера - + 0
Обход преобразования адресов во время индексации кэш-памяти + 2
Конвейеризация операций записи для быстрого попадания при записи + 1

Рис. 7.3. Обобщение методов оптимизации кэш-памяти

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

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



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

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

Кэш первого уровня процессора 486 имеет четырехканальную структуру (рис. 7.9). Каждый канал состоит из 128 строк по 16 байт в каждой. Одноименные строки всех четырех каналов образуют 128 наборов из четырех строк, каждый из которых обслуживает свои адреса памяти. Каждой строке соответствует 21-разрядная информация об адресе скопированного в нее блока системной памяти. Эта информация называется тегом (Tag) строки.

Рис. 7.9. Структура внутреннего кэша процессора 486.

Кроме того, в состав кэша входит так называемый диспетчер, то есть область памяти с организацией 128 х 7, в которой хранятся 4-битные теги действительности (достоверности) для каждого из 128 наборов и 3-битные коды LRU (Least Recently Used) для каждого из 128 наборов. Тег действительности набора включает в себя 4 бита достоверности каждой из 4 строк, входящих в данный набор. Бит достоверности, установленный в единицу, говорит о том, что соответствующая строка заполнена; если он сброшен в нуль, то строка пуста. Биты LRU говорят о том, как давно было обращение к данному набору. Это нужно для того, чтобы обновлять наименее используемые наборы.

Адресация кэш-памяти осуществляется с помощью 28 разрядов адреса. Из них 7 младших разрядов выбирают один из 128 наборов, а 21 старший разряд сравнивается с тегами всех 4 строк выбранного набора. Если теги совпадают с разрядами адреса, то получается ситуация кэш-попадания , а если нет, то ситуация кэш-промаха .

В случае цикла чтения при кэш-попадании байт или слово читаются из кэш-памяти. При кэш-промахе происходит обновление (перезагрузка) одной из строк кэш-памяти.

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

Такая политика записи называется сквозной или прямой записью (Write Through). В более поздних моделях процессоров применяется и обратная запись (Write Back), которая является более быстрой, так как требует гораздо меньшего числа обращений по внешней шине.

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

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

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

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

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

Режим пакетной передачи (Burst Mode), впервые появившийся в процессоре 486, предназначен для быстрых операций со строками кэша. Пакетный цикл обмена (Burst Cycle) отличается тем, что для пересылки всего пакета адрес по внешней шине адреса передается только один раз - в начале пакета, а затем в каждом следующем такте передаются только данные. Адрес для каждого следующего кода данных вычисляется из начального адреса по правилам, установленным как передатчиком данных, так и их приемником. Например, адрес каждого следующего слова данных вычисляется как инкрементированный адрес предыдущего. В результате время передачи одного слова данных значительно сокращается. Понятно, что обмен пакетными циклами возможен только с устройствами, изначально способными обслуживать такой цикл. Допустимая длина пакета не слишком велика, например, при чтении размер пакета ограничен одной строкой кэша.

Режим внутреннего умножения тактовой частоты процессора был предложен для того, чтобы повысить быстродействие процессора, но при этом устанавливать его в системные платы, рассчитанные на невысокие тактовые частоты. Например, модель процессора 486DX2-66 работает в системной плате с тактовой частотой 33, но эту частоту внутри себя преобразует в удвоенную частоту - 66 МГц. Это позволяет уменьшить общую стоимость системы, так как снижает требования к элементам системной платы.

Процессор 486 выпускался в 168- или 169-выводных корпусах. Напряжение питания - 5 В или 3,3 В. Введение пониженного напряжения питания 3,3 В связано с необходимостью снижения величины рассеиваемой мощности. Растущая тактовая частота и усложнение структуры процессоров приводят к тому, что рассеиваемая ими мощность достигает нескольких ватт. Для современных процессоров уже обязательно применение вентиляторов на корпусе процессора.