2つの異なる方法で行列を乗算する（時間を比較する）

Question

2つの行列の乗算を比較します - デフォルトの方法で2番目の行列の転置後の乗算を割り当てます。私はこのようなものを書いたが、timeとtime2はおおよそ等しい。あるケースでは、最初の方法は速く、同じサイズの行列で乗算を実行し、別の方法では2番目の方法が高速です。何かが間違っていますか？コード内で何かを変更する必要がありますか？

clock_t start = clock(); 

    int sum; 
    for(int i=0; i<size; ++i) { 
     for(int j=0; j<size; ++j) { 
      sum = 0; 
      for(int k=0; k<size; ++k) { 
       sum = sum + (m1[i][k] * m2[k][j]); 
      } 
      score[i][j] = sum; 
     } 
    } 

    clock_t end = clock(); 
    double time = (end-start)/(double)CLOCKS_PER_SEC; 

    for(int i=0; i<size; ++i) { 
     for(int j=0; j<size; ++j) { 
      int temp = m2[i][j]; 
      m2[i][j] = m2[j][i]; 
      m2[j][i] = temp; 
     } 
    } 

    clock_t start2 = clock(); 

    int sum2; 
    for(int i=0; i<size; ++i) { 
     for(int j=0; j<size; ++j) { 
      sum2 = 0; 
      for(int k=0; k<size; ++k) { 
       sum2 = sum2 + (m1[k][i] * m2[k][j]); 
      } 
      score[i][j] = sum2; 
     } 
    } 

    clock_t end2 = clock(); 
    double time2 = (end2-start2)/(double)CLOCKS_PER_SEC; 

Answer 1

お客様のコードおよび/またはご理解の点で重大な問題が複数あります。説明しようとしましょう。

行列の乗算は、プロセッサが値をメモリにロードしてメモリに格納できる速度でボトルネックになります。現在のアーキテクチャでは、キャッシュを使用しています。データはメモリからキャッシュに、キャッシュからメモリにはブロック単位で移動されます。キャッシングの利点を最大限に活用するには、そのブロック内のすべてのデータを確実に使用する必要があります。これを行うには、メモリに順次データにアクセスしてください。

Cでは、多次元配列はrow-major orderで指定されています。右端のインデックスはメモリ内で連続しています。つまり、a[i][k]とa[i][k+1]はメモリ内で連続しています。

アーキテクチャによっては、RAMからキャッシュに（またはその逆に）データを移動するためにプロセッサが待機する（何もしない）時間がCPU時間に含まれる場合と含まれない場合があります例えば、非常に貧弱な解像度であっても、clock()が測定されます）。この種の測定（"マイクロベンチマーク"）では、使用されたCPUとリアル（またはウォールクロック）時間の両方を測定し報告する方がはるかに優れています。特にマイクロベンチマークが異なるマシン上で実行されている場合は、変更の実際的な影響をよりよく理解することができます。

多くのバリエーションがありますので、通常、数百回の繰り返し（1回の操作で複数の操作が繰り返される可能性があるため、簡単に測定できます）を測定し、それぞれの期間を保存し、レポートしますそれらの中央値。なぜ平均値で、最小値ではなく最大値で平均値ですか？一般的には通常よりもはるかに高い値が得られることがありますが、時には不具合（外部イベントなどによる不合理な測定）があります。これは最大値を無関係にし、除去されない限り平均値（平均値）を歪ませます。最小限度は一般的に過度に楽観的なケースであり、すべてがちょうど完全に行なわれた。実際にはまれにしか起こらないので、実際の関心事ではなく好奇心です。一方、中央値の時間は実用的な測定値を与えます。テストケースのすべての実行の50％が測定された中央値時間を超えないようにすることができます。

POSIXyシステム（Linux、Mac、BSD）では、clock_gettime()を使用して時間を測定する必要があります。 struct timespecフォーマットはナノ秒の精度（1秒= 1,000,000,000ナノ秒）を有するが、分解能がより小さくてもよい（すなわち、クロックが変化するたびに1ナノ秒以上変化する）。私は個人的にあなたが運転する前にtiming_start()を呼び出し、操作後timing_stop()

#define _POSIX_C_SOURCE 200809L 
#include <time.h> 

static struct timespec cpu_start, wall_start; 
double     cpu_seconds, wall_seconds; 

