スーパースカラースタックプロセッサ：ヘビとハリネズミの交差

この記事では、 LLCとスタックドマシンのフロントエンドを備えたスーパースカラープロセッサの（ソフトウェア）モデルを開発します。



実際、 1と2が続きました。

はじめに

なぜスタックマシンなのか？

Philip Kupman は次のように書いています 。「理論的には、スタックはそれ自体が重要です。これは、適切に構造化されたコードを実行するための主要かつ最も自然なメカニズムであるためです... さらに、それらは非常にシンプルであり、かなり控えめなハードウェア要件で優れたパフォーマンスを示します。



スタックマシンの利点には、コードのコンパクトさ、コードのコンパイルと解釈の容易さ、およびプロセッサ状態のコンパクトさが含まれます。



スタックアーキテクチャを備えたコンピューターの成功例は、 Burroughs B5000 （1961 ... 1986）およびHP3000 （1974 ... 2006）と呼ばれます。 ソビエトエルブルスについて忘れないでください。



それでは、なぜレジスタプロセッサによってスタックマシンが進歩の余地まで混み合っているのでしょうか？ その理由は、次のとおりだと思います。

1. スタックプロセッサには、固定ハードウェアスタックとメモリ内にあるスタックの2つの「極端な」実装があります。 これらの両極端には重大な欠陥があります：固定サイズスタックの場合、コンパイラーやオペレーティングシステムに問題があり、スタックがオーバーフローまたは空になった場合に何が起こるか、および対応する割り込みを処理する方法について考える義務があります。 割り込み処理がない場合、手動でプログラム可能になる運命にあるマイクロコントローラーを扱っています。 このような割り込みのハンドラーがある場合、ハードウェアスタックはメモリへの「ウィンドウ」の役割を迅速にアクセスして果たし、この「ウィンドウ」の移動はかなり高価な手順です。 その結果、クプマンの観点からすると、これはそのようなプロセッサの生態学的なニッチにすぎませんが、リアルタイムシステムなどで、そのようなプロセッサの使用を許可しない予測できないプログラムの動作があります。
2. 完全にメモリ内にあるスタックの場合、ほぼすべての実行可能な命令に対してメモリにアクセスすることで支払いを行います。 したがって、全体的なシステムパフォーマンスは、メモリ帯域幅によって上から制限されます。
3. プロセッサの複雑さは、長い間開発を妨げるものではなくなりました。
4. ハードウェアで実装されたスタックは、イベントの厳密なシーケンスを意味し、その結果、プログラムの暗黙的な並列処理を使用できないことを意味します。 スーパースカラープロセッサ自体が利用可能なリソースに応じてパイプラインで命令を配布し、VLIWプロセッサがこの作業がコンパイラによって行われることを期待している場合、コード内の隠れた並列性を見つけようとするスタックマシンでは、ほとんど克服できない困難に直面します。 言い換えると、私たちは再び、技術が建築が手に入れる以上のものを提供できる状況に直面しています。 それは奇妙です。
5. レジスタマシンのプログラミングは、より「技術的」です。 わずか数個の汎用レジスタを使用して、「手動で」これを回避できない場合にのみメモリにアクセスするコードを簡単に作成できます。 スタックマシンの場合、これを達成するのははるかに難しいことに注意してください。 また、レジスター間での一時変数の最適な割り当てはNP完全タスクですが、妥当な時間でかなりまともなコードを作成できる安価で効果的なヒューリスティックがいくつかあります。

もちろん、スタックラッパー内のレジスタマシン、たとえばIgniteやICL2900を非表示にしようとしましたが、商業的な成功はありませんでした。 実際、コンパイルの便宜上、ユーザーはランタイムの固定コストを負担する必要がありました。



それでは、なぜ著者はこのトピックを再び取り上げて、この分野に見込みがあると考えさせるのでしょうか。

動機

スタックマシンのコードがレジスタアーキテクチャに比べてはるかにコンパクトであると主張する人はいません。 このコンパクトさの重要性に異議を唱えることは可能ですが、事実は残っています。 コード圧縮はどのように達成されますか？ 結局のところ、機能的に彼は同じことをします、トリックは何ですか？



式x + y * z + uを評価する簡単な例を考えてみましょう。

コンパイラがツリーを解析するとき、次のようになります。



この式のアセンブラコード（x86）は次のようになります。

mov eax,dword ptr [y] imul eax,dword ptr [z] mov ecx,dword ptr [x] add ecx,eax mov eax,ecx add eax,dword ptr [u]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

仮想スタックマシンの場合、擬似コードは次のとおりです。

  push x push y push z multiply add push u add
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

4つのメモリアクセス、加算、乗算に加えて、各レジスタプロセッサ命令にはレジスタ識別子が含まれています。



しかし、結局のところ、これらのレジスタは実際には存在しません。これは、スーパースカラープロセッサが命令間の関係を示すために使用するフィクションです。

レジスタとそれらの操作のセットは、プロセッサアーキテクチャを形成し、スーパースカラプロセッサが存在しなかったときでも（少なくともx86の場合）歴史的に開発され、レジスタ名は非常に物理的なレジスタを示していました。



ご存知のように、旅行中に犬は成長する可能性があり、登録識別子は現在他の目的に使用されています。 現在のアーキテクチャは、コンパイラとプロセッサの間のインターフェースに似ています。 コンパイラーは、プロセッサーが実際にどのように機能するかを知らず、互換性のあるデバイス全体のコードを生成できます。 また、プロセッサ開発者は、有用で重要なことに集中して、外部互換性のある製品を作成できます。



そのような統一の料金はいくらですか？

1. スーパースカラープロセッサの観点から。 ここに、例えば、Intelの記事 、逐語的に：

   その場でスーパースカラーがシリアルコードを並列化します。 しかし、この並列化プロセスは、現在のプロセッサの処理能力にとっても手間がかかりすぎるため、マシンのパフォーマンスが制限されます。 サイクルごとに一定数の命令よりも速くこの変換を行うことは不可能です。 あなたはもっとできますが、同時に時計仕掛けは落ちます-このアプローチは明らかに無意味です

   あなたのお気に入りから別のものがあります：

   問題はスーパースカラー自体ではなく、プログラムのプレゼンテーションにあります。 プログラムは順番に表示され、実行中に並列実行に変換する必要があります。 スーパースカラーの主な問題は、入力コードがそのニーズを満たせないことです。 カーネルの並列アルゴリズムと並列に編成されたハードウェアがあります。 しかし、それらの間には、真ん中に、特定の官僚組織があります-コマンドの一貫したシステム

2. コンパイラの観点から。 そこから：

   コンパイラはプログラムをシーケンシャルコマンドシステムに変換します。 プロセスの全体的な速度は、彼がこれを行う順序に依存します。 しかし、コンパイラはマシンがどのように動作するかを正確に知りません。 したがって、一般的に言えば、今日のコンパイラの仕事はシャーマニズムです

   コンパイラーは、プログラムを指定された数のレジスターに圧縮するために巨額の努力を払いますが、この数は架空のものです。 コンパイラーは、（ 針の目に入るロープのように）プログラムで検出されたすべての並列性をアーキテクチャーの制限を超えてプッシュしようとします。 大部分は失敗しました。

どうする

問題が示されています-インターフェイス/アーキテクチャが最新の要件を満たしていません。

これらの（新しい）要件は何ですか？

1. コンパイラーが認識しているすべての並行性は、損失なく渡される必要があります。
2. 命令間の依存関係をアンパックするコストは最小限に抑える必要があります。

繰り返しますが、式x + y * z + uをコンパイルした例を見てみましょう。

x86	スタックマシン
mov eax、dword ptr [y] imul eax、dword ptr [z] mov ecx、dword ptr [x] ecx、eaxを追加 mov eax、ecx eax、dword ptr [u]を追加します	xを押す yを押す Zを押す 掛ける 加える 押して 加える

x86レジスタは、異なる命令間の関係を示すように設計されています。 そして、スタックマシンについてはどうですか。これらの依存関係はどのように実装されますか。 暗黙的に、スタック内の位置を介して。 各命令は引数の数を知っており、実行前にスタックの最上部でそれらを見つけることを期待しています。



しかし、スタックの最上部について話すときに、それがデータスタックではなく、 操作の スタック （ マイクロ 操作 、モップ）である場合はどうでしょう 。

• スタック命令は外部から来ますが、プロセッサは実際にはレジスタであり、非常に伝統的な「add r1 r2 r3」のみを実行できます。 これらの「追加...」をモップと呼びます。 必要に応じて、モップはレジスタプロセッサの内部命令用の汎用ワークピースです。
• プロセッサにはモップのプールがあり、最初はすべて無料で、インデックスによるアクセスがあります。
• モップには関連情報、リンクがあります-親モップの数、先祖の数、...
• したがって、最初の命令は「プッシュx」（この場合xはアドレス）であり、このトランスレーターはそれを「lload R？、0x .....」に変換します。このモップには入力引数がなく、出力引数のみがあります。
• モップは無料プールから取得され、無料モップが終了するとデコーダーは一時停止します。
• 最初は 'lload R？、0x .....'でした。 ケースは定義されていません。
• これは「lload R？、0x .....」で、インデックスモップのスタックの一番上に配置します。
• 次に、「プッシュy;プッシュz」して、同じことをします。 現在、モップのスタックには3つのダウンロードがあります。
• 次は「乗算」です、彼女のデコーダーはモップ「lmul R？ R？ R？ '。
• デコーダーはこの命令に2つの引数が必要であることを知っているため、スタックの最上部から上位2つのモップを取得（および削除）し、指定されたモップとリンクします。 その後、mopインデックス「multiply」がスタックの一番上にプッシュされます。
• 次は「追加」で、すべてが同じです。1つの引数だけがメモリからロードされ、2番目は乗算です。
• mopインデックスがスタックを離れると、実行（mop）を試みることができます。 最初にあるのは「push x」で、現在は「lload R？、0x .....」です。
• 出力引数については、最初のレジスター（R1など）を使用して、ビジーとしてマークします。 このモップは誰も待たないため、実行のためにコンベアに入れることができます。
• このmopが実行された後、相続人（1つのみ、同じツリー）があれば、それを通知し、同時に引数レジスタ番号が決定され、親mopsのカウンターが減らされます。
• 入力引数がケース（s）を保持している場合、それら（ケース（s））は解放できます。
• （子モップで）予想されるモップのカウンターが0になった場合、このモップは対応するパイプラインにも転送できます。
• ...

どんな種類のモップがありますか？

1. レジスタの操作、たとえば追加：2つのレジスタの値が合計され、3番目のレジスタに配置されます。 これらのモップはバイナリです。スタックにプッシュされる前に、上位2つのモップへのリンクが削除され、このモップへのリンクが入力されます。 また、単項-符号の変更など。 このような操作を作成すると、スタックの最上部にあるリンクがそのリンクに置き換えられます。
2. メモリ操作-メモリからレジスタに値をロードする、またはその逆。 メモリからの読み込みには先行操作がなく、単にモップのスタックにプッシュされます。 メモリでアンロードすると、スタックから1つの要素が削除されます。 メモリからロードすると、リンクがスタックに追加されます。
3. 特別な操作はポップで、スタックの最上部から要素を削除するデコーダーへの命令です。
4. その他-検討するまで、分岐、関数呼び出し、サービス

メモリを使用した操作の場合、モップ間で特別なタイプの通信が発生します。たとえば、アドレスを介して、値をメモリにロードし、メモリからレジスタに読み込む。 正式には、これらの操作の間、レジスタを介した通信はありません。実際はそうです。 言い換えると、読み終わる前に記録の終わりまで待つのがいいでしょう。 したがって、デコーダキャッシュ内のモップの場合、そのような依存関係を監視する必要があります。 キャッシュ外では、この問題はメモリアクセスバスを介したシリアル化によって解決されます。

ソフトウェアモデル

投機的な構造は、それらを実現しようとする瞬間まで完全に機能します。 したがって、以下では、モデルの検証と並行して理論化します。



著者は、 アッカーマン関数を実行するのに十分なCのサブセットの単純なコンパイラーを実装しました。 コンパイラはスタックマシン用のコードを発行し、すぐに実行を試みます。



簡単なことを急いで練習しないでください、例えば

  long d1, d2, d3, d4, d5, d6, d7, d8; d1 = 1; d2 = 2; d3 = 3; d4 = 4; d5 = 5; d6 = 6; d7 = 7; d8 = 8; print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、最初にプロセッサモデルのパラメーターを決定する必要があります。

1. 32個の整数レジスタ
2. デコードされたサイクルあたり4命令
3. メモリを操作するための1つのコンベヤ;レジスタへの/レジスタからのワードのロードとアンロードには3クロックサイクルかかります
4. ALUを備えた 2つのコンベヤー、加算/減算の演算には3クロックサイクル、比較-1クロックかかります

ここおよび以下で、命令は、実行されたパイプラインでの実行の完了時（レジスタが既に定義されている場合）に表示されます。

タクト	コンバージョン 記憶の	コンバージョン N1	コンバージョン N2
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29日 32 35	LLOAD r3 LLOAD r2 LLOAD r1 LLOAD r0 LLOAD r7 LLOAD r6 LLOAD r5 LLOAD r4 LSTORE r3 LSTORE r2 LSTORE r1 LSTORE r0 LSTORE r7 LSTORE r6 LSTORE r5 LSTORE r4 LLOAD r11 LLOAD r10 LLOAD r8 LLOAD r15 LLOAD r12 LLOAD r19 LLOAD r17 LLOAD r16	LADD r11 r10-> r9 LADD r8 r15-> r14 LADD r12 r19-> r18 LADD r9 r14-> r13 LADD r17 r16-> r23 LADD r18 r23-> r22 LADD r13 r22-> r21

そして、35番目のサイクルのレジスター21では、切望されている36の値を取得します。

同じテーブルからのデータですが、モップの依存図の形式で、括弧内の[]はモップの完了の拍数です（xとyはここでは意味がなく、矢印の方向のみが値を持ちます）。



何が見えますか？

• 最初の8つのLLOAD命令-定数のロード
• さらに8 LSTORE-定数による変数の初期化。 最初は（LOADとSTORE）が混在していたため、同様の方法でシリアル化されたのは奇妙に思えるかもしれません。 しかし、メモリから定数をロードすることは3サイクル、サイクルあたり4命令であることを覚えておく価値があります。 最初の定数がロードを待機している間、LSTORE操作は依存関係のため、LLOADの背後のパイプラインで終了しました。 ところで、動作中のLLC 。
• 2つのパイプラインと明らかな並行性があるため、両方のパイプラインをロードできなかったのは奇妙に思えます。 一方、最後のメモリロードは26クロックサイクル（8 * 3 + 2）後に終了しました。 式ツリーの深さは、ステップごとに3〜3メジャーです。 合計で26 + 9 = 35サイクル、これを原理的に高速に計算することは不可能です。 つまり このコードをできるだけ迅速に計算するには、単一の整数パイプラインで十分です。

同じことを試してみましょう。ただし、変数を明示的に初期化することはありません。

  long d1, d2, d3, d4, d5, d6, d7, d8; print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タクト	コンバージョン 記憶の	コンバージョン N1	コンバージョン N2
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19	LLOAD r3 LLOAD r2 LLOAD r0 LLOAD r7 LLOAD r4 LLOAD r11 LLOAD r9 LLOAD r8	LADD r3 r2-> r1 LADD r0 r7-> r6 LADD r4 r11-> r10 LADD r1 r6-> r5 LADD r9 r8-> r15 LADD r10 r15-> r14 LADD r5 r14-> r13

計算には8 + 2 + 3 * 3 = 19サイクルが必要で、これは可能な限り最小で、1つのコンベアで十分でした。



ここで、すべての角かっこを削除して、変数を加算してみましょう。

  long d1, d2, d3, d4, d5, d6, d7, d8; print_long (d1+d2+d3+d4+d5+d6+d7+d8); //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タクト	コンバージョン 記憶の	コンバージョン N1	コンバージョン N2
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25	LLOAD r3 LLOAD r2 LLOAD r0 LLOAD r6 LLOAD r4 LLOAD r10 LLOAD r8 LLOAD r14	LADD r3 r2-> r1 LADD r1 r0-> r7 LADD r7 r6-> r5 LADD r5 r4-> r11 LADD r11 r10-> r9 LADD r9 r8-> r15 LADD r15 r14-> r13

この場合、データへの依存があり、パイプラインを完全にロードできないため、余分な6クロックサイクルが発生します。



表現を裏返しにしてはどうですか？

  long d1, d2, d3, d4, d5, d6, d7, d8; print_long (d1+(d2+(d3+(d4+(d5+(d6+(d7+d8))))))); //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それはまだ余分なバーの価値がありました。 データのロードは最適な順序ではありません。



明らかな並列性と2つの整数パイプラインが存在する場合、2番目のパイプラインはアイドル状態です。 システムを動かしてみましょう。 に戻りましょう

  long d1, d2, d3, d4, d5, d6, d7, d8; print_long (((d1 + d2)+(d3 + d4))+((d5 + d6)+(d7 + d8))); //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

メモリへのアクセス速度を上げて、1クロックサイクルでレジスタの読み取りを実行してみましょう。 面白いが、ほとんど変わっていない。 合計時間が2メジャー減少しました。より正確には、全体像が2メジャー増加しました。 メモリ帯域幅は変更されておらず、最初の結果が得られるまで遅延を削除しただけです。



おそらく、合計が速すぎます。 3回ではなく7回の測定を行います。

合計時間は29（8 + 3 * 7）ティックに増加しましたが、基本的には何も変化せず、2番目のコンベアはアイドル状態です。



16個の数字のピラミッドを要約し、2つのメモリパイプラインを導入してみましょう。 合計時間は36サイクル（16/2 + 4 * 7）です。 2番目の数値パイプラインは関係していません。 番号はペアになり、最初のレベルの8つの合計はすべてビートの遅延から始まり、これはすべてを1つのパイプラインに保持するのに十分です。



そして、4つのメモリパイプラインを入力し、サイクルごとに6つのデコードを許可する場合にのみ、2番目の数値パイプライン（最大3（sic！）命令を実行）になりますが、それでも合計時間は33サイクルです。 つまり 加算自体の効率はさらに悪化しました。



確かに、コンベヤーは非常に効果的なメカニズムであり、1つ以上のコンベヤーを使用するのにはかなりの理由が必要です。

レジスタ割り当て

上記の例では、レジスタの目的はモップが作成されたときに発生しました。 その結果、ピラミッドで変数を合計するときのレジスタ使用のマップは次のようになります（初期パラメーター-サイクルごとに4つの命令がデコードされ、1つのメモリパイプライン、読み取りと合計のための3サイクル）：

8変数	16変数

パイプラインに命令を配置するときにレジスタを割り当てると、図がより良く見えます。

8変数	16変数

制御のために、命令の依存関係図（8桁の数字）を持参する価値があります。

関数呼び出し

一般的な理由により、説明されているアーキテクチャでは、関数の呼び出しに問題があると想定されています。 実際、関数から戻った後、現在の関数のコンテキストでレジスタの状態を期待して返します。 最新のレジスタアーキテクチャでは、レジスタはこのために2つのカテゴリに分けられます-呼び出し側は一部の安全を担当し、呼び出し側は他の人を担当します。



しかし、このアーキテクチャでは、フロントエンドはスタックであるため、コンパイラーはレジスターの存在を認識しない場合があります。 また、プロセッサ自体がコンテキストの保存/復元を処理する必要がありますが、これは重要なタスクのようです。



ただし、この問題は次の記事で解決します 。