Benefícios do vizinho mais próximo de pesquisa com Morton-ordem?

Question

Ao trabalhar com a simulação de interações entre partículas, deparei-me com grade de indexação em Morton-ordem (ordem-Z)(Link da Wikipedia) que é considerado para proporcionar uma eficiente vizinho mais próximo célula de pesquisa.A principal razão que eu li é quase ordem seqüencial dos espacialmente perto células de memória.

Estar no meio de uma primeira implementação, eu não posso quebrar a minha cabeça em torno de como eficiente de implementar o algoritmo para os vizinhos mais próximos, especialmente em comparação com uma base uniforme de grade.

1. Dada uma célula (x,y) é trivial obter a 8 vizinho célula índices e calcular as respectivas z-index.Embora este fornece a constante de tempo de acesso aos elementos, o z-index tem de ser calculado, ou olhou para cima em tabelas predefinidas (separado para cada eixo e OU ing).Como é que isto pode ser mais eficiente?É verdade, que o acesso a elementos de uma matriz a em Uma ordem de dizer A[0] -> Um1 -> A[3] -> A[4] -> ...é mais eficiente do que em uma ordem Um[1023] -> A[12] -> A[456] -> A[56] -> ...?

2. Eu tenho esperado que existe um simples algoritmo para encontrar os vizinhos mais próximos, em ordem inversa.Algo ao longo das linhas de:encontrar primeira célula de vizinhos, iterar.Mas isso não pode ser verdade, como isso funciona muito bem, somente dentro de 2^4 blocos de tamanho.Há dois problemas, no entanto:Quando a célula não está no limite, pode-se determinar facilmente a primeira célula do bloco e iterar através de células no bloco, mas um foi para verificar se a célula é um vizinho mais próximo.Pior é o caso quando a célula está no limite, que um tem que levar em conta 2^5 células.O que estou ausente aqui?Há uma relativamente simples e eficiente algoritmo que vai fazer o que eu preciso?

A questão no ponto 1.é facilmente testáveis, mas eu não estou muito familiarizado com as instruções subjacentes que o descrito o padrão de acesso gera e realmente gostaria de entender o que está acontecendo por trás das cenas.

Agradecemos antecipadamente por qualquer ajuda, referências, etc...

---

EDITAR:
Obrigado por esclarecer o ponto 1!Assim, com Z-ordenação, a taxa de acertos de cache é aumentado, em média, para o vizinho células, interessante.Existe uma maneira de perfil de cache hit/miss taxas?

Relativamente ao ponto 2:Devo acrescentar que eu entendo como construir o Morton-ordenou matriz para uma nuvem de pontos em R^d) onde o índice i = f(x1, x2, ..., xd) é obtido a partir de bit a bit entrelaçamento etc.O que eu tento entender é se existe uma maneira melhor do que o seguinte ingênuo ansatz para obter os vizinhos mais próximos (aqui em 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

Na moderna multi-cache de nível baseado em sistemas de computador, localidade espacial é um fator importante na optimização do acesso em tempo para elementos de dados.

Simplificando, isso significa que se você acessar um elemento de dados em memória, em seguida, acessar outro elemento de dados na memória que é perto (tem um endereço que está perto de primeira) pode ser mais barato por várias ordens de magnitude que o acesso a um elemento de dados que está longe.

Quando a 1-d dados são acessados sequencialmente, como no simplesmente de processamento de imagem ou de som, processamento de dados, ou de iteração através de estruturas de dados processamento de cada elemento da mesma forma, em seguida, organizar os elementos de dados na memória tende a alcançar a localidade espacial - por exemplo,desde que você acessar o elemento N+1 só depois de acessar o elemento de N, os dois elementos devem ser colocados ao lado uns dos outros na memória.

Padrão de matrizes c (e muitas outras estruturas de dados) têm esta propriedade.

O ponto de Morton ordenação é para os regimes de apoio, onde os dados são acessados dois dimensionalmente, em vez de um dimensionalmente.Em outras palavras, depois de acessar o elemento (x,y), você pode ir para o acesso (x+1,y) ou (x,y+1) ou similar.

O Morton ordenação significa que (x,y), (x+1,y) e (x,y+1) estão perto uns dos outros na memória.Em um padrão de c matriz multidimensional, este não é necessariamente o caso.Por exemplo, na matriz myArray[10000][10000], (x,y) e (x,y+1) são 10000 elementos apart - muito longe de tirar vantagem da localidade espacial.

---

Em um Morton pedido, uma matriz c padrão pode ainda ser utilizado como um armazenamento de dados, mas o cálculo para saber onde (x,y) é não é mais tão simples como o armazenamento de[x+y*rowsize].

Para implementar seu aplicativo usando Morton pedido, você precisa descobrir como transformar uma coordenada (x,y) para o endereço da loja.Em outras palavras, você precisa de uma função f(x,y) que pode ser usado para acessar a loja, como no store[f(x,y)].

Parece que você precisa de fazer mais algumas pesquisas - siga os links da página do wikipédia, particularmente aqueles que se encontram no BIGMIN função.

Answer 2

Sim, acessar elementos da matriz em ordem é realmente mais rápido. A CPU carrega a memória da RAM em cache em pedaços. Se você acessar sequencialmente, a CPU poderá pré -carregar o próximo pedaço facilmente e você não notará o tempo de carregamento. Se você acessar aleatoriamente, não pode. Isso é chamado de coerência do cache, e o que significa é que o acesso à memória próximo à memória que você já acessou é mais rápido.

No seu exemplo, ao carregar A [1], A [2], A [3] e A [4], o processador provavelmente carregou vários desses índices ao mesmo tempo, tornando -os muito triviais. Além disso, se você tentar acessar um [5], ele poderá pré-carregar esse pedaço enquanto opera em um [1] e tal, tornando o tempo de carregamento eficazmente nada.

No entanto, se você carregar um [1023], o processador deverá carregar esse pedaço. Em seguida, ele deve carregar um [12]- que ainda não carregou e, portanto, deve carregar um novo pedaço. Et Cetera, etc. No entanto, não tenho idéia do resto da sua pergunta.