スタックマシン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

スタックマシンstack machine)とは、メモリがスタックの形式になっている計算モデルを意味する。 スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。

加えて、スタックマシンは「0オペランド」命令セットのマシンも意味する。0オペランドマシンでは、命令は暗黙のうちにスタックのトップにある値を使って演算を行い、結果をスタックのトップに置く。そのようなマシンでも、メモリの任意の位置の読み書きをする "load" 命令や "store" 命令がある(ただし、アドレスは明示的に指定せず、スタックのトップにある値をアドレスとして使用する)。

スタックマシン(0オペランド命令セット)がアキュムレータマシン(1オペランド命令セット)やレジスタマシン(2オペランド命令セット、3オペランド命令セット)に比較して優れているのは、0オペランド命令セットで書かれたプログラムのコード密度が他の命令セットで書かれた同じプログラムに比較して一般に高い点である。

コールスタックを使って入れ子になったサブルーチン呼び出しの局所変数群を管理する方式のコンピュータをスタックマシンとは呼ばない(普通は)。

計算のスタックモデル[編集]

計算機科学オートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。

スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード(ポップ)すべき値の個数かスタックにライト(プッシュ)すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。

スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0n1n(0の並びの後に同じ個数の1が並ぶ言語)のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。

一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる(チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する)。

スタックマシン型命令セット[編集]

スタックマシン型の命令セットでは、例えば加算 (ADD) 命令はスタック上のトップにある2つの値を暗黙のうちにオペランドとして使用し、それらの和をスタックのトップに格納する。オペランドとして使用した値はスタックから取り除かれ(ポップ)、和をスタックのトップに置く(プッシュ)。ほとんどの命令は命令コードだけで構成され、レジスタ番号やメモリアドレスや即値を指定する必要がない。演算を行う場合、先にスタック上に演算対象の値をプッシュし、その後に演算命令を実行することになる。これは逆ポーランド記法と呼ばれる数式の表現方法と同じである。この場合、演算命令は容易に3つ以上の値を対象とするよう拡張可能である。メモリ上の任意のアドレスにあるデータをスタックにプッシュする命令や即値をスタックにプッシュする命令が必要となる。

スタックマシンと対比されるレジスタマシンは、高速で小さいレジスタファイルを持ち、一時的な値をレジスタに保持する。その中でもアキュムレータマシンはレジスタを1つだけ持ち、そのレジスタとオペランドで指定したメモリ位置との間で演算を行う。初期のコンピュータには一時レジスタを持たず、常にメモリ間で演算を行うものもあった。

スタックマシンの実装方式は2つあり、レジスタファイルのみを小さなスタックとして利用する実装と、スタック自体はメモリ上にあって、スタックのトップを指すレジスタを持つ実装である。後者の例としては、バロース B5000HP 3000 がある。稀に、メモリ上のスタックとレジスタファイルによる小さいスタックを別々のスタックとして持つ実装もある。

スタックベースの命令セットを持つマシンは、複数のスタックを持つことがある。2つのスタックを持つ場合、一方を「データスタック」、もう一方を「リターンスタック」と呼び、データスタックはデータの処理に使われ、リターンスタックはサブルーチンコールの戻りアドレスを保持するのに使われる(コールスタックとも)。

ヒューレット・パッカード電卓には逆ポーランド記法を採用しているものがあり、一種のスタックマシンと言える。加算を行う際は数値を2つ入力した後に "+" キーを押下する。2つの数値はスタックにプッシュされ、加算によってそれらの和と置換される。

オペランドとしてレジスタを使うマシンは、容易にスタックマシンをシミュレートできる。このようなシミュレーションを「仮想スタックマシン」とも呼ぶ。

利点[編集]

