source

행렬 곱셈: 행렬 크기가 작거나 타이밍 차이가 큽니다.

gigabyte 2022. 8. 28. 09:47
반응형

행렬 곱셈: 행렬 크기가 작거나 타이밍 차이가 큽니다.

다음과 같은 행렬 곱셈 코드가 있습니다.

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

여기서 행렬의 크기는 다음과 같이 표시됩니다.dimension행렬의 크기가 2000이면 이 코드를 실행하는 데 147초가 걸리지만 2048이면 447초가 걸립니다.곱셈 수의 차이는 (2048*2048)/(2000*2000)= 1.073이지만, 타이밍 차이는 447/190=3입니다. 왜 이런 일이 일어나는지 설명해 주실 수 있나요?나는 그것이 선형적으로 확장될 것이라고 예상했지만, 그것은 일어나지 않았다.나는 가장 빠른 행렬 곱셈 코드를 만들려는 것이 아니라 단지 왜 그런 일이 일어나는지 이해하려는 것이다.

사양: AMD Opteron 듀얼 코어 노드 (2.2)GHz), 2G RAM, gcc v 4.5.0

as as as로 된 프로그램gcc -O3 simple.c

인텔의 icc 컴파일러에서도 실행해 본 결과, 같은 결과가 나왔습니다.

편집:

comments/communications에서 제시한 바와 같이 dimension=2060으로 코드를 실행했는데 145초 걸립니다.

전체 프로그램은 다음과 같습니다.

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

/* change dimension size as needed */
const int dimension = 2048;
struct timeval tv; 

double timestamp()
{
        double t;
        gettimeofday(&tv, NULL);
        t = tv.tv_sec + (tv.tv_usec/1000000.0);
        return t;
}

int main(int argc, char *argv[])
{
        int i, j, k;
        double *A, *B, *C, start, end;

        A = (double*)malloc(dimension*dimension*sizeof(double));
        B = (double*)malloc(dimension*dimension*sizeof(double));
        C = (double*)malloc(dimension*dimension*sizeof(double));

        srand(292);

        for(i = 0; i < dimension; i++)
                for(j = 0; j < dimension; j++)
                {   
                        A[dimension*i+j] = (rand()/(RAND_MAX + 1.0));
                        B[dimension*i+j] = (rand()/(RAND_MAX + 1.0));
                        C[dimension*i+j] = 0.0;
                }   

        start = timestamp();
        for(i = 0; i < dimension; i++)
                for(j = 0; j < dimension; j++)
                        for(k = 0; k < dimension; k++)
                                C[dimension*i+j] += A[dimension*i+k] *
                                        B[dimension*k+j];

        end = timestamp();
        printf("\nsecs:%f\n", end-start);

        free(A);
        free(B);
        free(C);

        return 0;
}

추측컨대 캐시

, 2000년, 2000년, 2년, 2000년, 2년, 2년, 이렇게 두 수 .double을 사용하다32kb L1 1캐while whilewhile whilewhile whilewhilewhile whilewhilewhilewhilewhilewhile 다른 필요한) ( 른른른 other)))

그러나 2048까지 확장하면 캐시 전체가 사용됩니다(다른 것을 위한 공간이 필요하기 때문에 일부 캐시는 유출됩니다).

캐시 정책이 LRU라고 가정하면 캐시를 조금만 흘리면 행 전체가 반복적으로 플래시되고 L1 캐시에 새로고침됩니다.

다른 하나는 2의 거듭제곱으로 인한 캐시 연관성입니다.그 프로세서는 쌍방향 L1 어소시에이션이라고 생각하기 때문에, 이 경우는 문제가 되지 않는다고 생각합니다.(어쨌든 그 아이디어는 밖으로 던질 거야)

생각할 수 있는 설명 2: L2 캐시의 슈퍼 얼라인먼트로 인해 캐시 누락이 발생합니다.