void timing_start(void) 
{ 
    clock_gettime(CLOCK_REALTIME, &wall_start); 
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &cpu_start); 
} 

void timing_stop(void) 
{ 
    struct timespec cpu_end, wall_end; 
    clock_gettime(CLOCK_REALTIME, &wall_end); 
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &cpu_end); 

    wall_seconds = (double)(wall_end.tv_sec - wall_start.tv_sec) 
       + (double)(wall_end.tv_nsec - wall_start.tv_nsec)/1000000000.0; 
    cpu_seconds = (double)(cpu_end.tv_sec - cpu_start.tv_sec) 
       + (double)(cpu_end.tv_nsec - cpu_start.tv_nsec)/1000000000.0; 
} 

を使用します。 cpu_secondsには取ったCPU時間が含まれ、実際の壁時計の時間はwall_secondsです（両方とも秒単位で、意味のある小数点をすべて印刷するには%.9fなど）。

MicrosoftはCコードを他のシステムに移植したくないため、上記はWindowsでは動作しません。代わりに独自の "標準"を開発することを好みます。 （これらのC11「安全」_s() I/O機能変異体は、例えばPOSIX getline()、またはWindowsを除くすべてのシステムでワイド文字のサポートの状態に比べて、愚かな偽です。）

行列の乗算が

c[r][c] = a[r][0] * b[0][c] 
     + a[r][1] * b[1][c] 
     :   : 
     + a[r][L] * b[L][c] 

です

ここで、aはL+1の列を持ち、bはL+1の行を持ちます。

合計ループで連続する要素を使用するには、bを転置する必要があります。 B[c][r] = b[r][c]場合、

c[r][c] = a[r][0] * B[c][0] 
     + a[r][1] * B[c][1] 
     :   : 
     + a[r][L] * B[c][L] 

そのような場合には効率的にキャッシュを利用する処理のために、aとBがメモリに連続していることは十分ではなく、別々の（おそらく「遠い」互いに離れる）ことに留意されたいです。

OPはbを転置するために、以下の疑似コードに似た単純なループを使用する：

For r in rows: 
    For c in columns: 
     temporary = b[r][c] 
     b[r][c] = b[c][r] 
     b[c][r] = temporary 
    End For 
End For 

上記の問題は、各要素が二回スワップに参加することです。たとえば、bに行と列が10個の場合、r = 3, c = 5はb[3][5]とb[5][3]を交換しますが、その後r = 5, c = 3はb[5][3]とb[3][5]を交換します。基本的に、ダブルループは、元の順序にマトリックスを復元することになります。;転置はしません。

には、次のエントリと実際の転置を考えてみましょう：

b[0][0] b[0][1] b[0][2]  b[0][0] b[1][0] b[2][0] 
b[1][0] b[1][1] b[1][2] ⇔ b[0][1] b[1][1] b[2][1] 
b[2][0] b[2][1] b[2][2]  b[0][2] b[1][2] b[2][2] 

対角線エントリがスワップされていません。それぞれのスワップが上三角形から下三角形に1つのエントリを入れ替えるので、上の三角部分（c > r）または下三角部分（r > c）にスワップするだけで、すべてのエントリを入れ替えることができます。 。

ので、おさらいします

は、何かが間違って行われていますか？

はい。あなたの転置は何もしません。なぜあなたは2番目の行列を転置したいのか理解していません。時間の測定には精度の低いCPU時間が使用されますが、RAMとCPUキャッシュ間でデータを移動するのにかかる時間は反映されません。 2番目のテストケースではm2が "転置"されています（そうでない場合を除き、各要素のペアを2回スワップして元の状態に戻すため）。最も内側のループが最も左の配列インデックスを超えています。間違った結果（さらに、最も内側のループの連続反復はメモリ内の互いに遠く離れたアイテムにアクセスするので、反最適化である：それは速度に関して最悪であるパターンを使用する。）

上記のすべてが厳しいと思われるかもしれませんが、それは意図されていません。にすべてです。私はあなたを知らず、私はあなたを評価しようとしていません。私はあなたの現在ののこの特定の答えの間違いを指摘しているだけで、あなたと他の誰かが同様の状況でこの質問に遭遇して学ぶのを助けることを望むだけです。