Как определить коэффициент блокировки для кеширования
Я пытаюсь найти способ кэшировать мой массив элементов для приложения, которое использует Ближайшая пара алгоритм (грубая сила в настоящее время).
В соответствии с Производительность кэша и оптимизация блокированного алгоритма бумага это говорит:
Блокировка — это общая техника оптимизации для увеличения
Эффективность иерархии памяти. Повторное использование данных в более быстром
Уровень иерархии, это сокращает среднюю задержку доступа. Это
также уменьшает количество ссылок на более медленные уровни
иерархия. Таким образом, блокирование превосходит оптимизацию, такую как
предварительная выборка, которая скрывает задержку, но не уменьшает память
Требуемая пропускная способность. Это сокращение особенно важно для
мультипроцессоры, так как пропускная способность памяти часто является узким местом
система. Было показано, что блокировка полезна для многих алгоритмов в
линейная алгебра.
В статье приведен матричный код умножения, и он модифицирован для блокирования с уменьшенными потерями в кеше:
for kk = 1 to N by B
for j = 1 to N by B
for i = 1 to N
for k = kk to min(kk + B-1, N)
r = X[i,k]; // register allocated
for j = jj to min(jj + B-1, N)
Z[i,j] += r * Y[k,j];
Вот, В это фактор блокировки но как мы можем определить это? Есть ли общий способ найти конкретный предел, который может обрабатывать кеш процессора? Вероятно, не все процессоры имеют одинаковый кеш. Общая процедура гласит:
- Во-первых, это реструктурировать код, чтобы разрешить блокировку тех циклов, которые содержат повторное использование.
- Во-вторых, выбрать фактор блокировки, который максимизирует местность.
Алгоритм ближайшей пары (перебор):
minDist = infinity
for i = 1 to length(P) - 1
for j = i + 1 to length(P)
let p = P[i], q = P[j]
if dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair
Подводить итоги:
- Как оптимизировать B-фактор без необходимости вручную проверять, какой лимит для конкретного размера кэша процессора. Есть ли способ вернуть текущий доступный кеш, используя язык Си?
- Как я могу оптимизировать алгоритм ближайшей пары, который использует одномерный массив? Я имею в виду, какие элементы должны храниться и использоваться повторно, поскольку это одномерный массив структурных элементов, которые содержат x, y кординаты и каждая точка должна сравниваться со всеми остальными точками (давайте придерживаться алгоритма грубой силы).
Заранее спасибо!
Решение
Первый вопрос:
Простого метода определения не существует В без фактического тестирования на машине, для которой вы собираетесь оптимизировать. Сказав это, вы можете, вероятно, с некоторыми экспериментами найти некоторые «хорошие для большинства систем» числа (я довольно много работал над такими вещами около 12-15 лет назад), и я обнаружил, что использование чего-то около 8-16KB блоков работает неплохо. Эффект довольно драматичен между «просто пробежаться по всей памяти» и «работать с блоками», и если вы начнете с действительно маленьких блоков, вы сможете увидеть некоторое значительное улучшение, когда начнете увеличиваться. Затем «возврат» падает, пока вы не достигнете уровня, на котором В настолько велик, что вы вернулись к тому, с чего начали (выбрасывая хороший кеш, чтобы получить что-то еще, что вы никогда не будете использовать до того, как оно будет выброшено).
Я вполне уверен, что если вы работаете через выбор «размеров» В для вашего кода, и тестирование производительности, которую вы получаете, и если вы строите график, вы, вероятно, обнаружите, что он выглядит как «ванна», если вы наносите «взятое время» (или вверх ногами ванну, если вы строите »число предметов, обработанных за единицу времени «). Просто найдите какую-то точку в «плоской» части ванны. Однако попробуйте это на нескольких разных машинах, просто чтобы убедиться, что вы находитесь в «плоском положении» на всех (или, по крайней мере, на большинстве) машин.
Для вашего второго вопроса, что-то вроде этого:
minDist = infinity
for i = 1 to length(P) - 1 by B
for j = i + 1 to length(P) by B
for ib = i to i+B-1
for jb = j to j+B-1
let p = P[ib], q = P[jb]
if dist(p, q) < minDist:
minDist = dist(p, q)
closestPair = (p, q)
return closestPair
Если length(P) не кратно В, есть немного дополнительной работы, чтобы иметь дело с последними несколькими элементами, поэтому вместо i+B-1 в ib цикл вам может понадобиться max(length(P), i+B-1) и подобное для jb петля.
Редактировать:
Кеш сам по себе решает, какие данные хранятся в кеше, и вы мало что можете сделать, чтобы изменить то, что здесь происходит. Вы можете изменить то, над какими блоками данных вы работаете.
Ключом к «блокированию» является сохранение данных, над которыми ведется работа, в (L1) кеше.
Допустим, вся блокировка данных составляет 100000 элементов по 4 байта каждый, то есть около 400 КБ. Это не поместится в кэш L1 любого современного процессора, так как он составляет не более 64 КБ, часто 32 КБ. Поэтому, когда мы перебираем пункты с i, j Цикл будет «выбрасывать» все хорошее содержимое кэша L1, загружая более поздние части массива. И, конечно же, как j цикл запускается в следующий раз, ни одна из данных, находящихся в данный момент в кеше, бесполезна, потому что это все высокие показатели массива.
Если мы вместо этого работаем с небольшим количеством массива за раз, в блоках, мы можем работать через квадрат В размер массива в каждом цикле — где В элементы не занимают больше места, чем могут поместиться в кеше. Итак jb цикл не выбрасывает данные для ib петля (или наоборот). Это означает, что каждый из внутренних циклов выполняется значительно быстрее (я видел более чем в 3 раза более быстрое выполнение, и это в коде, который уже должен был быть «хорошим»).
Другие решения
Других решений пока нет …
detector