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

159

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

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

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

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

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

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

Золотая середина
источник
1
В качестве вступления этот доклад дает хороший обзор youtu.be/BP6NxVxDQIs
schoetbi
Вышеуказанный сокращенный URL-адрес, похоже, больше не работает, это полный URL-адрес беседы: youtube.com/watch?v=BP6NxVxDQIs
Abhinav Upadhyay,

Ответы:

119

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Коврики N
источник
5
Когда мы рассмотрели различные стандартные тесты, мы увидели, что удивительно большая часть из них не использует 100% извлеченных строк кэша до того, как строки кэша будут удалены. Могу я спросить, какие инструменты профилирования дают вам такую ​​информацию и как?
Dragon Energy
«Организуйте свои данные, чтобы избежать дыр в выравнивании (сортировка элементов структуры по уменьшению размера - это один из способов)» - почему компилятор не оптимизирует это сам? почему компилятор не всегда может "сортировать элементы по уменьшению размера"? Что является преимуществом, чтобы держать участников не отсортированными?
javapowered
Я не знаю происхождения, но, с одной стороны, порядок членства имеет решающее значение, скажем, для сетевого взаимодействия, где вы можете отправлять целые байтовые структуры через Интернет.
Кобрар
1
@javapowered Компилятор может сделать это в зависимости от языка, хотя я не уверен, что кто-нибудь из них это сделает. Причина, по которой вы не можете сделать это в C, заключается в том, что совершенно правильно обращаться к членам по базовому адресу + смещению, а не по имени, что означает, что переупорядочивание членов полностью нарушит программу.
Дэн Бешард
56

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

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]

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

1800 ИНФОРМАЦИЯ
источник
9
Еще в колледже у нас было задание по умножению матриц. Оказалось, что быстрее было взять транспонирование матрицы «столбцы» и умножить строки на строки, а не строки на столбцы по этой точной причине.
Икаганович
11
на самом деле, большинство современных компиляторов могут сами в этом разобраться (с включенной оптимизацией)
Рикардо Нольде,
1
@ykaganovich Это также пример из статьи Ульриха Дрэпперса: lwn.net/Articles/255364
Саймон Стендер Боизен,
Я не уверен, что это всегда правильно - если весь массив помещается в кэш L1 (часто 32 КБ!), То оба ордера будут иметь одинаковое количество попаданий и пропусков кэша. Возможно, предварительная выборка памяти может оказать какое-то влияние. С радостью поправлюсь конечно.
Мэтт Паркинс
кто когда-нибудь выберет первую версию этого кода, если порядок не имеет значения?
silver_rocket
45

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

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

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

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

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

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

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

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

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

jalf
источник
4
+1, хороший и практичный совет. Одно добавление: локальная временная и пространственная локальность предполагают, что, например, для операций с матрицами целесообразно разделить их на более мелкие матрицы, которые полностью помещаются в строку кэша или чьи строки / столбцы помещаются в строки кэша. Я помню, как делал это для визуализации multidim. данные. Это обеспечило серьезный удар в штаны. Хорошо помнить, что кэш содержит более одной «строки»;)
AndreasT
1
Вы говорите, что только один процессор может иметь данный адрес в кеше L1 одновременно - я предполагаю, что вы имеете в виду строки кеша, а не адрес. Также я слышал о ложных проблемах совместного использования, когда по крайней мере один из процессоров выполняет запись, но не тогда, когда оба выполняют только чтение. Таким образом, под «доступом» вы на самом деле имеете в виду запись?
Джозеф Гарвин
2
@JosephGarvin: да, я имел в виду пишет. Вы правы: несколько ядер могут иметь одинаковые строки кэша в своих кэшах L1 одновременно, но когда одно ядро ​​выполняет запись по этим адресам, оно становится недействительным во всех других кэшах L1, а затем им необходимо перезагрузить его, прежде чем они смогут это сделать. ничего с этим. Извините за неточную (неправильную) формулировку. :)
jalf
44

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

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

Томи Кёстиля
источник
16
Вам следует добавить краткое изложение основных моментов из статьи.
Азмисов
Отличное чтиво, но еще одна книга, которую НЕОБХОДИМО упомянуть здесь, - это Хеннесси, Паттерсон, Компьютерная архитектура, Количественный подход , которая доступна в 5-м выпуске к сегодняшнему дню.
Хаймо Кучбах
15

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

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

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

Майкл Боргвардт
источник
9

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

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

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

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

Гровер
источник
@Grover: По поводу вашего пункта 2. поэтому можно сказать, что если внутри замкнутого цикла вызывается функция для каждого счетчика циклов, то он будет вообще извлекать новый код и вызывать пропадание кэша, вместо этого, если вы можете поместить функцию как код в самом цикле for, без вызова функции, это будет быстрее из-за меньшего количества кешей?
goldenmean
1
Да и нет. Новая функция будет загружена в кеш. Если места в кеше достаточно, то на второй итерации эта функция уже будет находиться в кеше, поэтому нет необходимости перезагружать ее снова. Так что это хит на первом звонке. В C / C ++ вы можете попросить компилятор разместить функции рядом друг с другом, используя соответствующие сегменты.
Гровер
Еще одно замечание: если вы вызываете вне цикла и недостаточно места в кеше, новая функция будет загружена в кеш независимо. Может даже случиться, что оригинальный цикл будет выброшен из кэша. В этом случае вызов будет включать до трех штрафов за каждую итерацию: один для загрузки цели вызова и другой для перезагрузки цикла. И третье, если заголовок цикла находится не в той же строке кэша, что и адрес возврата вызова. В этом случае прыжок к головке цикла также требует нового доступа к памяти.
Гровер
8

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

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

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

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

