float 배열의 빠름 abs-max

Question

오디오의 피크 미터를 실시간으로 그릴 필요가 있습니다. 초당 최소 44100 샘플, 최소 40 스트림. 각 버퍼는 64 샘플과 1024 샘플 사이에 있습니다. 각 버퍼에서 abs max를 가져와야합니다. (그런 다음 이들은 일종의 저역 통과 필터를 통해 공급되고 약 20ms 간격으로 그려집니다.)

for(int i = 0; i < numSamples; i++) 
{ 
     absMaxOfBuffer = MAX(fabs(buffer[i]), absMaxOfBuffer); 
} 

그게 지금하는 방법입니다. 훨씬 더 빨리하고 싶습니다. 버퍼에는 -1에서 1 범위의 부동 소수점이 있으므로 팹을 사용합니다.

질문 :이 작업을보다 빠르게 수행 할 수있는 까다로운 방법이 있습니까?

브랜치가없는 ABS와 MAX가 수레에 대해 기능하지 않는다면, 그것들이 존재합니까?

편집 : 기본 플랫폼은 Linux/gcc이지만 Windows 포트가 계획되어 있습니다 (아마도 mingw와 함께).

두 번째 편집 : 두 번째 :
나는 질문의 중심이었던 실제적인 알 고 구조에 관한 약간의 이유 때문에 하나의 동의를 받았다.
나는 루프를 4 개로 풀어서 시그니처를 제로로 만든 다음 SSE (maxps 명령)로 최대 값을 얻고 바나나를 떼어 내지 않는지 확인합니다. 제안 주셔서 감사 드리며, 나는 주자들과 같이 여러분 중 몇 명을 선정했습니다. :)

Answer 1

팹과 비교는 모두 IEEE 부동 소수점에 대해 매우 빠릅니다 (원칙적으로 단일 정수 연산과 같이 빠름).

컴파일러가 두 작업을 모두 인라인하지 않으면 컴파일 할 때까지 찌르거나 아키텍처 구현을 찾아서 직접 인라인하십시오.

(긍정) IEEE 부동 소수점은 같은 비트 패턴을 가진 정수와 같은 순서로 나타납니다. 그것은 당신이 fabs'ed 일단

f > g iff *(int*)&f > *(int*)&g 

그래서, 나는 (그들은 물론 같은 크기있어 가정) 인터넷 용 지점이없는 최대가 떠을 위해 일 것이라고 생각한다. 왜 여기에서 작동하는지에 대한 설명이 있습니다 : http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm. 하지만 컴파일러는 CPU를 사용하는 것처럼이 모든 것을 이미 알고 있으므로 아무런 차이가 없습니다.

더 빠르고 복잡한 방법은 없습니다. 귀하의 알고리즘은 이미 O (n)이며, 당신은 그것을 이길 수없고 여전히 모든 샘플을보아야합니다.

아마도 여러분의 코드보다 클럭 사이클 당 더 많은 데이터를 처리함으로써 프로세서의 SIMD (즉, Intel의 SSE2)에 도움이 될만한 것이있을 것입니다. 그러나 나는 무엇을 모른다. 있다면, 아마도 몇 배나 더 빠를 것입니다.

아마도 멀티 코어 CPU에서 병렬화 할 수 있습니다. 특히 40 개의 독립적 인 스트림을 처리하고 있기 때문입니다. 그것은 기껏해야 몇 가지 요소가 더 빠를 것입니다. "그냥"적절한 수의 추가 스레드를 실행하고 스레드 간 작업을 분할하고 가장 가벼운 프리미티브를 사용하여 스레드가 모두 완료되면 나타낼 수 있습니다 (아마도 스레드 장벽). 모든 40 개 스트림의 최대 값 또는 개별적으로 최대 값을 플로팅할지 여부는 명확하지 않으므로 결과가 다음 단계로 전달되는지 확인하는 것 이외에 실제로는 작업자 스레드를 동기화 할 필요가 없을 수도 있습니다. 데이터 손상없이

아마도 컴파일러가 루프를 풀어 놓은 지 확인하기 위해 디스 어셈블리를 살펴 보는 것이 좋습니다. 조금 더 풀어보고, 차이가 있는지 확인하십시오.