의 ★★★★★★★★★★★★★★★★★.B배열이 열에서 반복되고 있습니다.따라서 접근은 분산되어 있습니다.총 데이터 크기는 다음과 같습니다.2k x 2k32MB로 하다L2는 L2로 하다

데이터가 완벽하게 정렬되지 않으면 B에 상당한 공간적 인접성을 갖게 됩니다.행을 홉하고 캐시라인당1개의 요소만 사용해도 캐시라인은 L2 캐시에 남아 다음 번 미들루프에서 재사용됩니다.

그러나 데이터가 완벽하게 정렬되면(2048년) 이러한 홉은 모두 동일한 "캐시 방식"에 도달하여 L2 캐시 연결성을 훨씬 초과합니다.액세스된 은 " " " 입니다.B다음 반복에서는 캐시에 머무르지 않습니다.대신, 그것들은 램에서 완전히 끌어당겨야 할 것입니다.

내가 캐시 공명이라고 부르는 걸 확실히 얻고 있어.이것은 에일리어스와 비슷하지만 완전히 동일하지는 않습니다.제가 설명해 드릴게요.

캐시는 주소의 일부를 추출하여 테이블 내의 인덱스로 사용하는 하드웨어 데이터 구조입니다.소프트웨어의 배열과 다르지 않습니다.(실제로 하드웨어에서는 어레이라고 부릅니다).캐시 어레이에는 캐시 행의 데이터 및 태그가 포함되어 있습니다.이러한 엔트리는 어레이 내의 인덱스마다 1개씩(직접 매핑), 이러한 엔트리가 여러 개 포함되어 있는 경우도 있습니다(N-way 세트 관련성).주소의 제2 부분을 추출해, 어레이에 격납되어 있는 태그와 비교한다.인덱스와 태그는 함께 캐시 라인 메모리주소를 일의로 식별합니다.마지막으로 나머지 어드레스 비트는 액세스 크기와 함께 캐시 라인에서 어떤 바이트가 주소 지정되었는지 식별합니다.

일반적으로 인덱스와 태그는 단순한 비트필드입니다.메모리 주소는

  ...Tag... | ...Index... | Offset_within_Cache_Line

(인덱스와 태그는 해시일 수 있습니다.예를 들어 인덱스가 되는 중간 범위의 비트에 대한 다른 비트의 XOR 몇 개입니다.극히 드물게는 인덱스나 태그가 캐시 라인 주소 모듈로 소수인 경우가 있습니다.이 보다 복잡한 지수 계산은 공명 문제와 싸우기 위한 시도입니다. 여기서 설명하겠습니다.모두 어떤 형태로든 공명이 발생하지만, 가장 단순한 비트필드 추출 방식에서는 공통 접근패턴에 대한 공명이 발생합니다).

그래서, 전형적인 가치들은...Opteron Dual Core에는 여러 가지 모델이 있는데, 여기에는 어떤 모델이 있는지 구체적으로 나와 있지 않습니다.랜덤으로 하나를 선택하면 2012년 3월 12일 AMD 웹 사이트 BKDG(Bios and Kernel Developer's Guide for AMD Family 15h Models 00h-0Fh)에서 볼 수 있습니다.

(15h 패밀리 = 최신 하이엔드 프로세서인 불도저 시리즈 - BKDG는 듀얼 코어를 언급하고 있습니다.다만, 설명하신 제품 번호는 정확히 모릅니다.다만, 같은 공명 개념은 모든 프로세서에 적용됩니다.캐시 크기나 연관성 등의 파라미터가 약간 다를 수 있습니다.)

페이지 33부터:

AMD 패밀리 15h 프로세서에는 2개의 128비트 포트를 갖춘 16KB, 4방향 예측 L1 데이터 캐시가 포함되어 있습니다.이는 사이클당 최대 2개의 128바이트 로드를 지원하는 쓰기 캐시입니다.L1 캐시는 16개의 뱅크(각각 16바이트 너비)로 나누어져 있습니다.[...] L1 캐시의 특정 뱅크에서 한 사이클에 한 개의 로드만 수행할 수 있습니다.

정리하면:

  • 64 바이트 캐시 라인 => 캐시 라인 내의 오프셋 비트6

  • 16KB/4-way => 공명은 4KB입니다.

    즉, 주소 비트 0-5는 캐시 라인 오프셋입니다.

  • 라인 = 캐시 . 16KB/64B 캐시 라인 => 2^14/2^6 = 2^8=256 캐시 라인.
    (128년)모든 의존관계를 수정했습니다.)

  • 4방향 연관성 => 256/4 = 캐시 어레이 내의 64개의 인덱스.I(Intel)에서는, 이러한 것을 「세트」라고 부릅니다.

    즉, 캐시는 32개의 엔트리 또는 세트의 배열로 간주할 수 있으며 각 엔트리는 태그에 4개의 캐시 행을 포함합니다.(이것보다 더 복잡하지만 괜찮습니다.)