Зан Рысь
источник
2
+1 Совсем не устарел. Это лучший способ организовать данные для игровых движков - сделать блоки данных смежными и выполнить все операции определенного типа (скажем, AI), прежде чем переходить к следующему (скажем, физике), чтобы использовать близость / локальность кэша. ссылка.
Инженер
Я видел этот точный пример в видео где-то пару недель назад, но с тех пор потерял ссылку на него / не могу вспомнить, как его найти. Помните, где вы видели этот пример?
будет
@ Уилл: Нет, я точно не помню, где это было.
Zan Lynx
Это сама идея системы компонентов сущности (ECS: en.wikipedia.org/wiki/Entity_component_system ). Храните данные в виде структур массивов, а не более традиционных массивов структур, которые поощряются методами ООП.
BuschnicK
7

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

RussellH
источник
7

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

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

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и до сих пор петли не были оптимизированы. Комментарий Рикардо о том, что «большинство современных компиляторов могут сами в этом разобраться», не имеет места

Якуб М.
источник
Не уверен, что понял. В обоих примерах вы по-прежнему обращаетесь к каждой переменной в цикле for. Почему один путь быстрее другого?
Ред.
в конечном счете, для меня интуитивно понятно, как это влияет :)
Laie
@EdwardCorlew Это из-за порядка, в котором они доступны. Первый порядок у быстрее, потому что он обращается к данным последовательно. Когда запрашивается первая запись, кэш L1 загружает всю строку кеша, которая включает запрошенное int плюс следующие 15 (при условии 64-байтовой строки кеша), поэтому не происходит останова ЦП в ожидании следующих 15. -первый порядок медленнее, потому что доступ к элементу не является последовательным, и, по-видимому, N достаточно велик, чтобы доступ к памяти всегда находился вне кэша L1, и поэтому каждая операция останавливается.
Мэтт Паркинс
4

Я могу ответить (2), сказав, что в мире C ++ связанные списки могут легко уничтожить кэш процессора. Массивы являются лучшим решением, где это возможно. Нет опыта в том, применимо ли это к другим языкам, но легко представить, что возникнут те же проблемы.

Андрей
источник
@ Андрей: как насчет структур. Эффективны ли они для кэширования? Есть ли у них ограничения по размеру, чтобы быть эффективными в кеше?
золотая середина
Структура - это отдельный блок памяти, поэтому до тех пор, пока он не превысит размер вашего кэша, вы не увидите никакого влияния. Только когда у вас есть коллекция структур (или классов), вы увидите попадания в кеш, и это зависит от того, как вы организовали коллекцию. Массив сталкивает объекты друг с другом (хорошо), но связанный список может иметь объекты по всему вашему адресному пространству со ссылками между ними, что, очевидно, плохо сказывается на производительности кэша.
Андрей
Один из способов использовать связанные списки без уничтожения кэша, наиболее эффективный для небольших списков, - создать собственный пул памяти, то есть выделить один большой массив. затем вместо 'malloc'ing (или' new'ing в C ++) памяти для каждого маленького связанного элемента списка, который может быть выделен в совершенно другом месте в памяти, и тратит впустую пространство управления, вы отдаете ему память из своего пула памяти, Значительно увеличивая шансы, которые логически закрывают членов списка, будут вместе находиться в кеше.
Лиран Ореви
Конечно, но много работы по получению std :: list <> и др. использовать ваши собственные блоки памяти. Когда я был молодым кнутом, я бы пошел по этому пути, но в наши дни ... слишком много других вещей, которые нужно решать.
Андрей
4

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

Следовательно, структуры данных, содержащиеся в одной строке кэша, более эффективны.

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

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

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

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

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

(Кстати, как плохо, как может быть из-за кеша, хуже - если программа выгружается с жесткого диска ...)

Лиран Ореви
источник
4

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

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

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

  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] должны быть в кеше уже до этого шага, что позволяет избежать пропуска кеша данных
  5. works_on (2) ...

Может потребоваться больше шагов, тогда вы можете разработать многоступенчатый конвейер, если время выполнения шагов и время ожидания доступа к памяти совпадают, и вы будете испытывать небольшие потери в кеше кода / данных. Однако этот процесс должен быть настроен на множество экспериментов, чтобы определить правильную группировку шагов и время предварительной выборки. Из-за его требуемых усилий он видит больше принятия в обработке потока данных / потока высокой производительности. Хороший пример производственного кода можно найти в проекте конвейера очереди QoS DPDK: 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

Вей Шен
источник
1

Напишите вашу программу, чтобы взять минимальный размер. Вот почему не всегда хорошая идея использовать оптимизацию -O3 для GCC. Это занимает больший размер. Часто -Os так же хорошо, как -O2. Хотя все зависит от используемого процессора. YMMV.

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

Чтобы помочь вам лучше использовать временную / пространственную локальность команд, вы можете изучить, как ваш код преобразуется в сборку. Например:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

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

sybreon
источник
Интересный момент. Делают ли прогнозные кэши предположения, основанные на направлении цикла / прохода в памяти?
Андрей
1
Существует много способов создания спекулятивных кэшей данных. Страйд-ориентированные измеряют «расстояние» и «направление» доступа к данным. Контентные цепочки преследуют указатели. Есть и другие способы их дизайна.
Sybreon
1

Помимо выравнивания вашей структуры и полей, если ваша структура, если выделена куча, вы можете использовать распределители, которые поддерживают выравниваемые выделения; как _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); иначе у вас может быть случайное ложное разделение; помните, что в Windows куча по умолчанию имеет 16-байтовое выравнивание.

aracntido
источник