По крайней мере, с обычным настольным процессором, вы не можете точно указать, как напрямую используется кеш. Вы все еще можете попытаться написать код, дружественный к кешу. Что касается кода, это часто означает, что развертывание циклов (только для одного очевидного примера) редко полезно - оно расширяет код, а современный ЦП обычно сводит к минимуму накладные расходы зацикливания. Как правило, вы можете делать больше на стороне данных, чтобы улучшить локальность ссылок, защитить от ложного совместного использования (например, два часто используемых фрагмента данных, которые будут пытаться использовать одну и ту же часть кэша, в то время как другие части остаются неиспользованными).
Редактировать (чтобы некоторые моменты были более явными):
Типичный процессор имеет несколько различных кешей. Современный настольный процессор обычно имеет как минимум 2, а часто и 3 уровня кеша. Согласно (по крайней мере, почти) универсальному соглашению, «уровень 1» - это кэш, «ближайший» к элементам обработки, и оттуда числа идут вверх (уровень 2 следующий, уровень 3 после него и т. Д.)
В большинстве случаев (по крайней мере) кэш 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
Развертывание петли является довольно горячо оспариваемым предметом. С одной стороны, это может привести к гораздо более дружественному к процессору коду, уменьшая накладные расходы на инструкции, выполняемые для самого цикла. В то же время, он может (и, как правило, делает) увеличивать размер кода, так что это относительно недружелюбно кеширует. Мой собственный опыт заключается в том, что в синтетических тестах, которые, как правило, выполняют очень небольшие объемы обработки действительно больших объемов данных, вы многое получаете от развертывания циклов. В более практичном коде, где вы, как правило, выполняете больше операций с отдельным фрагментом данных, вы получаете намного меньше, а переполнение кэша, приводящее к серьезной потере производительности, встречается не так уж редко.
Размер кэша данных также ограничен. Это означает, что вы обычно хотите, чтобы ваши данные были упакованы настолько плотно, насколько это возможно, чтобы как можно больше данных помещалось в кэш. Просто для одного очевидного примера, структура данных, которая связана с указателями, должна немного выиграть с точки зрения вычислительной сложности, чтобы компенсировать объем пространства кэша данных, используемого этими указателями. Если вы собираетесь использовать связанную структуру данных, вы, как правило, хотите по крайней мере убедиться, что вы связываете вместе относительно большие фрагменты данных.
Однако во многих случаях я обнаружил, что приемы, которые я первоначально изучил для встраивания данных в крошечные объемы памяти в крошечных процессорах, которые (в основном) устарели десятилетиями, довольно хорошо работают на современных процессорах. Намерение теперь состоит в том, чтобы поместить больше данных в кэш, а не в основную память, но эффект почти тот же. Во многих случаях вы можете считать инструкции процессора практически свободными, а общая скорость выполнения определяется пропускной способностью кеша (или основной памяти), поэтому дополнительная обработка для распаковки данных из плотного формата работает в твоя польза Это особенно верно, когда вы имеете дело с достаточным количеством данных, которые больше не будут помещаться в кеш, поэтому общая скорость зависит от пропускной способности основной памяти. В этом случае вы можете выполнить lot инструкций, чтобы сохранить несколько операций чтения из памяти и при этом выйти вперед.
Параллельная обработка может усугубить эту проблему. Во многих случаях переписывание кода для параллельной обработки может привести практически к снижению производительности, а иногда даже к снижению производительности. Если общая скорость определяется пропускной способностью ЦП и памяти, наличие большего количества ядер, конкурирующих за эту пропускную способность, вряд ли принесет пользу (и может принести существенный вред). В таком случае использование нескольких ядер для повышения скорости часто сводится к тому, чтобы делать более плотную упаковку данных и использовать еще большую вычислительную мощность для распаковки данных, поэтому реальный выигрыш в скорости достигается за счет уменьшения потребляемой полосы пропускания. и дополнительные ядра просто не теряют время на распаковку данных из более плотного формата.
Другая проблема, связанная с кэшем, которая может возникнуть при параллельном кодировании, - это разделение (и ложное разделение) переменных. Если двум (или более) ядрам необходимо выполнить запись в одно и то же место в памяти, строка кэша, содержащая эти данные, может в конечном итоге перемещаться назад и вперед между ядрами, чтобы дать каждому ядру доступ к общим данным. Результатом часто является код, который работает медленнее параллельно, чем в последовательном (то есть на одном ядре). Существует разновидность так называемого «ложного совместного использования», при которой код на разных ядрах записывает в отдельные данные , но данные для разных ядер попадают в одну и ту же строку кэша. Поскольку кэш-память контролирует данные исключительно в виде целых строк данных, данные в любом случае перетасовываются назад и вперед между ядрами, что приводит к точно такой же проблеме.