オブジェクトコードのコンパクトさ
オペランドを指定する必要がないため、個々の命令が一般に小さく、6ビット程度で済む。分岐命令、即値のロード命令、ロード/ストア命令はオペランドを必要とするが、多くの場合それらの命令もスタック上の値をオペランドとすることで命令を小さくできる。前の命令の結果をスタックに自動的にプッシュすることで、次の命令でそれを暗黙のうちに利用できる。対照的にレジスタマシンでは、ALU命令で2つまたは3つのレジスタを指定するオペランドを必要とし、1命令あたり少なくとも16ビット以上を必要とする。アキュムレータマシンはオペランドが1つだが、複雑な式を計算する際に一時変数へ値を退避しなければならないので、余計なロード/ストア命令を必要とする。スタックマシンでは、逆ポーランド記法が括弧を使わないことからもわかるように、一時変数への退避が発生しない。
プロシージャや関数の局所変数や引数にアクセスするため、スタックマシンにも一種のロード/ストア命令がある。スタックのトップのアドレスからのオフセットでアドレスを指定する場合やフレームベースを指すレジスタにオフセットを指定する場合などがある。レジスタマシンでは「レジスタ+オフセット」のアドレス指定に相当するが、一般にレジスタマシンの命令ではオフセットフィールドのビット幅が大きい。
1960年代、メインフレームであっても主記憶容量が小さかったため、コード密度を高くすることは重要な課題だった。初期のミニコンピュータマイクロコンピュータでも同様だった。もっと最近では携帯機器へのソフトウェアのダウンロードで、ダウンロード時間短縮のためにコード密度を高くする必要が生じた。コード密度が高ければ、キャッシュメモリや命令プリフェッチの効果が高まる。組み込みシステムでは搭載するROMを小さくできる。ただし、コード密度を高めすぎると実行性能が低下することがある。
バロースのアーキテクチャは、スタックマシンにタグ付きメモリを組み合わせたものである(各メモリワードの一部ビットでデータ型などを表す)。タグ付きメモリはオペコード(命令コード)の縮小に貢献している。つまり、整数や浮動小数点数といった区別はメモリワード自身が持っているので、命令コードで示す必要がない。スタックマシンであるためオペランドも少なく、結果として命令長が小さくて済むようになっている。
コンパイラの単純さ
スタックマシン向けのコンパイラは、相対的に単純であり、作成が容易である。特にコード生成は単純であり、前後関係を考慮する必要がなく、構文解析に容易に組み込める。レジスタ割り付けを考慮する必要がなく、定数参照や簡単なメモリ参照を最適化する必要がない。加算命令、インデックス付きロード命令、コール命令などは、複雑な式や入れ子のプロシージャ呼び出しであっても全く同じ命令コードを使うことができ、コンパイラが特殊ケースを考慮する必要がない。
コンパイラが単純ということは、メモリ容量の小さなマシンでもコンパイラを利用可能ということでもある。また、オペレーティングシステムを高水準言語で素早く開発することが可能で、バロース B5000HP 3000 で実際にそのように開発された。UCSD p-System が初期の8ビットマイクロプロセッサを使ったメモリ容量の小さなシステムで動作できたのも、仮想スタックマシンをターゲットとしてコンパイルしたためである。
コンパイラが単純ということは、コンパイラ最適化の最新技術の恩恵にあずかれないという欠点もある。スタックマシンでのコンパイラ最適化は不可能ではない。バックエンド部の最適化で劇的にコードの効率を向上させた例があり[1][2]、大域的な最適化でさらに性能向上させた例もある[3]
インタプリタの単純さ
スタックマシンの命令セットには、直接ハードウェアで実装するのではなく、仮想機械インタプリタ的に解釈することを意図したものもある。仮想スタックマシンのインタプリタは相対的に構築が容易である。これは、メモリアドレスとして基本的にスタックのトップだけを意識すればよいという性質に起因している。また命令の種類も相対的に少ない。
プロセッサの状態数が少ない
データスタックを持つマシンで必須となるレジスタは、スタックのトップのアドレスを保持するレジスタ(スタックポインタ)と、次の命令のアドレスを保持するレジスタ(命令ポインタ)だけである。このためコンテキストスイッチ割り込みの際にセーブすべき状態情報が小さい。

欠点[編集]

