짧은 길이 순환 회선의 최적화

Question

나는 8 개의 부호없는 바이트 두 시퀀스를 가지고 있으며, 8 개의 부호없는 19 비트 정수를 산출하는 순환 회선을 계산해야합니다. 이 백만 번을 반복하면서 최적화하고 싶습니다.

직접적인 방법은 64 개의 MAC 연산을 필요로합니다. SSE/AVX 지침을 통해이 작업을 가속화하는 방법을 이미 알고 있으며 이는 내가 수행 한 작업이 아닙니다.

FFT 또는 수 이론 변환을 기반으로하는 다른 방법이있어 작동 횟수를 줄이거 나 다른 기법을 사용하여 속도를 향상시킬 수 있습니까?

사실 저는 8 가지 값이 필요하지 않습니다. 가장 큰 값과 해당하는 시프트로 충분합니다.

Answer 1

cyclic convolution은 각 입력의 Discrete Fourier Transform (DFT)을 취하여 변환을 곱하고 역 DFT를 취함으로써 계산할 수 있습니다. 고속 퓨리에 변환 알고리즘을 사용하면 DFT와 그 역함수는 N*log(N) 연산에서 계산할 수 있으며, 다음으로 변환을 곱하는 또 다른 연산이 가능합니다. 따라서 대충 말해서 3N*log(N)+N 작업이 필요합니다. 입력 크기가 8 인 경우 80으로 작동합니다. FFT 메서드의 연산은 MAC뿐 아니라 복소수 연산입니다.

그러나 하나의 최적화가 있습니다. 입력 데이터가 실제이기 때문에 정보를 손실하지 않고 N/2 + 1 복소수 포인트로 변환을 나타낼 수 있습니다. 이 속성을 활용하는 실수 변환 (및 역 변환)이 있습니다. 일반적으로 절반의 변환을 수행하는 것과 같습니다. 그러므로 우리가 3N*log(N)+N에 4를 연결하면 28이됩니다. 이제는 복소수 문제를 고려해야합니다. 복잡한 곱셈은 실수와 허수 성분 각각에 대해 두 곱셈과 덧셈입니다. 그래서 각각의 복합 연산은 대략 3 개의 MAC과 동등하며, 이것은 여전히 ​​직접 컨볼 루션보다 느리다는 것을 알 수 있습니다.

FFT 방식은 데이터 크기가 커지면서 성과가 나타납니다. 2048 길이의 입력으로 작업하는 경우 조작 수는 3 * 10240 + 1024 = 34k 조작이됩니다. 복소수 오버 헤드에 3을 곱한 경우에도 직접 구현의 ~ 4M 연산과 매우 유사합니다.

FFT 접근법을 고려해야 할 또 다른 경우는 하나의 배열을 다른 배열과 비교하거나 다른 배열을 모두에 대해 컨버팅해야하는 경우입니다. 이 경우 입력 변환을 한 번 계산하여 다시 사용할 수 있습니다. K 시퀀스의 경우 모든 K^2 교차 컨볼 루션을 수행해야하는 경우 K 변환, K^2 복소수 배열 곱하기 및 K^2 역변환을 수행 할 수 있습니다. 입력 크기가 8 인 10 개의 배열의 경우 복소수 연산이 1500 개 미만입니다 (입력, 변환 곱하기 및 출력의 경우 10*4*log(4) + 500 + 100*4*log(4)). 직접 접근 방식을 사용하려면 100*64 MAC이 필요하므로 FFT 방식이 유리합니다.

쌍의 경우에 대해 좋은 직접 구현은 손을 아래로 승자가 될 것 같습니다.

Answer 2

"Fast Fourier Transform and Convolution Algorithms"에서 Nussbaumer는 14 개의 곱셈과 46 개의 덧셈을 사용하여 8 개의 곱셈의 컨볼 루션을 계산하는 최적화 된 방법을보고합니다. 나는 더 나은 표준 산술을 사용하여 수행 할 수 있는지 의심.

나는 Fermat/Euler-number 변환이 적절하다는 느낌을 가지고 있지만 세부 사항을 채울 수는 없습니다.