スタックマシン

コンピュータサイエンス、コンピュータエンジニアリング、プログラミング言語実装 において、スタックマシンとは、主な相互作用がプッシュダウンスタックとの間で短命な一時値を移動することであるコンピュータプロセッサまたはプロセス仮想マシンである。ハードウェアプロセッサの場合は、ハードウェアスタックが使用される。スタックの使用により、必要なプロセッサレジスタの数が大幅に削減される。スタックマシンは、追加のロード/ストア操作や複数のスタックによってプッシュダウンオートマトンを拡張するため、チューリング完全である。

設計

ほとんどまたはすべてのスタックマシン命令は、オペランドがスタックから取得され、結果がスタックに格納されることを前提としています。スタックは2つ以上の入力または複数の結果を容易に保持できるため、豊富な演算セットを計算できます。スタックマシンコード（pコードと呼ばれることもあります）では、命令は多くの場合、操作を命令するオペコードのみを持ち、定数、レジスタ、またはメモリセルを識別する追加フ​​ィールドはありません。これはゼロアドレス形式として知られています。[ 1 ]命令の大部分が明示的なアドレスを含まないように動作するコンピュータは、ゼロアドレス命令を使用していると言われています。[ 2 ]これにより、命令のデコードが大幅に簡素化されます。分岐、ロード即値、およびロード/ストア命令は引数フィールドを必要としますが、スタックマシンはこれらの頻繁なケースがオペコードと共にコンパクトなビットグループに収まるように調整することがよくあります。以前の結果からのオペランドの選択は、命令の順序付けによって暗黙的に行われます。一部のスタックマシン命令セットは、ハードウェアを直接駆動するのではなく、仮想マシンの解釈実行を目的としています

整数定数オペランドはPushORLoad Immediate命令によってプッシュされます。メモリへのアクセスは、メモリアドレスを含むLoadOR命令、またはスタック内の値からアドレスを計算するOR命令によって行われることがよくあります。実用的なスタックマシンはすべて、明示的なアドレス計算なしでローカル変数や仮パラメータにアクセスするためのロード・ストア・オペコードのバリエーションを備えています。これは、現在のスタックトップアドレスからのオフセット、または安定したフレームベースレジスタからのオフセットによって行われます。 Store

この命令セットは、ほとんどのALU動作をポストフィックス（逆ポーランド記法）演算で実行します。これらの演算は式スタックのみを対象とし、データレジスタやメインメモリセルには適用されません。ほとんどの算術式はポストフィックス記法に簡単に変換できるため、高水準言語の実行に非常に便利です。

式A *( B − C ) + ( D + E )の二分構文木

例えば、式A *( B − C )+( D + E ) を逆ポーランド記法でA B C − * D E + + と書きます。これを単純な仮想スタックマシンでコンパイルして実行すると、次のようになります。 

 # スタックの内容 (左端 = 上 = 最新): A # Aを押す B # BAを押す C# CBAをプッシュ # B−CA を引く # A*(B−C) を掛ける D # DA*(B−C) を押す Eを押下 # EDA*(B−C) # D+EA*(B−C) を加える # A*(B−C)+(D+E) を足す

算術演算「減算」、「乗算」、「加算」は、スタックの最上位2つのオペランドに対して実行されます。コンピュータは、スタックの最上位（最新の）値から両方のオペランドを取得します。そして、計算された差、和、または積でそれらの2つの値を置き換えます。つまり、命令のオペランドはスタックから「ポップ」され、その結果はスタックに「プッシュ」され、次の命令に備えられます。

スタックマシンは、式スタックとコールリターンスタックを分離して構成することも、統合された一つの構造として構成することもできます。分離されている場合、スタックマシンの命令はパイプライン化され、相互作用が少なく設計の複雑さも軽減されるため、通常はより高速に動作します。

コンパイルされたスタックコードの最適化は十分に可能です。コンパイラ出力のバックエンド最適化は、コードを大幅に改善し、[ 3 ] [ 4 ]潜在的にパフォーマンスも向上することが実証されています。また、コンパイラ自体におけるグローバル最適化は、さらなる効果をもたらします。[ 5 ]

スタックストレージ

一部のスタックマシンは、レジスタファイルとして実装された、サイズが限られたスタックを持っています。ALUはインデックスを使ってこれにアクセスします。大きなレジスタファイルは多くのトランジスタを使用するため、この方法は小規模なシステムにのみ適しています。メモリ内に式スタックと別のレジスタスタックの両方を持つマシンもいくつかあります。この場合、ソフトウェアまたは割り込みによって、それらの間でデータを移動できます。一部のマシンは、RAM内の配列として実装された、サイズが無制限のスタックを持っており、メモリアクセスを減らすために、いくつかの「スタック最上位」アドレスレジスタによってキャッシュされます。明示的な「メモリからのロード」命令を除き、オペランドの使用順序はデータスタック内のオペランドの順序と同じであるため、優れたプリフェッチを簡単に実現できます

