====== Instruction decoder and controller ======

An Instruction Decoder is a circuit that processors implement in order to interpret instructions coming from memory. In synchronous designs, this circuit feeds the appropriate operands into the datapath of the processor, according to the instruction. Additionally, it must communicate with a Controller, whose role is to direct the flow of the execution at every stage of the pipeline. 

In this exercise we are interested in implementing the instruction decoder and controller for a small asynchronous processor. While these are often different circuits, in this case the simplicity of the processor allows us to incorporate all the functionality into a single module. From now on, in this exercise, we will refer to this combined module simply as Decoder.

The following figure shows a block diagram of the relevant processor modules. 

{{ instruction_decoder-diagram.svg?500, nolink }}

The diagram contains 6 blocks. Your task is to implement the block labelled as //DEC//. All the input and output signals for //DEC// are colored in red and blue, respectively. Signals in black do not interact with //DEC// and are shown only to provide context.

The different modules operate in the following way:
  * The instruction controller //INST// loads an instruction from memory and sets it into the instruction bus. When the bus is stabilised, it initiates a decoding request by firing the signal ''<color red>dec</color>''. After the instruction has been executed, as indicated by the ''<color blue>dec_ack</color>'' signal, this module requests a new address from the //IPC// module and loads it from memory.
  * The data memory //DATA MEM// has an address port ''@'' obtained directly from the instruction bus. It supports two types of operations, read and write, that are requested with the signals ''<color blue>mr</color>'' and ''<color blue>mw</color>'', respectively. After a read operation is finished, //DATA MEM// will set the memory value from the address in ''@'' into the read port ''r'' and enable ''<color red>mr_ack</color>''. Write operations are similarly handled with the signals ''<color blue>mw</color>'' and ''<color red>mw_ack</color>''. In this case, the data to write must be stable before ''<color blue>mw</color>'' is enabled.
  * The register block //REG// contains a small number of registers that can store values to perform arithmetic operations. It contains two read ports, ''a'' and ''b'', and one write port ''d''. Like in the case of //DATA MEM//, the port addresses are obtained directly from the instruction bus. The signals ''<color blue>rgr</color>'' and ''<color blue>rgw</color>'' are used to request read and write operations, respectively. The signals ''<color red>rgr_ack</color>'' and ''<color red>rgw_ack</color>'' acknowledge these operations in the same way as in the //DATA MEM// module.
  * The //ALU// module performs arithmetic operations. It decides what operation to execute according to the ''op'' port that comes from the instruction bus. It has three ports for its operands: ''imm'', ''a'' and ''b''. The first port allows the //ALU// to obtain values directly from the instruction bus, while ''a'' and ''b'' must be read from the register. The signal ''<color blue>alu</color>'' informs the //ALU// that the operands are set and an operation can take place. The result of this operation is placed in the output port ''d''. After an operation is complete, the signal ''<color red>alu_ack</color>'' is enabled. Furthermore, a signal ''<color red>z</color>'' is enabled if the result of the operation was //zero//. This value is guaranteed to remain stable until after the following operation is requested.
  * The //IPC// module stands for Instruction Process Counter, and its role is to keep track of the address for the instruction memory. In general, it keeps a copy of the last address loaded and increases it by one when the instruction controller requests a new address. It is also possible to request the module to add an //offset// different than one to the next address by enabling the signal ''<color blue>jmp</color>''. The offset is obtained from the port ''imp_ofs'' directly from the instruction bus.

The processor implements four instructions that must be decoded and controlled by //DEC//:
  * **Arithmetic operation**. Performs an arithmetic operation and stores the result in the register. Corresponds to the code ''<color red>op0</color> = 0'', ''<color red>op1</color> = 0''.
  * **Branch operation**. If the result of the last arithmetic operation is a ''0'', adds an offset into the next instruction address. Corresponds to the code ''<color red>op0</color> = 0'', ''<color red>op1</color> = 1''.
  * **Load from memory**. Reads from memory and stores the value into the register. Corresponds to the code ''<color red>op0</color> = 1'', ''<color red>op1</color> = 0''.
  * **Store in memory**. Stores a value from the register into memory. Corresponds to the code ''<color red>op0</color> = 1'', ''<color red>op1</color> = 1''.


