キャッシュ・プリフェッチ

キャッシュ・プリフェッチは、中央処理装置（CPU）が、命令やデータを実際に必要になる前に、低速メモリ内の主記憶装置から高速ローカルメモリにフェッチすることで実行性能を向上させる技術です。[ 1 ] [ 2 ]最近のCPUのほとんどは、高速なローカルキャッシュメモリを備えており、プリフェッチされたデータは必要になるまで保持されます。プリフェッチ操作のソースは通常、メインメモリです。その設計上、キャッシュメモリへのアクセスは通常、メインメモリへのアクセスよりもはるかに高速です。プリフェッチは、非ブロッキング・キャッシュ制御命令を使用して実行できます。プリフェッチは、 データ局所性の原則に基づいています

データキャッシュプリフェッチと命令キャッシュプリフェッチ

キャッシュ プリフェッチは、データまたは命令をキャッシュにフェッチできます。

  • データ・プリフェッチは、必要になる前にデータを取得します。データ・アクセス・パターンは命令パターンよりも規則性が低いため、正確なデータ・プリフェッチは一般的に命令プリフェッチよりも困難です。
  • 命令プリフェッチは、命令を実行する必要がある前に命令をフェッチします。何らかの形の命令プリフェッチを採用した最初の主流マイクロプロセッサは、Intel 8086（6バイト）とMotorola 68000（4バイト）でした。近年では、すべての高性能プロセッサがプリフェッチ技術を採用しています。

ハードウェアとソフトウェアのキャッシュプリフェッチ

キャッシュプリフェッチはハードウェアまたはソフトウェアによって実現できます。[ 3 ]

  • ハードウェアベースのプリフェッチは、通常、プロセッサ内に専用のハードウェアメカニズムを備え、実行中のプログラムによって要求されている命令またはデータのストリームを監視し、このストリームに基づいてプログラムに必要な次のいくつかの要素を認識し、プロセッサのキャッシュにプリフェッチすることで実現されます。[ 4 ]
  • ソフトウェアベースのプリフェッチは、通常、コンパイラがコードを分析し、コンパイル中にプログラムに追加の「プリフェッチ」命令を挿入することによって実現されます。[ 5 ]

ハードウェアプリフェッチの方法

ストリームバッファ

  • ストリームバッファは、アラン・ジェイ・スミスによって提案された「1ブロック先読み（OBL）方式」の概念に基づいて開発されました。[ 1 ]
  • ストリームバッファは、現在最も一般的に使用されているハードウェアベースのプリフェッチ手法の1つです。この手法は、もともと1990年にノーマン・ジョッピによって提案され、 [ 6 ]、それ以来、この手法の多くのバリエーションが開発されてきました。[ 7 ] [ 8 ] [ 9 ]基本的な考え方は、キャッシュミスアドレス（および後続のk個のアドレス）が深さkの別のバッファにフェッチされるというものです。このバッファはストリームバッファと呼ばれ、キャッシュとは別のものです。プロセッサは、プリフェッチされたブロックに関連付けられたアドレスが、プロセッサ上で実行されているプログラムによって生成された要求されたアドレスと一致する場合、ストリームバッファからデータ/命令を消費します。次の図はこの設定を示しています。
当初提案された典型的なストリームバッファの設定
1990年にノーマン・ジョッピが最初に提案した典型的なストリームバッファの設定[ 6 ]
  • プリフェッチ機構がメモリブロック（例えばA ）のミスを検出すると、ミスしたブロック以降の連続ブロックのプリフェッチを開始するためのストリームを割り当てます。ストリームバッファが 4 つのブロックを保持できる場合、プロセッサはA +1、A +2、A +3、A +4 をプリフェッチし、割り当てられたストリームバッファに保持します。プロセッサが次にA +1 を消費すると、それはストリームバッファからプロセッサのキャッシュへと「上」に移動されます。ストリームバッファの最初のエントリはA +2 になり、以下同様に続きます。連続するブロックをプリフェッチするこのパターンは、シーケンシャルプリフェッチと呼ばれます。これは主に、連続する位置をプリフェッチする場合に使用されます。たとえば、命令をプリフェッチする場合に使用されます。
  • このメカニズムは、複数のストリームバッファを追加することで拡張することができ、各ストリームバッファは個別のプリフェッチストリームを維持します。[ 10 ]新しいミスごとに新しいストリームバッファが割り当てられ、上記と同様に動作します。
  • ストリームバッファの理想的な深さは、様々なベンチマーク[ 6 ]に対する実験の対象であり、関連するマイクロアーキテクチャの残りの部分に依存します。[ 11 ]

