summaryrefslogtreecommitdiff
path: root/README
blob: 1570c9d8b09ebcd79191a9e76d3c19494b41de2a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
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

camlsim/
	A circuit simulator written in OCaml.
	This program does NOT do the scheduling. The netlist must be passed through
	the scheduler first.
	This program is *highly incomplete* and not recomended for real use..
	$ cd camlsim/
	$ ocamlbuild simulator.byte

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]
	<destination variable> <addr size> <word size> <read addr var>
		<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

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 :

<address width> <word size>
<data>

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



TODO
----

- More advanced commands for the simulator (cf Jonathan's simulator)
- RAM reads give result immediately
- Optimisation : SELECT/SLICE a variable which is a CONCAT

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

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