Преимущества поиска ближайшего соседа с помощью Мортон-заказа?
Работая над моделированием взаимодействий частиц, я наткнулся на индексацию сетки в порядке Мортона (Z-порядок)( ссылка на Википедию), которая, как считается, обеспечивает эффективный поиск ближайшей соседней ячейки. Основная причина, которую я прочитал, - это почти последовательное упорядочение пространственно близких ячеек в памяти.
Находясь в середине первой реализации, я не могу понять, как эффективно реализовать алгоритм для ближайших соседей, особенно по сравнению с базовой равномерной сеткой.
Для заданной ячейки (x,y) тривиально получить 8 индексов соседних ячеек и вычислить соответствующий z-индекс. Хотя это обеспечивает постоянное время доступа к элементам, z-индекс должен быть либо рассчитан, либо найден в предварительно определенных таблицах (отдельно для каждой оси и операции OR). Как это может быть более эффективным? Правда ли, что доступ к элементам в массиве A в порядке, скажем, A [0] -> A 1 -> A [3] -> A [4] ->... более эффективен, чем в порядке A[1023] ] -> A[12] -> A[456] -> A[56] -> ...?
Я ожидал, что существует более простой алгоритм поиска ближайших соседей в z-порядке. Что-то в этом роде: найти первую ячейку соседей, повторить. Но это не может быть правдой, поскольку это хорошо работает только в пределах 2^4 блоков. Однако есть две проблемы: когда ячейка не находится на границе, можно легко определить первую ячейку блока и выполнить итерацию по ячейкам в блоке, но нужно проверить, является ли ячейка ближайшим соседом. Хуже случай, когда ячейка лежит на границе, чем нужно учитывать 2^5 ячеек. Что мне здесь не хватает? Есть ли сравнительно простой и эффективный алгоритм, который будет делать то, что мне нужно?
Вопрос в пункте 1. легко тестируемый, но я не очень знаком с базовыми инструкциями, которые генерирует описанный шаблон доступа, и очень хотел бы понять, что происходит за кулисами.
Заранее спасибо за любую помощь, ссылки и т.д...
РЕДАКТИРОВАТЬ:
Спасибо за разъяснение пункта 1! Таким образом, при Z-упорядочении частота попаданий в кэш увеличивается в среднем для соседних ячеек, что интересно. Есть ли способ профилировать рейтинг попаданий / промахов в кеш?
Что касается пункта 2: я должен добавить, что я понимаю, как построить упорядоченный по Мортону массив для облака точек в R^d, где индекс i = f(x1, x2, ..., xd) получается из побитового чередования и т. Д. Я пытаюсь понять, есть ли лучший способ, чем следующий наивный анзац, найти ближайших соседей (здесь, в d=2, "псевдокод"):
// Get the z-indices of cells adjacent to the cell containing (x, y)
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2
point = (x, y)
zindex = f(x, y)
(zx, zy) = f^(-1)(zindex) // grid coordinates
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1), // neighbor grid
(zx , zy - 1), (zx, zy + 1), // coordinates
(zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]
ni= [f(x[0], x[1]) for x in nc] // neighbor indices
2 ответа
В современных многоуровневых компьютерных системах на основе кэша пространственная локальность является важным фактором оптимизации времени доступа к элементам данных.
Проще говоря, это означает, что если вы обращаетесь к элементу данных в памяти, то доступ к другому элементу данных в памяти, который находится поблизости (имеет адрес, который близок к первому), может быть дешевле на несколько порядков, чем доступ к элементу данных, который является далеко.
Когда к 1-м данным обращаются последовательно, как при простой обработке изображений или обработке звука, или итерируя по структурам данных, обрабатывая каждый элемент одинаковым образом, то расположение элементов данных в памяти имеет тенденцию к достижению пространственной локализации - то есть, поскольку вы получаете доступ к элементу N+1 сразу после доступа к элементу N, эти два элемента должны быть размещены рядом друг с другом в памяти.
Стандартные массивы c (и многие другие структуры данных) обладают этим свойством.
Задача упорядочения Мортона заключается в поддержке схем, в которых доступ к данным осуществляется в двух измерениях, а не в одном. Другими словами, после доступа к элементу (x,y), вы можете перейти к доступу (x+1,y) или (x,y+1) или подобному.
Порядок Мортона означает, что (x,y), (x+1,y) и (x,y+1) находятся рядом друг с другом в памяти. В стандартном многомерном массиве c это не обязательно так. Например, в массиве myArray[10000][10000], (x,y) и (x,y+1) разделены на 10000 элементов - слишком далеко друг от друга, чтобы использовать преимущества пространственной локализации.
При упорядочении по Мортону стандартный массив c все еще может использоваться в качестве хранилища данных, но вычисление для определения, где (x,y), уже не так просто, как store[x+y*rowize].
Чтобы реализовать свое приложение, используя порядок Мортона, вам нужно решить, как преобразовать координату (x, y) в адрес в магазине. Другими словами, вам нужна функция f(x,y) которые могут быть использованы для доступа к магазину, как в store[f(x,y)],
Похоже, вам нужно провести дополнительное исследование - перейдите по ссылкам со страницы википедии, особенно по ссылкам на BIGMIN функция.
Да, доступ к элементам массива по порядку действительно быстрее. Процессор загружает память из оперативной памяти в кеш порциями. Если вы осуществляете последовательный доступ, процессор может легко предварительно загрузить следующий блок, и вы не заметите время загрузки. Если вы получаете случайный доступ, он не может. Это называется когерентностью кэша, и это означает, что доступ к памяти рядом с памятью, к которой вы уже обращались, быстрее.
В вашем примере при загрузке A[1], A[2], A[3] и A[4] процессор, вероятно, загружал несколько из этих индексов одновременно, что делает их очень тривиальными. Более того, если вы продолжите пытаться получить доступ к A[5], он может предварительно загрузить этот чанк, пока вы работаете с A [1] и т. Д., Что практически ничего не изменит для времени загрузки.
Однако, если вы загрузите A[1023], процессор должен загрузить этот фрагмент. Затем он должен загрузить A[12]- который он еще не загрузил и, следовательно, должен загрузить новый кусок. И так далее, и так далее. Тем не менее, я не имею ни малейшего представления об остальной части вашего вопроса.