스트리밍을 위한 효율적인 메모리 대역폭 사용

https://stackoverflow.com/questions/709308

22-08-2019
|

문제

저는 250MB의 데이터를 스트리밍하고 데이터 청크(각각 2개의 32비트 단어)에 간단하고 빠른 신경망 임계값 함수를 적용하는 애플리케이션을 가지고 있습니다.(매우 간단한) 계산의 결과에 따라 청크는 예측할 수 없게 64개의 저장소 중 하나로 푸시됩니다.따라서 하나의 큰 스트림이 입력되고 64개의 더 짧은(가변 길이) 스트림이 출력됩니다.

이는 다양한 감지 기능을 사용하여 여러 번 반복됩니다.

컴퓨팅에는 메모리 대역폭이 제한되어 있습니다.훨씬 더 계산 집약적인 판별 함수를 사용해도 속도 변화가 없기 때문에 이를 알 수 있습니다.

메모리 대역폭을 최적화하기 위해 새 스트림의 쓰기를 구성하는 가장 좋은 방법은 무엇입니까? 특히 캐시 사용량과 캐시 라인 크기를 이해하는 것이 여기에 큰 역할을 할 수 있다고 생각합니다.64개의 출력 스트림이 있고 불행하게도 많은 스트림이 동일한 캐시 라인에 매핑되는 최악의 경우를 상상해 보십시오.그런 다음 다음 64비트 데이터를 스트림에 쓸 때 CPU는 오래된 캐시 라인을 주 메모리로 플러시하고 적절한 캐시 라인에 로드해야 합니다.각각은 64바이트의 대역폭을 사용합니다.따라서 내 대역폭이 제한된 응용 프로그램은 메모리 대역폭의 95%를 낭비할 수 있습니다(그러나 이 가상의 최악의 경우에서는).

효과를 측정하는 것조차 어렵기 때문에 이를 둘러싼 방법을 설계하는 것은 더욱 모호합니다.아니면 하드웨어가 내가 할 수 있는 것보다 더 잘 최적화되는 유령 병목 현상을 쫓고 있는 걸까요?

차이점이 있다면 Core II x86 프로세서를 사용하고 있습니다.

편집하다:다음은 몇 가지 예제 코드입니다.배열을 통해 스트리밍하고 해당 요소를 의사 무작위로 선택된 다양한 출력 배열에 복사합니다.동일한 양의 계산 및 메모리 읽기 및 쓰기가 수행되었더라도 서로 다른 수의 대상 저장소로 동일한 프로그램을 실행하면 런타임이 달라집니다.

2개의 출력 스트림:13초
8개의 출력 스트림:13초
32개의 출력 스트림:19초
128개 출력 스트림:29초
512 출력 스트림:47초

512와 2개의 출력 스트림을 사용하는 것의 차이는 4X입니다. 이는 캐시 라인 제거 오버헤드로 인해 발생합니다.

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}

해결책

64 개의 출력 쓰레기통에 글을 쓰면 여러 가지 메모리 위치를 사용할 것입니다. 빈이 본질적으로 무작위로 채워지면 때때로 Couls가 동일한 캐시 라인을 공유하는 두 개의 쓰레기통이 있음을 의미합니다. 큰 문제가 아닙니다. Core 2 L1 캐시는 8 방향 연관성입니다. 즉, 9 번째 캐시 라인에만 문제가 발생합니다. 언제든지 65 개의 라이브 메모리 참조 (1 읽기/64 쓰기)를 사용하면 8-way 연관성이 괜찮습니다.

L2 캐시는 분명히 12 방향 연관성입니다 (총 3/6MB, 12는 이상한 숫자가 아닙니다). 따라서 L1에서 충돌을 일으키더라도 여전히 메인 메모리를 치지 않는 기회가 꽤 좋을 것입니다.

그러나 마음에 들지 않으면 메모리에서 쓰레기통을 다시 정리하십시오. 각각의 빈을 순차적으로 스트로하는 대신에 인터 리브하십시오. 빈 0의 경우 오프셋 0-63에 덩어리 0-15를 저장하지만 오프셋 8192-8255에 덩어리 16-31을 저장하십시오. BIN 1의 경우 오프셋 64-127 등에 덩어리를 0-15로 저장하십시오. 이것은 약간의 교대와 마스크가 필요하지만 결과는 한 쌍의 빈 쌍이 8 개의 캐시 라인을 공유합니다.

이 경우 코드 속도를 높이는 또 다른 가능한 방법은 SSE4, 특히 X64 모드입니다. 16 개의 레지스터 x 128 비트를 얻을 수 있으며 캐시 오염을 제한하기 위해 읽기 (MOVNTDQA)를 최적화 할 수 있습니다. 그래도 읽기 속도에 많은 도움이 될지 확실하지 않습니다. Core2 Prefetcher가 이것을 잡을 것으로 기대합니다. 순차적 정수를 읽는 것이 가장 간단한 액세스가 가능합니다. 모든 프리 페터는이를 최적화해야합니다.

다른 팁

각 '청크'를 식별하기 위해 인라인 메타데이터가 포함된 단일 스트림으로 출력 스트림을 작성할 수 있는 옵션이 있습니까?'청크'를 읽으려면 임계값 함수를 실행한 다음 이를 특정 출력 스트림에 쓰는 대신 그것이 속한 스트림(1바이트)과 원본 데이터를 쓰면 됩니다. 스래싱을 줄이세요.

귀하가 이러한 데이터를 여러 번 처리해야 한다고 말한 사실을 제외하고는 이것을 제안하지 않습니다.각 연속 실행에서 입력 스트림을 읽어 bin 번호(1바이트)를 얻은 다음 다음 8바이트에서 해당 bin에 대해 수행해야 하는 모든 작업을 수행합니다.

