Первый цикл проходит r_rel в последовательном порядке памяти, проходя через каждую строку перед переходом к следующему: он обращается к r_rel[i][j], проходя итерацию по каждому значению j перед увеличением i.
Второй цикл пересекает r_rel с двумя движущимися точками доступа, одна проходит в последовательном порядке памяти и проходит по столбцам матрицы, перепрыгивая через ряды. Это последнее поведение плохо для кэша и имеет низкую производительность. Обход основных массивов строк вдоль столбцов, как известно, плохо влияет на производительность кэша.
Кэш-память - это дорогая высокопроизводительная память, которая используется для хранения копий недавно использованных данных или данных, которые были загружены из памяти в ожидании использования в ближайшем будущем. Когда программа использует память способом, который часто обращается к данным, находящимся в кеше, она может выиграть от высокой производительности кеш-памяти. Когда программа часто обращается к данным, которые не находятся в кеше, процессор должен обращаться к данным в общей памяти, которая намного медленнее, чем кэш.
Типичные особенности дизайна кэша:
- Кэш организован в строк , которые являются единицами непрерывной памяти. 64 байта - это типичный размер строки.
- Строки кэша организованы в наборы . Каждый набор связан с определенными битами из адреса памяти. Кэш может содержать, например, две или восемь строк в каждом наборе.
- В каждом наборе строка может быть копией любой части памяти, биты которой назначены ее набору. Например, рассмотрим адрес с битами
aa…aaabbbcccccc. Шесть c битов говорят нам, какой байт находится в строке кэша. (2 6 = 64). Три b бита говорят нам, в какой кеш должен быть установлен этот байт. a биты записываются в строке кэша, помня, где в памяти он принадлежит.
Когда процесс работает через r_rel[i][j] в последовательном порядке памяти, то каждый раз, когда он обращается к элементу r_rel, тот, к которому он обращается, является либо частью той же строки кэша, к которой только что обращались в предыдущей итерации, либо находится в следующей строке кэша. В первом случае данные уже находятся в кэше и быстро доступны для процессора. В последнем случае он должен быть извлечен из памяти. (Некоторые процессоры уже инициировали эту выборку, так как они предварительно выбирают данные, которые опережают недавние обращения к памяти. Они предназначены для этого, потому что такой доступ к памяти является распространенным шаблоном.)
Из приведенного выше видно, что первый набор кода должен будет выполнить одну загрузку строки кэша для каждой строки кэша в r_rel. Ниже мы сравним это число с аналогичным номером для второго набора кода.
Во втором наборе кода одно из применений r_rel продолжается так же, как и в первом наборе кода, хотя он проходит только половину массива. Для r_rel[i][j] он выполняет около половины загрузок кеша первого кода. Он выполняет несколько дополнительных нагрузок из-за неэффективного использования по диагонали, но мы можем пренебречь этим.
Однако другое использование r_rel, r_rel[j][i] затруднительно. Он проходит через ряды r_rel.
Вопрос не дает нам много подробностей, поэтому я приведу некоторые значения для иллюстрации. Предположим, что элементы r_rel имеют четыре байта каждый, а N, количество элементов в строке или столбце, кратно 128. Также предположим, что кэш состоит из 32 768 байтов, организованных в 64 набора по 8 строк по 64 байта. каждый. При этой геометрии остаток (остаток после деления) адреса по модулю 512 определяет, какому кэш-набору должна быть назначена память.
Итак, при обращении к r_rel[j][i] 64 байта памяти вокруг этого адреса заносятся в кеш и присваиваются определенному набору кеша.Когда при увеличении j память вокруг этого адреса заносится в кеш и назначается определенному набору кеша. Это один и тот же набор кэша. Поскольку строки состоят из 128 элементов, а каждый элемент составляет четыре байта, расстояние между двумя элементами, которые находятся на расстоянии ровно одной строки, составляет 128 • 4 = 512 байтов, что является одинаковымкак число, используемое для определения того, в какой набор кеша входит строка.Таким образом, эти два элемента присваиваются одному и тому же набору кеша.
Сначала все в порядке.Набор кэша состоит из восьми строк.К сожалению, код продолжает повторяться j.После того, как j был увеличен в восемь раз, он получает доступ к девятому элементу r_rel.Поскольку набор кеша содержит только восемь строк, процессор должен удалить одну из предыдущих строк из набора.Поскольку код продолжает повторять j, больше строк удаляются.В конце концов, все предыдущие строки удаляются.Когда код заканчивает свою итерацию j и увеличивает i, он возвращается к началу массива.
Вспомните, что в первом наборе кода при обращении к r_rel[0][2] онвсе еще находился в кеше с момента обращения к r_rel[0][1].Тем не менее, во втором наборе кода r_rel[0][2] давно ушел из кэша.Процессор должен загрузить его снова.
Для доступа к r_rel[j][i] второй набор кода фактически не получает никакой выгоды от кэша.Он должен загружаться из памяти для каждого доступа.Поскольку в этом примере в каждой строке кэша имеется 16 элементов (четырехбайтовые элементы, 64-байтовые строки), у него примерно в 16 раз больше обращений к памяти для половины матрицы.
Всего, есливо всем массиве имеется x строк кэша, первый набор кода загружает x строк кэша, а второй набор кода загружает около x / 2 кэшастрок для доступа r_rel[i][j] и около x / 2 • 16 = 8 • x строк кэша для доступа r_rel[i][j], всего 8,5 • x загрузка строки кэша.
Обход массива в порядке столбцов: ужасно для производительности кэша.
Приведенные выше примеры чисел.Наиболее гибким является размер массива N.Я предположил, что это было кратно 64. Мы можем рассмотреть некоторые другие значения.Если вместо этого он кратен 32, то r_rel[j][i] и r_rel[j+1][i] будут сопоставлены с различными наборами кэша.Однако r_rel[j][i] и r_rel[j+2][i] соответствуют одному и тому же набору.Это означает, что после восьми итераций j будут использоваться только четыре строки в каждом наборе, поэтому старые строки пока не нужно удалять.К сожалению, это очень мало помогает, потому что, как только i превышает 16, код итерирует j через достаточно значений, чтобы набор кеша снова очищался от более ранних строк, поэтому каждый цикл в j должен загружать каждую строку кеша, которую онвстреч.
С другой стороны, установка для N значения, такого как 73, может смягчить некоторые из этих эффектов.Конечно, вы не хотите изменять размер вашего массива только в соответствии с аппаратным обеспечением компьютера.Однако, одну вещь, которую вы можете сделать, это сделать размеры массива в памяти N на NP, даже если используются только элементы N на N.NP (расшифровывается как «N Padded») выбирается, чтобы сделать строки нечетного размера относительно геометрии кэша.Дополнительные элементы просто тратятся впустую.
Это обеспечивает быстрый способ изменить программу, чтобы продемонстрировать, что эффекты кэша замедляют ее выполнение, но обычно это не предпочтительное решение.Другой подход - плитка доступ к массиву.Вместо итерации i и j по всему массиву, массив разбивается на плитки некоторого размера, A строк по B столбцам.Два внешних цикла перебирают все тайлы, а два внутренних цикла перебирают элементы массива в каждом тайле.
Aи B выбраны так, чтобы все элементы одной плитки оставались в кэше, пока продолжаются внутренние циклы. Для приведенных выше примеров, A и B должны быть равны восьми или меньше, поскольку в одном наборе кэша может содержаться только восемь строк массива. (Могут быть и другие соображения, которые могут сделать оптимальный размер плитки несколько меньшим. Или для разных размеров элементов или значений N оптимальный размер плитки может быть больше.)
Обратите внимание, что при составлении кода возникают некоторые проблемы при написании кода. При обработке фрагмента по диагонали код будет обрабатывать элементы из двух точек в пределах одного фрагмента. При обработке тайла вне диагонали код будет обрабатывать элементы из одной точки в пределах одного тайла и транспонированной точки в другом тайле. Это может повлиять как на код, управляющий индексами массива, так и на границы внутренних циклов. Для плиток по диагонали внутренние петли будут выглядеть как ваше j < i условие, обрабатывая треугольник. Для недиагональных плиток внутренние циклы будут обрабатывать полный квадрат (или прямоугольник, если A и B отличаются).