(그런데 "set"과 "way"라는 용어의 정의는 다양합니다.

  • 가장 단순한 방식에서는 6개의 인덱스 비트가 있습니다.

    즉, 인덱스 비트(비트 6~11)에서 정확히 동일한 값을 가진 캐시 라인이 동일한 캐시 세트에 매핑됨을 의미합니다.

이제 당신의 프로그램을 보세요.

C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

루프 k는 가장 안쪽 루프입니다.2번 8번dimension dimension = 2048, k 2K의 B[dimension*k+j]루프가 액세스하는 값은 2048 * 8 = 16K 바이트 간격입니다.모두 동일한 L1 캐시 세트에 매핑되며 캐시에는 모두 동일한 인덱스가 있습니다. 대신입니다.

즉, 이 루프를 4회 반복할 때마다 캐시 누락이 발생할 수 있습니다.좋지 않습니다.

(사실 일이 좀 더 복잡해요.하지만 위의 내용은 첫 번째 이해입니다.상기의 B 엔트리의 주소는 가상 주소입니다.따라서 물리적 주소가 약간 다를 수 있습니다.또한 가상 주소 비트를 사용하여 가상 주소에서 물리적 주소로의 변환을 기다릴 필요가 없도록 예측 캐시를 제공합니다.단, 어느 경우든 코드의 "공진"은 16K입니다.L1 데이터 캐시의 공진은 16K입니다.좋지 않아.]

예를 들어 치수를 2048+1로 조금만 변경하면 어레이 B의 주소가 캐시 세트 전체에 분산됩니다.캐시 누락이 현저하게 줄어듭니다.

이러한 공진을 피하기 위해 어레이를 패딩하는 것은 매우 일반적인 최적화입니다.예를 들어 2048을 2049로 변경하는 등입니다.그러나 "캐시 차단은 훨씬 더 중요한 최적화입니다.http://suif.stanford.edu/papers/lam-asplos91.pdf


캐시 라인 공명 이외에도 다른 일이 일어나고 있습니다.예를 들어 L1 캐시에는 각각 16바이트의 폭이 있는 16개의 뱅크가 있습니다.차원 = 2048인 경우 내부 루프의 연속 B 액세스는 항상 동일한 뱅크로 이동합니다.따라서 병렬로 이동할 수 없습니다.또한 A 액세스권이 같은 은행으로 이동하게 되면 손해를 보게 됩니다.

내 생각에 이건 캐시 공명만큼 크지 않은 것 같아.

그리고, 네, 어쩌면 에일리어싱이 진행되고 있을지도 모릅니다.예를 들어 STLF(Store To Load Forwarding 버퍼)가 작은 비트필드만을 사용하여 비교하고 잘못된 일치를 얻을 수 있습니다.

(실제로 생각해 보면 캐시 내의 공명은 에일리어스와 같은 비트필드 사용과 관련되어 있습니다.공명은 여러 캐시 라인이 같은 세트를 매핑하고 분산되지 않기 때문에 발생합니다.알리사잉은 불완전한 주소 비트에 기반한 매칭에 의해 발생합니다.)


전체적으로 튜닝에 대한 권장 사항은 다음과 같습니다.

  1. 더 이상의 분석 없이 캐시 차단을 시도합니다.캐시 블로킹은 간단하기 때문에 이렇게 말하는 것입니다.필요한 것은 이것뿐일 가능성이 높기 때문입니다.

  2. 그 후 VTune 또는 OProf를 사용합니다.또는 캐시그린드.아니면...

  3. 잘 조정된 라이브러리 루틴을 사용하여 행렬 곱셈을 수행하는 것이 좋습니다.

이게 너무 오래된 건 알지만 한 입만 먹어볼게요.캐시에 관한 문제로 인해 약 2의 파워로 속도가 저하되고 있습니다.하지만 이것에는 또 다른 문제가 있다: 너무 느리다.컴퓨팅 루프를 보면,

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

가장 안쪽의 루프는 반복할 때마다 k가 1씩 변경됩니다. 즉, A의 마지막 요소에서 두 배만 떨어져 있어도 전체 '차원'은 B의 마지막 요소에서 두 배만 떨어져 있습니다.이것은 B 요소의 캐시를 전혀 이용하지 않습니다.

이것을 다음과 같이 변경하는 경우:

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k];

