前回の「各種メモリ／ストレージのアクセス時間，所要クロックサイクル，転送速度，容量の目安」は，思わぬ反響を呼んだので驚いております。
今回の記事は，その記事の活用編にあたる記事です。コンパイラのコード最適化を設計・実装する時に重要な観点を，つらつらと書いてみます。
原則: 高速なメモリ・ストレージは容量が小さい
前回の記事の結論を再掲します。
| メモリ/ストレージの種類 | アクセス時間 | アクセス開始までの所要クロックサイクル | 最大転送速度 | 容量 |
|---|---|---|---|---|
| レジスタ | 0.33〜1ナノ秒 | 1 | 96〜576Gbps換算 | 60〜256バイト換算 |
| L1キャッシュ | 1.33〜4ナノ秒 | 4程度 | 96〜576Gbps換算 | 32〜64KB |
| L2キャッシュ | 4〜15ナノ秒 | 12-15程度 | 96〜576Gbps程度？ | 512KB〜1MB |
| L3キャッシュ | 16〜50ナノ秒 | 〜50程度 | 96〜576Gbps程度？ | 16〜256MB |
| メインメモリ(DDR4) | 100ナノ秒 | 100〜300程度 | 96〜272Gbps程度 | 4GB〜2TB |
| NVMe SSD | 50マイクロ秒程度 | 50,000〜150,000程度 | 0.48〜33.6Gbps程度 (60〜4200MB/s程度) | 〜2TB |
| SATA3.0 SSD | 100〜200マイクロ秒程度 | 100,000〜600,000程度 | 0.14〜4Gbps程度 (17〜500MB/s程度) | 〜4TB |
| SATA3.0 HDD (3.5inch) | 10〜20数ミリ秒程度 | 10,000,000〜60,000,000程度 | 0.04〜0.8Gbps程度 (0.5〜100MB/s程度) | 〜16TB |
上に行くほど高速なメモリ・ストレージですが，上に行くほど容量も小さくなっていることがわかります。
なぜ高速なメモリ・ストレージの容量は小さいのか，この理由については，ぜひ考察してみてください。
解決策: 広い意味での「仮想記憶」
このような問題を解決するには，仮想記憶の考え方が重要となります。すなわち，実質的に広大な単一のメモリであるかのように見せかけるが，実際には高速で容量の小さいメモリを一時作業領域に効率よく使って，低速で大容量のメモリと組み合わせるということになります。
キャッシュメモリや，コンパイラで用いられるコード最適化技法の1つであるレジスタ割当の最適化も，広い意味での仮想記憶だと捉えることができます。
原則: CPUに比べて，メモリやストレージ，I/Oは遅い
前回の記事の結論をもう一度見てみましょう。
| メモリ/ストレージの種類 | アクセス時間 | アクセス開始までの所要クロックサイクル | 最大転送速度 | 容量 |
|---|---|---|---|---|
| レジスタ | 0.33〜1ナノ秒 | 1 | 96〜576Gbps換算 | 60〜256バイト換算 |
| L1キャッシュ | 1.33〜4ナノ秒 | 4程度 | 96〜576Gbps換算 | 32〜64KB |
| L2キャッシュ | 4〜15ナノ秒 | 12-15程度 | 96〜576Gbps程度？ | 512KB〜1MB |
| L3キャッシュ | 16〜50ナノ秒 | 〜50程度 | 96〜576Gbps程度？ | 16〜256MB |
| メインメモリ(DDR4) | 100ナノ秒 | 100〜300程度 | 96〜272Gbps程度 | 4GB〜2TB |
| NVMe SSD | 50マイクロ秒程度 | 50,000〜150,000程度 | 0.48〜33.6Gbps程度 (60〜4200MB/s程度) | 〜2TB |
| SATA3.0 SSD | 100〜200マイクロ秒程度 | 100,000〜600,000程度 | 0.14〜4Gbps程度 (17〜500MB/s程度) | 〜4TB |
| SATA3.0 HDD (3.5inch) | 10〜20数ミリ秒程度 | 10,000,000〜60,000,000程度 | 0.04〜0.8Gbps程度 (0.5〜100MB/s程度) | 〜16TB |
特に「アクセス開始までの所要クロックサイクル」に注目してください。レジスタへは1クロックでアクセスできるのに対し，メインメモリは100〜300程度のクロックサイクルを待たないとアクセスできません。最速のSSDであるNVMe SSDであっても50,000〜150,000程度のクロックサイクルの待ちが発生します。HDDに至っては10,000,000〜60,000,000程度のクロックサイクルもの間，ひたすら待つことになります。
下記論文によれば，このような「メモリストール」によって8〜65%もの実行時間を浪費しているとのことです。
解決策: 適切なタイミングでプリフェッチすることが大事
この問題を解決する方法は，データが必要になる前に読み込み指令を出しておくこと，すなわちプリフェッチすることが重要です。
メインメモリであれば，実際にループを回して計算を開始する100〜300クロック前にプリフェッチしてデータをキャッシュに載せておくことが重要になります。一旦L1キャッシュまで入れば，現代的なCPUは数々の予測機能を駆使してくれて，パイプラインがストールしないように前もってデータを読み込んでくれます。
プリフェッチをプログラムで明示的に指定するコード最適化技法を software-controlled prefetching といいます。先ほどの論文は，このような技法に関する研究論文です。
もちろん，高速なメモリは容量が小さいので，むやみやたらとプリフェッチしてしまうと，あふれてしまいます。
この辺りについて，気の利いた感じでコード最適化するというのは，まだまだ研究の余地が多々ある領域ではないかと思います。