StackとThe Lab【Turing Complete編】
目次
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
Stackステージ
Stackステージのゴールは、デジタル回路でスタックを組むことです。
スタックとは
スタック（stack）とは、後入れ先出しのデータ構造です。
※先入れ先出しのデータ構造の1つとして、キューがあります。
PUSH操作とPOP操作
・PUSH操作･･･スタックにデータを入れる。
・POP操作･･･スタックからデータを取り出す。
後入れ先入れについては、次のイラストから明らかです。後に入れたC0hが、先に取り出せていることがわかります。
スタックポインター
スタックポインター（SP）とは、スタックの操作を追跡するために使われるレジスターであり、スタック内の最後のプログラム要求のアドレスを保持しています。場合によってはそのアドレス自体がSPとして扱われます。
スタックポインターはスタックレジスターとも呼ばれます。
PUSU操作やPOP操作の際に、SPの保持するアドレスが変化します。
・PUSH操作⇒SPを1つ増やして、そのSPが指す位置にデータを記憶する。
・POP操作⇒SPの指す位置からデータを取り出して、SPの値を1つ減らす。
※今回はメモリーのアドレスの大きい方向に伸びていくように設計しているので、PUSHでSPを増やして、POPでSPを減らしました。アドレスの小さい方向に伸びていくアーキテクチャーもあり、その場合は逆にして設計されます。
RAMで実現するスタック構造
本ステージではRAMコンポーネントを使ってスタック構造を実現します。
RAMコンポーネントはアドレス的に左上をスタートして、右に伸びていきます。見た目では0Fhに到達したら折り返されていますが、実際にはずっと右に伸びている配列と考えても支障がありません。
RAMコンポーネントをスタックとして扱うなら、右に伸びるスタックと考えればよいだけです。単純に横倒しになっただけであり、データ構造上には変化がありません。
SPは0スタートとします。
前述のPUSHとPOPの操作通りだと、SPをインクリメントしてから、SPの指すアドレスにデータを記憶します。つまり、データを最初に記憶するアドレスは01hになります。
しかし、シミュレーターのレジスターはロードした時点中身のデータが出力されます。アドレス01hにしたければ、「インクリメントしてからセーブ⇒ロード」という2つのステップを踏まなければなりません。ちょっと回路上では面倒なので、今回はPUSHとPOPの操作時の挙動を変えます。次のように、SPが書き換わるタイミングを逆にします。
・PUSH操作⇒SPが指す位置にデータを記憶してから、SPを1つ増やす。
・POP操作⇒SPの値を1つ減らしてから、SPの指す位置からデータを取り出す。
これでSPが0スタートでも、アドレス00hからPUSHされたデータが格納されていきます。
Stackステージを解く
1：用意されている入力端子と出力端子に注目する
本ステージでは次に示す入力端子と出力端子があります。
| 入力 | ・Input 0端子･･･ONならPOPする。 ・Input 1端子･･･ONならPUSHする。 ・VALUE端子･･･POPやPUSHする対象バイトデータが入ってくる。 |
| 出力 | ・OUTPUT端子･･･出力用。 enabledピンを持ち、これがONになると出力しない。 |
2：スタックの設計方針を考察する
・記憶すべきデータは数個ではなく、十数個になる可能があるため、レジスターは使えない。代わりにRAMを使う。
・PUSUすると、データをスタックに格納する。
・POPのときのみ、スタックからデータを取り出して、出力端子からバイトデータが出てくる。
RAMコンポーネントのLoadピンは、POP用のInput 0端子とつながります。
RAMコンポーネントのSaveピンは、PUSU用のInput 1端子とつながります。
本ステージの一番難しいところは、スタックポインターをどうやって回路上に実装するかです。
スタックポインター周辺の回路をできあがれば、RAMコンポーネントのAddressピンも自然とつながります。
スタックポインターはRAMコンポーネントのアドレスを1つ保持します。このアドレスは1バイトで表現されているので、8 Bit Registerを使えばよいでしょう。
OutputピンはRAMコンポーネントのAddressピンにつながります。アドレスを実際に使うのはRAMコンポーネントなので当たり前といえます。
PUSHならアドレスをインクリメントし、POPならデクリメントしてから、アドレスを上書きします。Save valueピンとOutputピンをつなぎますが、その間にAddコンポーネントを配置します。Addコンポーネントでアドレスに1を足すか、1を引くか（-1を足すか）してから、上書きするわけです。加算と減算どちらをするのかについては、Switchで切り替えます。
なお、スタックにデータが格納されていないのに、POP命令がくるようなイレギュラーなケースは想定しません。
3：ナンバーフォーマットを切り替える
減算を使うので、見やすくするためにナンバーフォーマットを-1に切り替えておきます。
符号ありの8ビット値の場合、1111 1111bが-1に対応します。
4：簡単なワイヤリングから始める
簡単なところから攻めていきましょう。
入力端子とRAMコンポーネント、RAMコンポーネントと出力端子をワイヤリングします。ただし、Addressピンのところは後回しにします。
4：スタックポインターを実現する回路を組み込む
アドレスをインクリメントとデクリメントするわけですが、これはアドレス用のカウンターともいえます。Counterステージの回路を思い出すとヒントがあるかもしれません。
https://akademeia.info/?p=29559カウンターは加算によって増えていきますが、マイナスの値を加算すれば減らすこともできます。定数1と定数-1をADD演算すればよさそうです。
Counterステージの回路からマルチプレクサーをいったん取り除いてください。代わりに、Addコンポーネントの空いているInputピンに定数をつなげます。
8 Bit RegisterコンポーネントのLoadピンとSaveピンは常にONとします。このレジスターが保持するアドレスを更新する場合、セーブのみやロードのみという状況がなく、常にセーブとロードがセットで行うからです。
ざっくりと回路を組むと次のようになります。
5：回路の不具合を修正する
しかし、この回路にはバグがあります。実際に[Run]ボタンを押してテストするとわかりますが、途中で失敗して止まります。
テストデータやメッセージは符号なしの10進数で表示されるので、ナンバーフォーマットを255に戻します。
今度は[Next]ボタンでステップ実行してみます。「PUSH 251⇒PUSH 216⇒POP」のタイミングで止まりました。
RAMの中身を見ると、アドレス00hから251dと216dがセットされています。そして、どうやらPOPのタイミングで216dが取り出せずに、0dが取り出されてしまったようです。つまり、SPを減算する前にPOPが走ってしまったわけです。
そこで、マルチプレクサーである8 Bit Muxコンポーネントを使って、タイミングをずらすようにしてみましょう。具体的にいうと、SP-1も計算しておいて、PUSHの場合はその計算結果を使わない（今のままの動作。レジスターから出力された直の値を使う）、POPの場合はその計算結果を使うとするのです。
回路を修正すると次のようになります。加えた修正は黄色のワイヤーにしました。
6：テストする
テストにパスすると、ステージクリアになります。
今回の回路はComponent Factoryにセーブされて、Stackコンポーネントとして使えるようになります。
定数-1を使わずに、NEGコンポーネントを使う【別解】
-1は1の符号を反転した値です。すでに1という定数を使っているので、NEGコンポーネントを通すことで-1を作れます。
回路は次の通りです。
どちらの回路がよいかは、スコアで判断できます。
| 回路 | GATE SCORE | DELAY SCORE |
|---|---|---|
| 前述の回路 | 441 | 1136 |
| 別解の回路 | 537 | 1226 |
スコアによると、別解の回路の方がどちらのスコアも高くなっています。数値は低い方が効率的なので、（見やすさは別として）前述の回路に軍配が上がります。
マルチプレクサーを使わないバージョン【別解】
マルチプレクサーの代わりにSwitchを利用しています。さらに、定数1の代わりに255（-1）を使うようにしました。
The Labステージ
Component Factoryステージはコンポーネントを自作できるステージでしたが、The LabステージはLEGアークテクチャー向けのサンドボックス的なステージです。Tickを意識したテストも自在にできます。
以降はプログラミングのステージが登場しますが、プログラムがバグがなくても、回路にバグがあったらテストをパスできない可能性があります。プログラミングの問題を解いている最中に、回路のバグをデバッグ・修正する羽目になるのは、イライラの元です。しかも回路を修正したとしても、それによって以前に機能していたプログラムが壊れてしまう恐れがあります。
よって、ハードウェアを開発する際には、プログラミングを開始する前に100%の信頼性を目指すべきです。
その信頼性を担保するために、The Labステージ上で回路をテストしておきましょう。本ステージではプログラムを使って回路をテストできます。プログラムが実行されると、リンクされたコンポーネントが期待通りの動作かどうかをチェックできます。
テストプログラムと実行方法
Programコンポーネントの「Edit memory」アイコンを押すと、アセンブリーエディターが起動します。
ここでテスト用のプログラムを実装できます。
テスト用のサンプルプログラムがいくつか用意されています。プログラム名の一覧がシミュレーターの下側に表示されていますので、そのプログラム名を押せばそのプログラムを実行できます。[Run all]ボタンを押せば、全プログラムを順次実行します。
Expectキーワード
本ステージではExpectとset_inputという2つのキーワードが用意されており、プログラム内で使えます。テストを支援するためのキーワードです。
Expectは、メモリーアドレスが次のtickに保持すべき値を判定します。判定して一致すれば通過し、一致しなければエラーをは吐いて止まります。
Expect <Linked Component番号> <期待値>例えば、次の2行のコードがあったとします。
expect 2 4
copy 4 _ r2
最初の行は、2番目にリンクしたコンポーネントが次のtick後に値4を保持することを期待しています。
2行目のコードでは、REG 2が保持するデータに2をセットしています。これまでは入力端子やProgramコンポーネントからの出力を通じてレジスターの値を書き換えてきましたが、それではテストしにくいため、本ステージでは2行目のような書式が許可されています。
※プログラムの開始時、リンクされたコンポーネントは基本的にすべてが0を保持することを期待しています。RAMコンポーネントについては、変更処理が走った場合のみに変化します。
※ただし、カウンターは例外として、事前にセットされた値を保持します。カウンターなので当然ですが、tickごとに保持する値は増加します。
set_inputキーワード
set_inputでコンピューターの入力を制御できます。
set_input <入力データ（10進数値）>