또 다른 고려해야 할 점은 얼마나 많은 캐시 누락인지, 그리고 캐시에 몇 가지 단서를 제공하여 올바른 페이지를 미리로드 할 수 있는지 여부입니다. 그러나 나는 이것에 대한 경험이 없으며 많은 희망을 품지 않을 것이다. __builtin_prefetch는 gcc에 대한 마법의 주문이며 첫 번째 실험은 "이 블록의 루프를 시작하기 전에 다음 블록의 시작을 미리 프리 페치"하는 것과 같을 것입니다.

현재 필요한 속도의 몇 퍼센트입니까? 또는 "가능한 한 빨리"의 경우입니까?

Answer 2

다른 질문과 함께 대답하는 것은 정확하게 대답하지 않지만, 어이 ... 나는 C++ 개발자도 아니다.

당신은 C + +에서 이것을 개발하고 있고 dsp를하고 있기 때문에 matlab에 연결할 수 없으며 옥스포드 (opensource)를 수학에 연결할 수 없으며 결과를 얻지 못합니까?

frevz, stem, graph, plot, mesh 등의 기능을 이미 conv, fft, ifft, fir 및 plotting과 같은 기능이 있습니다. Photoshop에서 한 번 보았고 큰 폴더 인 MATLAB이 있습니다 ... .m 파일과 함께 응용 프로그램에서 호출을 받고 동적 matlab에 보내어 결과를 응용 프로그램에 반환합니다.

희망이 있습니다.

Answer 3

상황이 시도 :

• 팹()를 인라인 함수하지 않을 수 있습니다.
• 특별 조립 지침이 도움이 될 수 있습니다. Intel에서 SSE는 최대 4 개의 부동 소수점을 한 번에 계산하도록 지시합니다. 는 IEEE 754 규격은 A와 B음수 수레 경우 다음 < B는 * (INT *) & < * (INT의 *) & B에 해당되도록하고, 불합격
• . 또한, 어떤 a에 대해서도, MSB를 뒤집어서 -a를 계산할 수 있습니다. 함께, 이러한 속성은 약간의 twiddling 해킹을 가능하게합니다.
• 실제로 모든 샘플을 최대로 필요로합니까? 아마도 최대 값은 여러 번 발생할 수 있으므로 모든 입력을 검사하지 않을 가능성이 있습니다.
• 스트리밍 방식으로 최대 값을 계산할 수 있습니까?

Answer 4

MMX 명령어를 사용하여

또한 GCC의 최신 버전은 당신을 위해 무점포 fabs 인라인 점에 유의하시기 바랍니다 http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms에 문서화 무점포 팹,있다. fmin과 fmax도 있지만 GCC는이를 인라인하지 않습니다 (call fmin이 표시됨).

Answer 5

쉬운 최적화 나는 참조 :

• 는
• 는 IEEE 754 표준은 로그인 크기로 그 표현을 정의 (컴파일러이 표시되지 않는 것으로 가정) 포인터 산술 버전으로 루프를 번역합니다. 따라서 최상위 비트를 0으로 설정하면 fabs()를 호출하는 것과 동일합니다.어쩌면이 기능은 이미이 트릭을 사용합니다.

Answer 6

당신은 Eigen보고 할 수 있습니다.

SSE (2 이상) 및 비 벡터화 코드에 우아한 폴백을 갖는 AltiVec 명령어 세트를 사용하는 C++ 템플릿 라이브러리입니다.

패스트. (벤치 마크 참조).
Expression 템플릿을 사용하면 임시 파일을 지능적으로 제거하고 지연 평가 기능을 사용할 수 있습니다. Eigen은 자동으로이를 처리하고 대부분의 경우 별칭을 처리합니다.
SSE (2 이상) 및 AltiVec 명령어 세트에 대해 명시 적 벡터화가 수행되며 벡터화되지 않은 코드로 우아하게 대체됩니다. 식 템플릿을 사용하면 전체 식에 대해 이러한 최적화를 전역 적으로 수행 할 수 있습니다.
고정 크기 개체를 사용하면 동적 메모리 할당이 방지되고 루프가 의미가있을 때 풀립니다.
큰 행렬의 경우 캐시 친숙성에 특히주의해야합니다.

Answer 7

절대 값을 지정하지 않고 사각형을 지정할 수 있습니다. 수학적으로 | a | < | b | 만약^2 < b^2이고 그 반대도 마찬가지입니다. 곱셈은 ​​일부 컴퓨터 (?)에서 fabs()보다 빠를 수도 있습니다.