모턴 주문으로 가장 가까운 이웃 검색의 이점은 무엇입니까?

Question

입자 상호 작용에 대한 시뮬레이션을 수행하면서 모트 오더 (Z 순서) (Wikipedia link)의 그리드 인덱싱을 발견했습니다.이 모눈 인덱싱은 효율적으로 가장 가까운 이웃 셀 검색을 제공하는 것으로 간주됩니다. 내가 읽은 주된 이유는 메모리에서 공간적으로 가까운 셀을 거의 순차적으로 정렬한다는 것입니다.

첫 번째 구현의 중간에 있기 때문에 가장 가까운 이웃에 대한 알고리즘을 효과적으로 구현하는 방법에 대해 머리를 감쌀 수 없습니다. 특히 기본 균일 격자와 비교할 때 특히 그렇습니다.

1. 주어진 셀 (x, y)은 8 개의 인접 셀 인덱스를 얻고 각각의 z- 인덱스를 계산하는 것이 간단합니다. 이것은 요소에 대한 일정한 액세스 시간을 제공하지만, Z- 인덱스는 미리 정의 된 테이블 (각 축에 대해 개별적으로 OR 연산)에서 계산되거나 조회됩니다. 어떻게하면 더 효율적일까요? A [0] -> A 1 -> A [3] -> A [4] -> ...가 순서 A보다 더 효율적이라고 말하는 순서 A의 요소에 액세스하는 것은 사실입니까? ] -> A [12] -> A [456] -> A [56] -> ...?

2. 가장 가까운 이웃을 z 순서로 찾는 간단한 알고리즘이있을 것으로 기대했습니다. 선을 따라 뭔가 : 이웃의 첫 번째 셀을 찾아서 반복합니다. 그러나 이것이 사실 일 수는 없지만, 이것은 2^4 크기의 블록 안에서만 잘 작동합니다. 그러나 두 가지 문제가 있습니다. 셀이 경계에 없으면 블록의 첫 번째 셀을 쉽게 결정할 수 있고 블록의 셀을 반복 할 수 있지만 셀이 가장 가까운 이웃인지 여부를 확인해야합니다. 세포가 경계에 놓여있는 경우가 2^5 세포를 고려해야하는 것보다 나쁘다. 내가 여기서 무엇을 놓치고 있니? 필요한 것을 할 수있는 비교적 간단하고 효율적인 알고리즘이 있습니까?

포인트 1. 문제는 쉽게 테스트 할 수 있습니다,하지만 난 설명 된 액세스 패턴 생성 정말 무대 뒤에서 무슨 일이 일어나고 있는지 이해하고자하는 기본 지침에 익숙하지 않다. 어떤 도움, 참고 문헌 등 사전에

감사합니다 ...

---

편집 :
포인트 1을 명확히 주셔서 감사합니다! 따라서 Z 순서를 사용하면 흥미로운 인접 셀에 대한 평균 캐시 히트 율이 증가합니다. 캐시 히트/손실 비율을 프로파일 링하는 방법이 있습니까?

관련 항목 2 : 색인 i = f (x1, x2, ..., xd)가 얻어지는 R^d의 점 구름에 대해 모턴 배열을 만드는 방법을 이해해야한다고 추가해야합니다. 등 인터레이스 비트에서 내가 가장 가까운 이웃을 얻을 수있는 다음과 같은 순진한 가설 풀이보다 더 좋은 방법이 있는지 여부입니다 (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-d 데이터를 순차적으로 액세스하거나 각 요소를 동일한 방식으로 처리하는 데이터 구조를 반복 할 경우 메모리에 순서대로 데이터 요소를 배열하는 것이 공간적 위치 성을 얻는 경향이 있습니다. 즉 요소 N에 액세스 한 직후에 요소 N + 1에 액세스하기 때문에 두 요소를 서로 메모리에 배치해야합니다.

표준 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)는 더 이상 저장 [만큼이나 간단없는 곳에 계산이 운동하는 X + y * rowsize].

Morton 정렬을 사용하여 응용 프로그램을 구현하려면 좌표 (x, y)를 상점의 주소로 변환하는 방법을 알아야합니다. 다시 말해 store[f(x,y)]과 같이 저장소에 액세스하는 데 사용할 수있는 f(x,y) 함수가 필요합니다.

좀 더 조사해야 할 것 같습니다. 위키피디아 페이지의 링크, 특히 BIGMIN 기능의 링크를 따르십시오.

Answer 2

에 액세스하는 배열 요소가 실제로 더 빠릅니다. CPU는 RAM에서 캐시로 청크로 메모리를로드합니다. 순차적으로 액세스하면 CPU가 다음 덩어리를 쉽게 미리로드 할 수 있으며로드 시간을 알 수 없습니다. 무작위로 액세스하면 불가능합니다. 이를 캐시 일관성이라고하며, 이미 액세스 한 메모리 근처의 메모리에 액세스하는 것이 더 빠름을 의미합니다.

예를 들어, A [1], A [2], A [3] 및 A [4]를로드 할 때 프로세서가 여러 인덱스를 한꺼번에로드하여 매우 사소한 것입니다. 게다가 A [5]에 액세스하려고하면 A [1] 등에서 작업하면서 해당 청크를 미리로드 할 수 있으므로로드 타임을 효과적으로 만들지 못합니다.

그러나 A [1023]을로드하면 프로세서에서 해당 청크를로드해야합니다. 그런 다음 A [12]를로드해야합니다. 아직로드하지 않았으므로 새 덩어리를로드해야합니다. 기타 등등. 그러나 나머지 질문에 대해서는 잘 모릅니다.