ストライド・プリフェッチ

このタイプのプリフェッチは、メモリアクセスのアドレス間の差分を監視し、その中のパターンを探します

規則的な歩幅

このパターンでは、sアドレス離れたブロックに対して連続したメモリアクセスが行われます。[ 3 ] [ 12 ]この場合、プリフェッチャーはsを計算し、それを用いてプリフェッチするメモリアドレスを計算します。例えば、s = 4の場合、プリフェッチされるアドレスはA +4になります。

不規則な空間ストライド

この場合、連続するメモリアクセスのアドレス間の差分は変動しますが、それでもパターンに従います。一部のプリフェッチャー設計[ 9 ] [ 13 ] [ 14 ]では、この特性を利用して将来のアクセスを予測し、プリフェッチを行います

不規則な時間的プリフェッチ

このクラスのプリフェッチャーは、時間の経過とともに繰り返されるメモリアクセスストリームを探します。[ 15 ] [ 16 ]たとえば、メモリアクセスストリームN、A、B、C、E、G、H、A、B、C、I、J、K、A、B、C、L、M、N、O、A、B、C、…では、ストリームA、B、Cが時間の経過とともに繰り返されます。他の設計バリエーションでは、より効率的な実装を提供しようと試みられてきました。[ 17 ] [ 18 ]

協調的プリフェッチ

コンピュータアプリケーションはさまざまなアクセスパターンを生成します。これらのアプリケーションを実行するために使用されるプロセッサとメモリサブシステムのアーキテクチャは、生成されるメモリアクセスパターンをさらに明確にします。したがって、プリフェッチ方式の有効性と効率は、多くの場合、アプリケーションとそれを実行するために使用されるアーキテクチャに依存します。[ 19 ]最近の研究[ 20 ] [ 21 ]は、プリフェッチの範囲と精度を向上させるために、複数のプリフェッチ方式を相乗的に使用するための協調メカニズムの構築に焦点を当てています

ソフトウェアプリフェッチの方法

コンパイラによるプリフェッチ

コンパイラによるプリフェッチは、反復回数の多いループ内で広く使用されています。この手法では、コンパイラは将来のキャッシュミスを予測し、ミスペナルティと命令の実行時間 に基づいてプリフェッチ命令を挿入します

これらのプリフェッチは非ブロッキングメモリ操作です。つまり、これらのメモリアクセスは実際のメモリアクセスを妨げません。プロセッサの状態を変更したり、ページフォールトを引き起こしたりすることはありません。

ソフトウェアプリフェッチの主な利点の1つは、強制的なキャッシュミスの数を減らすことです。[ 3 ]

次の例は、キャッシュ パフォーマンスを向上させるためにコードにプリフェッチ命令を追加する方法を示しています。

次の反復では、 

for ( size_t i = 0 ; i < 1024 ; ++ i ) { array1 [ i ] *= 2 ; }

配列のi番目の要素array1にアクセスします。システムは、以下に示すようにプリフェッチ命令を挿入することで、将来の反復処理でアクセスされる可能性のある要素をプリフェッチできます。 

for ( size_t i = 0 ; i < 1024 ; ++ i ) {プリフェッチ( array1 [ i + k ] ); array1 [ i ] *= 2 ; }

