대각선으로 평탄화 된 행렬에 대한 인접 색인 계산

Question

대각선을 따라 평면 버퍼에 저장된 2D 행렬을가집니다. 예를 들어, 4 × 4 매트릭스는 인덱스과 같이 흩어져 것 :

이 유일합니다

, 원래의 인덱스와 X가 주어 이웃 요소의 인덱스를 계산하는 가장 효율적인 방법은/Y 오프셋 무엇인가? 예를 들어,

// return the index of a neighbor given an offset 
int getNGonalNeighbor(const size_t index, 
         const int x_offset, 
         const int y_offset){ 
    //... 
} 

// for the array above: 
getNGonalNeighbor(15,-1,-1); // should return 11 
getNGonalNeighbor(15, 0,-1); // should return 14 
getNGonalNeighbor(15,-1, 0); // should return 13 
getNGonalNeighbor(11,-2,-1); // should return 1 

여기서 오버플로가 발생하지 않고 랩 어라운드가 발생하지 않는다고 가정합니다.

나는 triangular number과 삼각근 계산을 많이 포함하는 솔루션을 가지고 있습니다. 또한 가능한 많은 분기를 포함하고 있습니다 (분기 제어 흐름이 비싼 GPU에서 실행될 수 있음). 내 솔루션은 작동하지만 매우 길다. 나는 그것을하는 훨씬 더 간단하고 덜 계산 집중적 인 방법이 있어야하는 것처럼 느낀다.

누군가가이 특정 문제/표현에 이름을 붙이면 도움이 될지도 모릅니다.

관심이있는 사람이라면 저의 전체 솔루션을 게시 할 수 있지만 제가 말했듯이 그러한 간단한 작업에는 매우 길고 복잡합니다. 간단히 말해서, 내 솔루션을 수행합니다

• 이 될 것 4 × 4 매트릭스를 들어

(17 될 것입니다 예를 들어 13)이 개 삼각형을 다루는 피하기 위해 더 큰 삼각 행렬로 원래 인덱스를 번역 :

0 2 5 9 14 20 27 
1 4 8 13 19 26 
3 7 12 18 25 
6 11 17 24 
10 16 23 
15 22 
21 

• 오프셋의 맨해튼 거리 인덱스의 삼각 루트를 사용해 표현 이웃의 대각선의 인덱스를 구한다.
• 오프셋을 사용하여이 대각선에서 이웃의 위치를 ​​계산합니다. 패딩을 제거하여 원래 표현으로 다시 변환합니다.

어떤 이유로이 방법은 내가 생각해 낼 수있는 가장 간단한 해결책입니다.

편집 :

오프셋 축적 루프를 갖는

나는 삼각형 번호의 속성 부여,이 두 개의 삼각형의 행렬을 분할하는 것이 더 쉽습니다 실현 (하자를 0 ~ 9의 '상 삼각형'과 10 ~ 15의 '아래 삼각형')을 호출하고, 위쪽 삼각형에 1을 더하고 아래쪽에 1을 더하여 오프셋을 누적하는 테스트 내부 루프를 갖습니다. 그러나 솔루션 루프의 경우 모든 비용, 특히 불균형 한 출장 횟수 (다시 말하면 , 매우이 GPU에 적합하지 않음)의 루프를 피해야합니다.

so 나는 알고리즘 중 하나 인 대수적 솔루션 대신에을 찾고 있습니다.

조회 테이블을 만들기 :

다시 때문에 GPU, 조회 테이블을 구축 방지하고 (매우 비싼)이 랜덤 액세스를하는 것이 바람직하다. 대수적 인 해결책이 바람직합니다. 행렬의

특성 :

• 행렬의 크기가 알려져있다.
• 지금은 사각형 행렬만을 고려하지만 직사각형 행렬에 대한 해법도 유용 할 것입니다.
• 이 예제에서 함수의 이름과 같이 N 차원 볼륨 (따라서 N-Gonal 평탄화)으로 솔루션을 확장하는 것이 좋습니다.

Answer 1

사실 내 코드의 다른 곳에서 해결할 요소가 있습니다. BLUEPIXY의 솔루션이 암시 하듯이, 이미 레이아웃 변환을 위해 구현 한 분산/수집 작업을 사용하고 있습니다.

이 솔루션은 기본적으로 행렬의 주어진 요소 색인을 다시 작성하고 인덱스 오프셋을 적용하고 결과를 변환 된 레이아웃으로 다시 변환합니다. 이 사각형을 2 개의 삼각형으로 분할하고 속한 삼각형에 따라 계산을 조정합니다.

거의 모든 대수적 변환입니다. 루프가없고 테이블 조회가없고 메모리 사용 공간이 적으며 분기가 거의 없습니다. 코드는 더 이상 최적화 될 수 있습니다. 여기

코드의 초안 :

#include <stdio.h> 
#include <math.h> 

// size of the matrix 
#define SIZE 4 

// triangle number of X 
#define TRIG(X) (((X) * ((X) + 1)) >> 1) 
// triangle root of X 
#define TRIROOT(X) ((int)(sqrt(8*(X)+1)-1)>>1); 