を考えてみましょうX+1。これはLoad X; Load 1;にコンパイルされますAdd。スタックが完全にRAMに格納されている場合、これはメモリ内スタックの暗黙的な書き込みと読み取りを行います。

  • Xをロードし、メモリにプッシュ
  • 1をロードしてメモリにプッシュ
  • メモリから2つの値をポップし、加算して結果をメモリにプッシュします

合計 5 つのデータ キャッシュ参照。

次のステップは、スタックトップレジスタを1つ持つスタックマシンまたはインタープリタです。上記のコードは、以下の処理を実行します。

  • Xを空のTOSレジスタにロードする（ハードウェアマシンの場合）またはTOSレジスタをメモリにプッシュする、XをTOSレジスタにロードする（インタープリタの場合）
  • TOSレジスタをメモリにプッシュし、TOSレジスタに1をロードします
  • 左オペランドをメモリからポップし、TOSレジスタに追加してそこに残します。

最悪の場合、データキャッシュへの参照は合計3回になります。一般的に、インタープリタは空かどうかを追跡しません。なぜなら、スタックポインタより下の値は空ではない値であり、TOSキャッシュレジスタは常にホットな状態にあるからです。しかし、プログラムとスタックには短いデータ値と長いデータ値が混在するため、一般的なJavaインタープリタはスタックの先頭をこのようにバッファリングしません。

ハードワイヤード スタック マシンに 2 つ以上のトップ スタック レジスタ、またはレジスタ ファイルがある場合、この例ではすべてのメモリ アクセスが回避され、データ キャッシュ サイクルは 1 つだけになります。

歴史と実装

一度に2つの値のみをレジスタに保持し、事前定義されたオペランドの限られたセットを使用して、追加のオペランド、関数、サブルーチンを定義することで拡張できるこのような方法の説明は、1961年の会議でロバート・S・バートンによって初めて提供されました。 [ 6 ] [ 7 ]

商用スタックマシン

ハードウェアで直接実行されるスタック命令セットの例には以下が含まれます

仮想スタックマシン

ソフトウェアで解釈される 仮想スタックマシンの例：

ハイブリッドマシン

純粋スタックマシンは、同じオブジェクトの複数のフィールドにアクセスする手続きには非常に非効率的です。スタックマシンのコードは、ポインタとオフセットの計算ごとにオブジェクトポインタを再ロードする必要があります。この問題の一般的な解決策は、スタックマシンにレジスタマシン機能を追加することです。具体的には、アドレスを保持するための専用のレジスタファイルと、ロードや単純なアドレス計算を行うためのレジスタスタイルの命令です。レジスタを完全に汎用化することは稀です。なぜなら、その場合、式スタックや後置命令を使用する強い理由がないからです。

もう一つの一般的なハイブリッドは、レジスタマシンアーキテクチャをベースに、スタックマシンのプッシュまたはポップ操作をエミュレートする別のメモリアドレスモードを追加することです。「memaddress = reg; reg += instr.displ」です。これはDECのPDP-11ミニコンピュータで初めて使用されました。[ 24 ]この機能はVAXコンピュータやMotorola 6809および68000シリーズのマイクロプロセッサにも引き継がれました。これにより、初期のコンパイラではよりシンプルなスタック方式を使用できるようになりました。また、スタックインタープリタやスレッドコードを使用した仮想マシンも効率的にサポートされました。しかし、この機能は、レジスタマシン自身のコードを純粋なスタックマシンコードほどコンパクトにするのには役立ちませんでした。また、実行速度はレジスタアーキテクチャに適切にコンパイルした場合よりも遅くなりました。スタックトップポインタをプログラム文ごとに常に上下させるよりも、時々（呼び出しまたは戻り値ごとに1回）変更する方が高速であり、メモリ参照を完全に回避すればさらに高速になります。

近年では、いわゆる第二世代スタックマシンでは、アドレスレジスタとして機能する専用のレジスタ群を採用し、データスタックからメモリアドレス指定のタスクをオフロードしています。例えば、MuP21は「A」と呼ばれるレジスタを使用していますが、より最近のGreenArraysプロセッサはAとBという2つのレジスタを使用しています。[ 25 ]

Intel x86ファミリーのマイクロプロセッサは、ほとんどの演算にレジスタ形式（アキュムレータ）の命令セットを採用していますが、x87 （Intel 8087）浮動小数点演算にはスタック命令を使用します。これは、8086および8088用のiAPX87（8087）コプロセッサにまで遡ります。つまり、プログラマがアクセス可能な浮動小数点レジスタはなく、80ビット幅、8レベルのスタックのみを備えています。x87は、演算実行においてx86 CPUの支援に大きく依存しています。

コールスタックとスタックフレームを使用するコンピュータ

