FrontPage

Principle of Locality

Contents

What is Principle of Locality ?

  • Definition
    The tendency of a processor to access the same set of memory locations repetitively over a short period of time.
    つまり、一度アクセス(参照)された命令群・データやその近辺のメモリに存在する命令群・データは、近い将来再度アクセス(参照)される傾向にあるという原理のこと。
    (日本語では、参照の局所性・アクセスの局所性などという)
    https://en.wikipedia.org/wiki/Locality_of_reference

  • Types
    この参照の局所性は、三種類の性質を持つ。

    • Spatial locality(空間的局所性)
      あるアドレス空間がアクセスされると、その近辺のアドレスもアクセスされる可能性が高い.
  • Temporal locality(時間的局所性)
    あるアドレス空間がアクセスされると、近い将来その同じアドレスがアクセスされる可能性が高い.
  • Sequential locality(逐次的局所性)
    メモリが逐次アクセスされるという概念.

https://i.stack.imgur.com/uwMoy.gif
(img:https://stackoverflow.com/questions/7638932/what-is-locality-of-reference)

これら三つの概念を上手く扱えるかどうかは、個人のプログラムの実装による.
(つまり、上手く応用できている場合とできていない場合がある.)

  • Application Field
    キャッシュメモリ・仮想記憶

Why do we need the locality ?

参照の局所性の必要性や応用について、記憶の階層構造とその周辺の概念を交えながら考えていく.

  • How to improve a computation in terms of cpu and memory
    • 理想のコンピューター
      高速なCPUと高速かつ大容量の記憶装置を使う
      ー>処理が速く、多くのデータを記憶できるコンピューターに

    • 現実のメモリ
      大きく以下の二つに分類できる
      • 大容量でアクセス速度の遅い安価なメモリ(ハードディスク,光ディスクなど)

      • 小規模でアクセス速度の速い高価なメモリ(SRAM,DRAMなど)

        メモリからの読み込みとディスクからの読み込みはランダムアクセスで1000倍程度違う
        有線ネットワークの方がHDDやSSDのアクセスより速い場合がある


名前読込速度(MB/s)
メモリ10000MB/s
有線ネットワーク1000MB/s
SSD(シーケンシャルアクセス)100MB/s
HDD(シーケンシャルアクセス)100MB/s
SSD(ランダムアクセス)10MB/s
HDD(ランダムアクセス)1MB/s
4Gネットワーク1MB-10MB/s


  • Memory hierarchy(記憶階層)
    メモリーにおいて、速度と容量はトレードオフの関係にある.
    高価だが高速で小容量のメモリと安価だが低速の大容量メモリを組み合わせて利用するために、記憶階層の概念ができた.
    先ほどの参照の局所性は、主にこの記憶階層のキャッシュメモリにデータを蓄える際に使われる.
    (以下の図を参考に)


  • Cache Memory
    実体は高速なSRAMメモリ.
    CPUとメモリの間に配置され、CPUの命令によりメモリからデータをフェッチする時、そのデータとそのアドレス近辺のデータを保持する役割を持つ.
    その後の取り出し命令の際に、CPUは初めにキャッシュの中身を確認し、該当のデータがあれば、そのデータを使用する,
  • L1 cache & L2 cache
    キャッシュには、CPUとの距離に応じて二つのキャッシュが作られている.
  • L1 キャッシュ
    マイクロプロセッサ内に存在する内部キャッシュで、キャッシュの中で最もCPUに近い.
    サイズは1KB~16KB.
  • L2 キャッシュ
    マイクロプロセッサ外に存在する外部キャッシュ.
    サイズは64KB~1MB.
  • キャッシュライン メモリからキャッシュにデータを転送する単位のこと.
    多すぎると、使わないデータが増え、メモリを圧迫してしまう.
    少なすぎると、一回の転送効率が悪い、かつ転送回数も増えてしまう.
    大抵の場合、32byte~256byteが一般的.
  • ライトスルー方式とライトバック方式
    メモリからキャッシュに移したデータに対して、書き込みを行う場合、以下の二つの書き込み方法が存在する.
    • ライトスルー方式 キャッシュとメモリのどちらにもデータを書き込む方式.
      キャッシュとメモリで一貫性が保てる.
      しかし、書き込みの際には毎回メモリにアクセスすることになり、速度は遅く、非効率.
    • ライトバック方式
      キャッシュだけにデータを書き込み、そのデータがメモリに送られるときにまとめて書き込む方式.
      書き込みの際もキャッシュだけに専念すればいいので、処理が高速になる.〜 しかし、データの一貫性が保てない.
      そのため、キャッシュミスが起こった時はキャッシュからメモリにデータを書き込む必要があり、ここのプロセッサがキャッシュを持つマイクロプロセッサには不向き.
  • ヒット率
    プロセッサがキャッシュにデータを取得しにアクセスした際、求めていたデータがキャッシュに存在した割合のこと.
  • ミス率
    ヒット率とは反対に、キャッシュにプロセッサが求めていたデータが存在しなかった時の割合のこと.
    このキャッシュミスにより、発生したCPU負荷のことをミスペナルティと呼ぶ.
    OSはコンパクションなどの概念を使って、ミスペナルティを少なくしている.
    http://4.bp.blogspot.com/-Xd1rnPxf6jk/U1yAgECRNzI/AAAAAAAAAKI/9hA9_dhosYM/s1600/Memory+Heirarchy.jpg
    (http://abhaycopi.blogspot.com/2014/04/memory-hierarchy.html)

https://elite-lane.com/wp-content/uploads/2019/04/Screen-Shot-2019-04-18-at-14.25.06.png
(https://elite-lane.com/cache-memory/)

How to write a program thinking of this principle ~ [#tced0ff5]

この授業を履修している人はプログラムを書く人が多いと思うので、実装の際にどのようなことに気をつければいいのか、行列演算の例をとって具体的に考えていきます.

  • NxNの行列を考える
    • (i)nのサイズが小さい時
      以下の書き方でもOK!
         for(i=0; i<n; i++)
             for(j=0;j<n; j++)
                 for(k=0;k<n; k++)
                       C[i][j] = A[i][j]*B[j][k];

    • (i)nのサイズが大きい時
      以下の書き方だと、一つの列と行を掛ける演算をする際に、列と行の要素が全てキャッシュに乗らない.
      つまり、局所性がなくなる.
         for(i=0; i<n; i++)
             for(j=0; j<n; j++)
                 for(k=0; k<n; k++)
                       C[i][j] = A[i][k]*B[k][j];~
      そのため、キャッシュのサイズを意識して、ある一定のサイズのブロックごとに行列の演算を行う.
         block = 16;
         for(ia=0; ia<n; ia+=block)
             for(ib=0; ib<n; ib+=block)
                 for(ic=0; ic<n; ic+=block)
                     for(i=ia; i<ia+block; i++)
                         for(j=ib; j<ib+block; j++)
                             for(k=ic; k<ic+block; j++)
                                 C[i][j] = A[i][k]*B[k][j];

  • (ii)局所性を意識せずに行列のコードを書くと
    二次元配列BにROW要素ごとにアクセスしている.
       for(i=0;i<raws<++i)
           for(j=0;j<cols;++j)
               for(k=0;k<len;++k)
                     C[i][j] = A[i][j]*B[j][k];~
  • (ii)局所性を意識して行列のコードを書くと
    全ての配列に順序の
      for(i=0;i<raws; ++i)
           for(j=0; j<lens; ++j)
               for(k=0; k<cols; ++k)
                     C[i][j] = A[i][k]*B[k][j];~

Reference

siiba(Ryusei Shiiba)


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-06-27 (木) 10:51:26 (813d)