ここで、プリフェッチストライドは、kキャッシュミスペナルティとforループの1回の反復実行にかかる時間という2つの要素に依存します。例えば、ループの1回の反復実行に7サイクルかかり、キャッシュミスペナルティが49サイクルの場合、k = 49/7 = 7となり、システムは7つの要素をプリフェッチする必要があることを意味します。最初の反復では、kiは0なので、システムは7番目の要素をプリフェッチします。この配置では、最初の7回のアクセス（k i= 0 → 6）は依然としてミスになります（kの各要素がarray1それぞれ独立したキャッシュラインにあるという単純化された仮定の下で）。

ハードウェアとソフトウェアのプリフェッチの比較

  • ソフトウェアプリフェッチはプログラマーやコンパイラーの介入を必要とするが、ハードウェアプリフェッチは特別なハードウェアメカニズムを必要とする。[ 3 ]
  • ソフトウェアプリフェッチは、プログラマがプリフェッチ命令を手動でコーディングする必要があるため、定期的に配列にアクセスするループでのみうまく機能します。一方、ハードウェアプリフェッチャーは、実行時のプログラムの動作に基づいて動的に動作します。[ 3 ]
  • ハードウェアプリフェッチは、ソフトウェアプリフェッチに比べてCPUオーバーヘッドが少ない。[ 22 ]しかし、ソフトウェアプリフェッチはハードウェアプリフェッチの制約を緩和することができ、パフォーマンスの向上につながる。[ 23 ]

キャッシュプリフェッチのメトリクス

キャッシュプリフェッチは主に3つの指標で判断できます。[ 3 ]

カバレッジ

カバレッジとは、プリフェッチによって排除されるミスの総数の割合です

カバレッジ = ⁠プリフェッチによりキャッシュミスが解消される/キャッシュミス合計⁠、

ここで

キャッシュミスの合計 = (プリフェッチによって排除されたキャッシュミス) + (プリフェッチによって排除されなかったキャッシュミス)。

正確さ

精度は、有効であったプリフェッチの合計数の割合、つまり、プログラムによって実際に参照されたプリフェッチされたメモリ アドレスの数と、実行されたプリフェッチの合計数の比率です。

プリフェッチ精度 = ⁠プリフェッチによりキャッシュミスを解消/（無駄なキャッシュプリフェッチ）+（プリフェッチによって排除されたキャッシュミス）⁠

完璧な精度はミスがないことを意味するように思われがちですが、実際はそうではありません。プリフェッチされたブロックが直接キャッシュに配置されると、プリフェッチ自体が新たなミスを引き起こす可能性があります。これらのミスは、プリフェッチを行わない場合に観測されるミスの総数に比べるとごくわずかかもしれませんが、ミスの数はゼロではありません。

適時性

適時性の定性的な定義は、プリフェッチから実際の参照までの経過時間です。例えば、各反復の実行に3サイクルかかり、プリフェッチ操作に12サイクルかかるforループでプリフェッチを有効にするには、システムは適時性を維持するために、プリフェッチを使用する12/3 = 4反復前に開始する必要があります

参照