現在のほとんどのコンピューター（あらゆる命令セットスタイル）とほとんどのコンパイラは、メモリ内に巨大なコールリターンスタックを使用して、現在アクティブなすべてのプロシージャまたは関数の短命なローカル変数とリターンリンクを整理します。ネストされた呼び出しごとにメモリ内に新しいスタックフレームが作成され、その呼び出しが完了するまで保持されます。このコールリターンスタックは、命令内の特殊なアドレスレジスタと特殊なアドレスモードを介して、ハードウェアによって完全に管理される場合があります。あるいは、汎用レジスタとレジスタ+オフセットアドレスモードを使用して、コンパイラが従う一連の規則にすぎない場合もあります。あるいは、その中間の場合もあります。

この手法はレジスタマシンにおいてもほぼ普遍的であるため、これらすべてのマシンをスタックマシンと呼ぶのは適切ではありません。この用語は、式スタックとスタックのみの算術命令を用いて単一の文の各部分を評価するマシンを指すのが一般的です。

コンピュータは一般的に、プログラムのグローバル変数と、現在の最も内側の手続きまたは関数（最上位のスタックフレーム）のローカル変数への直接的で効率的なアクセスを提供します。呼び出し元のスタックフレームの内容に対する「上位レベル」のアドレス指定は通常は不要であり、ハードウェアによって直接サポートされていません。必要に応じて、コンパイラはフレームポインタを追加の隠しパラメータとして渡すことでこれをサポートします。

一部のバローズスタックマシンは、特殊なアドレスモードと、すべての外部スコープのフレームアドレスを保持する特別な「表示」レジスタファイルを備え、ハードウェアで直接上位レベル参照をサポートしています。現在、MCST Elbrusのみがこれをハードウェアで実現しています。Niklaus WirthがCDC 6000シリーズ用の最初のPascalコンパイラを開発したとき、フレームポインタの完全な配列を常に更新するよりも、フレームポインタをチェーンとして渡す方が全体的に高速であることに気付きました。このソフトウェア方式は、上位レベル参照を持たないCなどの一般的な言語にもオーバーヘッドを追加しません。

同じバロウズマシンは、タスクまたはスレッドのネストもサポートしていました。タスクとその作成者は、タスク作成時に存在したスタックフレームを共有しますが、作成者の後続のフレームやタスク自身のフレームは共有しません。これは、レイアウト図がサワロサボテンの幹と枝に似たサボテンスタックによってサポートされていました。各タスクは、自身のスタックと所有するフレームを保持する独自のメモリセグメントを持っていました。このスタックのベースは、作成者のスタックの中央にリンクされています。従来のフラットアドレス空間を持つマシンでは、作成者スタックとタスクスタックは、1つのヒープ内の別々のヒープオブジェクトになります。

一部のプログラミング言語では、外部スコープのデータ環境が必ずしも時間的にネストされているとは限りません。これらの言語では、手続きの「アクティベーションレコード」を、線形スタックに追加されたスタックフレームではなく、独立したヒープオブジェクトとして整理します。

Forthのような単純な言語では、ローカル変数やパラメータ名がないため、スタックフレームにはリターン分岐アドレスとフレーム管理のオーバーヘッドしか含まれません。そのため、リターンスタックにはフレームではなく、リターンアドレスのみが保持されます。リターンスタックはデータ値スタックとは独立しており、呼び出しのセットアップとリターンのフローを改善します。

レジとの比較

スタックマシンは、レジスタ配列に値を保持するレジスタマシンとよく比較されます。レジスタマシンは、この配列にスタックのような構造を格納できますが、レジスタマシンにはスタックインターフェースを回避する命令があります。レジスタマシンはスタックマシンよりも優れた性能を示すことが多く、[ 26 ]スタックマシンはハードウェアシステムにおいてニッチな存在であり続けています。しかし、スタックマシンは実装が単純で容易なため、仮想マシンの実装によく使用されます。 [ 27 ]

命令

スタックマシンはコード密度が高いです。一般的なスタックマシン命令は6ビット以下に簡単に収まりますが、レジスタマシンはオペランドを選択するためにALU命令ごとに2つまたは3つのレジスタ番号フィールドを必要とします。最も密度の高いレジスタマシンは、命令ごとに平均約16ビットとオペランドを必要とします。レジスタマシンはまた、ロードストアオペコードに広いオフセットフィールドを使用します。スタックマシンのコンパクトなコードは、当然のことながらキャッシュに多くの命令を収めることができるため、キャッシュ効率が向上し、メモリコストを削減したり、与えられたコストでより高速なメモリシステムを実現したりできます。さらに、ほとんどのスタックマシン命令は非常に単純で、1つのオペコードフィールドまたは1つのオペランドフィールドのみで構成されています。したがって、スタックマシンは各命令をデコードするために必要な電子リソースはごくわずかです