===== Exercise 1: Arithmetic Instructions =====

The first instruction you have to implement is the arithmetic instruction. But before that, it is always a good idea with WTG to first set the basic structure of the controller. This not only makes it easier to approach the problem, but also allows Workcraft to infer signal values when possible. 

Let us first define the initialization and leave a waveform for every instruction. Remember to rename every waveform with the instruction it intends to solve.

++++ Detailed instructions|
  * Place a state and double click on it to set it as initial.
  * Add a new waveform, rename it //initialisation// and add a connection from the initial state. A signal cannot be ''unstable'' in the first initial state. We will assume that, in the initialization of this circuit, the signals ''<color red>op0</color>'' and ''<color red>op1</color>'' are ''low'' before becoming ''unstable''.
    * Click on the signal tool and hold <key>Shift</key> while clicking twice to add two input signals.
    * Rename them ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Double click on them while holding <key>Shift</key> and <key>Ctrl</key> to add a ''destabilise'' transition.
    * Double click on them again to add ''stabilise'' transitions.
  * Add a new state and four waveforms. Add a connection between //initialisation// and the state, and from the state to the new waveforms. 
  * Rename each waveform with one of the instructions: //arithmetic//, //branch//, //load// and //store//.
  * Set a guard for each waveform depending on the operation it implements:
    * Click on the //arithmetic// waveform and set, in the //guard// field on the property editor, the guard ''!op0, !op1''.
    * Click on the //branch// waveform and set, in the //guard// field on the property editor, the guard ''!op0, op1''.
    * Click on the //load// waveform and set, in the //guard// field on the property editor, the guard ''op0, !op1''.
    * Click on the //store// waveform and set, in the //guard// field on the property editor the guard,  ''op0, op1''.
++++

The WTG should look similar to the following figure.

{{ instruction_decoder-wtg_structure.svg?44%,nolink }}


You can now implement the arithmetic instruction controller.