参考文献

  1. ^ a b Smith, Alan Jay (1982-09-01). 「キャッシュメモリ」. ACM Comput. Surv . 14 (3): 473– 530. doi : 10.1145 /356887.356892 . ISSN  0360-0300 . S2CID  6023466
  2. ^ Li, Chunlin; Song, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min; Luo, Youlong (2020-09-01). 「エッジコンピューティング環境における適応型優先度ベースキャッシュ置換と予測ベースキャッシュプリフェッチ」 . Journal of Network and Computer Applications . 165 102715. doi : 10.1016/j.jnca.2020.102715 . S2CID 219506427 . 
  3. ^ a b c d e fソリヒン、ヤン (2016).並列マルチコア アーキテクチャの基礎。フロリダ州ボカラトン：CRC Press、Taylor & Francis Group。 p. 163.ISBN​ 978-1482211184。
  4. ^ Baer,​​ Jean-Loup; Chen, Tien-Fu (1991-01-01).データアクセスペナルティを軽減するための効果的なオンチッププリロード方式. 1991 ACM/IEEE スーパーコンピューティング会議. 米国ニューメキシコ州アルバカーキ: Association for Computing Machinery. pp.  176– 186. CiteSeerX 10.1.1.642.703 . doi : 10.1145/125826.125932 . ISBN  978-0897914598。
  5. ^ Kennedy, Porterfield, Allan (1989-01-01).スーパーコンピュータアプリケーションにおけるキャッシュパフォーマンス向上のためのソフトウェア手法（論文）. ライス大学. hdl : 1911/19069 .{{cite thesis}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  6. ^ a b c Jouppi, Norman P. (1990). 「小型フルアソシアティブキャッシュとプリフェッチバッファの追加によるダイレクトマップキャッシュ性能の向上」.第17回国際コンピュータアーキテクチャシンポジウム (ISCA 1990) 議事録. 第17回国際コンピュータアーキテクチャシンポジウム (ISCA 1990) 議事録. ニューヨーク州ニューヨーク: Association for Computing Machinery Press. pp.  364– 373. CiteSeerX 10.1.1.37.6114 . doi : 10.1145/325164.325162 . ISBN  0-89791-366-3。
  7. ^ Chen, Tien-Fu; Baer,​​ Jean-Loup (1995-05-01). 「高性能プロセッサのための効果的なハードウェアベースのデータプリフェッチ」. IEEE Transactions on Computers . 44 (5): 609– 623. Bibcode : 1995ITCmp..44..609T . doi : 10.1109/12.381947 . ISSN 0018-9340 . S2CID 1450745  
  8. ^ Palacharla, S.; Kessler, RE (1994-01-01).二次キャッシュ代替としてのストリームバッファの評価. 第21回国際コンピュータアーキテクチャシンポジウム. シカゴ、イリノイ州、米国: IEEEコンピュータ協会出版局. pp.  24– 33. CiteSeerX 10.1.1.92.3031 . doi : 10.1109/ISCA.1994.288164 . ISBN  978-0818655104。
  9. ^ a b Grannaes, Marius; Jahre, Magnus; Natvig , Lasse (2011). 「デルタ相関予測テーブルを用いたストレージ効率の高いハードウェアプリフェッチ」Journal of Instruction-Level Parallelism (13): 1– 16. CiteSeerX 10.1.1.229.3483 
  10. ^石井康雄、稲葉メアリー、平木啓 (2009-06-08). 「データキャッシュ・プリフェッチのためのアクセスマップ・パターンマッチング」 .第23回国際スーパーコンピューティング会議論文集. ICS 2009. ニューヨーク、米国: Association for Computing Machinery. pp.  499– 500. doi : 10.1145/1542275.1542349 . ISBN 978-1-60558-498-0. S2CID  37841036
  11. ^ Srinath, Santhosh; Mutlu, Onur; Kim, Hyesoon ; Patt, Yale N. (2007年2月).フィードバック・ディレクテッド・プリフェッチ：ハードウェア・プリフェッチャーの性能と帯域幅効率の向上. 2007 IEEE 第13回高性能コンピュータアーキテクチャ国際シンポジウム. pp.  63– 74. doi : 10.1109/HPCA.2007.346185 . ISBN 978-1-4244-0804-7. S2CID  6909725 .
  12. ^ Kondguli, Sushant; Huang, Michael (2017年11月). T2: 高精度かつエネルギー効率の高いストライドプリフェッチャー. 2017 IEEE International Conference on Computer Design (ICCD). pp.  373– 376. doi : 10.1109/ICCD.2017.64 . ISBN 978-1-5386-2254-4. S2CID  11055312 .
  13. ^ Shevgoor, Manjunath; Koladiya, Sahil; Balasubramonian, Rajeev; Wilkerson, Chris; Pugsley, Seth H.; Chishti, Zeshan (2015年12月).複雑なアドレスパターンの効率的なプリフェッチ. 2015年第48回IEEE/ACM国際マイクロアーキテクチャシンポジウム (MICRO). pp.  141– 152. doi : 10.1145/2830772.2830793 . ISBN 9781450340342. S2CID  15294463 .
  14. ^ Kim, Jinchun; Pugsley, Seth H.; Gratz, Paul V.; Reddy, AL Narasimha; Wilkerson, Chris; Chishti, Zeshan (2016年10月).パス信頼度に基づく先読みプリフェッチ. 2016年第49回IEEE/ACM国際マイクロアーキテクチャシンポジウム (MICRO). pp.  1– 12. doi : 10.1109/MICRO.2016.7783763 . ISBN 978-1-5090-3508-3. S2CID  1097472 .
  15. ^ Joseph, Doug; Grunwald, Dirk (1997-05-01). 「マルコフ予測器を用いたプリフェッチ」.第24回国際コンピュータアーキテクチャシンポジウム議事録. ISCA 1997. ISCA 1997. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp.  252– 263. doi : 10.1145/264107.264207 . ISBN 978-0-89791-901-2. S2CID  434419 .
  16. ^ Collins, J.; Sair, S.; Calder, B.; Tullsen, DM (2002年11月).ポインタキャッシュ支援プリフェッチ. 第35回IEEE/ACM国際マイクロアーキテクチャシンポジウム, 2002. (MICRO-35). Proceedings. pp.  62– 73. doi : 10.1109/MICRO.2002.1176239 . ISBN 0-7695-1859-1 . S2CID  5608519
  17. ^ Jain, Akanksha; Lin, Calvin (2013-12-07). 「相関プリフェッチの改善のための不規則メモリアクセスの線形化」 .第46回IEEE/ACM国際マイクロアーキテクチャシンポジウム議事録. MICRO-46. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  247– 259. doi : 10.1145/2540708.2540730 . ISBN 978-1-4503-2638-4. S2CID  196831 .
  18. ^ 「テンポラル・プリフェッチャーの実用化：MISBプリフェッチャー - 研究記事 - Arm Research - Armコミュニティ」 . community.arm.com . 2019年6月24日. 2022年3月16日閲覧
  19. ^ Kim, Jinchun; Teran, Elvira; Gratz, Paul V.; Jiménez, Daniel A.; Pugsley, Seth H.; Wilkerson, Chris (2017-05-12). 「プログラムカウンタの削除：プロセッサキャッシュ階層におけるプログラム動作の再構築」 . ACM SIGPLAN Notices . 52 (4): 737– 749. doi : 10.1145/3093336.3037701 . ISSN 0362-1340 . 
  20. ^ Kondguli, Sushant; Huang, Michael (2018-06-02). 「分業：プリフェッチへのより効果的なアプローチ」 .第45回国際コンピュータアーキテクチャシンポジウム論文集. ISCA '18. ロサンゼルス、カリフォルニア州: IEEE Press. pp.  83– 95. doi : 10.1109/ISCA.2018.00018 . ISBN 978-1-5386-5984-7. S2CID  50777324 .
  21. ^ Pakalapati, Samuel; Panda, Biswabandan (2020年5月).命令ポインタのブーケ：命令ポインタ分類器ベースの空間ハードウェアプリフェッチ. 2020 ACM/IEEE 第47回国際コンピュータアーキテクチャシンポジウム (ISCA). pp.  118– 131. doi : 10.1109/ISCA45697.2020.00021 . ISBN 978-1-7281-4661-4. S2CID  218683672 .
  22. ^ Callahan, David; Ken Kennedy; Porterfield, Allan (1991-01-01).ソフトウェア・プリフェッチ. プログラミング言語およびオペレーティングシステムのアーキテクチャサポートに関する第4回国際会議. 米国カリフォルニア州サンタクララ：計算機協会. pp.  40– 52. doi : 10.1145/106972.106979 . ISBN 978-0897913805。
  23. ^ Lee, Jaekyu、Kim, Hyesoon、Vuduc, Richard (2012)、「プリフェッチが機能する場合、機能しない場合、そしてその理由」(PDF)、ACM Trans. Archit. Code Optim.、9 : 1– 29、doi : 10.1145/2133382.2133384{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)
「 https://en.wikipedia.org/w/index.php?title=Cache_prefetching&oldid=1323732734」から取得