スタックマシン向けにコンパイルされたプログラムは、レジスタマシンやメモリツーメモリマシン向けにコンパイルされた場合よりも多くの命令を実行する必要があります。変数や定数へのロード命令は、その値を使用する命令にまとめられるのではなく、それぞれ独立したロード命令を必要とします。分離された命令は単純で実行速度も速くなりますが、それでも命令の総数は多くなります。

ほとんどのレジスタインタープリタは、レジスタを番号で指定します。しかし、ホストマシンのレジスタはインデックス配列でアクセスできないため、仮想レジスタにはメモリ配列が割り当てられます。そのため、レジスタインタープリタの命令は、生成したデータを次の命令に渡すためにメモリを使用する必要があります。このため、レジスタインタープリタは、微細プロセスルール（つまり、回路速度の向上なしにトランジスタを高速化したもの、例えばHaswell x86など）で製造されたマイクロプロセッサでは、大幅に遅くなります。これらのマイクロプロセッサでは、メモリアクセスには数クロックかかりますが、レジスタアクセスには1クロックしかかかりません。レジスタファイルの代わりにデータ転送回路を備えたスタックマシンの場合、スタックインタープリタは、スタックの上位数オペランドにホストマシンのメモリではなく、ホストマシンのレジスタを割り当てることができます。

スタックマシンでは、命令で使用されるオペランドは常に固定位置（スタックの最下部。ハードウェア設計では常にメモリ位置0になる場合がある）からの既知のオフセット（スタックポインタに設定される）に配置されるため、貴重なキャッシュ内またはCPU内ストレージを、多数のメモリアドレスやインデックス番号の格納に使用せずに済みます。これにより、このようなレジスタやキャッシュを非フロー計算に使用できるように節約できます。

一時的/ローカルな値

業界の中には、スタックマシンはレジスタマシンよりも一時値とローカル変数のデータキャッシュサイクルを多く実行すると考える人もいます。 [ 28 ]

スタックマシンでは、一時値はメモリに吐き出されることがよくありますが、レジスタを多数持つマシンでは、これらの一時値は通常レジスタ内に残ります。（ただし、これらの値は、プロシージャ定義の末尾にある「アクティベーションフレーム」、つまり基本ブロック、あるいは少なくとも割り込み処理中にメモリバッファに吐き出される必要がある場合が多いです。）メモリに吐き出された値は、キャッシュサイクルを増加させます。この吐き出しの影響は、スタックの先頭の値をバッファリングするために使用される隠しレジスタの数、ネストされたプロシージャ呼び出しの頻度、そしてホストコンピュータの割り込み処理速度に依存します。

最適化コンパイラを使用するレジスタマシンでは、最も頻繁に使用されるローカル変数がスタックフレームメモリセルではなくレジスタに保持されるのが一般的です。これにより、これらの値の読み書きに必要なデータキャッシュサイクルの大部分が削減されます。ライブ変数解析を実行し、重要な変数を長期間スタック上に保持する「スタックスケジューリング」の開発は、この問題の解決に役立ちます。[ 3 ] [ 4 ] [ 5 ]

一方、レジスタマシンは、ネストされた手続き呼び出しをまたぐ際に、多くのレジスタをメモリに吐き出す必要があります。どのレジスタをいつ吐き出すかは、呼び出しの動的な深さではなく、コンパイル時に静的に決定されます。そのため、高度なスタックマシン実装よりもデータキャッシュのトラフィックが増加する可能性があります。

共通部分式

レジスタマシンでは、共通部分式（同じ結果値で複数回使用される部分式）は一度だけ評価され、その結果は高速レジスタに保存されます。その後の再利用には時間やコードのコストはかからず、レジスタ参照のみが必要です。この最適化により、単純な式（たとえば、変数XやポインタPのロード）だけでなく、あまり一般的ではない複雑な式も高速化されます

対照的に、スタック マシンでは、結果を 2 つの方法のいずれかで格納できます。まず、結果をメモリ内の一時変数を使用して格納できます。格納とそれに続く取得には、追加の命令と追加のデータ キャッシュ サイクルがかかります。これを実行すると、部分式の計算にメモリからのフェッチよりも時間がかかる場合にのみメリットがあり、ほとんどのスタック CPU ではほとんどの場合に当てはまります。単純な変数とポインタ フェッチでは、アクセスごとに 1 つのデータ キャッシュ サイクルという同じコストが既にかかっているため、この方法は効果的ではありません。などの式では、かろうじて効果があるだけです。これらの単純な式は、連結型言語X+1以外の言語で記述されたプログラム内の冗長で最適化可能な式の大部分を占めます。最適化コンパイラは、プログラマがソース コードで回避できた冗長性に関してのみメリットがあります。

2つ目の方法は、計算された値をデータスタックに残し、必要に応じて複製する方法です。この方法では、スタックエントリをコピーする操作が使用されます。スタックの深さは、CPUが利用可能なコピー命令に対応できるほど浅くなければなりません。手書きのスタックコードはこのアプローチをよく使用しており、汎用レジスタマシンと同等の速度を実現しています。[ 29 ] [ 9 ]残念ながら、最適な「スタックスケジューリング」アルゴリズムは、プログラミング言語ではあまり使用されていません。

