¿Beneficios de la búsqueda del vecino más cercano con el pedido de Morton?

Question

Mientras trabajaba en la simulación de interacciones entre partículas, tropecé con la indexación de la cuadrícula en Morton-order (orden Z) (Wikipedia link) que se considera que proporciona una búsqueda eficiente de células vecinas más cercanas. La razón principal que he leído es el orden casi secuencial de celdas espacialmente cercanas en la memoria.

Al estar en la mitad de una primera implementación, no puedo entender cómo implementar eficientemente el algoritmo para los vecinos más cercanos, especialmente en comparación con una cuadrícula básica uniforme.

1. Dado una célula (x, y) es trivial para obtener los índices de glóbulos 8 vecino y calcular la respectiva z-index. Aunque esto proporciona tiempo de acceso constante a los elementos, el índice z debe calcularse o buscarse en tablas predefinidas (separadas para cada eje y OR '). ¿Cómo puede ser esto más eficiente? ¿Es cierto que acceder a los elementos de una matriz A en un orden de decir A [0] -> A 1 -> A [3] -> A [4] -> ... es más eficiente que en una orden A [1023 ] -> A [12] -> A [456] -> A [56] -> ...?

2. He esperado que exista un algoritmo más simple para encontrar los vecinos más cercanos en orden z. Algo a lo largo de las líneas: encuentre la primera celda de vecinos, itere. Pero esto no puede ser cierto, ya que esto funciona muy bien solo dentro de bloques de 2^4 tamaños. Sin embargo, hay dos problemas: cuando la celda no está en el límite, uno puede determinar fácilmente la primera celda del bloque e iterar a través de las celdas del bloque, pero hay que verificar si la celda es el vecino más cercano. Peor es el caso cuando la celda se encuentra en el límite, entonces uno tiene que tener en cuenta 2^5 celdas. ¿Que me estoy perdiendo aqui? ¿Existe un algoritmo comparativamente simple y eficiente que haga lo que necesito?

La pregunta en el punto 1. es fácilmente comprobable, pero no estoy muy familiarizado con las instrucciones subyacentes que el patrón de acceso descrito genera y realmente me gustaría entender lo que está pasando detrás de las escenas.

Gracias de antemano por cualquier ayuda, referencias, etc ...

---

EDIT:
Gracias por aclarar el punto 1! Entonces, con el orden Z, la tasa de aciertos de caché se incrementa en promedio para las celdas vecinas, interesante. ¿Hay alguna manera de registrar las tasas de aciertos/caídas del caché?

En relación con el punto 2: Debo añadir que entiendo cómo se construye la matriz ordenada por Morton para una nube de puntos en R^d donde se obtiene el índice i = f (x1, x2, ..., xd) bit a bit de entrelazado etc. lo que trato de entender es si hay una manera mejor que la siguiente ansatz ingenua para obtener los vecinos más cercanos (aquí en d = 2, "pseudo código"):

// 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

En sistemas informáticos modernos basados ​​en caché de varios niveles, la localidad espacial es un factor importante en la optimización del tiempo de acceso a los elementos de datos.

En pocas palabras, esto significa que si accede a un elemento de datos en la memoria, acceder a otro elemento de datos cercano (tiene una dirección cercana al primero) puede ser más barato en varios órdenes de magnitud que acceder a un elemento de datos que está muy lejos.

Cuando se accede a 1-d de datos de forma secuencial, como en simplemente procesamiento de imágenes o procesamiento de sonido, o iterar sobre estructuras de datos procesamiento de cada elemento de la misma manera, a continuación, la disposición de los elementos de datos en la memoria con el fin tiende a alcanzar localidad espacial - es decir, dado que accede al elemento N + 1 justo después de acceder al elemento N, los dos elementos deben colocarse uno al lado del otro en la memoria.

Las matrices c estándar (y muchas otras estructuras de datos) tienen esta propiedad.

El punto de Morton de pedido es apoyar los esquemas donde se accede a los datos dos dimensionalmente en lugar de uno dimensionalmente. En otras palabras, después de acceder al elemento (x, y), puede acceder a (x + 1, y) o (x, y + 1) o similar.

El orden de Morton significa que (x, y), (x + 1, y) y (x, y + 1) están cerca uno del otro en la memoria. En una matriz c multidimensional estándar, este no es necesariamente el caso. Por ejemplo, en la matriz myArray [10000] [10000], (x, y) y (x, y + 1) están separados 10000 elementos, demasiado separados para aprovechar la localidad espacial.

---

En una ordenación Morton, una matriz estándar c todavía puede ser utilizado como un almacén para los datos, pero el cálculo para calcular dónde (x, y) es ya no es tan simple como almacén [x + y * rowsize].

Para implementar su aplicación con el pedido de Morton, debe averiguar cómo transformar una coordenada (x, y) en la dirección de la tienda. En otras palabras, necesita una función f(x,y) que se puede usar para acceder a la tienda como en store[f(x,y)].

Parece que necesita investigar un poco más: siga los enlaces de la página de la wikipedia, especialmente los de la función BIGMIN.

Answer 2

Sí, accediendo los elementos de la matriz en orden son de hecho más rápidos. La CPU carga memoria en RAM en caché en fragmentos. Si accede de forma secuencial, la CPU puede precargar fácilmente el siguiente fragmento y no notará el tiempo de carga. Si tiene acceso aleatorio, no puede. Esto se llama coherencia de caché, y lo que significa es que acceder a la memoria cerca de la memoria a la que ya accedió es más rápido.

En su ejemplo, al cargar A [1], A [2], A [3] y A [4], el procesador probablemente cargó varios de esos índices a la vez, haciéndolos muy triviales. Además, si luego intenta acceder a A [5], puede precargar ese trozo mientras opera en A [1] y tal, lo que hace que el tiempo de carga sea realmente nada.

Sin embargo, si carga A [1023], el procesador debe cargar ese trozo. Luego, debe cargar A [12], que no se ha cargado todavía y, por lo tanto, debe cargar un nuevo fragmento. Et cetera, etcétera. No tengo idea sobre el resto de tu pregunta, sin embargo.