Wire Spaghetti【Turing Complete編】
目次
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
Wire Spaghettiステージ
LEGアーキテクチャーの構築に入ります。
LEGアーキテクチャーは、プログラムメモリー（実質Programコンポーネント）から1tickあたり4バイトを取得して処理を進めるコンピューターです。
1つの命令語が4バイトから構成されているわけです。
| 4バイトのうちどこのバイトか | 何のために使うか |
|---|---|
| 1バイト目 | 指示したい操作のコード（操作コードという）を表します。 オペレーションコード（operation code）、略してオペコード（OPECODE）と呼びます。 |
| 2バイト目 | 操作対象データの転送元（1つ目）。 多くの操作（ADDやORなど）は2つの引数を取り、この2バイト目と次の3バイト目を使います。 |
| 3バイト目 | 操作対象データの転送元（2つ目）。 一部の操作（NOTなど）は1つの引数だけしか使わず、そういった場合は無視されます。 |
| 4バイト目 | 操作で得られた結果データの転送先（宛先）。 |
4バイトは命令（指令）部とアドレス部（あるいはデータ部）に分けられます[1]現時点では外部入出力 or … Continue reading。
命令を構成するバイト数、命令語長（命令語の語長）を明示する場合、「○バイト命令」といいます。
LEGアーキテクチャーでは全命令が4バイトで構成されているため、4バイト命令だけを扱っています。
「レジスターAとレジスターBを○○演算し、その結果をレジスターCに保存する」の処理をしたい場合、太字の部分を1バイトで確定していくわけです。
一方、効率化を図ったCPUアーキテクチャーでは、命令語の語長は固定ではありません。1バイト命令、2バイト命令、3バイト命令ように、複数の形式を持ちます。
アキュムレーターというレジスターが用意されており、演算命令の対象データを入れたり、計算結果データを入れたりといった使われ方をします。
「アキュムレーターとレジスターBを○○演算し、その結果をアキュムレーターに保存する」という形で命令語を書きます。太字に注目すると2ヶ所しかありません。
指定の演算の仕様として、アキュムレーターを明示的に指定しなくても、演算の1つ目の引数としてアキュムレーター内のデータを使うというルールが定められているのです。
Turing Completeでは命令語長は固定ですが、CPU本の解説では命令語長が固定でない（ことが多い）と頭の隅に入れておいてください。
空のキャンバスを準備する
Wire Spaghettiステージを開始すると、我々のCPUが引き継がれて表示されます。
次のステップにしたがい、
1：「Switch schematic」アイコンから、新しい空のキャンバスを作ります。ここでは新規に”LEG”と命名しました。
※過去に作ったCPUを消さないために、別の空キャンバスを用意して回路を組みます。
2：入力端子（Level input）、出力端子（Level output）、Level Screenコンポーネントのみが配置された、空のキャンバスが表示されます。
Wire Spaghettiステージを解く
1：Programコンポーネントを配置する
今ステージから使うProgramコンポーネントは、4つの出力（Output 1～Output 4ピン）を持ちます。
キャンバス上にProgramコンポーネントを配置します。
2：プログラムカウンターを接続する
8 Bit Counterコンポーネントを配置して、Increment byのところで増分を4に設定します。
そして「8 Bit CounterコンポーネントのOutputピン」を「ProgramコンポーネントのAddressピン」に接続します。
※Overwrite valueピンとIncrement/Overwriteピンについては後述します。
3：6個のレジスターを配置する
6個のレジスターを用意します。8 Bit Registerコンポーネント（またはレジスター機能を備えたカスタムコンポーネント）を用います。
ここでは、8 Bit Registerコンポーネントを縦に並ぶように配置しました。上から、それぞれをREG 0、･･･、REG5と呼ぶことにします。
※後でワイヤリングする際に各コンポーネントの位置を調整するので、現時点のところ位置を気にする必要はありません。
4：リンクコンポーネントを設定する
Programコンポーネントの「Edit linked components」アイコンを押して、リンクコンポーネントを設定します。
0～5をREG 0～REG 5に接続します。6をカウンター、7を出力に接続します。
5：命令のフォーマットを確認する
現時点ではオペコードは常に0とします。本ステージではこのオペコードはADD演算とします。
ADD演算なので、引数1と引数2を要します。演算の結果を宛先に保存します。引数や宛先で指定する値は、次の意味を持ちます。
| 指定の際に使う値 | 取り出す場所 or 格納する場所 |
|---|---|
| 0 | REG 0 |
| 1 | REG 1 |
| 2 | REG 2 |
| 3 | REG 3 |
| 4 | REG 4 |
| 5 | REG 5 |
| 6 | カウンター |
| 7 | 転送元の場合は入力端子 転送先の場合は出力端子 |
例えば、「0 1 2 4」という4バイトであれば、「REG 1の内容」と「REG 2の内容」をADD演算し、その計算結果をREG 4に保存します。
※次のステージではオペコードを実装します。（作成済みでアンロックされている）ALUコンポーネントは使えないので、新たにALUの回路を実装します。
6：「REG 0とREG 1の内容をADD演算して、その結果をREG2に保存する」というケースのための回路を実装する。
本ステージのオペコードはADD演算固定（0とする）ですので、ProgramコンポーネントのOutput1には何も接続しません。
ADD演算は2つの引数を取ります。AddコンポーネントのInput 1とInput 2がADD演算の2つの引数に対応するわけです。
いきなりすべてのパターンを考えると複雑で間違えやすいので、ここでは「REG 0とREG 1の内容をADD演算して、その結果をREG2に保存する」という一例を満たす回路を組むことを目指します。
[1]ADD演算の計算対象の1つ目に注目する
ADD演算の第1引数は、命令の4バイトのうち、2番目のバイトデータで指定します。「ProgramコンポーネントのOutput 2ピン」から第1引数のバイトデータが送出されます。
REG 0を指定するには、（2番目のバイトデータが）0dのときになります。
0dかどうかは、ビット列に変換してから1の位がONかどうかで識別できます。回路的には、8 Bit Splitterコンポーネントに通して、3 Bit decoderコンポーネントの1番ピンがONであれば、0dということです。
このときREG 0の内容を取り出して、ADD演算に与えます。
0dのときだけ、REG 0の内容をADD演算に渡す必要があるので、途中に8 Bit Switchコンポーネントを設置します。「8 Bit SwitchコンポーネントのEnableピン」と「3 Bit decoderコンポーネントの1番ピン」をつなげます。これで、0dのときはREG 0の内容がADD演算に渡され、0d以外のときはREG 0の内容はADD演算に渡されません（他のレジスターから流れる回路を後で組む）。
※2番目のバイトデータを処理する際には、AddコンポーネントのInput 1にワイヤーがつながっています。
[2]ADD演算の計算対象の2つ目に注目する
ADD演算の第2引数のことです。ADD演算の第2引数は、命令の4バイトのうち、3番目のバイトデータで指定します。「ProgramコンポーネントのOutput 3ピン」から第2引数のバイトデータが送出されます。
REG 1を指定するには、（3番目のバイトデータが）1dのときになります。
以下、[1]と同様に考えると、次の回路が得られます。
※3番目のバイトデータを処理する際には、AddコンポーネントのInput 2にワイヤーがつながっています。
[3]ADD演算の計算結果に注目する
REG 0とREG 1のADD演算するとして、入力に相当する回路はできました。次に計算結果をREG 2に保存する回路について考えていきます。
計算結果を格納するレジスターは、命令の4バイトデータのうち4番目で指定することに決まっていました。
「ProgramコンポーネントのOutput 4ピン」から計算結果の保存先を示すバイトデータが送出されます。
これまで通り、8 Bit Splitterコンポーネントと3 Bit decoderコンポーネントを使います。
AddコンポーネントのResultピンから伸びたワイヤーはぐるりと回って、REG 2のSave valueピンにつながります。
[4]レジスターの残りのピンをワイヤリングする
8 Bit RegisterのSave valueピンとOutputピンはワイヤリングしていますが、LoadピンとSaveピンはまだワイヤリングしていません。
REG 0とREG 1は転送元レジスターなので、LoadピンをONにします。転送するバイトデータは途中のスイッチのON・OFFで届くかどうかが決まるので、常に保存データを出力してよいことになります。
転送先のレジスターは、転送先として指定された時点でSaveピンをONにします。今回の例ではREG 2が転送先レジスターであり、「3 Bit decoderの3番ピン」とSaveピンをつなげます。この間にスイッチは不要です。そもそも転送先として選ばれなければ、「3 Bit decoderの3番ピン」はOFFになるためです。
以上で「REG 0とREG 1の内容をADD演算して、その結果をREG2に保存する」というケースの回路ができあがったことになります。
他のケースについても以上と同様に考えられます。例えば、「REG 0とREG 1の計算結果をREG 0にセットする」という別のケースを考えてみます。AddコンポーネントのResultピンから伸びるワイヤーは、ぐるりと回って、REG 0のSaved valueピンにつながります。
その際、スイッチやEnableピンで出入りを制御できるので、今回設置したワイヤーを兼用できます。
すべてのレジスターについて、同様にぐるりと循環するような配線になります。
ここまできたら一気にやってしまいましょう。ここからはワイヤリングが見やすいように、コンポーネントやワイヤーの位置を調整してください。
各レジスターのResultピンは2つに分岐させて、AddコンポーネントのInput 1ピンとInput 2に接続させます。上のワイヤーは第1引数、下のワイヤーは第2引数のバイトデータが流れます。
※今後の拡張のためにワイヤーの色の枠を残しておきたいので、ここでは色を変更していません。
※カウンター、入力端子、出力端子に対するワイヤリングは後述します。具体的にいうと、3つある3 Bit decoderコンポーネントにおいて、7番ピンと8番ピンはまだ接続しません。
9：カウンター周辺をワイヤリングする
8 Bit CounterコンポーネントがADD演算の計算対象になったり、計算結果で上書きされたりします。
要するに、3つの3 Bit decoderコンポーネントの7番ピンと接続されます。
今はProgramコンポーネントの左側に配置していますが、レジスターの下に配置した方がワイヤーが並んできれいになります。
移動させても、「8 Bit CounterコンポーネントのOutputピン」と「ProgramコンポーネントのAddressピン」との接続は保ったままにしておきます。
それでは8 Bit Counterコンポーネントの残りのピンのワイヤリングをしていきます。
Overwrite valueピンからは上書きすべきバイトデータが入ってきます。つまり、ADD演算の結果が来るはずです。
Increment/Overwriteピンは、OFFのときは指定の増分でインクリメントし、ONのときは現在のカウンター値を上書きします。
転送先にカウンターが指定されたときに上書きするわけなので、左側（4バイト目に対応する）の3 Bit decoderの7番ピンと接続します。
ちなみに、Overwrite valueピンの手前にスイッチは不要です。不要なバイトデータが入ってきても、Incement/OverwriteピンがOFFであれば無視されるからです。
後は、カウンターが第1引数か第2引数として指定されたケースに対応させます。中央（2バイト目に対応）と右側（3バイト目に対応）の3 Bit decoderの7番ピンの処理になります。
レジスターと同じようにスイッチを介して、Addコンポーネントに接続します。
なお、ここでもProgramコンポーネントのAddressピンにつながってい状態と維持します。
10：入力端子をワイヤリングする
入力端子（Level input）は、InputピンとDisable/Enableピンを備えています。
Disable/EnableピンがONならInputピンからバイトデータが送出されます。入力がされていないと見なされます。
OFFの場合は入力端子が実質的に無効になるわけですが、シミュレーター的には0が送出されます。つまり、「ONの場合に0が送出されている状況」と「OFFで強制的に0が送出されている状況」が区別がつきません。そのため、Input端子をAddコンポーネントのInput 1・2端子に直結できません。対応策としては、これまで通り途中にスイッチを設けて、確かに2バイト目や3バイト目に7（Inputに対応する識別値）が指定されたら、スイッチをONにしてワイヤーを接続するのです。
同時に、2バイト目または3バイト目に7が指定されたら、Disable/EnableピンをONにする必要があるので、ORコンポーネントを通したうえでDisable/Enableピンでつなげます。
11：出力端子をワイヤリングする
出力端子（Level output）は、OutputピンとDisable/Enableピンを備えています。
残っているピンが少なくなってきましたし、これまでの解説の流れで、深く悩まずとも正しいワイヤリングがわかってくるはずです。
左の3 Bit decoderの7番ピンがまだ未接続です。これは計算結果の転送先に出力端子を指定したときにONになります。つまり、このピンから伸びたワイヤーがDisable/Enableピンに接続するとわかります。
Outputピンには、AddコンポーネントのResultピンから伸びて、ぐるりと回ってきたワイヤーを接続します。
ちなみに、Outputピンの手前にスイッチはいりません。Disable/EnableピンがOFFであれば、そもそも出力しないためです。
12：全体の回路を見直す
配線ミスがないか、配線し忘れがないかを確認します。全体的にきれいに配線していれば、ミスを見つけやすくなるという恩恵が得られるはずです。
13：テストする
テストにパスすると、ステージクリアになります。
カスタムレジスターを使用したバージョン【別解】
8 Bit MATHグループにRegisterPlusコンポーネントが用意されています。今回はこれを活用することにします
RegisterPlusコンポーネントは8 Bit Registerを内蔵しており、Always outputピンが増えています。
このピンは1バイトデータを出力するものであり、名称の通りLoad・Saveにかかわらずバイトデータを出力します。
とりあえず、単純に8 Bit RegisterコンポーネントをRegisterPlusコンポーネントに置き換えた回路を作ります。
※Always outputピンはまだ使いません。
さらに、8 Bit Registerコンポーネントを消した時点で、リンクコンポーネントの接続が切れるので、再設定してください。
テストを実行して、問題ないことを確認してください。
※Outputピンではなく、Always outputピンに接続していても、テストにパスします。
Equalコンポーネントを利用してワイヤリングをすっきりさせる【別解2】
これまでの回路では、8 Bit Splitterコンポーネントや3 Bit decoderコンポーネントを使っていました。これはバイトデータをビットに分割して、処理を制御するためです。
我々はすでにバイトデータに関する一致回路を組んで、Equalコンポーネントをアンロックしています。これをうまく活用すれば、1バイトを分離する必要はなく、その分ワイヤーの本数が減って見やすくなるはずです。
※実際に回路を組む場合にワイヤー数が減るわけではなく、シミュレーター上でワイヤー数が減ります。
Equalコンポーネントは「8BIT」＞「MATH」の中に収録されています。
Equalコンポーネントの入出力は次の通りです。Input 1とInput 2が一致したときだけ、OutputからONを出力します。
中央のレジスター用の「EqualコンポーネントのInput 1ピン（あるいはInput 2ピン）[2]一致するかどうかを調べるコンポーネントなので、どちらのピンでも構いません。」は「ProgramコンポーネントのOutput 2ピン」とつなげます。
そして、「EeualコンポーネントのInput 2（あるいはInput 1ピン）」は8 Bit Constantコンポーネントとつなげます。8 Bit Consantコンポーネントは1バイトの定数データを出力し続けます。どういった定数を出力するかは明示的に指定できます。8個の8 Bit Constantコンポーネントを縦に並べることになりますが、上から0、･･･、7を出力するようにするのです。
以上を踏まえて、中央のワイヤリングを整理すると、次の回路になります。
※スペースがあまり空いていなかったので、Equalコンポーネントを180度回転させて配置しています。
テストがパスするのを確認したら、左側と右側も同様のワイヤリングで整理していきます。
※すでに完成した回路がある場合、全部が完成してからまとめてテストするのではなく、ある程度のコンポーネントを置き換えてワイヤリングを調整したら、テストすることをおすすめします。段階的にテストするのです。これを意識することで、問題が発生したときの手戻りを最小減に押さえられます。
完成した回路は次の通りです。これまでの回路と比べてだいぶすっきりしていると感じるでしょう。
※線の交差が多くて、接点なのかそうでないのか見にくくなってきたので、一部のワイヤーに色をつけました。