メモリ参照が多い
業界には、一時変数や局所変数の操作でレジスタマシンよりもスタックマシンの方がデータキャッシュに頻繁にアクセスするという見方もある[4]。一方、それとは全く逆の主張もある[5]。ここでは、スタックマシンにおけるメモリアクセスパターンを理解する必要がある。
スタックマシンでは一時変数がメモリに置かれることが多いのに対し、多数のレジスタを持つマシンでは一時変数はレジスタに保持され続ける。ただし、多数のレジスタがあるということは、割り込みやコンテキストスイッチでセーブ/リストアすべきデータが多いということも意味する。一時変数がメモリに置かれれば、データキャッシュへのアクセスは増えるが、その度合いはスタックのトップをどれだけレジスタ化しているかで変化するし、プロシージャコールが入れ子になる頻度や割り込み発生頻度によっても変わってくる。
スタックのトップ部分をレジスタ化していない単純な実装では、レジスタマシンよりも性能が低くなる。例えば X+1 という式はスタックマシンでは 'Load X; Load 1; Add' という3命令になる。これは、「Xをロードしてスタック(メモリ)にプッシュ。1をスタックにプッシュ。スタックから2つの値をポップしてそれらを加算し、結果をスタックにプッシュ」という意味であり、5回データキャッシュにアクセスすることになる。スタックのトップがレジスタ化されていても、最悪ケースではデータキャッシュのアクセス回数は減らない。レジスタマシンでは最適化によってなるべく値をレジスタに保持しようとするので、最初にXをロードするだけで済む。一方で、レジスタマシンはプロシージャコールの入れ子で一時変数として使っているレジスタの内容を一斉にメモリにセーブする必要が生じる。
共通部分式除去のコストが高い
レジスタマシンでは、同じ式の値を複数回使用する場合に、それを1回だけ計算して結果をレジスタに保持しておき、再利用することができる。スタックマシンで同じことをしようとすると、2つの方法が考えられる。1つは、共通部分式の計算結果をメモリ上の一時変数にセーブする方法である。しかし、これは共通部分式が単なるメモリ上の変数の参照などだった場合、全く最適化になっておらず、ある程度複雑な式でないと効果を生じない。そしてプログラマは複雑な式の結果をソースコード上で局所変数に格納し、何度も同じ式を書くことはしないのが一般的である。2つめは、共通部分式の計算結果をスタック上に残し、それを必要なだけ複製して利用する方法である。これは、"DUP"、"ROT"、"OVER" といったスタック操作を行ってもスタックがそれほど深くならない場合には効果的である。仮想スタックマシンの中には、"PICK" という命令でスタック内の指定した位置の値をスタックトップに複製する機能を持つものもある。Forthなどで書かれたプログラムはこのような技法を多用していることが多く、結果としてレジスタマシン並みの性能を達成している[6][5]。残念なことに、スタック・スケジューリングの最適化アルゴリズムは一般に知られておらず、スタックマシンを意識しない通常の言語でそのような最適化を行うことは難しい。結果としてスタックマシン向けコンパイラでは共通部分式除去などの最適化は行われていない。
コード順序の厳密性
最近のコンピュータでは、データをフェッチするのにかかる時間は、ALUで演算を行うのにかかる時間よりも長い。したがって、メモリ上のデータが実際に必要になるよりも十分前にフェッチを開始すれば、命令パイプラインをストールさせることなく高速に処理を継続できる。アウト・オブ・オーダー実行方式では、複数の命令をプロセッサが調べてそのような動作をしている。アウト・オブ・オーダー方式でなくともレジスタマシンであれば、コンパイラが賢ければそのようなコードを生成することができる[4]。この命令スケジューリングには使っていないレジスタがなければならない。従って純粋なスタックマシンにはこのような命令の並べ替えは不可能である。例えば A - B という式があるとき、スタックマシンではAとBをロードしてスタックにプッシュしてから即座に減算を行う。途中に別の命令を挟もうとしても、スタックマシンの命令は基本的にスタックをいじるので、ほとんど何もできない。スタックマシンでは、メモリからのロード遅延を隠蔽できるほど深いパイプラインでアウト・オブ・オーダー実行を行うか、ハードウェアマルチスレッディングでスレッドを切り換えてロード遅延を隠蔽するしかない。ユニシスのA9システムでは後者の方式を実装している[7]。最近では計算負荷の並列性が高まっており、この欠点は過去のものとなりつつある。
高速レジスタを隠蔽する
多くのスタックマシンは、スタックのトップN個の場所に対応するレジスタファイルを備えており、ロード命令やALU命令はその最上位近辺を対象とし、プッシュによってあふれた最下位のレジスタの内容はメモリ上のスタックに自動的に転送される。このため命令自体を小さくでき、命令のデコーダも小さくできる。しかし、命令が明示的にレジスタファイル内の個々のレジスタを指定できれば、コンパイラでレジスタの利用効率を向上させる最適化が可能となる。
HP 3000タンデムコンピューターズの T/16 はスタックマシンだが、RISCマシンへ移行する際にスタックマシンのコード列を等価なRISCのコード列に変換するトランスレータを用意した[8][9]。この際に局所的最適化を施して、スタックアーキテクチャのオーバーヘッドの多くを除去している。例えばアドレス計算の反復を、使ってないレジスタに保持することで1回にしている。変換後のコードにはマシン間のアーキテクチャの違いからエミュレーションによるオーバーヘッドが多々含まれていたが、スタックマシンでの実行効率とほぼ同程度の効率を達成している。そして、ソースコードをRISCマシン向けの最適化コンパイラで再コンパイルした場合、効率は倍化している。このことから、スタックマシンのアーキテクチャと非最適化コンパイラは、そのハードウェアの能力の半分を浪費していたと見られる。
レジスタファイルは、データキャッシュ経由のメモリ参照に比べると高帯域幅で低レイテンシである。ALUでの演算の場合、2つのレジスタを入力として1つのレジスタに演算結果を格納するまでを1サイクル以下で実行できる。一方データキャッシュは1サイクルに1回のアクセスしかできないため、同じことをしようとすると最低でも3サイクルかかることになり、実際にはそれぞれのアクセスが1サイクルで完了することはない。
仮想スタックマシンの問題点
仮想スタックマシン向けにプログラムをコンパイルすると、レジスタマシン向けよりも(コードサイズは小さくとも)命令数が多くなる。仮想スタックマシンを実装したインタプリタは、命令コードに従って分岐して対応する命令コードの処理を行う。また、スレッデッドコードで実装した場合も頻繁にジャンプを繰り返すことになる。このため、ホストマシンのパイプラインは仮想スタックマシンの命令をデコードして実行するたびにリスタートすることになる。個々の命令が単純で命令数が多くなるため、そのような状況はスタックマシン以外の仮想機械よりも仮想スタックマシンで発生しやすいと言われている[10][11]。AndroidのDalvik仮想マシンJavaを実行するが、本来のJava仮想マシンが8ビットのスタックマシンなのに対して、16ビットのレジスタマシンとなっている。これにより命令数を少なくし、命令コードディスパッチでのストールを低減している。算術命令は4ビット(以上)のオペランドを使って直接局所変数をフェッチまたはストアすることができる。