パイプライン

現代のマシンでは、データキャッシュから変数をフェッチする時間は、基本的なALU演算に必要な時間よりも数倍長くなることがよくあります。メモリのロードを、その変数を必要とする命令の数サイクル前に開始できれば、プログラムはストールすることなく高速に実行されます。複雑なマシンは、深いパイプラインと、多くの命令を一度に検査して実行する「アウトオブオーダー実行」によってこれを実現できます。レジスターマシンは、はるかに単純な「インオーダー」ハードウェア、浅いパイプライン、そしてわずかに賢いコンパイラでさえこれを実現できます。ロードステップは別の命令になり、その命令はコードシーケンスのずっと早い段階で静的にスケジュールされます。コンパイラは、その間に独立したステップを配置します

メモリアクセスのスケジュール設定には、明示的で予備のレジスタが必要である。これは、マイクロアーキテクチャの一部をプログラマに公開しなければ、スタックマシンでは不可能である。式 AB − の場合、B はマイナスステップの直前に評価され、プッシュされる必要がある。スタックの並べ替えやハードウェアマルチスレッドがなければ、ロード B が完了するのを待つ間に、比較的有用なコードを入れることはほとんどできない。スタックマシンは、一度に多くの命令をカバーする深いアウトオブオーダー実行パイプラインを備えるか、またはより可能性が高いのは、ロードが完了する間に他のワークロードで動作できるようにスタックを並べ替えるか、または Unisys A9 システムのように、異なるプログラムスレッドの実行をインターレースするかのいずれかによって、メモリ遅延を回避することができる。[ 30 ]しかし、今日のますます並列化している計算負荷を考えると、これは過去に考えられていたほどの欠点ではないかもしれない。

スタックマシンはレジスタマシンのオペランドフェッチ段階を省略することができる。[ 29 ]例えば、Java Optimized Processor（JOP）マイクロプロセッサでは、スタックの上位2つのオペランドがレジスタファイルよりも高速なデータ転送回路に直接入る。[ 31 ]

アウトオブオーダー実行

トマスロアルゴリズムは、データが利用可能になると命令を発行することで、命令レベルの並列性を見つけます。概念的には、スタック内の位置のアドレスは、レジスタファイルのレジスタインデックスと変わりません。この考え方により、トマスロアルゴリズムのアウトオブオーダー実行をスタックマシンで使用できるようになります

スタックマシンにおけるアウトオブオーダー実行は、多くの理論的および実践的な困難を軽減または回避すると思われる。[ 32 ]引用された研究によると、このようなスタックマシンは命令レベルの並列性を活用でき、その結果得られるハードウェアは命令のデータをキャッシュする必要がある。このようなマシンは、スタックへのほとんどのメモリアクセスを効果的にバイパスする。その結果、ロード・ストア・アーキテクチャのマシンに匹敵するスループット（クロックあたりの命令数）と、はるかに高いコード密度（オペランドアドレスが暗黙的であるため）が達成される。

研究で提起された問題の一つは、ロード・ストア・アーキテクチャのマシンでは、1命令分の作業を実行するのに約1.88個のスタックマシン命令が必要であるという点でした。そのため、競合するアウトオブオーダー・スタックマシンでは、命令を追跡するための電子リソース（「発行ステーション」）が約2倍必要になります。これは、命令キャッシュとメモリ、そして命令デコード回路の節約によって補える可能性があります。

より高速なレジを内部に隠す

一部のシンプルなスタックマシンでは、個々のレジスタレベルに至るまで完全にカスタマイズされたチップ設計が採用されています。スタックトップアドレスレジスタとN個のスタックトップデータバッファは、独立したレジスタ回路で構成され、独立した加算器とアドホック接続を備えています。

しかし、ほとんどのスタックマシンは、N個のデータバッファがレジスタファイル内にまとめて格納され、読み書きバスを共有する、より大きな回路部品で構成されています。デコードされたスタック命令は、その隠されたレジスタファイル上の1つ以上のシーケンシャルアクションにマッピングされます。ロードとALU演算は最上位のいくつかのレジスタに作用し、暗黙的なスピルとフィルは最下位のレジスタに作用します。デコーダーにより、命令ストリームはコンパクトになります。しかし、コードストリームに明示的なレジスタ選択フィールドがあり、それが下層のレジスタファイルを直接操作していれば、コンパイラはすべてのレジスタをより有効に活用でき、プログラムの実行速度が向上します。

マイクロプログラム化されたスタックマシンはその一例です。内部のマイクロコードエンジンは、RISCのようなレジスタマシン、または複数のレジスタファイルを使用するVLIWのようなマシンです。タスク固有のマイクロコードによって直接制御される場合、このエンジンは、同じタスクに対して同等のスタックコードによって間接的に制御される場合よりも、サイクルごとにはるかに多くの作業を完了します。

