7

私は分析と測定を行っており、分析と測定から異なる結果を得ています。このコードは、サイズが 512 バイト、ブロック サイズが 32 バイトのデータ キャッシュを使用する 2 つのループです。

int SumByColRow (int matrix[M][M], int size)
{
  int i, j, Sum = 0;

  for (j = 0; j < size; j ++) {
    for (i = 0; i < size; i ++) {
      Sum += matrix[i][j];
    }
  }
  return Sum;
}

int SumByRowCol (int matrix[M][M], int size)
{
  int i, j, Sum = 0;

  for (i = 0; i < size; i ++) {
    for (j = 0; j < size; j ++) {
      Sum += matrix[i][j];
    }
  }
  return Sum;
}

Cは行列を行ごとに格納するため、内側のループで行を切り替えない方が速いと思います。そのため、SumByRowColは高速になるはずですが、測定では逆です。値が連続した要素からのものであるため、空間的局所性の原則によるキャッシュが内部ループを高速化できると、高速になると思いましたか? 実際にSumByColRowの方が速いと計測した時の実行時間を計測した理由は何ですか？

SumByColRow: Result: 31744
6415.29 us(641529 ticks)
SumByRowCol: Result: 31744
7336.47 us(733647 ticks)

アップデート

プログラムを再度実行して、実際にデータ キャッシュを使用していることを確認しました。今度は期待どおりの結果が得られたので、上記の結果は偶然の一致である可能性があり、次のようになります。

SumByColRow: Result: 31744
5961.13 us(596113 ticks)
SumByRowCol: Result: 31744
2328.89 us(232889 ticks)
4

1 に答える 1

4

あなたのコードに基づいて、反例を提供できます。

コード

#include "timer.h"
#include <stdio.h>

enum { M = 128 };

extern int SumByColRow (int matrix[M][M], int size);
extern int SumByRowCol (int matrix[M][M], int size);

int SumByColRow (int matrix[M][M], int size)
{
    int Sum = 0;

    for (int j = 0; j < size; j ++)
    {
        for (int i = 0; i < size; i ++)
            Sum += matrix[i][j];
    }
    return Sum;
}

int SumByRowCol (int matrix[M][M], int size)
{
    int Sum = 0;

    for (int i = 0; i < size; i ++)
    {
        for (int j = 0; j < size; j ++)
            Sum += matrix[i][j];
    }
    return Sum;
}

static inline int max(int i, int j) { return (i > j) ? i : j; }

int main(void)
{
    int matrix[M][M];
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            matrix[i][j] = 1000*i + j;

    Clock clk;
    unsigned long long x[M];
    char buffer[32];
    unsigned long long sum;

    clk_init(&clk);

    clk_start(&clk);
    for (int i = 0; i < M; i++)
        x[i] = SumByColRow(matrix, max(M - i, 10));
    clk_stop(&clk);
    sum = 0;
    for (int i = 0; i < M; i++)
        sum += x[i];
    printf("SumByColRow: value = %llu, time = %s\n", sum, clk_elapsed_us(&clk, buffer, sizeof(buffer)));

    clk_start(&clk);
    for (int i = 0; i < M; i++)
        x[i] = SumByRowCol(matrix, max(M - i, 10));
    clk_stop(&clk);
    sum = 0;
    for (int i = 0; i < M; i++)
        sum += x[i];
    printf("SumByRowCol: value = %llu, time = %s\n", sum, clk_elapsed_us(&clk, buffer, sizeof(buffer)));

    return 0;
}

2 つのSumBy機能は実質的に変更されていません (マイナーな表記の微調整以外は何もありません)。タイミング ハーネスは開始時刻と終了時刻をClock構造体に格納し、clk_elapsed_us()関数はマイクロ秒単位の経過時間を、渡される文字列にフォーマットします。

いじり回しx[i]などは、コンパイラーがすべてを最適化しないように (試して) 確実にすることです。

出力

マシン: Mac OS X 10.8.5、GCC (i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Apple Inc. ビルド 5658 に基づく) (LLVM ビルド 2336.11.00))、Intel Core 2 Duo 2 GHz、4 GB 1067 MHz DDR3 RAM (「Early 2009」Mac Mini)。

SumByColRow: value = 33764046316, time = 0.002411
SumByRowCol: value = 33764046316, time = 0.000677

これは予想される結果を示しています — 行列がページにまたがるのに十分な大きさ (64 KiB) であるため、行ごとの列の計算が遅くなります。サイズとは何か、また関数に渡されるMものはまだ明確ではありませんが、「十分な大きさ」の配列とさまざまなサイズを使用すると、期待されるパフォーマンス パターンを得ることができます。sizeSumBy

これらの時間は快適に過ごすには十分ではありません — むしろ、より低い時間は 1 秒か 2 秒のオーダーでした。for (int j = 0; j < 1600; j++)メイン プログラムの各タイミング ループの前にループを追加すると、次のようになります。

SumByColRow: value = 33764046316, time = 2.529205
SumByRowCol: value = 33764046316, time = 1.022970

比率は小さくなっていますが (3.56 対 2.47)、それでも明らかに有利に傾いていSumByRowCol()ます。

マトリックスを初期化すると、ウォーミングできる範囲で「キャッシュがウォーミングされます」。計算の順序を逆にしても (SumByColRow の前に SumByRowCol)、タイミングに大きな違いはありません。結果は、複数の実行にわたってかなり一貫しています。

アセンブラ出力

コンパイル済みgcc -O3 -std=c99 -S:

    .section        __TEXT,__text,regular,pure_instructions
    .globl  _SumByColRow
    .align  4, 0x90
_SumByColRow:
Leh_func_begin1:
    pushq   %rbp
Ltmp0:
    movq    %rsp, %rbp
Ltmp1:
    testl   %esi, %esi
    jg      LBB1_5
    xorl    %eax, %eax
LBB1_2:
    popq    %rbp
    ret
LBB1_5:
    movl    %esi, %ecx
    xorl    %eax, %eax
    movq    %rcx, %rdx
    jmp     LBB1_6
    .align  4, 0x90
LBB1_3:
    addl    (%r8), %eax
    addq    $512, %r8
    decq    %rsi
    jne     LBB1_3
    addq    $4, %rdi
    decq    %rdx
    je      LBB1_2
LBB1_6:
    movq    %rcx, %rsi
    movq    %rdi, %r8
    jmp     LBB1_3
Leh_func_end1:

    .globl  _SumByRowCol
    .align  4, 0x90
_SumByRowCol:
Leh_func_begin2:
    pushq   %rbp
Ltmp2:
    movq    %rsp, %rbp
Ltmp3:
    testl   %esi, %esi
    jg      LBB2_5
    xorl    %eax, %eax
LBB2_2:
    popq    %rbp
    ret
LBB2_5:
    movl    %esi, %ecx
    xorl    %eax, %eax
    movq    %rcx, %rdx
    jmp     LBB2_6
    .align  4, 0x90
LBB2_3:
    addl    (%r8), %eax
    addq    $4, %r8
    decq    %rsi
    jne     LBB2_3
    addq    $512, %rdi
    decq    %rdx
    je      LBB2_2
LBB2_6:
    movq    %rcx, %rsi
    movq    %rdi, %r8
    jmp     LBB2_3
Leh_func_end2:
于 2013-10-08T09:22:45.853 に答える