ハイブリッド方式[編集]

純粋なスタックマシンは、構造を持つデータオブジェクトの複数のフィールドにアクセスするのが不得意である。スタックマシンでは、オブジェクトのベースアドレスとフィールドのオフセットからアドレスを計算しなおして、ポインタをスタック上に置きなおす必要がある。一般的な対処方法としては、レジスタマシンの一部機能をスタックマシンに取り入れ、アドレス格納用にソフトウェアから見えるレジスタファイルを用意し、レジスタマシン風の命令でロードや単純なアドレス計算を行う。なお、レジスタファイルを汎用なものにするとスタックマシンである積極的な理由がなくなってしまう。

もう1つの一般的なハイブリッド方式として、レジスタマシンのアーキテクチャを出発点とし、スタックマシンでのプッシュおよびポップをエミュレートする操作を追加する方式がある。この方式を最初に採用したのは、DECPDP-11ミニコンピュータである。これがVAXに受け継がれ、MC6800MC68000といったマイクロプロセッサにも採用された。これにより初期のコンパイラでスタックを簡単に扱えるようになった。また、スタックインタプリタまたはスレッデッドコードを使って仮想機械を効率的にサポートする。ただし、これによってレジスタマシンのコードが純粋なスタックマシンほどコンパクトになるわけではない。このようなハイブリッド方式のマシンで、スタックマシンのように頻繁にプッシュやポップを行うと性能は悪くなる。スタック操作はプロシージャコールの際にのみ行う方がよく、当然ながらメモリ参照せずにレジスタのみで処理するのが最善である。

第2世代スタックマシンと呼ばれるものは、データスタックからメモリアドレッシングの処理を肩代わりするアドレスレジスタ群を備えている。例えば、MuP21は "A" というレジスタを持っており、もっと最近の GreenArrays のプロセッサは A と B という2つのレジスタを持っている[5]

x86ファミリは基本的にレジスタ指向の命令セットだが、最初のFPUである Intel 8087 はスタックマシンの命令セットを採用していた。

実用化されたスタックマシン[編集]

ハードウェアで直接実行されるスタックマシン型命令セットの例を挙げる。

仮想スタックマシン[編集]

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

コールスタックとスタックフレームを使ったコンピュータ[編集]

現代のほとんどのコンピュータ(命令セットを問わない)とほとんどのコンパイラは、メモリ上のコールスタックを局所変数の格納場所およびサブルーチンからの復帰のための情報格納に使っている。サブルーチンコールのたびに「スタックフレーム」をコールスタック上に作り、そのサブルーチンから呼び出し側に復帰するまで対応するスタックフレームが維持される。コールスタックを特別なアドレスレジスタなどを使ってハードウェアで管理する場合もある。あるいは、コンパイラの呼出規約によって特定の汎用レジスタをコールスタック処理に使う場合もある。

一般にコンピュータは、大域変数とその時点で実行中のプロシージャまたは関数の局所変数への効率的アクセス手段を提供する。一般に呼び出し側のプロシージャまたは関数のスタックフレームを遡ってアクセスする必要性はほとんどなく、ハードウェアが直接そのような手段を提供することもない。必要ならば、スタックフレーム内にあるフレームポインタで遡ることもできる。

