Как написать код, который лучше всего использует кэш процессора для повышения производительности?

Question

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

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

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

3. Существуют ли какие-либо программные конструкции (если for, switch, break, goto, ...), поток кода (для if, if внутри for и т.д. ...), за которым следует следовать / избежать в этом вопросе?

Я с нетерпением жду возможности услышать индивидуальный опыт, связанный с созданием эффективного кеш-кода в целом. Это может быть любой язык программирования (C, C ++, Assembly, ...), любая аппаратная цель (ARM, Intel, PowerPC, ...), любая ОС (Windows, Linux, Symmbian, ...) и т. Д. .

Разнообразие поможет лучше понять его.

Answer 1

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

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

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

Улучшение использования строки кэша помогает в трех отношениях:

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

Общие методы:

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

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

Современные ЦП: у них часто есть один или несколько аппаратных предварительных загрузчиков . Они тренируются по промахам в тайнике и пытаются выявить закономерности. Например, после нескольких пропусков в последующих строках кеша, средство предварительной выборки hw начнет извлекать строки кеша в кеш, ожидая потребностей приложения. Если у вас есть обычный шаблон доступа, аппаратный предварительный выборщик обычно делает очень хорошую работу. И если ваша программа не отображает обычные шаблоны доступа, вы можете улучшить ситуацию, добавив инструкции предварительной выборки самостоятельно.

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

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

Объединение циклов, которые касаются одних и тех же данных ( слияние циклов ), и использование методов перезаписи, известных как tiling или блокирование , все стремятся избежать этих дополнительных выборок памяти .

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

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

Answer 2

Не могу поверить, что на это больше нет ответов. В любом случае, одним из классических примеров является итерация многомерного массива «наизнанку»:

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

Причина, по которой этот кэш неэффективен, заключается в том, что современные процессоры загружают строку кеша с «близкими» адресами памяти из основной памяти при доступе к одному адресу памяти. Мы выполняем итерацию по «j» (внешним) строкам в массиве во внутреннем цикле, поэтому для каждой поездки по внутреннему циклу строка кэша будет очищаться и загружаться строкой адресов, которые находятся рядом с [ j] [i] запись. Если это изменено на эквивалент:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Он будет работать намного быстрее.

Answer 3

Основные правила на самом деле довольно просты. Трудно понять, как они применяются к вашему коду.

Кэш работает по двум принципам: временная локальность и пространственная локальность. Первая идея заключается в том, что если вы недавно использовали определенную порцию данных, вам, вероятно, скоро понадобится это снова. Последнее означает, что если вы недавно использовали данные по адресу X, вам, вероятно, скоро понадобится адрес X + 1.

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

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

Простым примером является обход массива 2D, который показал ответ 1800 года. Если вы просматриваете его по очереди, вы читаете память последовательно. Если вы сделаете это по столбцам, вы прочитаете одну запись, затем перейдете в совершенно другое место (начало следующей строки), прочитаете одну запись и снова прыгнете. И когда вы наконец вернетесь к первому ряду, он больше не будет в кеше.

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

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

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

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

Answer 4

Я рекомендую прочитать статью из 9 частей Что должен знать каждый программист об памяти Ульриха Дреппера, если вы заинтересованы в том, как взаимодействуют память и программное обеспечение. Это также доступно как 104-страничный PDF .

Разделы, особенно относящиеся к этому вопросу, могут быть Часть 2 (кэши ЦП) и Часть 5 (Что могут сделать программисты - оптимизация кэша).

Answer 5

Помимо шаблонов доступа к данным, основным фактором в кеширующем коде являются данные размер . Чем меньше данных, тем больше их помещается в кэш.

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

Аналогично, логический массив Java использует целый байт для каждого значения, чтобы разрешить непосредственную работу с отдельными значениями. Вы можете уменьшить размер данных в 8 раз, если используете фактические биты, но тогда доступ к отдельным значениям становится намного более сложным, требуя операций сдвига битов и маски (класс BitSet сделает это за вас). Однако из-за эффектов кэширования это все равно может быть значительно быстрее, чем использование логического [], когда массив большой. IIRC I однажды таким образом добился ускорения в 2 или 3 раза.

Answer 6

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

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

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

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

Answer 7

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

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

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

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

Answer 8

Замечание к «классическому примеру» пользователя 1800 ИНФОРМАЦИЯ (слишком долго для комментария)

Я хотел проверить разницу во времени для двух порядков итераций («внешний» и «внутренний»), поэтому я провел простой эксперимент с большим двумерным массивом:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

и второй случай с замененными петлями for.

Более медленная версия («x first») была 0,88 с, а более быстрая - 0,06 с. Это сила кеширования:)

Я использовал gcc -O2, и все же циклы были не оптимизированы. Комментарий Рикардо о том, что "большинство современных компиляторов могут сами в этом разобраться", не выдерживает

Answer 9

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

Answer 10

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

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

Этот тип шаблона лучше всего подходит для процедур,

1. можно разбить на разумные множественные подэтапы, S [1], S [2], S [3], ... время выполнения которых примерно сопоставимо со временем доступа к ОЗУ (~ 60-70 нс).
2. принимает пакет данных и делает несколько вышеупомянутых шагов, чтобы получить результат.

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

def proc(input):
    return sub-step(input))

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

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

Однако, как уже говорилось ранее, если выполнение шага примерно совпадает со временем доступа к ОЗУ, вы можете еще больше улучшить код до следующего:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

Поток выполнения будет выглядеть так:

1. prefetch (1) попросить CPU предварительно извлечь ввод [1] в кэш, где инструкция предварительного выбора берет P циклов и возвращает их, а в фоновом режиме ввод [1] поступит в кэш после R циклов.
2. works_on (0) холодный промах на 0 и работает на нем, что занимает M
3. prefetch (2) выдать другую выборку
4. works_on (1) если P + R <= M, то входы [1] должны быть в кеше уже перед этим шагом, поэтому избегайте пропуска кеша данных </li>
5. works_on (2) ...

Может потребоваться больше шагов, тогда вы можете разработать многоступенчатый конвейер, если время выполнения шагов и время ожидания доступа к памяти совпадают, и вы не будете испытывать небольшую потерю кеша кода / данных. Однако этот процесс должен быть настроен на множество экспериментов, чтобы определить правильную группировку шагов и время предварительной выборки. Из-за его требуемых усилий, он видит больше принятия в высокопроизводительной обработке потока данных / пакетов. Хороший пример производственного кода можно найти в схеме конвейера DPOK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Глава 21.2.4.3. Постановка трубопровода.

Более подробную информацию можно найти:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf