Système Digital 2013-2014
Cours J.Vuillemin, TD T.Bourke

Alex AUVOLAT (Info 2013)


Introduction
============

Contents of the repository :
----------------------------

sched/
    A scheduler for netlists.
    Input : a netlist.
    Output : a netlist with topologically sorted operators
     plus a dumbed-down version for input to the C circuit simulator
    This program is also capable of a few optimisation (usually reduces netlist
    size by 1/4 or 1/3).
    $ cd sched/
    $ ocamlbuild main.byte

csim/
    A circuit simulator written in C.
    This program does NOT do the scheduling.
    This program does NOT read a netlist, it reads a specifically formatted
    dumbed-down netlist, that is output by the scheduler.
    $ cd csim/
    $ make

minijazz/
    The MiniJazz compiler (given by the teachers).

tests/
    Various test files.

*.pdf
    Documentation about the project.



REFERENCES
----------

  - Computer organization and design : the hardware/software interface
    4th ed
    Chapters 2 to 4



INTERNALS
=========

Convention for binary values
----------------------------

/!\ This convention is contrary to the one used in the example file nadder.mj
    (Therefore I have modified that file...)

The bit array [a_0 a_1 a_2 ... a_n-1] represents the decimal number :
    a_0 + 2*a_1 + 4*a_2 + ... + 2^(n-1)*a_n-1

When represented in binary, we write the bits in the order :
    a_0 a_1 a_2 ... a_n-1
Even though the normal notation for a binary number is :
    a_n-1 a_n-2 ... a_0

/!\ BINARY NUMBERS ARE WRITTEN REVERSE !

What we call a shift-left does a left shift on the representation as a binary
number, but we use the reverse notation here. Therefore in the ALU, the shift-left
should actually right-shift the bits when they are seen in the order a0, a1, ...

The right shift is also inverted.
- left shift -> right shift
- right shift -> left shift
- left shift logical -> rigth shift logical


The dumbed-down netlist format (OLD FORMAT)
-------------------------------------------

This is the description of the old format, not used anymore.

The C simulator does NOT read a properly formatted netlist, but only a file
representing it written in a simple format, that can be parsed with only calls
to `scanf`. The file is organized as follows :

<number of variables>
<variable types and names *1>
<inputs *2>
<outputs *2>
<number of equations>
<equation list *3>

*1 : this section contains for each variable a line in the format :
<variable width> <variable name>

In the rest of the files, the variables are referenced by their position in the
list given in *1 (the first line gives variable #0, etc.)

*2 : these section contain one line :
<number of inputs/outputs> [<variable number> ...]

*3 : this section contains one line for each equation, in the following format :
<destination variable> <equation type> [<argument> ...]

Table of equation types :

Type#   Desc    Arguments
0       Arg     <arg>
1       Reg     <var#>
2       Not     <arg>
3       Binop   <op# *4> <arg> <arg>
4       Mux     <arg> <arg:when false> <arg:when true>
5       Rom     <addr_size> <word_size> <arg:read_addr>
6       Ram     <addr_size> <word_size> <arg:read_addr> <arg:write_enable>
                    <arg:write_addr> <arg:data>
7       Concat  <arg> <arg>
8       Slice   <begin> <end> <arg>
9       Select  <id> <arg>

An argument (<arg> or <arg:*>) can be either a binary value, represented by the
bits in standard order defined above, either a reference to another variable,
with the syntax $<var_id>

*4 : The operators are :
0   OR
1   XOR
2   AND
3   NAND
    
This syntax is formalized by the reference implementation provided in the source
file csim/load.h.

To simplify the internals, we have created an intermediate format where <arg>
can be nothing but a reference to another variable. All constants will then have
to be assigned to a constant-type variable that can be counted among the inputs
(or whatever - anyway, no need to recalculate them at every iteration). This new
file format is the one described in the next section.


The dumbed-down netlist format (NEW FORMAT)
-------------------------------------------

This is the description of the format currently used by the C simulator.

<var count>
[for each variable]
    <var size> <var name>
<input list size> [for each input <input var id>]
<out list size> [for each input <output var id>]
<register list size>
[for each register]
    <register destination variable> <register source variable>
<ram list size>
[for each ram]
    <addr size> <word size>
        <write enable var> <write addr var> <data var>
<equation list size>
[for each equation]
    <destination variable> <equation type> <args...>

Equation types :
ID  DESCR       ARGS
--  -----       ----
0   Copy        var_id
1   Not         var_id
2   Binop       op_id var_a_id var_b_id
3   Mux         var_a_id var_b_id
4   ROM         addr_size word_size write_addr_var_id
5   Concat      var_a var_b
6   Slice       begin end var_id
7   Select      number var_id
8   RAM Read    ram_number var_id

Operators :
0   OR
1   XOR
2   AND
3   NAND

Constant variables are standardized so that their name (eg. $00101)
gives the value of the constant, therefore there is no need to write a constant
list in the program file.


The Input/Output format
-----------------------

The C simulator is capable of reading inputs for each step from a file (by
default stdin, but can be redirected from a file using the -in option) and of
writing the outputs at each step to a file (by default stdout, but can be
redirected with -out).

The input format is extremely straightforward : at each step, read a line
containing for each input variable, *in the order given in the program file*,
either a binary value (represented by a series of bits given in the standard
order), either a decimal value prefixed with a slash (/), which is then
converted to binary according to the standard representation defined above.

The output format contains at each step one line for each output variable, in
the format :
<variable name>\t<binary representation>\t<decimal representation>
The output contains an empty line at the end of every cycle.


How ROMs are handled
--------------------

The MiniJazz language has many flaws, and one is the impossibility to specify
what is to be loaded in a ROM (it can be specified in the .mj file, but it won't
appear in the generated .net file).

To know what file to load in a ROM chip, we recognize a certain prefix in the
name of the variable holding the ROM. For example, if we have in a netlist the
following line :

    decode7_128 = ROM 4 7 _l_42_122

which is a possible output for the MiniJazz compiler, and if the simulator is
provided with the command-line argument :

    -rom decode7 path/to/decode7.rom
    
then the simulator will detect the prefix `decode7` in the variable name
decode7_128, and use the ROM data from the file specified on the command line.

The format of a ROM file is as follows :

<number of words defined> <word size>
<data>

The data is composed of n values separated by spaces. If they have no prefix,
they are read as binary. If they have a / prefix, they are read as decimal. If
they have a x prefix, they are read as hexadecimal (this enables the use of
whichever representation is preferred).

When the ROM is used, all the extra words (those needed by the simulator but
not defined in the ROM file) will be considered zeroes.



TODO
----

- More advanced commands for the simulator (cf Jonathan's simulator)

NEXT STEPS
----------

- Define convention for processor input/output
- Code UI
- How can we generate netlists with ocaml code ?
- Code processor