동일한 결과(모듈로 이중 추가 연결 오류)를 얻을 수 있지만, 훨씬 더 캐시 친화적입니다(로컬).시험해 봤는데 상당히 좋아졌어요.이는 다음과 같이 요약할 수 있습니다.

행렬을 정의로 곱하지 말고 행으로 곱하십시오.


속도 향상 예제(차원을 인수로 받아들이도록 코드를 변경했습니다)

$ diff a.c b.c
42c42
<               C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];
---
>               C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k];
$ make a
cc     a.c   -o a
$ make b
cc     b.c   -o b
$ ./a 1024

secs:88.732918
$ ./b 1024

secs:12.116630

보너스로(그리고 이 문제가 이 문제와 관련이 있는 것은) 이 루프가 이전 문제로 인해 고통받지 않는다는 것입니다.

이미 알고 계셨다면 사과드립니다!

L2 캐시 문제에 대해 몇 가지 답변이 있었습니다.

캐시 시뮬레이션을 통해 실제로 확인할 수 있습니다.발그린드의 캐시그린드 툴로 할 수 있어요

valgrind --tool=cachegrind --cache-sim=yes your_executable

명령줄 매개 변수를 CPU의 L2 매개 변수와 일치하도록 설정합니다.

다른 매트릭스 크기를 사용하여 테스트하면 L2 미스비가 갑자기 증가할 수 있습니다.

몇 가지 가능한 설명이 있습니다.생각할 수 있는 설명 중 하나는 한정된 자원(캐시 또는 TLB)의 고갈입니다.또 하나의 가능성이 있는 것은 에일리어스 스톨입니다.이러한 에일리어스 스톨은 연속되는 메모리액세스가 2의 배수(통상 4KB)로 분리되었을 때 발생할 수 있습니다.

다양한 값의 시간/차원^3을 표시하여 작업 중인 내용을 좁힐 수 있습니다.캐시를 날려버리거나 TLB 리치가 모두 소진된 경우 2000~2048년 사이에 평탄한 섹션이 나타나고 이어서 평탄한 섹션이 나타납니다.에일리어스 관련 스톨이 표시되어 있는 경우는, 2048에서 위로 가는 스파이크를 가지는 다소 평평한 그래프가 표시됩니다.

물론 이것은 진단 능력이 있지만 결정적인 것은 아닙니다.속도 저하의 원인을 결정적으로 알고 싶다면 성능 카운터에 대해 알아야 합니다. 성능 카운터는 이러한 질문에 확실하게 답할 수 있습니다.

언급URL : https://stackoverflow.com/questions/7905760/matrix-multiplication-small-difference-in-matrix-size-large-difference-in-timi

반응형