局所性 - yuuk1's Digital Garden

# 局所性 ## 定義局所性とは、アプリケーションがデータへ近い時間(時間局所性)または近い場所(空間局所性)で繰り返し触れる度合いであり、キャッシュや先読みが効く度合いを決める。2008 年の DARPA 研究は、これを 0 から 1 のスコアで測り、局所性を活かすアーキテクチャの設計をエクサスケールの研究方向に据えた。キャッシュ機構そのものは [[メモリ階層とキャッシュ]] が扱う。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 5 Exascale Application Characteristics]], [[@2008__DARPA__ExaScale Computing Study - Chapter 8 Exascale Challenges and Key Research Areas]]) ## 局所性と並列性の関係 - **並行性を上げると局所性が下がり、両立が 1000 倍化の難所になる。** - 根拠: 第 5 章は「並行性の増加は局所性の低下で相殺される」と述べ、局所性を悪くても効かせる機構、メモリ階層の制御を露出するハードと API、局所性を自動で作る変換、局所性と並列性を両立するアルゴリズムを研究方向に挙げる。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 5 Exascale Application Characteristics]]) - 根拠: 図 5.16(局所性の逆数と直列性の平面)と図 8.6 は、アプリの局所性・並列性の傾向とハード傾向の間に「DARPA-hard gap」を示す。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 5 Exascale Application Characteristics]], [[@2008__DARPA__ExaScale Computing Study - Chapter 8 Exascale Challenges and Key Research Areas]]) - 留保: 局所性の低い結合物理系アプリを、傾向に逆らって扱えるかは第 8 章でも開いたままである。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 8 Exascale Challenges and Key Research Areas]]) - **実アプリの局所性は HPL と乱数アクセスの間に散らばり、局所性が低いほどメモリ要求が増える。** - 根拠: HPL(時間局所性ほぼ最大)、STREAM(空間局所性ほぼ最大・再利用なし)、small RA(局所性ほぼなし)の間に実アプリが位置する。Overflow と RFCTH はさらにメモリ集約的で、目安として 1 GFlops あたり主記憶 0.5 GB 以上を要する。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 5 Exascale Application Characteristics]]) ## 局所性を意識したアーキテクチャ - **階層ごとのテーパと明示的な階層管理で、局所性のあるアクセスにだけエネルギーを配る設計が候補になる。** - 根拠: 積極設計ストローマンは階層ごとにテーパ(1 アクセスあたりに実行される flops 数)を定める。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 7 Strawmen - Where Evolution Is and Is Not Enough]]) - 根拠: 第 8 章は、明示的かつ先行的なメモリ階層管理(IBM Cell 型)、ハイブリッド管理、電力適応アーキテクチャ(固定電力上限下でピーク性能の割合を高める)を研究対象とする。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 8 Exascale Challenges and Key Research Areas]]) - 根拠: 適応的バランスノードは、各階層が全電力を使い切れるよう構成し、スロットリングで上限を守る。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 7 Strawmen - Where Evolution Is and Is Not Enough]]) ## 未解決の問い - 局所性を改善または許容するハード・API・コンパイラ・アルゴリズム技術と、その上限見積もりツール(依存関係・アクセス系列の解析、パターンのデータマイニング、oracle 並列度の推定)はどう作るか。 - 局所性の低い結合物理系アプリを、DARPA-hard gap に逆らって扱えるか。 - 局所性スコアと [[メモリ階層とキャッシュ]] の時間的・空間的局所性の記述は、現代の GPU や HBM の階層でどこまで対応するか。 ## 未編纂の観察 - 局所性の議論は [[データ移動エネルギー]] と対になる。局所性が低いほど遠い階層へ多く動かすことになり、第 7 章の電力配分(メモリ 31%・インターコネクト 27%)を押し上げる。ただし原文が局所性スコアと電力配分を直接結ぶ式は示していない。(Source: [[@2008__DARPA__ExaScale Computing Study - Chapter 5 Exascale Application Characteristics]], [[@2008__DARPA__ExaScale Computing Study - Chapter 7 Strawmen - Where Evolution Is and Is Not Enough]]) ## 関連 - [[メモリ階層とキャッシュ]]、[[メモリウォール]]、[[データ移動エネルギー]]、[[エクサスケール]] - ハブ: [[ExaScale Computing Study - Technology Challenges in Achieving Exascale Systems]] - MOC: [[HPC - MOC]] ## 出典 - [[@2008__DARPA__ExaScale Computing Study - Chapter 5 Exascale Application Characteristics]](局所性スコア、4 類型、DARPA-hard gap) - [[@2008__DARPA__ExaScale Computing Study - Chapter 7 Strawmen - Where Evolution Is and Is Not Enough]](テーパ、適応的バランスノード) - [[@2008__DARPA__ExaScale Computing Study - Chapter 8 Exascale Challenges and Key Research Areas]](局所性を意識したアーキテクチャ、電力適応)