 |
Dataflow Software Stack
032db78
Master Thesis of Mathijs Saey at the VUB
|
|
Dataflow Software Stack
032db78
Master Thesis of Mathijs Saey at the VUB
|
This guide is deprecated! People looking for a complete DIS reference can always contact me.
This page defines the standard of DIS, the DVM Instruction Set. DIS is the only input accepted by DVM, and can be generated by an external tool. As the name might say, DIS simply contains the instruction set that DVM uses to execute programs. Simply said, DIS is a string representation of the DVM instruction memory.
Seeing that DIS is a string version of the instruction memory, it might be handy to know what the instruction memory looks like.
The DVM instruction memory is divided into chunks, each of these chunks contains instructions that have certain properties. At the time of writing, the instruction memory contains 2 chunks, instructions that need to be matched by the context matcher and instructions that don't need to be matched.
The instructions that don't need to be matched are located in chunk 0, while those that need to be matched are located in chunk 1.
A DIS file contains 4 types of statements, seperated by newlines.
Besides these, DIS can contain comments, a comment is started by using $
The following sections detail the exact nature of the other statements.
Like the instruction memory, a DIS file is divided in chunks. A chunk simply contains all the instructions present in this chunk. A new chunk is started with the following statement:
CHUNK <idx>
Where chunk is a keyword while idx is the index of the chunk. A chunk ends when a new chunk begins or when the file ends. It is not possible to nest chunks.
A link allows us to define from-to relationships between instructions. A link is added in the following way:
LINK <from> -> <to>
Where LINK is a keyword while from is the address (chunk, instruction, port) of the port on the source node while to is the address of the port on the to node.
A port address is represented with the following syntax:
<chunk> <instruction> <port>
Thus a link from port 0 of instruction 3 in chunk 0 to port 0 of instruction 1 in chunk 1 would look like this:
LINK 0 3 0 -> 0 1 0
Links can occur anywhere in the file, and transcend chunk boundaries. However, a link should never precede the declaration of it's source.
An instruction in DIS looks like this:
INST <type> <idx> <args>
Where idx is the index of the instruction in the chunk of memory, while type is the type of instruction we are creating. Args represents the arguments. These depend on the type of instruction.
The following table defines the possible instruction types, their type code and the argument string they accept. Additional explanation on each of these types can be found below.
| Type | Code | Args |
|---|---|---|
| Sink | SNK | None |
| Switch | SWI | <dstList> |
| Constant | CNS | None |
| ContextChange | CHN | <to> <return sink> |
| ContextRestore | RST | None |
| OperationInstruction | OPR | <opCode> <inputs> |
Sinks are the the simplest instruction that is available. A sink is a simple link between a from and to. It will send whatever input it receives on a port to the destination for that port.
Sinks are mainly used to have a static point in the program that can catch input (such as the start of a function). A sink takes no arguments, since it's behavior is defined by it's destinations, which are added through links.
A Switch allows us to change the destination of a token depending on a condition. A switch stores all the tokens that it receives, until it's destination is determined. Once the destination is determined, all the stored tokens are sent to this destination. Further tokens that are received will also be sent to the same destination.
The destination is determined by a token that arrives at port 0. This token carries an index, which corresponds to a destination in the destination list of the switch.
A Switch only modifies the destination address of the tokens it receives, it does not touch the port. Sinks should be used when rederection is required.
A Sink is declared in the following manner:
INST SW <idx> <destination list>
A destination list looks like this:
<chunk 0> <address 0> <chunk 1> <address 1> ... <chunk n> <address n>
Simply put, a destination list is a list of chunk, address pairs, their order determines the index that they are assigned to.
For instance, in the following example:
INST SW 0 0 22 1 5
Index 0 would correspond to sending further tokens to instruction (0, 22), while index 1 would correspond to sending the tokens to instruction (1, 5).
A Context change instruction changes the context of a token. Look into the documentation for further information.
A context change instruction takes 4 arguments:
Thus a context change will look like this:
INST CC <idx> <binds> <restores> <address> <address>
Such an address is similar to a link address:
<chunk> <instruction>
Thus a context change instruction is added in the following manner:
INST CC 2 2 1 0 4 0 3
A context Restore finds the return instruction of a token based on it's context and sends it to that location. It can be compared to a return from a call. Once again, we refer to the documentation for additional information.
A context restore takes no arguments.
An operation instruction represents an operation on the data of a set of tokens. It takes an opcode, which represents the operation it performs, and a number detailing the amount of inputs it should receive. It ends up looking like this:
INST OP <idx> <opCode> <inputs>
Example:
INST OP 0 1 2
The opCodes can be found in the appendix
A constant instruction is an instruction that will always return the same result, regardless of the input. This operation should only be used if a literal cannot be eliminated from the program. A constant instruction should also only receive a single token from the same context, or it will resend it's result.
A constant takes it's value as an argument and is declared in the following way:
INST CO <idx> <= <value>
For possible values of this value, check the literals section. Constant instructions should only be used when it is not possible to add this value as a literal to the program in another way.
In order to communicate with the outside world, the DVM needs to have a predefined entry and exit point to the program. These are added by using a special instruction that can only be used for this purpose. These special instructions have to be placed at predefined locations.
The entry point of the program should be located in chunk 0 at address 0, while the exit point should be located at chunk 0 at address 0. These points are added through the program begin and program end points. The program entry point should also defined the amount of inputs the program accepts.
entry point:
INST PB 0 <inputs>
exit point:
INST PE 0
Some instructions can take some arguments that are known in advance. Examples are additions where one of the elements is already known or function calls with a few predefined arguments. It's important to know that every instruction needs at least one unknown attribute, an attribute which is not a literal. Any instruction that only accepts literals should be precomputed.
A literal is defined with the following statement:
LITR <instruction> <port> <= <value>
Where instruction is the index of an instruction, which is located in the current chunk. Port is the idx of the port where the literal will end up and value is the value of the literal. Thus adding a literal to an instruction at address 0 at port 1 is done in the following way.
LITR 0 1 <= "A literal string"
Literals can only be added to operation and context change instructions. The following table defines the various types that can be defined as literals.
| Type | Example |
|---|---|
| Bool | True |
| Number | 1298 |
| String | "Hello World" |
| Array | [21, "test"] |
Some programs do not need any external input to complete, in this case, the dataflow semantics do not allow DVM to actually execute anything. This is why the triv statement is introduced. If a program can be completely predetermined, it's value can be defined by using the triv statement.
The triv statement is similar to a literal without a real destination, instead, upon program start, the runtime will see if we have encountered any trivial statements. If we did, we simply return the value and stop execution. Only one triv statement should be present in a dis file.
A trivial program is defined with the following statement:
TRIV <= <value>
Thus the program
TRIV <= 42
Will never really execute and just return 42 instead.
The example below presents the DIS code for a program that contains most of the available DIS functionality while still remaining simple.
1.8.8
