512x512のマトリックスの転置が、513x513のマトリックスの転置よりもはるかに遅いのはなぜですか?

224
Luchian Grigore 2012-07-11 03:00.

さまざまなサイズの正方行列でいくつかの実験を行った後、パターンが浮かび上がりました。常に、サイズの行列の転置は、サイズの行列の2^n転置よりも遅くなります2^n+1。の値が小さい場合n、違いは大きくありません。

ただし、512の値を超えると大きな違いが発生します。(少なくとも私にとっては)

免責事項:要素が二重にスワップされているため、関数が実際に行列を転置しないことはわかっていますが、違いはありません。

コードに従います:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

変更MATSIZEすると、サイズを変更できます(ええと!)。私はideoneに2つのバージョンを投稿しました:

  • サイズ512-平均2.46ミリ秒-http://ideone.com/1PV7m
  • サイズ513-平均0.75ミリ秒-http://ideone.com/NShpo

私の環境(MSVS 2010、完全な最適化)では、違いは似ています:

  • サイズ512-平均2.19ミリ秒
  • サイズ513-平均0.57ミリ秒

なんでこんなことが起こっているの?

3 answers

198
Luchian Grigore 2012-07-11 03:00.

説明は、C ++のソフトウェアの最適化におけるAgnerFogからのものであり、データへのアクセス方法とキャッシュへの保存方法に限定されています。

用語と詳細情報については、キャッシュに関するwikiエントリを参照してください。ここで絞り込みます。

キャッシュはセット行で構成されています。一度に使用されるセットは1つだけで、そこに含まれる任意の行を使用できます。1行がミラーリングできるメモリに行数を掛けると、キャッシュサイズがわかります。

特定のメモリアドレスについて、次の式を使用して、どのセットがそれをミラーリングする必要があるかを計算できます。

set = ( address / lineSize ) % numberOfsets

この種の式は、各メモリアドレスが読み取られる可能性が高いため、理想的にはセット全体に均一に分散されます(理想的には言った)。

重複が発生する可能性があることは明らかです。キャッシュミスの場合、メモリがキャッシュに読み込まれ、古い値が置き換えられます。各セットにはいくつかの行があり、そのうち最も使用頻度の低い行が新しく読み取られたメモリで上書きされることを忘れないでください。

Agnerの例にいくらか従おうとします。

各セットに4行あり、それぞれが64バイトを保持していると仮定します。最初0x2710に、セットに含まれるアドレスの読み取りを試み28ます。そして、我々はまた、アドレスを読み込もう0x2F000x37000x3F000x4700。これらはすべて同じセットに属しています。読む前0x4700に、セット内のすべての行が占有されていたでしょう。そのメモリを読み取ると、セット内の既存の行、つまり最初に保持していた行が削除され0x2710ます。問題は、(この例では)0x800離れているアドレスを読み取るという事実にあります。これは重要な進歩です(この例でも)。

クリティカルストライドも計算できます。

criticalStride = numberOfSets * lineSize

間隔を空けた変数criticalStrideまたは複数離れた変数は、同じキャッシュラインをめぐって競合します。

これは理論の部分です。次に、説明(Agnerも、間違いを避けるために厳密にフォローしています):

64x64のマトリックス(効果はキャッシュによって異なることに注意してください)、8kbキャッシュ、セットあたり4行* 64バイトの行サイズを想定します。各行は、マトリックス(64ビットint)内の8つの要素を保持できます。

クリティカルストライドは2048バイトで、これはマトリックスの4行に対応します(メモリ内で連続しています)。

行28を処理していると仮定します。この行の要素を取得して、列28の要素と交換しようとしています。行の最初の8つの要素はキャッシュ行を構成しますが、8つの異なる要素になります。列28のキャッシュライン。クリティカルストライドは4行離れていることを忘れないでください(列内の4つの連続した要素)。

列で要素16に達すると(セットごとに4つのキャッシュラインと4行離れている=トラブル)、ex-0要素はキャッシュから削除されます。列の終わりに達すると、以前のすべてのキャッシュ行が失われ、次の要素にアクセスするときに再ロードする必要があります(行全体が上書きされます)。

