ARM 네온 : 8 바이트 벡터 레인에서 0이 아닌 바이트의 n 번째 위치 저장

Question

네온 64 비트 벡터 레인을 n 번째 위치로 변환하려고합니다. 0이 아닌 (일명 0xFF) 8 비트 값을 가져온 다음 나머지 벡터에 0을 채 웁니다. 다음은 몇 가지 예입니다.

0 1 2 3 4 5 6 7 

d0: 00 FF 00 FF 00 00 00 FF 
d1: 1 3 7 0 0 0 0 0 

d0: 00 FF FF FF 00 00 FF 00 
d1: 1 2 3 6 0 0 0 0 

d0: FF FF FF FF FF FF FF FF 
d1: 0 1 2 3 4 5 6 7 

d0: FF 00 00 00 00 00 00 00 
d1: 0 0 0 0 0 0 0 0 

d0: 00 00 00 00 00 00 00 00 
d1: 0 0 0 0 0 0 0 0 

다른 "좋은"벡터가있는 1 ~ 2 비트 시프트 네온 지침입니다. 어떻게해야합니까?

Answer 1

이 모든 것이 간단하지는 않습니다.

순진한 접근 방식은 간단히 인덱스를 얻는 것으로 시작됩니다 (비트 마스크로 0 1 2 3 4 5 6 7 및 vand의 정적 벡터로드). 그러나, 출력 벡터의 한쪽 끝에서 - 그것들이 나타내는 입력 레인과는 다른 차선에서 그것들을 모으기 위해서 - 당신은 임의의 순열 연산을 필요로합니다. 벡터를 임의로 치환 할 수있는 명령은 하나 뿐이며 vtbl (또는 vtbx, 본질적으로 같은 것)입니다. 그러나 vtbl은 대상 순서의 소스 인덱스 벡터를 사용하며 이는 생성하려고하는 것과 정확히 동일합니다. 따라서 최종 결과를 산출하기 위해서는 최종 결과를 사용해야하므로 비효율적 인 효율적인 솔루션은 불가능합니다. QED.

기본적으로 문제는 벡터를 정렬하는 것인데, 본질적으로 병렬 SIMD 작업이 아닙니다. NEON은 미디어 처리를 위해 설계된 병렬 SIMD 명령어 세트이며보다 일반적인 벡터 처리의 데이터 종속/수평/분산 수집 작업에 대해서는 실제로 제외되지 않습니다.

포인트를 증명하기 위해 순수한 NEON에서 스칼라 코드를 전혀 사용하지 않고 관리했습니다. 끔찍한입니다. 가장 좋은 "하나 또는 두 개의 비트 시프트 NEON 명령어"는 몇 가지 조건부 선택 기반 회전 비트 마스크 누적 트릭킹입니다. 이 명확하지 않으면, 나는 그것이 무엇을 (example)를 따라 디버거 또는 시뮬레이터를 통해 스테핑 좋을 것 :

// d0 contains input vector 
vmov.u8 d1, #0 
vmov.u8 d2, #0 
vmvn.u8 d3, #0 
vdup.u8 d4, d0[0] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[1] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[2] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[3] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[4] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[5] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[6] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[7] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vbic.u8 d1, d1, d3 
// d1 contains output vector 

부정 행위와 반대 방향으로 d0 회전 필요로 루프를 (사용하여 우리가 할 수있는 그러한 이 작은 수) d0[0]을 통해 각 원래 차선에 접근하지만, 정말 덜 끔찍하지 :

vmov.u8 d1, #0 
vmov.u8 d2, #0 
vmvn.u8 d3, #0 
mov r0, #8 
1: 
vdup.u8 d4, d0[0] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
subs r0, r0, #1 
vext.u8 d0, d0, d0, #1 
vsub.u8 d1, d1, d3 
bne 1b 
vbic.u8 d1, d1, d3 

를 이상적으로,이 벡터의 상수가 아닌 순열을 필요 피하기 위해 알고리즘의 다른 부분을 재 작업 모두 가능하다면, 어떻게 그 대신에.

Answer 2

벡터를 정렬하여이 작업을 수행 할 수 있습니다. 이런 작업에 기대되는 것보다 훨씬 복잡한 작업이지만, 더 좋은 점을 찾지 못했습니다.

는 d0에 00/ ff 바이트의 목록을 감안할 때, 그리고 d1의 상수 0, 1, 2, ..., 7, 당신은 vorn를 사용하여 활성 컬럼의 정렬 목록을 만들 수 있습니다. 이제 d0의 모든 원치 않는 차선 0xff과 나머지로 대체되었습니다

vorn.u8 d0, d1, d0 

는 자신의 차선 인덱스로 대체되었습니다. 거기에서 그 목록을 정렬하여 끝에있는 원치 않는 모든 차선을 클러스터링 할 수 있습니다.다음

vmov.u8 d1, #255 

그리고 홀수/짝수 벡터로 분할 :

는 16 바이트로 목록을 확장 할 수 있고, 그렇게하려면

vuzp.u8 d0, d1 

정렬 작업이 구성 vmin/vmax 벡터 사이에 비틀 거리기 연산을 수행 한 다음 vmin/vmax 쌍을 사용하여 개의 값을 쌍으로 정렬하여 값이 ir 적당한 장소. 그래서 같이 :

이

vmin.u8 d2, d0, d1 
vmax.u8 d3, d0, d1 
vsri.u64 d2, d2, #8 ; stagger the even lanes (discards d0[0]) 
vmax.u8 d4, d2, d3 ; dst reg would be d0, but we want d0[0] back... 
vmin.u8 d1, d2, d3 
vsli.u64 d0, d4, #8 ; revert the stagger, and restore d0[0] 

이 전체 네트워크의 두 단계를 구현하고, 전체 블록 4 번 (여덟 단계)를 반복하는 d0[0]에 끝까지 거품에 d0[7]에서 뭔가 것이 가능하게합니다 마지막 바이트의 극단적 인 경우가 유일한 0이 아닌 입력이되거나 d0[0]의 경우 첫 번째 바이트가 유일한 0 입력이면 d0[7]이됩니다.

vzip.u8 d0, d1 

을 그리고 당신은 남은 차선에서 제로 싶어서 :

당신이 그들을 정렬을 완료하면, 다시 함께 결과를 스티치

vmov.u8 d1, #0 
vmax.s8 d0, d1 

을 그리고 지금 d0는 결과를 포함해야합니다.

는 위키 백과의 sorting network 페이지를 선택하면 교체 (8 개 개의 차선에 대한 이론적 최소 깊이는 6 단계 (vmin/vmax의 육쌍) 인 것을 볼 수 있습니다, 그래서 순열의 집합을 찾을 수있을 수 있습니다 내 vsli 및 vsri 작업) 구현 한 8 단계 삽입/선택/vbubble 정렬 대신 6 단계 정렬 네트워크를 구현합니다. 그러한 것이 존재하고 NEON의 순열 연산과 호환되면 확실하게 찾을 가치가 있지만 볼 시간이 없습니다.

또한 정렬은 필요한 것보다 많은 총 16 바이트에서 작동하며 q 레지스터를 사용하면 32 바이트에서 작동 할 수 있습니다 ... 따라서 최대 길이 처리량.

아, 그리고 심지어이 구성에서 나는 당신이 정렬의 마지막 단계를 필요로하지 않는다고 생각합니다. 독자에게 남겨진 운동.