Tomasulo 法

2025年10月23日

Tomasulo 法

英語表記: Tomasulo’s Algorithm

概要

Tomasulo法は、高性能なCPUが命令を効率よく実行するために使用する動的なスケジューリング手法です。これは、CPUの仕組み（命令セット, パイプライン）における「スーパースカラと OoO」の文脈で、特に「OoO 実行」（アウト・オブ・オーダー実行、順序不同実行）を可能にするための画期的なアルゴリズムとして知られています。

この手法の主な目的は、命令間のデータ依存性（ハザード）によってパイプラインが停止してしまうのを防ぎ、複数の命令を並列に、かつ、実行可能な順序で処理することです。これにより、スーパースカラプロセッサの性能を最大限に引き出し、CPUの利用効率を劇的に向上させることができるのです。

詳細解説

背景：OoO実行の必要性と課題

現代の高性能CPUは、1クロックサイクルで複数の命令を発行・実行できる「スーパースカラ」アーキテクチャを採用しています。さらに、処理効率を高めるために、命令がプログラム上で書かれた順番（イン・オーダー）ではなく、準備ができたものから先に実行する「OoO 実行」を行います。これが、私たちが今見ている「CPUの仕組み（命令セット, パイプライン） → スーパースカラと OoO → OoO 実行」という階層の中で、Tomasulo法が最も重要視される理由です。

しかし、OoO実行には大きな課題があります。それは「データハザード」です。特に、レジスタを介したデータ依存性（ある命令が書き込むレジスタを、別の命令が読み込んだり、あるいは書き込んだりする）があると、誤った結果を生む可能性があります。Tomasulo法は、このデータハザードを動的に解決するために、1960年代後半にIBMによって開発されました。これは本当に革新的なアイデアだったと言えますね。

主要な構成要素と動作原理

Tomasulo法がデータ依存性を克服するために利用する主要なコンポーネントは、主に以下の3つです。

1. リザベーション・ステーション（Reservation Stations: RS）

リザベーション・ステーション（RS）は、機能ユニット（加算器、乗算器など）の前に設けられた待機場所です。命令が発行されると、オペランド（処理対象のデータ）が揃うまで、このRSで待機します。命令そのものと、必要なオペランドの値、またはその値がどこから来るかを示す情報（タグ）を保持します。これにより、命令はレジスタファイルではなく、RS間で直接データをやり取りできるようになります。

2. 共通データバス（Common Data Bus: CDB）

CDBは、機能ユニットが計算を終えた結果を、CPU全体にブロードキャストするための高速バスです。結果がCDBに書き込まれると、それを必要としているすべてのアクティブなリザベーション・ステーションやレジスタファイルが同時にその結果を受け取ります。これは、結果ができた瞬間に必要な場所へ即座に供給される仕組みであり、遅延を最小限に抑える上で非常に重要です。

3. レジスタ・リネーミング（Register Renaming）

Tomasulo法の最も巧妙な部分の一つがレジスタ・リネーミングです。これは、プログラム上のレジスタ名（論理レジスタ）を、CPU内部のより多くの物理レジスタに動的に割り当てる技術です。

なぜリネーミングが必要なのでしょうか？データハザードには、真の依存性（RAW: Read After Write）の他に、名前の依存性（WAR: Write After Read, WAW: Write After Write）があります。WARやWAWは、実際にはデータの流れとは関係なく、たまたま同じレジスタ名を使ったために発生する見かけ上の依存性です。

レジスタ・リネーミングを行うことで、これらのWAR/WAWハザードを完全に解消できます。それぞれの命令に独自の「一時的な格納場所」を与えるイメージです。これにより、命令は互いに独立して実行できるようになり、OoO実行の自由度が大幅に向上します。これは、まさにTomasulo法の心臓部と言っても過言ではありません。

動作の流れ

