분기없이 정수 시퀀스를 생성 할 수 있는지를 결정하는 기술?

Question

브랜칭이 비싼 아키텍처 (PS3의 셀 프로세서)에 최적화되어 있다면 분기를 사용하지 않거나 최소한 분기 수를 줄이지 않고도 주어진 알고리즘을 표현할 수 있는지 여부를 결정하는 것이 중요 할 수 있습니다 . 최적화되지 않은 코드에서 많이 볼 수있는 패턴 중 하나는 인덱스를 일부 배열로 조정하는 데 사용되는 if 묶음입니다 (배열의 크기가 홀수 인 경우 인덱스를 1, 다른 상황에서는 2를 곱하는 등).). 따라서 한 목록을 다른 목록으로 변환하는 분기없는 함수를 작성할 수 있는지 여부를 결정할 수있는 두 가지 숫자 목록이있는 방법이 있다면 좋을 것입니다.

예를 들어, 최근에 나는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9을 0, 2, 4, 6, 8, 9, 7, 5, 3, 1 (오름차순으로 오름차순으로 오름차순)으로 변환하는 분기없는 함수를 작성할 수 있는지 알고 싶었습니다. 기술적으로, 나는 큰 switch/case 함수를 작성할 수는 있지만, 분명히 나는 ​​임의의 크기에 대한 패턴을 따르는 함수에 관심이있다. 이 변환을 수행하는 함수를 작성하는 것은 분기를 사용하면 간단하지만, 그렇게하는 것이 비대칭 인 방법이라면 즉시 명백하지 않습니다.

이런 종류의 문제 또는 빠른 리트머스 테스트에 대한 일반적인 접근법이 있습니까? 아니면 사례별로 증거를 제시해야합니까? 이런 종류의 문제에 더 열심히 일할 수는 있지만 말 그대로 불가능하다면 그것은 무의미합니다. 어떤 시점에서 분기를 사용하지 않고 산술만을 사용하는 함수에 공식적인 수학적 단어가 있다는 것을 기억하지만, 기억하지 못합니다.

Answer 1

속도가 실제로 핵심이라면 목록에 대한 지침을 특정 길이까지 작성할 수 있습니까? (물론이 코드를 미리 생성 할 수 있습니다.)

너무 :

void algorithm1_Length6(int *srcList, int *destList) 
{ 
     *destList++ = *srcList; 
     *destList++ = srcList[2]; 
     *destList++ = srcList[4]; 
     *destList++ = srcList[5]; 
     *destList++ = srcList[3]; 
     *destList++ = srcList[1]; 
} 

및 특정 길이 개까지 다른 모든 변화. 이 같은 방법을 사용할 수 있습니다 주어진 배열에 대한

Answer 2

:

void tranform(int[] src, int[] dest) { 
     //0, 2, 4, 6, 8, 9, 7, 5, 3, 1 
     dest[0] = src[0]; 
     dest[1] = src[2]; 
     dest[2] = src[4]; 
     dest[3] = src[6]; 
     dest[4] = src[8]; 
     dest[5] = src[9]; 
     dest[6] = src[7]; 
     dest[7] = src[5]; 
     dest[8] = src[3]; 
     dest[9] = src[1]; 
    } 

그러나 큰 배열 일반적으로 당신이 다음과 같이 생성 방법을 쓰는 경우 따라서는 도움이 될 것입니다, 이러한 방법을 쓰기 어렵다 :

를

static void createFunction(int[] src, int[] dest) { 
     System.out.println("void tranform(int[] src, int[] dest) {"); 
     for (int i = 0; i < dest.length; i++) { 
      for (int j = 0; j < src.length; j++) { 
       if (dest[i] == src[j]) { 
        System.out.println("dest[" + i + "]=src[" + j + "];"); 
        break; 
       } 
      } 
     } 
     System.out.println("}"); 
    } 

하면 배열을 호출 :이 방법의 createFunction(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, new int[]{0, 2, 4, 6, 8, 9, 7, 5, 3, 1});

및 붙여 넣기 출력을 프로그램에.

Answer 3

는 특히 PS3 최적화하는 경우는 Power PC Compiler Writers Guide 절 3.1.5에 branchfree 코드에 기술을 가지고 있으며 Superoptimizer 시퀀스 Mike Acton's Cell Performance에서

당신은 할 수 있습니다 관심 부록 D.에서 branchfree 코드를 GNU있다 블로그뿐.

Answer 4

입력 색인에 대해 원하는 색인을 플롯하면 삼각형 모양의 기능을 갖게됩니다.그것은 당신의 n = 10 경우에, 그것은 일반적으로 n를 들어, 따라서

9.5 - abs(2 (x - 4.75)) 

이라고 밝혀, 그것은이

n-0.5 - abs(2*(x - n/2-0.25)) 

또는 정수 형태로

