캐시 사용, 공간 지역성 및 대기 시간

Question

공간적 지역성에 관한 캐시 연산을 배우고 있습니다. (내 참조는 지금까지 린 스나이더, this tutorial에 의해 병렬 프로그래밍의 원리, 물론 위키 백과 있습니다.)

(인텔 코어 2 듀오 CPU를 사용하여, 전문 윈도우 7에서 실행, GCC로 컴파일 다음 예를 보자 L7500).

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

int main() 
{ 
    int *array; 
    int length; 
    int count; 
    int range; 
    int i; 

    // generate an array of a million integers between 0 and 99 
    length = 1000000; 
    range = 100; 
    array = calloc(length, sizeof(int)); 
    srand(time(NULL)); 
    for(i = 0; i < length; i++) 
    { 
     array[i] = rand() % range; 
     // printf("%d\n", array[i]); 
    } 

    // count the number of occurrences of 3 in the array 
    count=0; 
    for(i=0; i<length; i++) 
    { 
     if(array[i]==3) 
     { 
      count++; 
     } 
    } 
    printf("count = %6d\n", count); 

    return 0; 
} 

지금 루틴의 후반부에서, 정수의 전체 배열은 CPU가 미리 캐시로로드되어야 공간 지역성 당 있도록 판독 될 것이다. 그러나 배열 중 어느 정도가 루프 중에 한 번에 캐시로로드 될 수 있습니까? 한 번에 하나의 캐시 라인 (int = 16 정수 당 64 바이트/4 바이트), 큰 블록 또는 하나의 전체 배열이 급습 했습니까?

또한 RAM에서 캐시로 (또는 로컬이 아닌 로컬 메모리에서) 교과서별로 데이터를로드하는 데 소요되는 대기 시간은 실제로 루틴을 실행하는 데 필요한 시간보다 훨씬 더 중요 할 수 있습니다. . 참된?

이제이 코드를 다중 프로세서/멀티 코어 컴퓨터로 옮기고 코드의 카운팅 부분을 병렬 스레드 (pthread 사용)에서 실행되도록 변경하고 배열의 개별 부분을 계산합니다 마지막에 개인 수를 합산합니다. 이로 인해 RAM 대 캐시 대기 시간이 여러 번 분리되어 병렬 버전이 직렬 버전보다 느리게 실행될 수 있습니까?

Answer 1

예, 메모리 속도와 대기 시간이 많은 알고리즘을 지배하므로 가능한 한 효율적으로 메모리 캐시를 사용하여 속도를 높여야합니다.

평행을 달리고 은 일 수 있습니다. 이것을 알아 내기 위해서는 많은 테스트와 조정이 필요합니다.

예를 들어 RAM의 한 뱅크에 연결된 쿼드 코어 칩을 사용하십시오. 알고리즘이 최대 속도의 메모리 읽기를 필요로하고 연산이 RAM 속도보다 항상 빠르다면 병렬로 실행해도 아무 것도 얻지 못할 것이고 속도가 느려질 것입니다.

듀얼 소켓 시스템을 사용하는 경우 각 CPU에는 고유 한 RAM이 있으며 알고리즘의 속도가 빨라집니다.

또는 시스템이 RAM 1 뱅크에서 4로 업그레이드하고 단일 채널에서 4 채널 RAM 구성으로 전환 할 수 있습니다. 이 시점에서 RAM 속도는 계산 속도를 초과 할 수 있으며 쿼드 코어는 더 많은 스레드를 실행하여 이익을 얻습니다.

제 생각에는 코어 당 스레드를 실행하면 대개 도움이되며 시스템 업그레이드를 활용할 것입니다. 단일 스레드를 실행하면 약간의 동기화 오버 헤드를 피할 수 있지만 나중에 프로그램이 항상 제한됩니다.