HP 3000およびTandem NonStopスタックマシンのコードを、それらのマシンのレジスタベースRISC代替品のコードに変換したオブジェクトコードトランスレータも、もう一つの例です。 [ 33 ] [ 34 ]これらのトランスレータは、スタックコードシーケンスを同等のRISCコードシーケンスに変換しました。軽微な「ローカル」最適化により、スタックアーキテクチャのオーバーヘッドの大部分が削減されました。予備レジスタは、繰り返し実行されるアドレス計算を除外するために使用されました。変換されたコードには、元のマシンとターゲットマシンの不一致によるエミュレーションオーバーヘッドが依然として多く残っていました。このような負担にもかかわらず、変換されたコードのサイクル効率は、元のスタックコードのサイクル効率と一致しました。さらに、最適化コンパイラを介してソースコードをレジスタベースマシンに直接再コンパイルすると、効率は2倍になりました。これは、スタックアーキテクチャとその非最適化コンパイラが、基盤となるハードウェアのパワーの半分以上を無駄にしていたことを示しています。

レジスタ ファイルは、データ キャッシュを介したメモリ参照に比べて帯域幅が広く、レイテンシが非常に低いため、コンピューティングに適したツールです。単純なマシンでは、レジスタ ファイルにより、2 つの独立したレジスタの読み取りと 3 つ目のレジスタの書き込みを、すべて 1 ALU サイクルで 1 サイクル以下のレイテンシで実行できます。一方、対応するデータ キャッシュでは、1 サイクルにつき 1 つの読み取りまたは 1 つの書き込み (両方ではありません) しか開始できず、読み取りのレイテンシは通常 2 ALU サイクルです。これは、パイプライン遅延が 2 倍で、スループットが 3 分の 1 になります。1サイクルにつき 2 つ以上の命令を実行するAthlonのような複雑なマシンでは、レジスタ ファイルにより、4 つ以上の独立したレジスタの読み取りと他の 2 つのレジスタの書き込みを、すべて 1 ALU サイクルで 1 サイクルのレイテンシで実行できます。一方、対応するデュアル ポート データ キャッシュでは、1 サイクルにつき 2 つの読み取りまたは書き込みしか開始できず、レイテンシは複数サイクルになります。これも、レジスタのスループットの 3 分の 1 になります。ポートを追加したキャッシュを構築するのは非常にコストがかかります。

スタックはほとんどのソフトウェアプログラムの構成要素であるため、たとえソフトウェアが厳密にはスタックマシンではないとしても、ハードウェアスタックマシンはプログラムの内部動作をより忠実に模倣する可能性があります。プロセッサレジスタは熱コストが高いため、スタックマシンはより高いエネルギー効率を主張する可能性があります。[ 35 ]

割り込み

割り込みへの応答には、レジスタをスタックに保存し、次に割り込みハンドラコードに分岐することが含まれます。多くの場合、スタックマシンは割り込みに迅速に応答します。これは、ほとんどのパラメータがすでにスタック上にあり、そこにプッシュする必要がないためです。一部のレジスタマシンは、瞬時にスワップできる複数のレジスタファイルを持つことでこの問題に対処していますが[ 36 ]、これはコストを増加させ、レジスタファイルの速度を低下させます

インタプリタ

仮想スタックマシン用のインタプリタは、レジスタマシン用のインタプリタよりも構築が容易です。メモリアドレスモードを処理するロジックは、多くの命令で繰り返されるのではなく、1か所にまとめられています。また、スタックマシンはオペコードのバリエーションが少ない傾向があり、1つの汎用オペコードで、メモリ参照や関数呼び出しのセットアップにおいて、頻繁に発生するケースと、あまり一般的ではないコーナーケースの両方を処理できます。（ただし、同じ操作に短縮形と長文形式を追加することで、コード密度が向上することがよくあります。）

仮想スタックマシンのインタープリタは、他のスタイルの仮想マシンのインタープリタよりも遅くなることがよくあります。[ 37 ]この速度低下は、現在のx86チップなどの深い実行パイプラインを備えたホストマシンで実行する場合、最も深刻になります。

一部のインタープリタでは、次のオペコードをデコードし、そのオペコードのステップに分岐するために、Nウェイスイッチジャンプを実行する必要があります。オペコードを選択する別の方法として、スレッドコードがあります。ホストマシンのプリフェッチ機構は、インデックス付きまたは間接的なジャンプのターゲットを予測してフェッチすることができません。そのため、ホストマシンの実行パイプラインは、ホストされているインタープリタが別の仮想命令をデコードするたびに再起動する必要があります。これは、他のタイプの仮想マシンよりも仮想スタックマシンで頻繁に発生します。[ 38 ]