バロース B5000 ではハードウェアでスタックフレームを遡る手段を提供しているが、これは動的な入れ子構造ではなく、プログラムの静的な入れ子構造(変数のスコープ)を辿るものである。その後このような機能をハードウェアで実装した例はない。ニクラウス・ヴィルトCDC 6000 シリーズ向けにPascalコンパイラを開発した際、フレームポインタを配列に格納して常に更新するよりも、コールスタック上のフレームポインタを遡ってたどった方が全体として高速だということを発見した。この方式だと、遡って参照することのないC言語などのプログラミング言語でも、余計なオーバーヘッドが発生しない。

バロース B5000 では、タスクまたはスレッドの入れ子もサポートしている。あるタスクとそのタスクを作ったタスクは、タスク作成時点のスタックフレームを共有するが、作成した側の次のフレームや作成されたタスク自身のフレームは共有されない。そのため西部劇でよく見るようなサボテンのようなスタック構造になる。各タスクは自身のスタックとフレームを保持するメモリセグメントを持つ。そのスタックのベースは作成した側のスタックの途中とリンクされている。一般的なフラットなアドレス空間を持つマシンでは、あるタスクのスタックとそれを作成した側のスタックは1つのヒープ内の別々のヒープオブジェクトになる。

プログラミング言語によっては、外側のスコープのデータ環境が常に入れ子になっているわけではない。そのような言語では、1つのスタックにスタックフレームを積んでいくのではなく、別個のヒープオブジェクトとしてプロシージャの「アクティベーション・レコード」を編成する。

Forthのような単純な言語では、局所変数やパラメータの名前がなく、スタックフレームにはリターンアドレス以外に何も必要としない。そのため、リターンスタックにはフレームが存在せず、単にリターンアドレスが格納される。リターンスタックとデータスタックは分離しており、プロシージャの呼び出しと復帰は高速に行われる。

脚注・出典[編集]

  1. ^ Koopman, Philip (1994). “A Preliminary Exploration of Optimized Stack Code Generation”. Journal of Forth applications and Research 6 (3). http://www.ece.cmu.edu/~koopman/stack_compiler/stack_co.pdf. 
  2. ^ Bailey, Chris (2000). “Inter-Boundary Scheduling of Stack Operands: A preliminary Study”. Proceedings of Euroforth 2000 Conference. http://www.complang.tuwien.ac.at/anton/euroforth/ef00/bailey00.pdf. 
  3. ^ Shannon, Mark; Bailey C (2006). “Global Stack Allocation : Register Allocation for Stack Machines”. Proceedings of Euroforth Conference 2006. http://www.complang.tuwien.ac.at/anton/euroforth2006/papers/shannon.pdf. 
  4. ^ a b "Computer Architecture: A Quantitative Approach", John L Hennessy, David A Patterson; See the discussion of stack machines.
  5. ^ a b c LaForest, Charles Eric (2007), Second-Generation Stack Computer Architecture, http://www.eecg.utoronto.ca/~laforest/Second-Generation_Stack_Computer_Architecture.pdf 
  6. ^ Stack Computers: the new wave book by Philip J. Koopman, Jr. 1989
  7. ^ 'Introduction to A Series Systems', Burroughs Corporation, page 41,
  8. ^ HP3000 Emulation on HP Precision Architecture Computers, Arndt Bergh, Keith Keilman, Daniel Magenheimer, and James Miller, Hewlett-Packard Journal, Dec 1987, p87-89,
  9. ^ Migrating a CISC Computer Family onto RISC via Object Code Translation, K. Andrews and D. Sand, Proceedings of ASPLOS-V, October, 1992
  10. ^ "Virtual Machine Showdown: Stack vs. Registers", Yunhe Shi, David Gregg, Andrew Beatty, M. Anton Ertle,
  11. ^ 'The Case for Virtual Register Machines', Brian Davis, Andrew Beatty, Kevin Casey, David Gregg and John Waldron
  12. ^ "The World's First Java Processor", by David A. Greve and Matthew M. Wilding, Electronic Engineering Times, Jan. 12, 1998,
  13. ^ 'MARC4 4-bit Microcontrollers Programmers Guide', Atmel, http://www.atmel.com/dyn/resources/prod_documents/doc4747.pdf
  14. ^ Forth chips
  15. ^ F21 Microprocessor Overview
  16. ^ PSC1000 Microprocessor Reference Manual, Patriot Scientific Corporation
  17. ^ The 4stack processor by Bernd Paysan
  18. ^ 'Porting the GNU C Compiler to the Thor Microprocessor', Harry Gunnarsson and Thomas Lundqvist

外部リンク[編集]