クリティカルストライドの倍数ではないサイズを使用すると、垂直方向でクリティカルストライドが離れている要素を処理しなくなったため、災害のこの完璧なシナリオが台無しになり、キャッシュのリロードの数が大幅に削減されます。

別の免責事項-私は説明に頭を悩ませ、それを釘付けにしたいと思っていますが、間違っているかもしれません。とにかく、Mysticialからの返信(または確認)を待っています。:)

78
Voo 2012-07-11 03:26.

Luchianは、この動作が発生する理由を説明していますが、この問題に対する1つの可能な解決策を示し、同時にキャッシュ忘却アルゴリズムについて少し示すのは良い考えだと思いました。

あなたのアルゴリズムは基本的に以下を行います:

for (int i = 0; i < N; i++) 
   for (int j = 0; j < N; j++) 
        A[j][i] = A[i][j];

これは現代のCPUにとっては恐ろしいことです。1つの解決策は、キャッシュシステムの詳細を把握し、アルゴリズムを微調整してこれらの問題を回避することです。あなたがそれらの詳細を知っている限り、うまく機能します..特にポータブルではありません。

それよりもうまくやれるでしょうか?はい、できます。この問題への一般的なアプローチは、名前が示すように特定のキャッシュサイズに依存しないようにするキャッシュ忘却アルゴリズムです[1]。

解決策は次のようになります。

void recursiveTranspose(int i0, int i1, int j0, int j1) {
    int di = i1 - i0, dj = j1 - j0;
    const int LEAFSIZE = 32; // well ok caching still affects this one here
    if (di >= dj && di > LEAFSIZE) {
        int im = (i0 + i1) / 2;
        recursiveTranspose(i0, im, j0, j1);
        recursiveTranspose(im, i1, j0, j1);
    } else if (dj > LEAFSIZE) {
        int jm = (j0 + j1) / 2;
        recursiveTranspose(i0, i1, j0, jm);
        recursiveTranspose(i0, i1, jm, j1);
    } else {
    for (int i = i0; i < i1; i++ )
        for (int j = j0; j < j1; j++ )
            mat[j][i] = mat[i][j];
    }
}

少し複雑ですが、短いテストでは、VS2010x64リリースの古いe8400で非常に興味深いものが示されています。 MATSIZE 8192

int main() {
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);
    recursiveTranspose(0, MATSIZE, 0, MATSIZE);
    QueryPerformanceCounter(&end);
    printf("recursive: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));

    QueryPerformanceCounter(&start);
    transpose();
    QueryPerformanceCounter(&end);
    printf("iterative: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));
    return 0;
}

results: 
recursive: 480.58ms
iterative: 3678.46ms

編集:サイズの影響について:ある程度は目立ちますが、それほど顕著ではありません。これは、1まで再帰する代わりに反復ソリューションをリーフノードとして使用しているためです(再帰アルゴリズムの通常の最適化)。LEAFSIZE = 1に設定した場合、キャッシュは私に影響を与えません[ 8193: 1214.06; 8192: 1171.62ms, 8191: 1351.07ms-それは許容誤差の範囲内であり、変動は100msの領域にあります。この「ベンチマーク」は、完全に正確な値が必要な場合は、あまり快適ではありません])

[1]このようなものの出典:Leisersonと共同でこれについて働いた誰かから講義を得ることができないなら..私は彼らの論文が良い出発点であると思います。これらのアルゴリズムがまだほとんど説明されていません。CLRにはそれらに関する脚注が1つあります。それでも、それは人々を驚かせる素晴らしい方法です。


編集(注:私はこの回答を投稿した人ではありません。これを追加したかっただけです):
上記のコードの完全なC ++バージョンは次のとおりです。

