파이썬 numpy.fft가 strides를 바꾼다

Question

친애하는 stackoverflow 커뮤니티!

오늘 저는 하이 엔드 클러스터 아키텍처에서 1921 x 512 x 512 크기의 2 개 큐브의 요소 단위 승수가 ~ 27 초를 차지한다는 것을 알았습니다. 이것은 현재 구현에서 파워 스펙트럼의 방위각 평균에 대해 적어도 256 번 같은 계산을 수행해야하므로 너무 길다. 느린 성능은 주로 다른 스트라이드 구조 (한 사례에서는 C, 다른 시나리오에서는 FORTRAN) 때문인 것으로 나타났습니다. 두 배열 중 하나는 새로 생성 된 부울 그리드 (C 순서)이고 다른 하나 (FORTRAN 순서)는 3D numpy.fft.fftn() 입력 격자의 푸리에 변환 (C 순서)에서 왔습니다. numpy.fft.fftn()이 축을 뒤집는 것을 제외하고는이를 방지하는 방법에 대한 보행과 아이디어를 변경하는 이유는 무엇입니까? (이는 단지 일시적인 해결책 일까?) 비슷한 보폭 (FT 그리드의 ndarray.copy())으로 ~ 4s를 달성 할 수 있습니다. 엄청난 개선입니다.

문제는 다음과 같은 그러므로 :

배열을 고려

ran = np.random.rand(1921, 512, 512) 
ran.strides 
(2097152, 4096, 8) 

a = np.fft.fftn(ran) 
a.strides 
(16, 30736, 15736832) 

우리는 보폭 구조가 다르다 볼 수 있듯이. 어떻게 이것을 막을 수 있습니까? (= ran, axes = (1,0)) = np.fft.fftn을 사용하지 않고? 스트라이드 구조에 영향을 줄 수있는 다른 numpy 배열 루틴이 있습니까? 이 경우 어떻게 할 수 있습니까?

유용한 조언은 평소와 같이 많이 감사합니다!

Answer 1

numpy.fft.fftn()가 축을 반전을 제외하고 (단지 해결 방법이 될 것이다) 것을 방지하는 방법에 대한 발전과 아이디어를 변경하는 이유 모든 이유는?

어레이의 다차원 DFT를 계산하는 것은 각 차원에서 1D DTF를 연속적으로 계산하는 것으로 구성됩니다. 두 가지 전략이 있습니다.

1. 1D DTF 계산을 인접한 1D 배열로 제한하십시오. 배열이 인접 해 있으므로 대기 시간/캐시 누락과 관련된 문제가 줄어 듭니다. 이 전략에는 주요 단점이 있습니다. 즉, 배열을 각 차원간에 옮겨야합니다. numpy.fft에서 채택한 전략입니다. 계산이 끝나면 배열이 전치되었습니다. 불필요한 계산을 피하기 위해 전치 배열이 반환되고 보폭이 수정됩니다.
2. 스트라이드 된 배열에 대해 1D DDFT 계산을 사용합니다. 이로 인해 대기 시간과 관련된 문제가 발생할 수 있습니다. fftw의 전략이며, 인터페이스 pyfftw을 통해 사용할 수 있습니다. 결과적으로 출력 배열은 입력 배열과 동일한 진보를 특징으로합니다.

타이밍 numpy.fftn하고 pyfftw.numpy.fftnhere 수행 there 또는 there이 FFTW 서쪽에 변환 여부를 정말 빠른 푸리에입니다 여부를 알려줍니다 ...

• 그 NumPy와를 확인하려면 첫 번째 사용 전략, numpy/fft/fftpack.py을보십시오. 81-85 행에서 work_function(a, wsave) (즉,fftpack.cfftf, FFTPACK, 인수는 there으로 문서화되어 있습니다)은 교환을 수행하는 numpy.swapaxes()에 대한 호출 사이에 포함됩니다.

• scipy.fftpack.fftn 진보가 바뀌지 않는 것 같습니다. 그럼에도 불구하고, 첫 번째 전략을 사용하는 것으로 보입니다. scipy.fftpack.fftn()은 zfftf1에 기반하여을 호출하는 scipy.fftpack.zfftnd()을 호출하며 스트라이드 된 DFT를 처리하지 않는 것으로 보입니다. 또한, zfftnd()은 중첩을 수행하는 함수 flatten()을 여러 번 호출합니다.

• 또 다른 예 : 병렬 분산 메모리 다차원 DFT의 경우 1D DTF 동안 프로세스 간의 MPI 통신을 피하기 위해 FFTW-MPI uses the first strategy. 물론 functions to transpose the array은 그리 멀지 않았으며 MPI 통신이이 프로세스에 관련되어 있습니다. 보폭 구조에 영향을 미칠 수있는 다른 NumPy와 배열 루틴은

이 있습니까? 이 경우 어떻게 할 수 있습니까?

search the github repository of numpy for swapaxes 수 있습니다.이 기능은 몇 번만 사용됩니다. 따라서, 내 마음에,이 "strides의 변경"은 fft.fftn()이며, 대부분의 numpy 함수는 스트라이드를 변경하지 않고 유지합니다.

마지막으로 "strides 변경"은 첫 번째 전략의 특징이며이를 방지 할 방법이 없습니다. 유일한 해결 방법은 계산 끝에서 축을 교환하는 것인데, 이는 값이 비쌉니다. fftw이 매우 효율적인 방법으로 두 번째 전략을 구현하기 때문에 pyfftw에 의존 할 수 있습니다. DFT 계산은 더 빨라질 것이고, 다른 어레이의 스트라이드가 일관성있게되면 후속 계산이 더 빨라질 것입니다.

Answer 2

numpy.fft.fftn 대신 scipy.fftpack.fftn (hpaulj에서 제안한대로)을 사용하여 원하는대로 작업 할 수 있습니다. 그것은 약간 덜 성능 그러나입니다 :

import numpy as np 
import scipy.fftpack 

ran = np.random.rand(192, 51, 51) # not much memory on my laptop 
a = np.fft.fftn(ran) 
b = scipy.fftpack.fftn(ran) 

ran.strides 
(20808, 408, 8) 
a.strides 
(16, 3072, 156672) 
b.strides 
(41616, 816, 16) 

timeit -n 100 np.fft.fftn(ran) 
100 loops, best of 3: 37.3 ms per loop 
timeit -n 100 scipy.fftpack.fftn(ran) 
100 loops, best of 3: 41.3 ms per loop