++++ Detailed instructions|
  * Double click on the //arithmetic// waveform to move to the waveform level. 
  * Use the property editor to declare the signals ''<color red>op0</color>'' and ''<color red>op1</color>'' by clicking on their checkbox.
  * This instruction requires interactions with the modules //INST//, //REG// and //ALU//. Add all the signals used to interact with them:
    * Add the input signals ''<color red>dec</color>'', ''<color red>rgr_ack</color>'', ''<color red>rgw_ack</color>'' and ''<color red>alu_ack</color>''. The signal ''<color red>z</color>'' is not needed for this instruction and so it can be ignored.
    * Add the output signals ''<color blue>dec_ack</color>'', ''<color blue>rgr</color>'', ''<color blue>rgw</color>'', ''<color blue>alu</color>''.
    * Remember that signals can be reorganized by holding <key>Shift</key> while dragging them vertically.
  * The signal ''<color red>dec</color>'' indicates the start of this scenario. First, the operands must be loaded from the register into the //ALU//:
    * Add a ''rise'' transition for signals ''<color red>dec</color>'' and ''<color blue>rgr</color>'' by double clicking on them.
    * Add a connection from the transition of ''<color red>dec</color>'' to the transition of ''<color blue>rgr</color>''
  * When the register is done loading the values in its output ports, it will ''rise'' the ''<color red>rgr_ack</color>'' signal. We can then request //ALU// to perform the operation.
    * Add ''rise'' transitions to the signals ''<color red>rgr_ack</color>'' and ''<color blue>alu</color>''.
    * Connect the transition of ''<color blue>rgr</color>'' to the transition of ''<color red>rgr_ack</color>'', and the transition from ''<color red>rgr_ack</color>'' to the transition of ''<color blue>alu</color>''.
  * The //ALU// will ''rise'' the signal ''<color red>alu_ack</color>'' after the operation is performed. The register can then be requested to write the result. 
    * Add new ''rise'' transitions for signals ''<color red>alu_ack</color>'' and ''<color blue>rgw</color>''. 
    * Connect the transition of ''<color blue>alu</color>'' to the transition of ''<color red>alu_ack</color>''.
    * Connect the transition of ''<color red>alu_ack</color>'' to the transition of ''<color blue>rgw</color>''.
  * After the register has finished storing the result of the operation, the //ALU// can stop holding the value and drop the request to write in the register. This can be done in parallel.
    * Connect the transition from ''<color blue>rgw</color>'' to a new transition for signal ''<color red>rgw_ack</color>''.
    * Add ''fall'' transitions for signals ''<color blue>rgw</color>'' and ''<color blue>alu</color>''.
    * Connect the transition for signal ''<color red>rgw_ack</color>'' to the ''fall'' transitions of ''<color blue>rgw</color>'' and ''<color blue>alu</color>''.
  * When the //ALU// acknowledges the end of the operation, we can drop the request to read from the register.
    * Add a ''fall'' transition for signals ''<color red>alu_ack</color>'' and ''<color blue>rgr</color>''.
    * Connect the ''fall'' transition of signal ''<color blue>alu</color>'' to the ''fall'' transition of ''<color red>alu_ack</color>'', and the ''fall'' transition of ''<color red>alu_ack</color>'' to the ''fall'' transition of ''<color blue>rgr</color>''.
  * After the register acknowledges the end of the read and write operations, the decoder informs that the operation has been finished.
    * Add a ''fall'' transition for signals ''<color red>rgr_ack</color>'' and ''<color red>rgw_ack</color>'' and a ''rise'' transition for signal ''<color blue>dec_ack</color>''.
    * Connect the ''fall'' transition of ''<color blue>rgr</color>'' to the ''fall'' transition of ''<color red>rgr_ack</color>''.
    * Connect the ''fall'' transition of ''<color blue>rgw</color>'' to the ''fall'' transition of ''<color red>rgw_ack</color>''.
    * Connect the ''fall'' transition of ''<color red>rgr_ack</color>'' and ''<color red>rgw_ack</color>'' to the ''rise'' transition of ''<color blue>dec_ack</color>''.
  * Since the operation is finished, the signals ''<color red>op0</color>'' and ''<color red>op1</color>'' might change value and so they should be considered ''unstable''. In parallel, ''<color red>dec</color>'' acknowledges the finalization of the operation.
    * Add ''destabilise'' transitions to signals ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Add a ''fall'' transition to signal ''<color red>dec</color>''.
    * Connect the ''rise'' transition from signal ''<color blue>dec_ack</color>'' to the transitions you just added.
    * Add a ''fall'' transition for signal ''<color blue>dec_ack</color>''.
    * Connect the ''fall'' transition of signal ''<color red>dec</color>'' to the ''fall'' transition of ''<color blue>dec_ack</color>''.
  * At some point before the end of the waveform, the signals op0 and op1 must become ''stable''.
    * Double click the signals ''<color red>op0</color>'' and ''<color red>op1</color>'' to add a ''stabilise'' transition.
  * The instruction is now complete and the decoder waits for the next instruction.
    * At the waveform level, add a connection from //arithmetic// to the previous nodal state.
++++

The implementation for the first signal can be seen in the next figure.

{{ instruction_decoder-arithmetic.svg?44%,nolink }}


===== Exercise 2: Branch Instructions =====

The next instruction we will implement is the branching instruction. This instruction allows the processor to alter the execution flow depending on logic conditions. Any operation performed in the //ALU// will set the signal ''<color red>z</color>'' to ''high'' if the result was ''zero''. It will set ''low'' otherwise. By using this signal we can determine whether to branch or not.

This instruction will need to use //guards//. Implement structure of the WTG for the branch instruction and the common waveform before the //guard//. Keep in mind that ''<color red>z</color>'' has to be initialized in a similar way to ''<color red>op0</color>'' and ''<color red>op1</color>''. The value of this signal is only relevant to the branch operation, so it should remain ''unstable'' in every waveform and become ''stable'' when we need it.