이 메커니즘의 캐싱 동작에 관해서는 두 개의 데이터 스트림만 통과하고 첫 번째 경우를 제외하고는 읽는 만큼의 데이터를 쓰기 때문에 하드웨어는 여러분이 기대할 수 있는 모든 도움을 제공할 것입니다. 프리페칭, 캐시 라인 최적화 등

데이터를 처리할 때마다 추가 바이트를 추가해야 한다면 최악의 캐시 동작은 평균적인 경우입니다.스토리지 비용을 감당할 수 있다면 나에게는 승리인 것 같습니다.

당신이 정말로 필사적이라면 몇 가지 아이디어가 있습니다 ...

하드웨어 업그레이드를 고려할 수 있습니다. 스트리밍 애플리케이션의 경우 귀하와 다소 유사한 경우 I7 프로세서로 변경하여 빠른 속도 향상을 받았습니다. 또한 AMD 프로세서는 메모리 바운드 작업의 Core 2보다 낫습니다 (최근에 직접 사용하지는 않았지만).

고려할 수있는 또 다른 솔루션은 CUDA와 같은 언어를 사용하여 그래픽 카드에서 처리하는 것입니다. 그래픽 카드는 매우 높은 메모리 대역폭을 갖고 빠른 부동 소수점 수학을 수행하도록 조정되었습니다. 직접 최적화되지 않은 C 구현에 비해 CUDA 코드의 개발 시간을 5 배에서 20 배 지출 할 것으로 예상됩니다.

파일을 메모리에 매핑하기 위해 탐색할 수도 있습니다.이렇게 하면 커널이 메모리 관리를 대신 처리할 수 있습니다.커널은 일반적으로 페이지 캐시를 처리하는 방법을 가장 잘 알고 있습니다.서로 다른 Oses가 서로 다른 방식으로 메모리 관리를 처리하므로 응용 프로그램이 둘 이상의 플랫폼에서 실행되어야 하는 경우 특히 그렇습니다.

ACE와 같은 프레임워크가 있습니다(http://www.cs.wustl.edu/~schmidt/ACE.html) 또는 부스트(http://www.boost.org) 이를 통해 플랫폼 독립적인 방식으로 메모리 매핑을 수행하는 코드를 작성할 수 있습니다.

이와 같은 상황에 대한 실제 답변은 몇 가지 접근 방식과 시간을 코딩하는 것입니다. 당신이 분명히 한 일. 나와 같은 모든 사람들은 시도 할 다른 접근법을 제안하는 것입니다.

예를 들어 : 캐시 스 래싱이없는 경우에도 (출력 스트림이 동일한 캐시 라인에 매핑) 크기가 크기 = 1 << 19 및 sizeof (int) = 4, 32 비트 인 크기를 쓰는 경우 크기를 작성하는 경우 -IE입니다. 당신은 8MB의 데이터를 작성하고 있으며 실제로 8MB를 읽은 다음 8MB를 쓰고 있습니다. 데이터가 X86 프로세서의 일반 WB (WriteBack) 메모리에 있으면 라인에 쓰기 위해서는 먼저 데이터를 읽으려고하더라도 먼저 선의 이전 사본을 읽어야합니다.

(a) WC 메모리 (아마도 설치 통증) 또는 (b) SSE 스트리밍 스토어, 일명 NT (비 임계) 상점을 사용 하여이 불필요한 RFO 읽기 트래픽을 제거 할 수 있습니다. Movnt* -Povntq, movntps 등 (MovntDQA 스트리밍 하중도 있습니다.

차라리 인터넷 검색으로 방금 찾은이 논문이 마음에 듭니다. http://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

지금 : movnt*는 WB 메모리에 적용되지만 소수의 쓰기 cmbining 버퍼를 사용하여 WC 메모리처럼 작동합니다. 실제 숫자는 프로세서 모델에 따라 다릅니다. 첫 번째 인텔 칩에는 P6 (일명 Pentium Pro)가있는 첫 번째 인텔 칩에는 4 개만있었습니다. OOF ... 불도저의 4K WCC (쓰기 결합 캐시) 기본적으로 64 개의 쓰기 결합 버퍼를 제공합니다. http://semiaccute.com/forums/showthread.php?t=6145&page=40, 4 개의 클래식 WC 버퍼 만 있지만. 하지만 http://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf 일부 프로세스에는 6 개의 WC 버퍼가 있으며 일부는 8. 일반적으로 64가 아닙니다.

그러나 여기에 시도 할 수있는 것이 있습니다. 자신을 결합하는 글을 구현하십시오.

a) 64 (#Streams) 버퍼의 단일 세트, 각 크기 64b (캐시 라인 크기), 또는 128 또는 256b의 단일 세트에 씁니다. 이 버퍼를 일반적인 WB 메모리에 두십시오. Movnt*를 사용할 수는 있지만 일반 상점으로 액세스 할 수 있습니다.

이 버퍼 중 하나가 가득 차면 스트림이 실제로 갈 예정인 메모리의 버스트로 복사하십시오. Movnt* 스트리밍 스토어 사용.

이것은 임시 버퍼에 저장된 * n 바이트를 수행하여 L1 캐시 * 64 * 64 바이트를 쳤다. * 스트리밍 스토어를 통해 작성된 바이트 - 기본적으로 메모리로 바로 이동합니다.

즉, 바이트 캐시 히트 read + n 바이트 캐시 히트 쓰기 + n 바이트 캐시 미스

V와 N BYTES 캐시 MISS read + N Bytes 캐시 쓰기 읽기.

캐시 미스 읽기의 N 바이트를 줄이면 추가 오버 헤드를 보충하는 것보다 MOE가 될 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow