|
|
| 1行目: |
1行目: |
| − | '''スタックマシン'''（''stack machine''）とは、メモリが[[スタック]]の形式になっている計算モデルを意味する。 | + | '''スタックマシン'''（''stack machine''） |
| | + | |
| | + | メモリが[[スタック]]の形式になっている計算モデルを意味する。 |
| | スタックマシンを実装あるいはシミュレートしている実在の[[コンピュータ]]もスタックマシンと呼ぶ。 | | スタックマシンを実装あるいはシミュレートしている実在の[[コンピュータ]]もスタックマシンと呼ぶ。 |
| | | | |
| 8行目: |
10行目: |
| | [[コールスタック]]を使って入れ子になった[[サブルーチン]]呼び出しの局所変数群を管理する方式のコンピュータを'''スタックマシン'''とは'''呼ばない'''（普通は）。 | | [[コールスタック]]を使って入れ子になった[[サブルーチン]]呼び出しの局所変数群を管理する方式のコンピュータを'''スタックマシン'''とは'''呼ばない'''（普通は）。 |
| | | | |
| − | == 計算のスタックモデル ==
| + | {{テンプレート:20180815sk}} |
| − | [[計算機科学]]の[[オートマトン]]理論における「スタックマシン」は、メモリにランダムアクセスすることができず、[[LIFO]]型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。
| |
| − | | |
| − | スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード（ポップ）すべき値の個数かスタックにライト（プッシュ）すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態では[[アルファベット (計算機科学)|アルファベット]]それぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。
| |
| − | | |
| − | スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0<sup>n</sup>1<sup>n</sup>（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、[[有限オートマトン]]よりも高いが、[[プッシュダウン・オートマトン|決定性プッシュダウン・オートマトン]]よりも低い。
| |
| − | | |
| − | 一方、複数のスタックを持つスタックマシンは[[チューリングマシン]]と等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる（チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する）。
| |
| − | | |
| − | == スタックマシン型命令セット ==
| |
| − | スタックマシン型の命令セットでは、例えば加算 (ADD) 命令はスタック上のトップにある2つの値を暗黙のうちにオペランドとして使用し、それらの和をスタックのトップに格納する。オペランドとして使用した値はスタックから取り除かれ（ポップ）、和をスタックのトップに置く（プッシュ）。ほとんどの命令は命令コードだけで構成され、レジスタ番号やメモリアドレスや即値を指定する必要がない。演算を行う場合、先にスタック上に演算対象の値をプッシュし、その後に演算命令を実行することになる。これは[[逆ポーランド記法]]と呼ばれる数式の表現方法と同じである。この場合、演算命令は容易に3つ以上の値を対象とするよう拡張可能である。メモリ上の任意のアドレスにあるデータをスタックにプッシュする命令や即値をスタックにプッシュする命令が必要となる。
| |
| − | | |
| − | スタックマシンと対比されるレジスタマシンは、高速で小さい[[レジスタファイル]]を持ち、一時的な値をレジスタに保持する。その中でも[[アキュムレータ (コンピュータ)|アキュムレータマシン]]はレジスタを1つだけ持ち、そのレジスタとオペランドで指定したメモリ位置との間で演算を行う。初期のコンピュータには一時レジスタを持たず、常にメモリ間で演算を行うものもあった。
| |
| − | | |
| − | スタックマシンの実装方式は2つあり、[[レジスタファイル]]のみを小さなスタックとして利用する実装と、スタック自体はメモリ上にあって、スタックのトップを指すレジスタを持つ実装である。後者の例としては、[[バロース B5000]] や [[HP 3000]] がある。稀に、メモリ上のスタックとレジスタファイルによる小さいスタックを別々のスタックとして持つ実装もある。
| |
| − | | |
| − | 回路素子の高速化によりメモリアクセスなどの配線遅延が問題となるに連れて、スタックを階層構造のキャッシュに収める実装が現れた。明示的なロード命令を用いない限り、スタック内のオペランドが使われる順序は、スタックトップから下方へ積まれている順序と一致する。このため、スタックトップから優先してより高速の記憶素子に収められた状態を保つだけで、オペランドの強力なプリフェッチが実現され、配線遅延が隠蔽される。仮想スタックマシンの多くでは、スタックトップはメモリ領域ではなくホストマシンのレジスタファイルで実装されるレジスタで実現されている。FPGA上のJAVAプロセッサである[http://www.jopdesign.com/ JOP]では、レジスタファイルよりさらに高速で小さい記憶素子である、命令パイプライン上の[[ラッチ回路]]をスタックトップ2個に充てている。
| |
| − | | |
| − | スタックベースの命令セットを持つマシンは、複数のスタックを持つことがある。2つのスタックを持つ場合、一方を「データスタック」、もう一方を「リターンスタック」と呼び、データスタックはデータの処理に使われ、リターンスタックは[[サブルーチン]]コールの戻りアドレスを保持するのに使われる（[[コールスタック]]とも）。データスタックとリターンスタックを分離すると、スタック管理処理の大部分を排除して、全体の動作を大幅に高速化できる。このスタックを2つ持つという方式は独自に3回発明されている(バロース B5000、Forth、[[PostScript]])。また、[[Java仮想マシン]]でも使われている。
| |
| − | | |
| − | [[ヒューレット・パッカード]]の[[関数電卓]]が有名だが、一種のスタックマシンを操作モデルとしている電卓がある。プッシュに相当する「Enter」キーが特徴である。具体例で説明すると、加算を行う際は、「数値1」「Enter」「数値2」「+」の順に操作する。この操作で、まず2つの数値がスタックにプッシュされた後、加算のためにポップされ加算され結果がプッシュされる。逆ポーランド記法(順)の電卓、と呼ばれている。
| |
| − | | |
| − | オペランドとして[[レジスタ (コンピュータ)|レジスタ]]を使うマシンは、容易にスタックマシンをシミュレートできる。このような[[シミュレーション]]を「仮想スタックマシン」とも呼ぶ。
| |
| − | | |
| − | === 利点 ===
| |
| − | ; オブジェクトコードのコンパクトさ
| |
| − | : オペランドを指定する必要がないため、個々の命令が一般に小さく、6ビット程度で済む。分岐命令、即値のロード命令、ロード/ストア命令はオペランドを必要とするが、多くの場合それらの命令もスタック上の値をオペランドとすることで命令を小さくできる。前の命令の結果をスタックに自動的にプッシュすることで、次の命令でそれを暗黙のうちに利用できる。対照的にレジスタマシンでは、ALU命令で2つまたは3つのレジスタを指定するオペランドを必要とし、1命令あたり少なくとも16ビット以上を必要とする。アキュムレータマシンはオペランドが1つだが、複雑な式を計算する際に一時変数へ値を退避しなければならないので、余計なロード/ストア命令を必要とする。スタックマシンでは、逆ポーランド記法が括弧を使わないことからもわかるように、一時変数への退避が発生しない。
| |
| − | : プロシージャや関数の局所変数や引数にアクセスするため、スタックマシンにも一種のロード/ストア命令がある。スタックのトップのアドレスからのオフセットでアドレスを指定する場合やフレームベースを指すレジスタにオフセットを指定する場合などがある。レジスタマシンでは「レジスタ+オフセット」のアドレス指定に相当するが、一般にレジスタマシンの命令ではオフセットフィールドのビット幅が大きい。
| |
| − | : 1960年代、メインフレームであっても主記憶容量が小さかったため、[[命令セット#コード密度|コード密度]]を高くすることは重要な課題だった。初期の[[ミニコンピュータ]]や[[マイクロコンピュータ]]でも同様だった。もっと最近では携帯機器へのソフトウェアのダウンロードで、ダウンロード時間短縮のためにコード密度を高くする必要が生じた。コード密度が高ければ、[[キャッシュメモリ]]や命令[[プリフェッチ]]の効果が高まる。[[組み込みシステム]]では搭載するROMを小さくできる。ただし、コード密度を高めすぎると実行性能が低下することがある。
| |
| − | : バロースのアーキテクチャは、スタックマシンにタグ付きメモリを組み合わせたものである（各メモリワードの一部ビットでデータ型などを表す）。タグ付きメモリは[[オペコード]]（命令コード）の縮小に貢献している。つまり、整数や浮動小数点数といった区別はメモリワード自身が持っているので、命令コードで示す必要がない。スタックマシンであるためオペランドも少なく、結果として命令長が小さくて済むようになっている。
| |
| − | ; コンパイラの単純さ
| |
| − | : スタックマシン向けの[[コンパイラ]]は、相対的に単純であり、作成が容易である。特に[[コード生成]]は単純であり、前後関係を考慮する必要がなく、[[構文解析]]に容易に組み込める。[[レジスタ割り付け]]を考慮する必要がなく、定数参照や簡単なメモリ参照を最適化する必要がない。加算命令、インデックス付きロード命令、コール命令などは、複雑な式や入れ子のプロシージャ呼び出しであっても全く同じ命令コードを使うことができ、コンパイラが特殊ケースを考慮する必要がない。
| |
| − | : コンパイラが単純ということは、メモリ容量の小さなマシンでもコンパイラを利用可能ということでもある。また、[[オペレーティングシステム]]を高水準言語で素早く開発することが可能で、[[バロース B5000]] や [[HP 3000]] で実際にそのように開発された。[[UCSD p-System]] が初期の8ビットマイクロプロセッサを使ったメモリ容量の小さなシステムで動作できたのも、仮想スタックマシンをターゲットとしてコンパイルしたためである。
| |
| − | : コンパイラが単純ということは、[[コンパイラ最適化]]の最新技術の恩恵にあずかれないという欠点もある。スタックマシンでのコンパイラ最適化は不可能ではない。バックエンド部の最適化で劇的にコードの効率を向上させた例があり<ref>{{Cite journal|last=Koopman|first=Philip|title=A Preliminary Exploration of Optimized Stack Code Generation|journal=Journal of Forth applications and Research|year=1994|volume=6|issue=3|url= http://www.ece.cmu.edu/~koopman/stack_compiler/stack_co.pdf}}</ref><ref>{{Cite journal|last=Bailey|first=Chris|title=Inter-Boundary Scheduling of Stack Operands: A preliminary Study|journal=Proceedings of Euroforth 2000 Conference|year=2000|url= http://www.complang.tuwien.ac.at/anton/euroforth/ef00/bailey00.pdf}}</ref>、大域的な最適化でさらに性能向上させた例もある<ref>{{Cite journal|last=Shannon|first=Mark|coauthors=Bailey C|title=Global Stack Allocation : Register Allocation for Stack Machines|journal=Proceedings of Euroforth Conference 2006|year=2006|url= http://www.complang.tuwien.ac.at/anton/euroforth2006/papers/shannon.pdf}}</ref>。
| |
| − | ; インタプリタの単純さ
| |
| − | : スタックマシンの命令セットには、直接ハードウェアで実装するのではなく、[[仮想機械]]で[[インタプリタ]]的に解釈することを意図したものもある。仮想スタックマシンのインタプリタは相対的に構築が容易である。これは、メモリアドレスとして基本的にスタックのトップだけを意識すればよいという性質に起因している。また命令の種類も相対的に少ない。
| |
| − | ; プロセッサの状態数が少ない
| |
| − | : データスタックを持つマシンで必須となるレジスタは、スタックのトップのアドレスを保持するレジスタ（スタックポインタ）と、次の命令のアドレスを保持するレジスタ（命令ポインタ）だけである。このため[[コンテキストスイッチ]]や[[割り込み]]の際にセーブすべき状態情報が小さい。
| |
| − | ;高速なオペランドアクセス
| |
| − | :レジスタマシンと異なりオペランドを指定する領域が命令内に存在しないため、命令の読み出し・デコードと並行して、その命令が使用するオペランドの読み出しを行うことが出来る。加えて、明示的なロード命令を用いない限り、スタック内のオペランドが使われる順序は、スタックトップから下方へ積まれている順序と一致する。このため、スタックトップから優先して[[レジスタファイル]]などにキャッシュされた状態を保つだけで、オペランドの強力なプリフェッチが実現される。さらに、各命令のオペランドが取り出される場所はスタックトップ数個の範囲内に絞られるため、このスタックトップ数個をキャッシュする代わりに命令パイプライン内のフォアワーディング回路に流すことで、レジスタファイルへのアクセスを命令パイプラインの実行ステージ以前のステージから排除できる。このようにレジスタマシンと比較して命令パイプラインの長さを短く出来るため、より高い動作周波数、または、より少ない[[遅延スロット]]を実現できる。
| |
| − | :仮想マシンの場合でも、この性質は有用である。ハードウェアでのフォアワーディング回路の代わりに、スタックトップをレジスタにキャッシュする実装が広く行われており、メモリロード遅延の影響が抑えられている。レジスタマシンを仮想マシンで実装する場合、多くのホストマシンでは実行時にレジスタを番号で参照することができないため、番号で参照するならメモリ配列を用いる方が単純かつ高速となる。また、仮想マシンの管理用にホストマシンのレジスタが消費されるため、ターゲットマシンのレジスタの全てを実装するにはホストマシンのレジスタが足りなくなる事もある。このため、ターゲットマシンのレジスタを実装するのにホストマシンのメモリ領域が使われる事が多い。
| |
| − | | |
| − | === 欠点 ===
| |
| − | ; メモリ参照が多い
| |
| − | : 業界には、一時変数や局所変数の操作でレジスタマシンよりもスタックマシンの方がデータキャッシュに頻繁にアクセスするという見方もある<ref name="Hennesy">"Computer Architecture: A Quantitative Approach", John L Hennessy, David A Patterson; See the discussion of stack machines.</ref>。一方、それとは全く逆の主張もある<ref name="LaForest2007" />。ここでは、スタックマシンにおけるメモリアクセスパターンを理解する必要がある。
| |
| − | : スタックマシンでは一時変数がメモリに置かれることが多いのに対し、多数のレジスタを持つマシンでは一時変数はレジスタに保持され続ける。ただし、多数のレジスタがあるということは、割り込みやコンテキストスイッチでセーブ/リストアすべきデータが多いということも意味する。一時変数がメモリに置かれれば、データキャッシュへのアクセスは増えるが、その度合いはスタックのトップをどれだけレジスタ化しているかで変化するし、プロシージャコールが入れ子になる頻度や割り込み発生頻度によっても変わってくる。
| |
| − | : スタックのトップ部分をレジスタ化していない単純な実装では、レジスタマシンよりも性能が低くなる。例えば X+1 という式はスタックマシンでは 'Load X; Load 1; Add' という3命令になる。これは、「Xをロードしてスタック（メモリ）にプッシュ。1をスタックにプッシュ。スタックから2つの値をポップしてそれらを加算し、結果をスタックにプッシュ」という意味であり、5回データキャッシュにアクセスすることになる。スタックのトップがレジスタ化されていても、最悪ケースではデータキャッシュのアクセス回数は減らない。レジスタマシンでは最適化によってなるべく値をレジスタに保持しようとするので、最初にXをロードするだけで済む。一方で、レジスタマシンはプロシージャコールの入れ子で一時変数として使っているレジスタの内容を一斉にメモリにセーブする必要が生じる。
| |
| − | ; [[共通部分式除去]]のコストが高い
| |
| − | : レジスタマシンでは、同じ式の値を複数回使用する場合に、それを1回だけ計算して結果をレジスタに保持しておき、再利用することができる。スタックマシンで同じことをしようとすると、2つの方法が考えられる。1つは、共通部分式の計算結果をメモリ上の一時変数にセーブする方法である。しかし、これは共通部分式が単なるメモリ上の変数の参照などだった場合、全く最適化になっておらず、ある程度複雑な式でないと効果を生じない。そしてプログラマは複雑な式の結果をソースコード上で局所変数に格納し、何度も同じ式を書くことはしないのが一般的である。2つめは、共通部分式の計算結果をスタック上に残し、それを必要なだけ複製して利用する方法である。これは、"DUP"、"ROT"、"OVER" といったスタック操作を行ってもスタックがそれほど深くならない場合には効果的である。仮想スタックマシンの中には、"PICK" という命令でスタック内の指定した位置の値をスタックトップに複製する機能を持つものもある。[[Forth]]などで書かれたプログラムはこのような技法を多用していることが多く、結果としてレジスタマシン並みの性能を達成している<ref>[http://www.ece.cmu.edu/~koopman/stack_computers/ ''Stack Computers: the new wave''] book by Philip J. Koopman, Jr. 1989</ref><ref name="LaForest2007" />。しかし、スタック・スケジューリングの最適化アルゴリズムは一般に知られておらず、スタックマシンを意識しない通常の言語でそのような最適化を行うことは難しい。結果としてスタックマシン向けコンパイラでは[[共通部分式除去]]などの最適化は行われていない。
| |
| − | ; コード順序の厳密性
| |
| − | : 最近のコンピュータでは、データをフェッチするのにかかる時間は、ALUで演算を行うのにかかる時間よりも長い。したがって、メモリ上のデータが実際に必要になるよりも十分前にフェッチを開始すれば、[[命令パイプライン]]をストールさせることなく高速に処理を継続できる。[[アウト・オブ・オーダー実行]]方式では、複数の命令をプロセッサが調べてそのような動作をしている。アウト・オブ・オーダー方式でなくともレジスタマシンであれば、コンパイラが賢ければそのようなコードを生成することができる<ref name="Hennesy" />。この命令スケジューリングには使っていないレジスタがなければならない。従って純粋なスタックマシンにはこのような命令の並べ替えは不可能である。例えば A - B という式があるとき、スタックマシンではAとBをロードしてスタックにプッシュしてから即座に減算を行う。途中に別の命令を挟もうとしても、スタックマシンの命令は基本的にスタックをいじるので、ほとんど何もできない。スタックマシンでは、メモリからのロード遅延を隠蔽できるほど深いパイプラインでアウト・オブ・オーダー実行を行うか、[[ハードウェアマルチスレッディング]]でスレッドを切り換えてロード遅延を隠蔽するしかない。ユニシスのA9システムでは後者の方式を実装している<ref>[http://www.bitsavers.org/pdf/burroughs/A-Series/1170057_aSeries_Intro_apr86.pdf 'Introduction to A Series Systems'], Burroughs Corporation, page 41,</ref>。最近では計算負荷の並列性が高まっており、この欠点は過去のものとなりつつある。
| |
| − | :スタックトップの内容を追跡する事によって、この欠点は克服されている。例えば、スタックトップ2個がレジスタ化されているインタプリタで"A B C - /"という式(逆ポーランド記法の場合。通常記法での"A / (B - C)"に当たる。)を計算するとき、"Aのロード"と"B C - の演算"の両方とも、結果がレジスタに格納される。[[レジスタ・リネーミング]]を行う物理プロセッサでは、レジスタ間演算の依存関係を認識してアウト・オブ・オーダー実行が行われる。このため、"Aのロード"と"B C - の演算"に依存関係がなく並べ替えが可能であることを物理プロセッサは認識し、"Aのロード"の途中で"B C - の演算"を挟む。[[Mops]]をx86_64(レジスタマシン)向けにコンパイルするiMopsでは、コンパイル時に追跡可能なスタックをノードとするノードグラフを対象にレジスタ割り当てを行い、プロセッサによる命令並べ替えを助ける[http://www18.atwiki.jp/imops-forth/pages/15.html]。物理スタックマシンについても、レジスタマシンで論理レジスタをレジスタ・リネーミングするのと同様に、スタックなどのメモリ領域をリネーミングすることで[[Tomasuloのアルゴリズム]]の実装が可能だと言われている<ref name="boost">{{cite web|last1=Chatterji|first1=Satrajit|last2=Ravindran|first2=Kaushik|title=BOOST: Berkeley's Out of Order Stack Thingy|url=https://www.researchgate.net/publication/228556746_BOOST_Berkeley's_Out-of-Order_Stack_Thingy|website=Research Gate|publisher=Kaushik Ravindran|accessdate=16 February 2016|ref=boost}}</ref>。
| |
| − | ; 高速レジスタを隠蔽する
| |
| − | : 多くのスタックマシンは、スタックのトップN個の場所に対応する[[レジスタファイル]]を備えており、ロード命令やALU命令はその最上位近辺を対象とし、プッシュによってあふれた最下位のレジスタの内容はメモリ上のスタックに自動的に転送される。このため命令自体を小さくでき、命令のデコーダも小さくできる。しかし、命令が明示的にレジスタファイル内の個々のレジスタを指定できれば、コンパイラでレジスタの利用効率を向上させる最適化が可能となる。
| |
| − | : [[HP 3000]] や[[タンデムコンピューターズ]]の T/16 はスタックマシンだが、[[RISC]]マシンへ移行する際にスタックマシンのコード列を等価な[[RISC]]のコード列に変換するトランスレータを用意した<ref>HP3000 Emulation on HP Precision Architecture Computers, Arndt Bergh, Keith Keilman, Daniel Magenheimer, and James Miller, [http://www.hpl.hp.com/hpjournal/pdfs/IssuePDFs/1987-12.pdf Hewlett-Packard Journal, Dec 1987], p87-89, </ref><ref>Migrating a CISC Computer Family onto RISC via Object Code Translation, K. Andrews and D. Sand, Proceedings of ASPLOS-V, October, 1992</ref>。この際に局所的最適化を施して、スタックアーキテクチャのオーバーヘッドの多くを除去している。例えばアドレス計算の反復を、使ってないレジスタに保持することで1回にしている。変換後のコードにはマシン間のアーキテクチャの違いからエミュレーションによるオーバーヘッドが多々含まれていたが、スタックマシンでの実行効率とほぼ同程度の効率を達成している。そして、ソースコードをRISCマシン向けの最適化コンパイラで再コンパイルした場合、効率は倍化している。このことから、スタックマシンのアーキテクチャと非最適化コンパイラは、そのハードウェアの能力の半分を浪費していたと見られる。
| |
| − | : レジスタファイルは、データキャッシュ経由のメモリ参照に比べると高帯域幅で低レイテンシである。ALUでの演算の場合、2つのレジスタを入力として1つのレジスタに演算結果を格納するまでを1サイクル以下で実行できる。一方データキャッシュは1サイクルに1回のアクセスしかできないため、同じことをしようとすると最低でも3サイクルかかることになり、実際にはそれぞれのアクセスが1サイクルで完了することはない。
| |
| − | ; 仮想スタックマシンの問題点
| |
| − | : 仮想スタックマシン向けにプログラムをコンパイルすると、レジスタマシン向けよりも（コードサイズは小さくとも）命令数が多くなる。仮想スタックマシンを実装したインタプリタは、命令コードに従って分岐して対応する命令コードの処理を行う。また、[[スレッデッドコード]]で実装した場合も頻繁に分岐を繰り返すことになる。インタプリタの分岐先は命令コードの種類という膨大な数であり、その様な分岐を効率よく行うため、[[間接分岐命令]]が使われる。ところが初期の[[分岐予測]]機構では、間接分岐命令への対応が欠けている。このため、仮想スタックマシンの命令をデコードして実行するたびに、ホストマシンのパイプラインは誤った分岐先を投機実行し、修正のためリスタートすることになる。個々の命令が単純で命令数が多くなるため、そのような状況はスタックマシン以外の仮想機械よりも仮想スタックマシンで発生しやすいと言われている<ref>[http://usenix.org/events/vee05/full_papers/p153-yunhe.pdf "Virtual Machine Showdown: Stack vs. Registers"], Yunhe Shi, David Gregg, Andrew Beatty, M. Anton Ertle </ref><ref>[http://www.scss.tcd.ie/David.Gregg/papers/Gregg-SoCP-2005.pdf 'The Case for Virtual Register Machines'], Brian Davis, Andrew Beatty, Kevin Casey, David Gregg and John Waldron</ref>。Androidの[[Dalvik仮想マシン]]は[[Java]]を実行するが、本来の[[Java仮想マシン]]が8ビットのスタックマシンなのに対して、16ビットのレジスタマシンとなっている。これにより命令数を少なくし、命令コードディスパッチでのストールを低減している。算術命令は4ビット（以上）のオペランドを使って直接局所変数をフェッチまたはストアすることができる。
| |
| − | : ただし、分岐予測が成功している場合、パイプラインのリスタートは生じず、予測と実行後の分岐先を比較するALU演算程度まで分岐命令のコストは低下する。Java仮想マシンインタプリタの普及に伴い、インタプリタにも対応できる分岐予測器を積んだプロセッサが普及しており<ref>[https://hal.inria.fr/hal-01100647/document "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore"] Erven Rohou, Bharath Narasimha Swamy, Andr ́e Seznec</ref>、この問題でのレジスタマシンとスタックマシンとの差は縮まっている。
| |
| − | | |
| − | === ハイブリッド方式 ===
| |
| − | 純粋なスタックマシンは、構造を持つデータオブジェクトの複数のフィールドにアクセスするのが不得意である。スタックマシンでは、オブジェクトのベースアドレスとフィールドのオフセットからアドレスを計算しなおして、ポインタをスタック上に置きなおす必要がある。一般的な対処方法としては、[[レジスタマシン]]の一部機能をスタックマシンに取り入れ、アドレス格納用にソフトウェアから見える[[レジスタファイル]]を用意し、レジスタマシン風の命令でロードや単純なアドレス計算を行う。なお、レジスタファイルを汎用なものにするとスタックマシンである積極的な理由がなくなってしまう。
| |
| − | | |
| − | もう1つの一般的なハイブリッド方式として、レジスタマシンのアーキテクチャを出発点とし、スタックマシンでのプッシュおよびポップをエミュレートする操作を追加する方式がある。この方式をポピュラーなものにしたのは、[[ディジタル・イクイップメント・コーポレーション|DEC]]の[[PDP-11]]ミニコンピュータである。これが[[VAX]]に受け継がれ、[[MC6800]]や[[MC68000]]といったマイクロプロセッサにも採用された。これにより初期のコンパイラでスタックを簡単に扱えるようになった。また、スタックインタプリタまたは[[スレッデッドコード]]を使って[[仮想機械]]を効率的にサポートする。ただし、これによってレジスタマシンのコードが純粋なスタックマシンほどコンパクトになるわけではない。このようなハイブリッド方式のマシンで、スタックマシンのように頻繁にプッシュやポップを行うと性能は悪くなる。スタック操作はプロシージャコールの際にのみ行う方がよく、当然ながらメモリ参照せずにレジスタのみで処理するのが最善である。
| |
| − | | |
| − | 第2世代スタックマシンと呼ばれるものは、データスタックからメモリアドレッシングの処理を肩代わりするアドレスレジスタ群を備えている。例えば、MuP21は "A" というレジスタを持っており、もっと最近の GreenArrays のプロセッサは A と B という2つのレジスタを持っている<ref name="LaForest2007">{{Citation|first=Charles Eric |last=LaForest |url= http://www.eecg.utoronto.ca/~laforest/Second-Generation_Stack_Computer_Architecture.pdf |title= Second-Generation Stack Computer Architecture |year=2007}}</ref>。
| |
| − | | |
| − | [[x86]]ファミリは基本的にレジスタ指向の命令セットだが、初期は外付けされ、後には内蔵・一体化された、浮動小数点関係の[[x87]]命令と浮動小数点レジスタは、スタック(マシン)指向である。これも一種のハイブリッドと言えよう。これは初期（1980年代）に、命令空間やチップ面積を節約する必要があったためである。現代の64ビット化されたx86である[[x64]]では、（互換のために従来のFPUも残されているが）通常使用される[[Streaming SIMD Extensions|SSE]]の浮動小数点関係の命令も全てレジスタ指向の命令（レジスタ指向のSIMD命令）となっている。
| |
| − | | |
| − | === 実用化されたスタックマシン ===
| |
| − | ハードウェアで直接実行されるスタックマシン型[[命令セット]]の例を挙げる。
| |
| − | * [http://greenarrays.com/ GreenArrays, Inc.] の GA144 マルチコンピュータチップ
| |
| − | * [[バロース B5000]] アーキテクチャ（1961年から）
| |
| − | * [[:en:English Electric KDF9|English Electric KDF9]] (1964)。レジスタで16段のスタックを実装。
| |
| − | * [[:en:Rockwell Collins|Collins Radio]] のミニコンピュータ Collins Adaptive Processing System (CAPS, 1969) と [[:en:Rockwell Collins|Rockwell Collins]] の Advanced Architecture Microprocessor (AAMP, 1981)<ref>[http://hokiepokie.org/docs/EETimes.ps, "The World's First Java Processor"], by David A. Greve and Matthew M. Wilding, Electronic Engineering Times, Jan. 12, 1998,</ref>
| |
| − | * [[UCSD p-System|UCSD Pascal]] p-machine をハードウェアで実装したもの（[[:en:Pascal MicroEngine|Pascal MicroEngine]]など）
| |
| − | * [[:en:Manchester computers|MU5]]と [[:en:ICL 2900 Series|ICL 2900]] シリーズ。スタックマシンとアキュムレータマシンのハイブリッド方式。アキュムレータはスタックトップの値をバッファする。
| |
| − | * [[タンデムコンピューターズ]] T/16
| |
| − | * [[HP 3000]] （PA-RISC ではなく、それ以前の CISC）
| |
| − | * Atmel MARC4 [[マイクロコントローラ]]<ref>'MARC4 4-bit Microcontrollers Programmers Guide', Atmel,
| |
| − | http://www.atmel.com/dyn/resources/prod_documents/doc4747.pdf</ref>
| |
| − | * [[Forth]]言語を実装したチップ<ref>[http://www.colorforth.com/chips.html Forth chips]</ref>。RTX2000、F21<ref>[http://www.ultratechnology.com/f21.html F21 Microprocessor Overview]</ref>、PSC1000<ref>[http://www.forthfreak.net/misc/psc1000.pdf PSC1000 Microprocessor Reference Manual, Patriot Scientific Corporation]</ref>など。
| |
| − | * Bernd Paysan による4つのスタックを持つマシンの提案<ref>[http://www.jwdt.com/~paysan/4stack.html The 4stack processor by Bernd Paysan]</ref>
| |
| − | * [http://www.ptsc.com/products/igniteIP_data%20sheet_20050506.pdf "Ignite"] スタックマシン。[[チャールズ・ムーア]]がアーキテクチャを設計。
| |
| − | * [[:en:RUAG Space|Saab Ericsson Space]] の放射線耐性を強化したマイクロプロセッサ Thor<ref>[http://lundqvist.dyndns.org/Publications/thesis95/ThorGCC.pdf 'Porting the GNU C Compiler to the Thor Microprocessor'], Harry Gunnarsson and Thomas Lundqvist</ref>
| |
| − | *{{仮リンク|インモス|en|Inmos}} [[トランスピュータ]]
| |
| − | | |
| − | === 仮想スタックマシン ===
| |
| − | ソフトウェアで解釈される[[仮想機械|仮想]]スタックマシンの例を挙げる。
| |
| − | * [[SECDマシン]]
| |
| − | * [[Pコードマシン|UCSD Pascal p-machine]]
| |
| − | * [[Java仮想マシン]]命令セット
| |
| − | * [[.NET Framework]] 環境における[[共通中間言語]]命令セットおよびその仮想機械である VES（仮想実行システム）
| |
| − | * [[Forth]]言語処理系。特に[[スレッデッドコード]]で実装されているもの。
| |
| − | * アドビの[[PostScript]]
| |
| − | * [[サン・マイクロシステムズ]]の [[Sun Ray]] [[ICカード|スマートカード]]の定義作成のための SwapDrop 言語
| |
| − | * [[CPython]] [[バイトコード]]インタプリタ
| |
| − | | |
| − | == コールスタックとスタックフレームを使ったコンピュータ ==
| |
| − | {{Main|コールスタック}}
| |
| − | 現代のほとんどのコンピュータ（命令セットを問わない）とほとんどのコンパイラは、メモリ上の[[コールスタック]]を局所変数の格納場所および[[サブルーチン]]からの復帰のための情報格納に使っている。サブルーチンコールのたびに「スタックフレーム」をコールスタック上に作り、そのサブルーチンから呼び出し側に復帰するまで対応するスタックフレームが維持される。コールスタックを特別なアドレスレジスタなどを使ってハードウェアで管理する場合もある。あるいは、コンパイラの[[呼出規約]]によって特定の汎用レジスタをコールスタック処理に使う場合もある。
| |
| − | | |
| − | 一般にコンピュータは、大域変数とその時点で実行中のプロシージャまたは関数の局所変数への効率的アクセス手段を提供する。一般に呼び出し側のプロシージャまたは関数のスタックフレームを遡ってアクセスする必要性はほとんどなく、ハードウェアが直接そのような手段を提供することもない。必要ならば、スタックフレーム内にあるフレームポインタで遡ることもできる。
| |
| − | | |
| − | [[バロース B5000]] ではハードウェアでスタックフレームを遡る手段を提供しているが、これは動的な入れ子構造ではなく、プログラムの静的な入れ子構造（変数のスコープ）を辿るものである。その後このような機能をハードウェアで実装した例はない。[[ニクラウス・ヴィルト]]は [[CDC 6600|CDC 6000 シリーズ]]向けに[[Pascal]]コンパイラを開発した際、フレームポインタを配列に格納して常に更新するよりも、コールスタック上のフレームポインタを遡ってたどった方が全体として高速だということを発見した。この方式だと、遡って参照することのない[[C言語]]などのプログラミング言語でも、余計なオーバーヘッドが発生しない。
| |
| − | | |
| − | バロース B5000 では、タスクまたはスレッドの入れ子もサポートしている。あるタスクとそのタスクを作ったタスクは、タスク作成時点のスタックフレームを共有するが、作成した側の次のフレームや作成されたタスク自身のフレームは共有されない。そのため西部劇でよく見るようなサボテンのようなスタック構造になる。各タスクは自身のスタックとフレームを保持するメモリセグメントを持つ。そのスタックのベースは作成した側のスタックの途中とリンクされている。一般的なフラットなアドレス空間を持つマシンでは、あるタスクのスタックとそれを作成した側のスタックは1つのヒープ内の別々のヒープオブジェクトになる。
| |
| − | | |
| − | プログラミング言語によっては、外側のスコープのデータ環境が常に入れ子になっているわけではない。そのような言語では、1つのスタックにスタックフレームを積んでいくのではなく、別個のヒープオブジェクトとしてプロシージャの「アクティベーション・レコード」を編成する。
| |
| − | | |
| − | [[Forth]]のような単純な言語では、局所変数やパラメータの名前がなく、スタックフレームにはリターンアドレス以外に何も必要としない。そのため、リターンスタックにはフレームが存在せず、単にリターンアドレスが格納される。リターンスタックとデータスタックは分離しており、プロシージャの呼び出しと復帰は高速に行われる。
| |
| − | | |
| − | == 脚注・出典 ==
| |
| − | {{Reflist}}
| |
| − | | |
| − | == 外部リンク ==
| |
| − | *[http://www.ece.cmu.edu/~koopman/stack_computers/ ''Stack Computers: the new wave'' book by Philip J. Koopman, Jr. 1989]
| |
| − | *[http://www.excamera.com/articles/20/mp3c.html Homebrew CPU in an FPGA] - FPGA で自家製スタックマシンを作る
| |
| − | *[http://www.holmea.demon.co.uk/Mk1/Architecture.htm Mark 1 FORTH Computer] - TTLチップで構成した自家製スタックマシン
| |
| − | *[http://www.holmea.demon.co.uk/Mk2/Architecture.htm Mark 2 FORTH Computer] - ビットスライス/PLDを使った自家製スタックマシン
| |
| − | *[http://www.eecg.utoronto.ca/~laforest/Second-Generation_Stack_Computer_Architecture.pdf Second-Generation Stack Computer Architecture] - スタックマシンの歴史と設計に関する論文
| |
| − | | |
| | {{DEFAULTSORT:すたつくましん}} | | {{DEFAULTSORT:すたつくましん}} |
| | [[Category:コンピュータアーキテクチャ]] | | [[Category:コンピュータアーキテクチャ]] |
| | [[Category:計算モデル]] | | [[Category:計算モデル]] |
| | [[Category:数学に関する記事]] | | [[Category:数学に関する記事]] |