++++ Detailed instructions|
  * The signal ''<color red>z</color>'' is ''unstable'' in most waveforms, but it first needs to be initialised with a known value.
    * Double click the //initialisation// waveform and add a new input signal ''<color red>z</color>''.
    * Add a ''destabilise'' transition by double clicking ''<color red>z</color>'' while holding <key>Shift</key> and <key>Ctrl</key>.
  * A waveform with a guard must always declare the signals that are guarded.
    * Double click the //branch// waveform and declare the signals ''<color red>op0</color>'' and ''<color red>op1</color>'' in the property editor.
  * The signal ''<color red>z</color>'' is necessary to determine whether branching occurs. This signal must become ''stable'' before taking a decision.
    * Use the property editor to declare ''<color red>z</color>''.
    * Double click on ''<color red>z</color>'' to add a ''stabilise'' transition.
  * The model must now decide what to do depending on the value of ''<color red>z</color>''.
    * Go to the state level by double clicking outside of the waveform.
    * Place a new state and a connection between //branch// and the state.
    * Place two new waveforms and rename them //no_jmp// and //jmp//.
    * Add a connection from the new state to the new waveforms.
    * Click on //no_jmp// and, in the property editor, set the //Guard// field to ''!z''.
    * Click on //jmp// and, in the property editor, set the //Guard// field to ''z''.
++++

The resulting WTG can be seen in the following figure.

{{ instruction_decoder-branch_structure.svg?44%,nolink }}

The simplest scenario occurs when ''<color red>z</color>'' is ''low''. In this case, there is nothing to do and //DEC// immediately acknowledges the instruction after the decoding request. Implement the waveform for this scenario.

++++ Detailed instructions|
  * Declare the signals that are needed to process this scenario.
    * In the property editor, use the //declare// button for the signals ''<color red>z</color>'', ''<color red>dec</color>'', ''<color red>op0</color>'', ''<color red>op1</color>'' and ''<color blue>dec_ack</color>''.
  * The first transition must be the request for the operation. This is immediately acknowledged in this scenario, since there is nothing to be done.
    * Add a ''rise'' transition for signals ''<color red>dec</color>'' and ''<color blue>dec_ack</color>''.
    * Add a connection from the transition of ''<color red>dec</color>'' to the transition of ''<color blue>dec_ack</color>''.
  * Signals ''<color red>z</color>'', ''<color red>op0</color>'' and ''<color red>op1</color>'' are no longer needed and can become ''unstable''. 
    * Add an ''unstable'' transition to signals ''<color red>z</color>'', ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Connect the transition from ''<color blue>dec_ack</color>'' to the transitions of ''<color red>z</color>'', ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Add a ''stabilise'' transition to signals ''<color red>op0</color>'' and ''<color red>op1</color>''.
  * Finally, the request for decoding and the acknowledge can be set to ''low''.
    * Add a ''fall'' transition for signal ''<color red>dec</color>''.
    * Connect the ''rise'' transition of ''<color blue>dec_ack</color>'' to the ''fall'' transition of ''<color red>dec</color>''.
    * Add a ''fall'' transition for signal ''<color blue>dec_ack</color>''.
    * Connect the ''fall'' transition of signal ''<color red>dec</color>'' to the ''fall'' transition of signal ''<color blue>dec_ack</color>''.
  * The model returns to its waiting state until a new request arrives.
    * At the state level, add a connection between //no_jmp// and the state before the guards.
++++

You can see the implementation of //no_jmp// in the following figure.

{{ instruction_decoder-branch_no_jmp.svg?44%,nolink }}

Finally, implement the last waveform for the branch instruction.