,

(2*n-1 - abs(4*x - 2*n + 1))/2 

입니다 것 당신의 출력 인덱스가 단일 mathematecal 함수로 생성된다는 점에서 완전히 branchless입니다. 일반적인 접근 방식은 원하는 인덱스를 플롯하고 패턴을 찾고 수학 함수로 표현하는 방법이라고 생각합니다.

원하는 최종 인덱스가 직선을 형성하는 경우 분명히 변환이 간단합니다. 매핑에 꼬임이있는 경우 절대 값 기능을 사용하여 굴곡을 도입하려는 경우 배율을 조정하여 굴곡 각도를 변경할 수 있습니다. 바이어스로 꼬임을 기울일 수 있습니다 (예 : abs(x)+x/2). 최종 인덱스 함수에서 점프 불연속 점이 필요한 경우 sign 함수를 사용하십시오. (잘하면 builtin 또는 abs (x)/x를 사용하십시오). 여기에 일반적인 기능의 그래프를 사용하는 방법에 창의적이어야합니다. 당신의 인덱싱 기능이 구분 적 선형 인 경우

---

부록

은 간단한 알고리즘이 있습니다. 원하는 인덱스 함수는 모든 K 모든 K 및 sxK> SX (K-1)에 대한 exK> sxK가 (좌에서 우로 넣어) 세그먼트

{(sx1,sy1)-(ex1,ey1), (sx2,sy2)-(ex2,ey2), ... , (sxN,syN)-(exN,eyN)} 
segment 1   segment 2     segment N 

들의리스트로 표현된다고 가정.

k = 1 
f(x) = Make affine model of segment k 
g(x) = f(x) 
Do: 
    k = k + 1 
    h(x) = Makeaffine model of segment k 
    If g(x) and h(x) intersect between ex(k-1) and ex(k) 
     f(x) = f(x) + [slope difference of g(x) and h(x)] * ramp(x) 
    Else 
     f(x) = f(x) + (h(ex(k-1)) - f(ex(k-1))) * step(x) 
     f(x) = f(x) + [slope difference of g(x) and h(x)] * ramp(x) 

곳 ramp(x) = (abs(x)+x)/2 및 step(x) = (sign(x)+1)/2. f (x)는 원하는 함수를 나타 내기위한 것이고, g(x)은 마지막 세그먼트의 아핀 모델이고, h(x)은 현재 세그먼트의 아핀 모델입니다. 아핀 모델은 경사 옵셋 형태의 선인 a*x+b이고 기울기 차이는 기울기의 차이입니다. 이 알고리즘은 단순히 왼쪽에서 오른쪽으로 진행하여 적절한 기능을 추가합니다. 추가 기능은 x <= 0에 대해 항상 0이므로 지금까지 작성된 f(x)에 영향을 미치지 않습니다.

물론 위의 버그/오타가있을 수 있습니다. 나는 정말로 회의에 가야한다. 그래서 나는 더 이상 쓸 수 없다.

Answer 5

변환 : 0, 1, 2, 3, 4, 5, 6, 7, 8,9 : 0, 2, 4, 6, 8, 9, 7, 5 홀수에서 내림차순으로).

단순 : 0부터 N-1까지의 N의 N 값의 시퀀스가 ​​주어지면 시퀀스의 전반부가 2X임을 알 수 있습니다. 시퀀스의 두 번째 절반은 (2N-1) -2X입니다. 시퀀스는 X = (N + 1)/2에서 "정수"수학으로 나뉩니다. 으로 파워가 ANDC 있기 때문에 여기에서 사용되는 마스크 패턴 빠르다고

int Transform(int x) 
{ 
    const int seq1=x+x; 
    const int mask=(x-((N+1)>>1))>>31; 
    const int seq2=(N+N-1)-seq1; 
    return (mask&seq1)|((~mask)&seq2); 
} 

주 (하고 : 상기 예, N의 == 10

너무 산술 오른쪽 시프트 32 비트 부호의 int 가정 보완)을 사용하면 (~mask)이 무료로 작동합니다.

Answer 6

예를 들어 라그랑주 보간법을 사용하여 항상 다항식을 쓸 수 있습니다. 예쁘지는 않지만 (또는 특히 빠르지 만) 가지가 없을 것입니다.

Answer 7

기술적으로 모든 일련의 연산은 부울 연산을 사용하는 상태 시스템을 사용하여 "분기"하지 않고 실행할 수 있습니다. 분기의 개념은 대부분의 프로그램이 한 방향으로 또는 다른 방향으로 갈 수있는 프로그램 카운터에 의해 실행되는 일련의 명령이기 때문입니다.

상태가없는 순수한 기능적 접근 방식에 대해 이야기하고 있더라도 유한 값의 이산 값에 대해서는 룩업 테이블을 항상 사용할 수 있습니다.