> [!note] PDF 原本なし > SlideShare のボット対策(Client Challenge)により `fetch-slide-deck.sh` での PDF 取得が失敗した。`image.slidesharecdn.com` の CDN から個別スライド画像(638×478px、24枚)を直接取得して代替した。原本 PDF は `.raw/slides/cs-metatechniques-slideshare/` に存在しない。解像度はやや低いが文字・図の判読には十分だった。 ## 概要 金沢工業大学 情報工学科の中野淳氏が2015年4月30日に公開した講義・発表用スライド。情報科学の各分野(コンピュータアーキテクチャ・OS・分散システム・データベース・ネットワーク・ソフトウェア工学)を横断して繰り返し現れる18の基本技法を「メタテクニック」として列挙し、各技法に着想(なぜその技法が有効か)と代表例を1枚のスライドで簡潔に示す。個々の技法解説自体に新規性はなく、既存分野の知見をまとめて一望性を与える点が資料の主眼(p.2「取り上げた例は若干コンピューターアーキテクチャーに偏っている」との自己申告あり)。 ## 18のメタテクニック一覧 **Slide p.2: 18のメタテクニック一覧** ![[_attachments/cs-metatechniques-slideshare/slide02-18techniques-overview.jpg]] (18技法を2列9行で列挙したスライド。番号順に意味上の並びはなく、キャッシング・パイプライニング・並列化のようなアーキテクチャ寄りの技法とチェックポイント・トランザクションのような信頼性寄りの技法が混在する。Source: p.2) 1. **キャッシング(Caching)**: 空間的/時間的ローカリティの利用、80:20の法則。例: データ/命令キャッシュ、Pentium 4 のトレースキャッシュ、Web ブラウザキャッシュ、プロキシサーバー、メモ化、LZW 圧縮(高頻度データ列を辞書登録)(p.4)。 2. **ブロッキング vs. ノンブロッキング**: 待ち時間の有効活用。例: マルチタスク OS スケジューラー、マルチスレッド、非同期 I/O、MPI の非同期通信、プロセッサーの out-of-order 実行、MSHR(Miss Status Holding Register、キャッシュミス中でも別ラインの読み込みを許可)(p.5)。 3. **プロファイリング**: 実行時情報を使った最適化。例: gprof によるホットスポット特定、コードレイアウト最適化を行う Spike コンパイラ(p.6)。 4. **パイプライニング**: より高いスループットの追求。例: プロセッサーパイプライン(フェッチ・デコード・実行・メモリアクセス・ライトバック)(p.7)。 5. **投機的実行(予測)**: 自分の予測を信じて先に進める。例: 分岐予測、データのプリフェッチ、関数の返り値予測、メインスレッドのキャッシュミス遅延を隠蔽する投機的ヘルパースレッド(p.8)。 6. **条件の緩和(Relaxation)**: 制約を緩めたときの挙動を考える。例: マルチプロセッサーシステムの relaxed memory consistency(Sequential consistency はプログラマーに都合が良いがアーキテクチャ最適化を阻むため、Write Buffer 等で利便性を一部犠牲にする)、分散ハッシュテーブルの eventual consistency(p.9)。 7. **すぐやる vs. 先延ばし(Eager vs. Lazy)**: 例: 要求ページング/Copy on write(先延ばし)、フィボナッチヒープ等の償却計算量削減データ構造、Java の JIT コンパイラ、MPI プロトコルの Eager(小メッセージを即送信) vs. Rendezvous(大メッセージはネゴシエーション後に送信)(p.11)。 8. **フィルタリング**: より深く潜る必要があるかを素早く判断。例: キャッシュ階層(L1→L2→メインメモリ)、Bloom filter(p.12)。 9. **再利用(Reuse)**: 計算コストが高く頻繁に必要な結果を保存しておく。例: メモ化、Dynamic Instruction Reuse(Sodani and Sohi, ISCA 1997)(p.13)。 10. **並列化**: 2倍の計算資源で時間を半分に(現実には Amdahl の法則に留意)。例: SMP・マルチコア・クラスター・MapReduce(p.14)。 11. **結合 vs. 分離(Coupling vs. Decoupling)**: 分離により相互依存性を下げ部品の自由度を上げる。例: L1/L2 キャッシュの役割分離、インターフェースと実装の分離(オブジェクト指向)、ポリシーとメカニズムの分離(コンピューターネットワーク)、SDN の control plane と data plane、TCP/IP の階層構造、データベースのリレーション正規化(p.15)。 12. **多階層・クラスター化**: 例: キャッシュ階層、ファイルシステム、TCP/IP(p.16)。 13. **先読み・先取り(Lookahead, Prefetching)**: 例: メモリからのデータのプリフェッチ、キャッシュライン(p.18)。 14. **動的(適応)**: 実行中にも実行時情報を利用する点でプロファイリングと対をなす。例: Java の JIT コンパイラ、LLVM の動的最適化、Web サーバー群のロードバランサー(p.19)。 15. **複製(Replication)**: より良いローカリティと信頼性の獲得。例: ディスクミラーリング、分散データベースのレプリケーション、分散ハッシュテーブルのレプリカ、CDN(Akamai)、GFS(Google File System)(p.20)。 16. **仮想化(Virtualization)**: 物理的制限を超える、リダイレクト。例: 仮想メモリ・仮想デバイス・仮想マシン・仮想ファイルシステム・データベースのビュー・Windows ショートカット/UNIX シンボリックリンク(p.21)。 17. **チェックポイント・スナップショット**: 障害や人的ミスへの備え(ただし Output commit problem に留意)。例: データベース、Copy on write(p.22)。 18. **トランザクション**: 複数操作を不可分に扱う。例: データベース、トランザクショナルメモリー(ロックを駆使した手書き最適化は正確で速いが熟練を要し、トランザクショナルメモリーは多少のオーバーヘッドと引き換えに安全なプログラムを書きやすくする、というトレードオフ)(p.23)。 ## 視覚的に重要な図表 **Slide p.7: パイプライニング(洗濯の比喩)** ![[_attachments/cs-metatechniques-slideshare/slide07-pipelining-laundry.jpg]] (4人のタスクA〜Dが「洗濯→乾燥→折畳み」を行う例で、逐次的洗濯(1人分が全工程を終えてから次の人に移る)とパイプライン化された洗濯(各工程が異なる人のタスクを並行して処理する)を並べて図示し、後者がスループットで優ることを示す。出典は UC Berkeley CS152 の講義資料("http://www.cs.berkeley.edu/~pattrsn/252S01/")とスライド内に明記されている。Source: p.7) **Slide p.21: 仮想化(幻想と実体の層構造)** ![[_attachments/cs-metatechniques-slideshare/slide21-virtualization-illusion.jpg]] (「仮想的幻想」ブロックが「物理的実体」ブロックの上に重なり、目のアイコンから矢印で仮想的幻想へ向かう図。仮想化を「観測者(利用者)が物理的実体を直接見るのではなく、その上に構築された仮想的な幻想を通して見る」という一般化された構造として示す。Source: p.21) ## 口頭説明・補足 音源・動画・transcript は取得していない(スライド資料のみの取り込み)。 ## 概念・実体への接続 - [[中野淳]](発表者)、[[金沢工業大学]](所属)。 - 関連する既存 concept: [[メモリ階層とキャッシュ]](#1 キャッシング, #8 フィルタリング, #12 多階層・クラスター化と関連)、[[パイプライン処理]](#4 パイプライニング)、[[コンテナ仮想化]](#16 仮想化の一般化された上位概念)、[[分散トランザクション]](#18 トランザクション)、[[クォーラムベースレプリケーション]](#15 複製)。個々のスライドは各技法を1〜2文で紹介するに留まり、これら既存 concept の横断的知見に追記できるほどの深さはないため、`## 横断的知見` への追記は行わず、発見性のための一方向リンクにとどめる。 - 本資料の核となる主張(「分野横断で繰り返し現れる技法を少数のメタテクニックに集約できる」)は新設 concept [[メタテクニック（情報科学）]] に集約した。 ## 限界・不確実点 - PDF 原本が取得できず、CDN 提供の 638×478px JPEG 画像(SlideShare 側でリサイズ済み)を代替原本とした。原寸解像度ではない。 - 発表イベント(講義かセミナーか)は資料からは判別できない。金沢工業大学 情報工学科の授業スライドである可能性が高いが、確定情報ではないため `confidence: medium` とした。 - #2(ブロッキング vs. ノンブロッキング)における「MSHR」、#7 における「Eager/Rendezvous」等は説明が簡潔で、他分野の読者には背景知識が前提とされている箇所がある。