Преимущества поиска ближайшего соседа с помощью Мортон-заказа?

Question

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

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

1. Учитывая ячейку (x, y), тривиально получить 8 индексов соседних ячеек и вычислить соответствующий z-индекс.Хотя это обеспечивает постоянное время доступа к элементам, z-индекс должен быть либо рассчитан, либо найден в предварительно определенных таблицах (отдельно для каждой оси и операции OR).Как это может быть более эффективным?Правда ли, что доступ к элементам в массиве A в порядке, скажем, A [0] -> A 1 -> A [3] -> A [4] -> ... более эффективен, чемв порядке A [1023] -> A [12] -> A [456] -> A [56] -> ...?

2. Я ожидал, что существуетболее простой алгоритм поиска ближайших соседей в 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

Answer 1

В современных многоуровневых компьютерных системах на основе кэша пространственная локальность является важным фактором оптимизации времени доступа к элементам данных.

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

Когда к 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.

Answer 2

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

В вашем примере при загрузке A [1], A [2], A [3] и A [4], процессор, вероятно, загружал несколько таких индексов одновременно, что делает их очень тривиальными.Более того, если вы продолжите пытаться получить доступ к A [5], он может предварительно загрузить этот чанк, пока вы работаете с A [1] и т. Д., Что фактически не дает времени загрузки.

Однако, есливы загружаете A [1023], процессор должен загружать этот фрагмент.Затем он должен загрузить A [12] - который он еще не загрузил и, следовательно, должен загрузить новый чанк.И так далее, и так далее.Однако я не имею понятия об остальной части вашего вопроса.