Разработать код для размещения в кэше процессора?

StackOverflow https://stackoverflow.com/questions/1822295

Вопрос

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

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

Это было полезно?

Решение

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

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

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

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

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

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

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

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

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

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

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

Другие советы

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

Полезная статья, которая расскажет вам больше, чем вы когда-либо хотели знать о кеши, - это Что каждый программист Должен знать о памяти Ульриха Дреппера. Хеннесси освещает это очень тщательно. Кристер и Майк Актон тоже написали много хороших вещей об этом.

Думаю, вам стоит больше беспокоиться о кеше данных, чем о кеше команд & # 8212; по моему опыту, промахи dcache более частые, более болезненные и более полезные.

ОБНОВЛЕНИЕ: 13.01.2014 По словам этого старшего дизайнера чипов, в настоящее время пропуски кеша являются ОЧЕНЬ доминирующим фактором в производительности кода, поэтому мы в основном вернулись к середине 80-х и к быстрым 286 чипам с точки зрения относительных узких мест производительности в загрузке, хранении, целочисленных значениях. арифметика и кеш отсутствует.

Ускоренный курс современного оборудования от Клифф Клик @ Azul , , , , .

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

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

Пример: сопоставление индексов

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

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

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

Это сократило требования к хранилищу до 2 КБ для двойников и до 1250 байт для 8-разрядных индексов. Это сократилось на 10000 байт до 3298. Поскольку программа потратила 90% или больше своего времени в этом внутреннем цикле, эти 2 вектора так и не были вытеснены из кэша данных 8 КБ. Программа сразу удвоила производительность. Этот код получил ~ 100 миллиардов раз в процессе вычисления значения OAS для 1+ миллионов ипотечных кредитов.

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

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

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

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

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

Новые инструкции Hazwell по обработке битов

ОБНОВЛЕНИЕ: 29.12.2013

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

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

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

<Ол>

  • Входящие требования были добавлены к заголовку и разделу Summary одновременно, рядом друг с другом в соседних строках кода.

  • При срабатывании таймера хвост вычитался из сечения Сводка, а результаты оставлялись в срезе Сводка, как и следовало ожидать

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

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

  • Учитывая вышесказанное, я начал задаваться вопросом, смогу ли я получить больше производительности, если вместо того, чтобы срез Summary оставался в одном месте, у меня был "roam" между головой и хвостом, так что он всегда был рядом с головой для добавления новых требований, и прямо рядом с хвостом, когда срабатывал таймер, а значения хвоста нужно было вычитать из сводки.

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

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

    Лидером до конца ринга (на самом деле барабан, 512 дорожек шириной) был Хвост, но я

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

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

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

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top