Код проекта для установки в кеш процессора?

Question

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

Если вы знаете какие-либо хорошие ссылки, объясняющие кэширование ЦП, тогда укажите мне в этом направлении.

Answer 1

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

Edit (чтобы сделать некоторые моменты немного более явные):

Типичный процессор имеет целый ряд различных кэшей. Современный настольный процессор обычно имеет как минимум 2 и часто 3 уровня кеша. По (по крайней мере, почти) универсальному соглашению «уровень 1» является кешем «ближе всего» к элементам обработки, а номера идут вверх (уровень 2 следующий, уровень 3 после этого и т. Д.)

В в большинстве случаев (по крайней мере) кеш уровня 1 разделен на две половины: кеш команд и кеш данных (Intel 486 - это единственное исключение, о котором я знаю, с одним кешем для обеих команд и данных - но он настолько устарел, что, вероятно, не заслуживает много размышлений).

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

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

Это означает, что при обработке данных обычно лучше читать относительно небольшой объем данных (достаточно маленький, чтобы вписаться в кеш), делать как можно больше обработки этих данных, а затем перейти к следующий фрагмент данных. Алгоритмы, такие как Quicksort, которые быстро ломают большие объемы ввода в постепенно уменьшенные кусочки, делают это более или менее автоматически, поэтому они, как правило, довольно удобны для кеша, почти независимо от точных деталей кеша.

Это также имеет последствия для того, как вы пишете код. Если у вас есть цикл, как:

for i = 0 to whatever 
    step1(data); 
    step2(data); 
    step3(data); 
end for 

Вы обычно лучше нанизывать, как многие из шагов вместе, как вы можете до суммы, которая будет вписываться в кэше. В тот момент, когда вы переполняете кеш, производительность может/резко упасть.Если код для шага 3 выше было достаточно большим, что она не будет вписываться в кэш, вы, как правило, будет лучше разорвать петлю на две части как это (если это возможно):

for i = 0 to whatever 
    step1(data); 
    step2(data); 
end for 

for i = 0 to whatever 
    step3(data); 
end for 

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

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

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

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

Другая проблема с кешем, которая может возникать при параллельном кодировании, заключается в совместном использовании (и ложном обмене) переменных. Если два (или более) ядра необходимо записать в одно и то же место в памяти, линия кэша, содержащая эти данные, может быть переведена туда и обратно между ядрами, чтобы предоставить каждому ядру доступ к совместно используемым данным. Результатом часто является код, который работает медленнее параллельно, чем в серийном (то есть на одном ядре). Существует вариация, называемая «ложным совместным использованием», в которой код на разных ядрах записывается для разделения данных, , но данные для разных ядер заканчиваются в одной и той же строке кэша. Поскольку кеш управляет данными исключительно по всем строкам данных, данные все равно перетасовываются между ядрами, что приводит к точно такой же проблеме.

Answer 2

Если бы я тебя, я бы убедиться, что я знаю, какие части кода являются горячие точки, которые я определяю как

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

Если у вас есть такая точка доступа, то она должна входить в кеш. Я не знаю, как вы это делаете, но я подозреваю, что это автоматическое.

Answer 3

Вот ссылка на действительно хорошее paper на оптимизацию кэшей/памяти Кристером Эрикссон (от God of War I/II/III fame). Это уже пару лет, но это все еще очень актуально.

Answer 4

Большинство компиляторов C/C++ предпочитают оптимизировать размер, а не «скорость». То есть, меньший код обычно выполняется быстрее, чем разворачиваемый код из-за эффектов кеша.

Answer 5

Полезная бумага, которая расскажет вам больше, чем вы когда-либо хотели узнать о кешах, - What Every Programmer Should Know About Memory от Ulrich Drepper. Hennessey охватывает его очень тщательно. Кристер и Майк Актон написали кучу хороших вещей об этом тоже.

Я думаю, что вам следует больше беспокоиться о кеше данных, чем кеш для команд —, по моему опыту, пропуски dcache более часты, более болезненны и более полезны.

Answer 6

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

Это стало болезненно очевидным, когда я написал код здесь, в StackOverflow, чтобы отменить бит в массиве 4096 бит, который через 30+ после введения ПК, микропроцессоры просто не уделяют много внимания или ресурсов битам, и что я надеюсь, что это изменится. В частности, мне бы очень хотелось, чтобы во-первых, тип bool стал фактическим битовым типом данных в C/C++, а не до смешного расточительного байта, который он сейчас представляет.

UPDATE: 12/29/2013

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

Голова, хвостовые векторы были рядом друг с другом в памяти, за исключением случаев, когда сначала была голова, а затем хвост, завернутый в начало массива. Однако срединный (сводный) Срез-сегмент находился в фиксированном, статически распределенном массиве, который не был особенно близок ни к одному из них, и даже не был выделен из кучи.

Думая об этом, и изучая код, некоторые подробности привлекли мое внимание.

1. Требование, которые приходят в были добавлены главы и Резюме ломтика в то же время, в непосредственной близости друг к другу в соседних строках кода.

2. Когда таймер выстреле Tail вычитали из Резюме среза, и результаты были оставлены в итоговом срезе, как и следовало ожидать

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

4. пользователь хочет больше гибкости в ряде требований, управление которыми, от 512 до 4098, или, возможно, больше. Я чувствовал, что самый надежный, идиотский способ сделать это состоит в том, чтобы выделить как 1000 квантов времени, так и итоговый срез все вместе как один непрерывный блок памяти, так что НЕВОЗМОЖНО, чтобы срез Сводки заканчивался другой длиной чем другие 1000 срезов времени.