template<class InIt, class OutIt>
void transpose(InIt const input, OutIt const output,
    size_t const rows, size_t const columns,
    size_t const r1 = 0, size_t const c1 = 0,
    size_t r2 = ~(size_t) 0, size_t c2 = ~(size_t) 0,
    size_t const leaf = 0x20)
{
    if (!~c2) { c2 = columns - c1; }
    if (!~r2) { r2 = rows - r1; }
    size_t const di = r2 - r1, dj = c2 - c1;
    if (di >= dj && di > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, (r1 + r2) / 2, c2);
        transpose(input, output, rows, columns, (r1 + r2) / 2, c1, r2, c2);
    }
    else if (dj > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, r2, (c1 + c2) / 2);
        transpose(input, output, rows, columns, r1, (c1 + c2) / 2, r2, c2);
    }
    else
    {
        for (ptrdiff_t i1 = (ptrdiff_t) r1, i2 = (ptrdiff_t) (i1 * columns);
            i1 < (ptrdiff_t) r2; ++i1, i2 += (ptrdiff_t) columns)
        {
            for (ptrdiff_t j1 = (ptrdiff_t) c1, j2 = (ptrdiff_t) (j1 * rows);
                j1 < (ptrdiff_t) c2; ++j1, j2 += (ptrdiff_t) rows)
            {
                output[j2 + i1] = input[i2 + j1];
            }
        }
    }
}
67
Ruslan 2017-12-30 12:34.

Luchian Grigoreの回答の説明の例として、64x64および65x65マトリックスの2つのケースでのマトリックスキャッシュの存在がどのように見えるかを示します(数値の詳細については、上記のリンクを参照してください)。

以下のアニメーションの色は、次のことを意味します。

  • –キャッシュにない、
  • –キャッシュ内、
  • –キャッシュヒット、
  • – RAMから読み取るだけで、
  • –キャッシュミス。

64x64の場合:

新しい行へのほぼすべてのアクセスがキャッシュミスを引き起こすことに注意してください。そして今、それが通常の場合、65x65マトリックスをどのように探すか:

ここでは、最初のウォームアップ後のアクセスのほとんどがキャッシュヒットであることがわかります。これは、CPUキャッシュが一般的に機能することを目的とした方法です。


上記のアニメーションのフレームを生成したコードは、ここで確認できます。

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

ジェイ・ブルースはどうやら子供を妊娠することによってメッツから離れて取引されていることを祝った

ジェイ・ブルースはどうやら子供を妊娠することによってメッツから離れて取引されていることを祝った

あなたが一時的に会っていなかったとき。シーズン11-1を開始したチームであるニューヨークメッツは、日曜日の午後にフィラデルフィアで行われた最後の11試合の9試合目を失いました。

スティーブンキングのアウトサイダーはトランプ時代のそれです

スティーブンキングのアウトサイダーはトランプ時代のそれです

スティーブン・キングのアウトサイダーは、多くの点で先祖返りの小説であり、80年代の全盛期から引き裂かれたように見える生き物の特徴であり、おそらくセル以来の彼の最もパルプのような本ですが、今日の恐怖の中で間違いなく設立された作品です。表面上は、形を変えるペニーワイズのような子供たちの殺人者を中心としており、その最も暗い脅威は、封じ込められず、神経質に平凡なものよりも幻想的で打ち負かされません。

スティーブンユニバースは、強烈な内部エピソードのペアで、それ自体のバックストーリーをさりげなく粉砕します

スティーブンユニバースは、強烈な内部エピソードのペアで、それ自体のバックストーリーをさりげなく粉砕します

スティーブンユニバースビーチシティのエピソードが実行されるたびに、いくつかのクライマックスイベントが発生し、スティーブンユニバースのより広い神話に対する理解の一部が失われます。これはあなたが期待していたことですか?今日のエピソードは両方とも、容赦なくゆっくりと、シーズンの終盤の主要な部分を設定する決定的な結論に向かって進みます。そして、ロナウドは、静かな納屋が倒れているのを発見した夜中にスティーブンを捕まえるためにやって来ます。月に。

ディズニーワールドの旅行のヒントを教えてください

ディズニーワールドの旅行のヒントを教えてください

「光が触れるものはすべて私たちの王国です。」今週のHackYour Cityでは、1つのテーマパークを取り上げます。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

Come diventare Web Developer?

Come diventare Web Developer?

Vorresti diventare web developer e non sai da dove cominciare?! Qui troverai tutte le risposte necessarie, anche io non sapevo che strada intraprendere ma voglio aiutarti a non commettere i miei stessi errori. Cosa imparare? Le competenza essenziali per qualsiasi web developer sono almeno tre.

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

Language