一例として、Javaプログラミング言語が挙げられます。Javaの標準的な仮想マシンは8ビットのスタックマシンとして規定されています。しかし、Androidスマートフォンで使用されているJava用Dalvik仮想マシンは、効率性を考慮して16ビットの仮想レジスタマシンを採用しています。算術命令は、4ビット（またはそれ以上）の命令フィールドを介してローカル変数を直接フェッチまたはストアします。[ 39 ]同様に、Luaのバージョン5.0では、仮想スタックマシンがより高速な仮想レジスタマシンに置き換えられました。[ 40 ] [ 41 ]

Java仮想マシンが普及して以来、マイクロプロセッサは間接ジャンプのための高度な分岐予測器を採用してきました。[ 42 ]この進歩により、Nウェイジャンプからのパイプラインの再開がほとんど回避され、スタックインタープリタに影響を与える命令カウントコストが大幅に削減されます。

参照

参考文献

  1. ^ビアード、ボブ（1997年秋）「KDF9コンピュータ - 30年後」。コンピュータ復活
  2. ^ Hayes, John P. (1978).コンピュータアーキテクチャと組織. McGraw-Hill International Book Company. p. 164. ISBN 0-07-027363-4。
  3. ^ a b Koopman, Jr., Philip John (1994). 「最適化されたスタックコード生成の予備的調査」(PDF) . Journal of Forth Applications and Research . 6 (3).
  4. ^ a b Bailey, Chris (2000). 「スタックオペランドの境界間スケジューリング：予備的研究」(PDF) . Euroforth 2000 Conference Proceedings of Euroforth 2000 .
  5. ^ a bシャノン、マーク、ベイリー、クリス (2006). 「グローバルスタック割り当て：スタックマシンのレジスタ割り当て」(PDF) .ユーロフォース会議2006議事録.
  6. ^バートン、ロバート・S. (1961-05-09). 「デジタルコンピュータの機能設計への新しいアプローチ」 . 1961年5月9～11日開催のIRE-AIEE-ACM合同コンピュータ会議における発表論文. 1961年IRE-AIEE-ACM合同コンピュータ会議. pp.  393– 396. doi : 10.1145/1460690.1460736 . ISBN 978-1-45037872-7. S2CID  29044652 .{{cite conference}}：ISBN / 日付の非互換性（ヘルプ）
  7. ^ Barton, Robert S. (1987). 「デジタルコンピュータの機能設計への新しいアプローチ」 . IEEE Annals of the History of Computing . 9 (1): 11– 15. Bibcode : 1987IAHC....9a..11B . doi : 10.1109/ MAHC.1987.10002
  8. ^ Blaauw, Gerrit Anne ; Brooks, Jr., Frederick Phillips (1997). 『コンピュータアーキテクチャ：概念と進化』 ボストン、マサチューセッツ州、米国: Addison-Wesley Longman Publishing Co., Inc.
  9. ^ a b LaForest, Charles Eric (2007年4月). 「2.1 Lukasiewiczと第一世代：2.1.2 ドイツ：Konrad Zuse (1910–1995); 2.2 第一世代のスタックコンピュータ：2.2.1 Zuse Z4」.第二世代スタックコンピュータアーキテクチャ(PDF) (論文). ウォータールー、カナダ：ウォータールー大学. p. 8, 11, その他. 2022年1月20日時点のオリジナルよりアーカイブ(PDF) 。 2022年7月2日閲覧。（178ページ）[1]
  10. ^ Greve, David A.; Wilding, Matthew M. (1998-01-12). 「世界初のJavaプロセッサ」 . Electronic Engineering Times .
  11. ^ 「Mesaプロセッサの動作原理」 . DigiBarnコンピュータ博物館. Xerox. 2024年5月14日時点のオリジナルよりアーカイブ。2023年9月20日閲覧。
  12. ^ 「DigiBarn: Xerox Star 8010 "Dandelion"」「 . DigiBarnコンピュータ博物館. 2024年5月3日時点のオリジナルよりアーカイブ。2023年9月20日閲覧。
  13. ^ 「シングルチップ32ビットプロセッサの命令セット」ヒューレット・パッカード・ジャーナル34 (8)。ヒューレット・パッカード。1983年8月。2024年2月5日閲覧。
  14. ^ MARC4 4ビットマイクロコントローラプログラマーズガイド(PDF) . Atmel .
  15. ^ 「Forthチップ」 Colorforth.com . 2006年2月15日時点のオリジナルよりアーカイブ。2017年10月8日閲覧。
  16. ^ 「F21マイクロプロセッサの概要」 . Ultratechnology.com . 2017年10月8日閲覧。
  17. ^ "ForthFreak wiki" . GitHub.com . 2017年8月25日. 2017年10月8日閲覧。
  18. ^ 「Javaチップが利用可能に！」 Developer.com 1999年4月8日。2022年9月30日時点のオリジナルよりアーカイブ。2022年7月7日閲覧。
  19. ^ 「GNU CコンパイラのThorマイクロプロセッサへの移植」(PDF) 1995年12月4日. 2011年8月20日時点のオリジナル(PDF)からアーカイブ。 2011年3月30日閲覧。
  20. ^ 「ZPU - GCCツールチェーンを搭載した世界最小の32ビットCPU：概要」 opencores.org . 2015年2月7日閲覧。
  21. ^ Randell, Brian ; Russell, Lawford John (1964). Algol 60 の実装(PDF) . ロンドン, イギリス: Academic Press . ISBN 0-12-578150-4。{{cite book}}：ISBN / 日付の非互換性（ヘルプ）
  22. ^ 「Lua 5.0の実装」（PDF）
  23. ^ 「命令セット」。TrueTypeリファレンスマニュアル。
  24. ^ Duncan, Fraser George (1977-05-01). 「スタックマシン開発：オーストラリア、イギリス、ヨーロッパ」（PDF） . Computer . 第10巻、第5号. ブリストル大学、バージニア州ブリストル、米国. pp.  50– 52. doi : 10.1109/MC.1977.315873 . eISSN 1558-0814 . ISSN 0018-9162 . S2CID 17013010. CODEN CPTRB4 . 2023年10月15日時点のオリジナル（ PDF）からアーカイブ。 2023年10月15日閲覧。    （3ページ）
  25. ^ "colorForth の手順" . Colorforth.com . 2016年3月10日時点のオリジナルよりアーカイブ。2017年10月8日閲覧。(F18A コアの命令セット。歴史的な理由から colorForth と名付けられています。)
  26. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005). 「仮想マシン対決：スタック対レジスタ」.第1回ACM/USENIX国際仮想実行環境会議議事録. pp.  153– 163. doi : 10.1145/1064979.1065001 . ISBN 1595930477. S2CID  811512 .
  27. ^ハイド、ランドール(2004). 『素晴らしいコードを書く 第2巻：低レベルで考え、高レベルで書く』 第2巻. No Starch Press . p. 391. ISBN 978-1-59327-065-02021年6月30日閲覧。
  28. ^ジョン・L・ヘネシー、デイビッド・アンドリュー・パターソン著『コンピュータアーキテクチャ：定量的アプローチ』スタック マシンの説明を参照してください。
  29. ^ a b Koopman, Jr., Philip John. 「Stack Computers: the new wave」 . Ece.cmu.edu . 2017年10月8日閲覧。
  30. ^ Aシリーズシステム入門(PDF) . Burroughs Corporation . 1986年4月. 2023年9月20日閲覧。
  31. ^ 「効率的なスタックマシンの設計と実装」（PDF） . Jopdesign.com . 2017年10月8日閲覧。
  32. ^ Sinha, Steve; Chatterji, Satrajit; Ravindran, Kaushik. 「BOOST: Berkeley's Out of Order Stack Thingy」 . Research Gate . 2023年11月11日閲覧。
  33. ^ Bergh, Arndt; Keilman, Keith; Magenheimer, Daniel; Miller, James (1987年12月). 「HP Precision Architecture ComputersにおけるHP3000エミュレーション」(PDF) . Hewlett-Packard Journal . Hewlett-Packard : 87– 89. 2023年10月22日時点のオリジナル(PDF)からのアーカイブ。 2023年9月20日閲覧。
  34. ^ Kristy Andrews、Duane Sand（1992年10月）。「オブジェクトコード変換によるCISCコンピュータファミリのRISCへの移行」ASPLOS-V議事録。
  35. ^ 「文書」 . GreenArrays, Inc. F18Aテクノロジー. 2022年7月7日閲覧。
  36. ^ 8051 CPUマニュアル、Intel、1980年
  37. ^ Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertle, M. Anton. 「仮想マシン対決：スタック vs. レジスタマシン」（PDF） . Usenix.org . 2017年10月8日閲覧。
  38. ^ Davis, Brian; Beatty, Andrew; Casey, Kevin; Gregg, David; Waldron, John. 「仮想レジスタマシンの事例」(PDF) . Scss.tcd.ie. 2023年9月20日閲覧。
  39. ^ Bornstein, Dan (2008-05-29). 「Dalvik VM内部構造のプレゼンテーション」(PDF) . p. 22. 2008-09-05時点のオリジナル(PDF)からアーカイブ。2010-08-16閲覧。
  40. ^ 「Lua 5.0の実装」（PDF） . Lua.org . 2017年10月8日閲覧。
  41. ^ 「Lua 5.0の仮想マシン」（PDF） . Inf.puc-rio.br . 2017年10月8日閲覧。
  42. ^ 「分岐予測と通訳者のパフォーマンス - 民間伝承を信用するな」 Hal.inria.fr . 2023年9月20日閲覧。
「 https://en.wikipedia.org/w/index.php?title=Stack_machine&oldid=1335187459」より取得