5. Учитывая вышеизложенное, я начал задаваться вопросом, могу ли я получить больше производительности, если бы вместо того, чтобы скомпилированный фрагмент оставался в одном месте, у меня было «брожение» между головой и хвостом, поэтому оно всегда было прав рядом с Главой для добавления новых требований и рядом с Хвостом, когда таймер выстрелил, а значения Хвоста должны были быть вычтены из Сводки.

Я сделал именно это, но затем нашел несколько дополнительных оптимизаций в этом процессе. Я изменил код, который рассчитал скользящее сводку, чтобы он оставил результаты в хвосте, а не срез Сводки. Зачем? Поскольку следующая функция выполняла memcpy(), чтобы переместить срез Summary в память, только что занятую хвостом. (странно, но верно, Хвост ведет голову до конца кольца, когда он обертывается). Оставив результаты суммирования в Tail, мне не пришлось выполнять memcpy(), мне просто пришлось назначить pTail для pSummary.

Аналогичным образом, новая глава заняла старую ячейку памяти старого устаревшего фрагмента, поэтому я просто назначил pSummary для pHead и обнулял все его значения с помощью memset до нуля.

Прохождение к концу кольца (на самом деле барабан шириной 512 дорожек) был хвостом, но мне пришлось сравнить его указатель с постоянным указателем pEndOfRing, чтобы обнаружить это условие. Все остальные указатели могли бы назначить значение указателя вектора перед ним. IE: Мне нужен только условный тест для 1: 3 указателей, чтобы их правильно обернуть.

Первоначальный проект был использован байт Интса для максимального использования кэша, однако, я был в состоянии ослабить это ограничение - удовлетворение пользователей просят обращаться с более высокими счетчиками ресурсов для каждого пользователя в миллисекунду - использовать неподписанные шорты и до сих пор двойной производительность , поскольку даже с 3 смежными векторами из 512 неподписанных шорт, кеш данных 32K данных L1 может легко удерживать требуемые 3,720 байт, 2/3rds которых были в только что используемых местах. Только когда обложка «Хвост», «Сводка» или «Голова» была 1 из 3, разделенных любым значительным «шагом» в 8-мегабайтном кэше L3.

Общий объем памяти во время выполнения для этого кода составляет менее 2 МБ, поэтому он полностью запускается из кэшей на кристалле, и даже на чипе i7 с 4 ядрами 4 экземпляра этого процесса могут запускаться без какого-либо ухудшения в целом, а общая пропускная способность немного увеличивается с 5 процессами. Это Opus Magnum для использования кеша.

Answer 7

UPDATE: 1/13/2014 В соответствии с этим старшим дизайнером чипа, промаха в настоящее время в подавляющем большинстве случаев доминирующим фактором в производительности кода, поэтому мы в основном все пути назад к середине 80-х годов и быстрой 286 чипов с точки зрения относительной производительности узких мест загрузки, хранения, целочисленной арифметики и пропусков в кэше.

A Crash Course In Modern Hardware by Cliff Click @ Azul . . . . .

--- мы теперь вернемся к вам регулярной плановой программы ---

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

Пример: Подстрочное Картирование

Вот пример методики я использовал, чтобы соответствовать данным в кэш чипа, который имеет полезность общее назначения.

У меня был вектор с двойным поплавком, который составлял 1250 элементов, что было кривой эпидемиологии с очень длинными хвостами. «Интересная» часть кривой имела только около 200 уникальных значений, но я не хотел, чтобы 2-сторонний if() тест делал беспорядок конвейера ЦП (таким образом, длинные хвосты, которые могли бы использовать в качестве индексов самые экстремальные значения кода Монте-Карло выплюнули бы), и мне понадобилась логика предсказания ветвления для еще дюжины других условных тестов внутри «горячей точки» в коде.

Я остановился на схеме, где я использовал вектор 8-битных ints в качестве индекса в двойной вектор, который я сократил до 256 элементов. Крошечные ints имели одинаковые значения до 128 перед нулем, а 128 после нуля, поэтому, за исключением средних значений 256, все они указывали либо на первое, либо на последнее значение в двойном векторе.

Это уменьшило требования к хранению до 2k для удвоений и 1250 байт для 8-разрядных индексов. Это сократилось на 10 000 байт до 3,298. Поскольку программа потратила 90% или более времени на этот внутренний цикл, 2 вектора никогда не выталкивались из кэша данных 8k. Программа сразу удвоила ее производительность. Этот код попал ~ 100 миллиардов раз в процессе вычисления стоимости OAS для 1 миллиона миллионов ипотечных кредитов.

Поскольку хвосты кривой были редко затронуты, очень возможно, что только в середине 200-300 элементов крошечного вектора int фактически хранились в кеше, а также 160-240 средних удвоений, составляющих 1/8 тыс. Процентов интерес. Это было замечательное увеличение производительности, достигнутое во второй половине дня, в программе, которую я потратил более года на оптимизацию.

Я согласен с Джерри, так же как и мой опыт, что отклонение кода к кэшу команд не так успешно, как оптимизация для кеша данных. Это одна из причин, по которой я думаю, что общие кэши AMD не так полезны, как отдельные кэши данных данных и команд Intel. IE: вы не хотите, чтобы инструкции загружали кеш, так как это не очень полезно. Частично это объясняется тем, что наборы команд CISC были изначально созданы, чтобы компенсировать огромную разницу между скоростью процессора и памяти, и за исключением аберрации в конце 80-х годов, это почти всегда было правдой.

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