Beneficios de la más cercana de búsqueda vecino con Morton orden?

Question

Mientras se trabaja en la simulación de las interacciones de partículas, me encontré con indexación rejilla en Morton orden (orden Z) ( Wikipedia enlace ) que se considera para proporcionar una eficiente búsqueda de célula vecina más cercana. La razón principal por la que he leído es el ordenamiento secuencial de células casi espacialmente cercanos en la memoria.

Al estar en el medio de una primera aplicación, no puedo hacerme a la forma de aplicar eficazmente el algoritmo de los vecinos más cercanos, especialmente en comparación con una red 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 o bien ha de ser calculada o mirado en tablas predefinidas (separado para cada eje y OR'ing). ¿Cómo puede posiblemente ser más eficiente? Es cierto, que el acceso a elementos de una matriz A en un orden digamos A [0] -> A 1 -> a [3] -> a [4] -> ... es más eficiente que en un orden a [1023] -> a [12] -> a [456] -> A [56] -> ...

2. he esperado que existe un algoritmo simple para encontrar los vecinos más cercanos en orden z. Algo a lo largo de las líneas: encontrar primera celda de vecinos, iterate. Pero esto no puede ser cierto, ya que esto funciona muy bien sólo dentro de 2 ^ 4 bloques de tamaño. Hay dos problemas sin embargo: cuando la célula no está en el límite, se puede determinar fácilmente la primera celda del bloque y iterar a través de las células en el bloque, pero uno tiene que comprobar si la célula es un vecino más cercano. Peor aún es el caso cuando las mentiras de células en el límite, que uno tiene que tener en cuenta 2 ^ 5 células. ¿Que me estoy perdiendo aqui? ¿Existe un algoritmo relativamente simple y eficiente que va a hacer 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 sería realmente como para 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! Por lo tanto, la orden Z, la tasa de aciertos de caché se incrementa en promedio para las células vecinas, interesante. ¿Hay una manera de tasas de éxito / Miss perfil de caché?

Respecto al punto 2: Debo añadir que entiendo cómo construir la matriz ordenada-Morton para una nube de puntos en R ^ d donde el índice i = f (x1, x2, ..., xd) se obtiene de modo bit entrelazado etc. Lo que intento 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 los sistemas informáticos basados ??en caché multinivel modernas, localidad espacial es un factor importante en la optimización de acceso en tiempo de elementos de datos.

En pocas palabras, esto significa que si se accede a un elemento de datos en la memoria, a continuación, acceder a otro elemento de datos en la memoria que está cerca (tiene una dirección que está cerca de la primera) puede ser más barato en varios órdenes de magnitud que el acceso a un conjunto de datos elemento 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 las estructuras de datos de 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, desde que elemento de acceso N + 1 justo después de acceder a elementos N, los dos elementos deben ser colocados uno junto al otro en la memoria.

matrices estándar de C (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 elemento (x, y), puede ir de acceso (x + 1, y) o (x, y + 1) o similar.

Los medios de ordenamiento Morton que (x, y), (x + 1, y) y (x, y + 1) están cerca el uno al otro en la memoria. En una matriz multidimensional c estándar, esto no es necesariamente el caso. Por ejemplo, en la myArray array [10000] [10000], (x, y) y (x, y + 1) son 10000 elementos aparte -. Demasiado separados para tomar ventaja de 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 la aplicación mediante Morton pedido, es necesario encontrar la manera de transformar una coordenada (x, y) en la dirección en la tienda. En otras palabras, se necesita un f(x,y) función que se puede utilizar para acceder al almacén como en store[f(x,y)].

Parece que tienen que hacer más investigación - siga los enlaces de la página de Wikipedia, en particular los de la función BIGMIN

.

Answer 2

Sí, el acceso a elementos de la matriz con el fin de hecho es más rápido. La memoria RAM de cargas de CPU en la memoria caché en trozos. Si accede a secuencialmente, la CPU puede precargar el siguiente fragmento fácilmente, y no se dará cuenta el tiempo de carga. Si un acceso aleatorio, no se puede. Esto se llama coherencia de caché, y lo que significa es que el acceso a la memoria cerca de la memoria que ya ha accedido es más rápido.

En su ejemplo, cuando se carga un [1], A [2], A [3] y A [4], el procesador probablemente cargan varios de esos índices a la vez, haciéndolos muy trivial. Por otra parte, si a continuación, pasar a tratar de acceder a un [5], se puede pre-carga que trozo mientras está operando en un [1] y la red, para establecer el tiempo de carga efectivamente nada.

Sin embargo, si se carga A [1023], el procesador debe cargar ese trozo. Entonces debe cargar A [12] - que no ha ya cargado y por lo tanto debe cargar un nuevo trozo. Etcétera, etcétera. No tengo ninguna idea sobre el resto de su pregunta, sin embargo.