++++ Detailed instructions|
  * Declare the signals that are needed to process this scenario.
    * In the property editor, use the //declare// button for the signals ''<color red>z</color>'', ''<color red>dec</color>'', ''<color red>op0</color>'', ''<color red>op1</color>'' and ''<color blue>dec_ack</color>''.
    * Use the signal tool to declare ''<color blue>jmp</color>'' and ''<color red>ipc_ack</color>''.
  * The first transition must be the request for the operation. This follows with a request to the //IPC// to branch the address.
    * Add a ''rise'' transition for signals ''<color red>dec</color>'' and ''<color blue>jmp</color>''.
    * Add a connection from the transition of ''<color red>dec</color>'' to the transition of ''<color blue>jmp</color>''.
  * When the transaction with //IPC// is over, //DEC// signals the end of the instruction.
    * Add a ''rise'' transition to signal ''<color red>ipc_ack</color>''.
    * Connect the transition of ''<color blue>jmp</color>'' to the transition of ''<color red>ipc_ack</color>''.
    * Add ''fall'' transitions to signals ''<color blue>jmp</color>'' and ''<color red>ipc_ack</color>''.
    * Connect the ''rise'' transition of ''<color red>ipc_ack</color>'' to the ''fall'' transition of ''<color blue>jmp</color>'' and the ''fall'' transition of ''<color blue>jmp</color>'' to the ''fall'' transition of ''<color red>ipc_ack</color>''.
    * Add a ''rise'' transition to signal ''<color blue>dec_ack</color>''.
    * Connect the ''fall'' transition of ''<color red>ipc_ack</color>'' to the ''rise'' transition of ''<color blue>dec_ack</color>''.
  * Proceed like in the //no_jmp// waveform to finish this waveform.
    * Add an ''unstable'' transition to signals ''<color red>z</color>'', ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Add a ''stabilise'' transition to signals ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Add a ''fall'' transition for signal ''<color red>dec</color>''.
    * Connect the transition from ''<color blue>dec_ack</color>'' to the transitions of ''<color red>z</color>'', ''<color red>op0</color>'', ''<color red>op1</color>'' and ''<color red>dec</color>''.
    * Add a ''fall'' transition for signal ''<color blue>dec_ack</color>''.
    * Connect the ''fall'' transition of signal ''<color red>dec</color>'' to the ''fall'' transition of signal ''<color blue>dec_ack</color>''.
  * The model returns to its waiting state until a new request arrives.
    * At the state level, add a connection between //jmp// and the state before the guard
++++

The next figure shows a complete implementation of the branch instruction.

{{ instruction_decoder-branch.svg?44%,nolink }}


===== Exercise 3: Simplify the model =====

By looking at our current design, you can observe that the instructions always finish in the same way. This is due to the protocol between //DEC// and //INST//. In this exercise, your task is to identify the common parts and create a new waveform called //instruction_finished// that produces the necessary transitions between completing instruction and waiting for the next.

++++ Detailed instructions|
  * Modify the structure to accommodate for a waveform after the instructions.
    * Remove the connections that go from the instruction waveforms to the nodal state.
    * Add a new nodal state and connect the waveforms //arithmetic//, //no_jmp// and //jmp// to it.
    * Add a new waveform and a connection from the previous nodal state to this new waveform. Rename the waveform //instruction_finished//.
    * Add a connection from //instruction_finished// to the nodal state preceding the instruction waveforms.
  * Remove the common transitions from the instruction waveforms.
    * Double click on the waveform //arithmetic//:
      * Click on the ''fall'' transition for signal ''<color red>dec</color>''.
      * In the property editor, change the //Direction// to ''raise''. This will remove the transition and the connections to and from it.
      * Follow the same procedure to remove the ''fall'' transition for ''<color blue>dec_ack</color>'' and the ''stabilise'' transitions for ''<color red>op0</color>'' and ''<color red>op1</color>''.
    * Repeat the same procedure for the waveforms //no_jmp// and //jmp//.
  * Add the removed transitions to the //instruction_finished// waveform.
    * Double click on the //instruction_finished// waveform.
    * Declare the signals ''<color red>op0</color>'', ''<color red>op1</color>'', ''<color red>dec</color>'' and ''<color blue>dec_ack</color>'' by using the //declare// option in the property panel.
    * Add a ''fall'' transition to ''<color red>dec</color>'' and ''<color blue>dec_ack</color>''.
    * Connect the transition of ''<color red>dec</color>'' to the transition of ''<color blue>dec_ack</color>''.
    * Add ''stabilise'' transitions to ''<color red>op0</color>'' and ''<color red>op1</color>''.
++++

The simplified WTG can be seen in the next figure.

{{ instruction_decoder-simplified.svg?44%,nolink }}


===== Exercise 4: Load and Store Instructions =====

The remaining instructions have to access the //DATA MEM// module for read and write operations. This module uses a similar handshake protocol to the //REG// module. Complete the //DEC// module by adding the Load and Store operations to the WTG.

This exercise intentionally lacks detailed instructions to encourage working on it independnetly. You can compare your solution to the complete WTG of the decoder: <wrap download>{{instruction_decoder.wtg.work|}}</wrap> 


===== Solutions =====

Download all the Workcraft models discussed in this tutorial here:

<wrap download>{{instruction_decoder.zip|All instruction decoder WTGs}}</wrap>