// return the index of a neighbor given an offset 
int getNGonalNeighbor(const size_t index, 
         const int x_offset, 
         const int y_offset){ 
    // compute largest upper triangle index 
    const size_t upper_triangle = TRIG(SIZE); 

    // position of the actual element of index 
    unsigned int x = 0,y = 0; 

    // adjust the index depending of upper/lower triangle. 
    const size_t adjusted_index = index < upper_triangle ? 
       index : 
       SIZE * SIZE - index - 1; 

    // compute triangular root 
    const size_t triroot = TRIROOT(adjusted_index); 
    const size_t trig = TRIG(triroot); 
    const size_t offset = adjusted_index - trig; 

    // upper triangle 
    if(index < upper_triangle){ 
     x = offset; 
     y = triroot-offset; 
    } 
    // lower triangle 
    else { 
     x = SIZE - offset - 1; 
     y = SIZE - (trig + triroot + 1 - adjusted_index); 
    } 

    // adjust the offset 
    x += x_offset; 
    y += y_offset; 

    // manhattan distance 
    const size_t man_dist = x+y; 

    // calculate index using triangular number 
    return TRIG(man_dist) + 
      (man_dist >= SIZE ? x - (man_dist - SIZE + 1) : x) - 
      (man_dist > SIZE ? 2* TRIG(man_dist - SIZE) : 0); 
} 

int main(){ 
    printf("%d\n", getNGonalNeighbor(15,-1,-1)); // should return 11 
    printf("%d\n", getNGonalNeighbor(15, 0,-1)); // should return 14 
    printf("%d\n", getNGonalNeighbor(15,-1, 0)); // should return 13 
    printf("%d\n", getNGonalNeighbor(11,-2,-1)); // should return 1 
} 

그리고 출력은 참으로 :이 솔루션은 복잡하고 비효율적 인 이상 보이는 생각한다면

11 
14 
13 
1 

것은, 내가 당신을 생각 나게하는 여기에 대상 메모리 액세스에 비해 계산 비용이 거의 들지 않는 GPU이며 대규모 인덱스 아키텍처를 사용하여 모든 인덱스 계산이 동시에 계산됩니다.

Answer 2

테이블 조회는

#include <stdio.h> 

#define SIZE 16 
#define SIDE 4 //sqrt(SIZE) 

int table[SIZE]; 
int rtable[100];// {x,y| x<=99, y<=99 } 

void setup(){ 
    int i, x, y, xy, index;//xy = x + y 

    x=y=xy=0; 
    for(i=0;i<SIZE;++i){ 
     table[i]= index= x*10 + y; 
     rtable[x*10+y]=i; 
     x = x + 1; y = y - 1;//right up 
     if(y < 0 || x >= SIDE){ 
      ++xy; 
      x = 0; 
      y = xy;; 
      while(y>=SIDE){ 
       ++x; 
       --y; 
      } 
     } 
    } 
} 
int getNGonalNeighbor(int index, int offsetX, int offsetY){ 
    int x,y; 
    x=table[index]/10 + offsetX; 
    y=table[index] % 10 + offsetY; 
    if(x < 0 || x >= SIDE || y < 0 || y >= SIDE) return -1; //ERROR 
    return rtable[ x*10+y ]; 
} 

int main() { 
    int i; 
    setup(); 
    printf("%d\n", getNGonalNeighbor(15,-1,-1)); 
    printf("%d\n", getNGonalNeighbor(15, 0,-1)); 
    printf("%d\n", getNGonalNeighbor(15,-1, 0)); 
    printf("%d\n", getNGonalNeighbor(11,-2,-1)); 
    printf("%d\n", getNGonalNeighbor(0, -1,-1)); 

    return 0; 
} 

테이블 버전을 사용하지 마십시오.

#include <stdio.h> 

#define SIZE 16 
#define SIDE 4 

void num2xy(int index, int *offsetX, int *offsetY){ 
    int i, x, y, xy;//xy = x + y 

    x=y=xy=0; 
    for(i=0;i<SIZE;++i){ 
     if(i == index){ 
      *offsetX = x; 
      *offsetY = y; 
      return; 
     } 
     x = x + 1; y = y - 1;//right up 
     if(y < 0 || x >= SIDE){ 
      ++xy; 
      x = 0; 
      y = xy;; 
      while(y>=SIDE){ 
       ++x; 
       --y; 
      } 
     } 
    } 
} 
int xy2num(int offsetX, int offsetY){ 
    int i, x, y, xy, index;//xy = x + y 

    x=y=xy=0; 
    for(i=0;i<SIZE;++i){ 
     if(offsetX == x && offsetY == y) return i; 
     x = x + 1; y = y - 1;//right up 
     if(y < 0 || x >= SIDE){ 
      ++xy; 
      x = 0; 
      y = xy;; 
      while(y>=SIDE){ 
       ++x; 
       --y; 
      } 
     } 
    } 
    return -1; 
} 
int getNGonalNeighbor(int index, int offsetX, int offsetY){ 
    int x,y; 

    num2xy(index, &x, &y); 

    return xy2num(x + offsetX, y + offsetY); 
} 

int main() { 
    printf("%d\n", getNGonalNeighbor(15,-1,-1)); 
    printf("%d\n", getNGonalNeighbor(15, 0,-1)); 
    printf("%d\n", getNGonalNeighbor(15,-1, 0)); 
    printf("%d\n", getNGonalNeighbor(11,-2,-1)); 
    printf("%d\n", getNGonalNeighbor(0, -1,-1)); 

    return 0; 
}