発行（Issue）: 命令がデコードされ、空いているリザベーション・ステーション（RS）に割り当てられます。このとき、オペランドがレジスタファイルにある場合は値がRSにコピーされます。もしオペランドがまだ計算中の場合は、その値が将来CDBで利用可能になることを示す「タグ」がRSに記録されます。
実行（Execute）: RS内の命令は、オペランドがすべて揃った時点で実行を開始します。オペランドが揃っていれば、たとえプログラム上の先行命令がまだ実行中でも、この命令は先に進むことができます（OoO実行）。
結果の書き込み（Write Result）: 実行が完了すると、結果はCDBを通じてブロードキャストされます。この結果は、それを待っていた他のRS、そしてレジスタファイルに同時に書き込まれます。

この動的なプロセスにより、データ依存性による待ち時間を最小限に抑え、CPUのパイプラインが常にフル稼働する状態を目指すのです。これは、CPUの仕組み全体を理解する上で、非常に洗練された概念だと思います。

具体例・活用シーン

Tomasulo法は、現代の高性能プロセッサ（Intel CoreシリーズやAMD Ryzenなど）のOoO実行エンジンの中核技術として広く使われています。私たちが日常的に体験する高速な処理性能は、このアルゴリズムに大きく支えられていると言えます。

厨房の比喩（アナロジー）

Tomasulo法とOoO実行の仕組みを理解するために、高級レストランの厨房を想像してみてください。

機能ユニット（シェフ）: 厨房には、グリル担当、揚げ物担当、デザート担当など、専門のシェフ（機能ユニット）が複数います（スーパースカラ）。
注文伝票（命令）: ウェイターがテーブルから注文（命令）を受け付けます。
リザベーション・ステーション（食材準備スペース）: 各シェフの作業台の横には、そのシェフが担当する注文の食材や調味料が置かれるスペース（RS）があります。
レジスタ・リネーミング（一時的な皿）: 複数の注文で「鶏肉」という共通の食材（レジスタ名）が使われていたとしても、それぞれの注文には専用の「一時的な皿」が割り当てられます。これにより、鶏肉を調理する順番が前後しても、注文Aと注文Bの調理が混ざってしまうことはありません（WAR/WAWハザードの回避）。
共通データバス（結果ブロードキャスト）: スープ担当のシェフが「出汁」を作り終えたとします。彼はその出汁を、ウェイターを介さず、厨房全体に響くベル（CDB）で「出汁ができたよ！」と知らせます。この出汁を必要としていた他のシェフ（RSで待機していた命令）は、すぐにその出汁を受け取り、調理を再開します。

この厨房では、注文の順番通りに料理を作る必要はありません。食材（オペランド）が揃い次第、空いているシェフがどんどん調理を始めます。これが、プログラムの順序（注文の順番）とは異なる順序で実行が進む「OoO 実行」のイメージです。Tomasulo法は、この厨房が混乱せず、最も効率的に動き続けるための管理システムなのです。

資格試験向けチェックポイント

Tomasulo法は、応用情報技術者試験や高度試験（特にエンベデッドシステムスペシャリストやネットワークスペシャリストの午前II）で頻出する、CPUの高性能化技術の中でも特に重要なトピックです。

押さえておくべき重要用語と概念:

OoO実行（順序不同実行）: Tomasulo法が実現したい目標です。命令の並列性を高めます。
リザベーション・ステーション（RS）: 命令とオペランドを保持し、実行可能になるまで待機させるバッファ機能。
レジスタ・リネーミング: 見かけ上の依存性（WAR/WAW）を解消し、真の依存性（RAW）のみを残すための技術。これにより、OoO実行の効率が飛躍的に向上します。
データハザード: RAW（真の依存）、WAR、WAW（名前の依存）の種類と、Tomasulo法がそれらをどのように解決するかを説明できるようにしてください。特にWAR/WAWの解決が試験で問われやすいポイントです。

この知識は、「CPUの仕組み（命令セット, パイプライン） → スーパースカラと OoO → OoO 実行」という流れの中で、いかに現代のCPUが賢く動作しているかを理解するための鍵となります。