Код дизайна для помещений в Кэш ЦП?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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