Recursive microprogram
How to microprogram
n-machine (2)
The microarchitecture of n-machine is:
register bank: two read ports, one write port.
read port: selector xR, yR to feed two wires: s1, s2
write port: selector dR connected to rin (wires)
contain registers: e, {e1, e2 from ustack}, fp, sp, rv
alu: function {+,-,=,<,>,inc,pass1,pass2,isnil,isatom}
output to T register. =,<,>,isnil,isatom output 1/0.
input connected to wires: s1, in2
mux1 at inport of R
function {sT, sM}
select: mbus or tbus
input: mbus, tbus (from T)
output: rin
mux2 at input2 of alu
function {ss2, sarg, sfs, sk, snil}
select:
ss2 -- outport2 of R
sarg -- arg field of e
sfs -- fs field of e
sk -- k field of e
snil -- out nil
input: s2, arg, fs, k, nil
output: in2 to alu
T register connected to output of alu
mar register connected to tbus (output of T)
Memory address is connected to mar
Memory data is connect to mbus
writing memory data via tbus
reading memory data to mbus
One cycle of a
microprogram word
The cycle in one microprogram word does, reading two registers to s1,
s2, alu outputs to T, writing result back to a register, alternately
read or write memory, and miscellaneous control. The sequences in
simulator are as follows:
- xsrc R to s1
- ysrc R to s2
- sel mux2 to in2 alu
- alu op to T
- for mem cycle
- mW data from tbus, ads in MAR
- mR data to mbus, ads in MAR
- sel mux1 (mbus/tbus) to rin
- write to dest R
- misc control
- goto next
The control bits are defined in the microprogram specification
file. Their bit-positions are declared in the specification. The
following events are defined:
xsrc = xR where R = {e, e1, e2,
fp, sp, rv}
ysrc = yR
dest = dR
mux1sel = {sT, sM}
mux2sel = {ss2, sarg, sfs, sk,
snil}
alufunc = {add, sub, inc, eq, lt,
gt, pass1, pass2, isnil, isatom}
mem = {mR, mW}
goto = {jmp, jT, jF, switchop,
recur, ret}
control = {lmar, save, new, sys}
Microprogramming
There are two sections: signal definitions and microprogram
.s
signal* .m mpgm* .e
.. is the comment
signal is the name of event, the order denotes its bit-position in the
microprogram word. Each microprogram word contains:
:label
signal* /label ;
where :label is the declaration of label, /label is the use of that
label. ";" denotes the end of a microprogram word. label is
optional.
meaning of events
The semantic of each event is defined in the simulator, evalmp() (the
source file nmac.c).
- xR read R to s1
- yR read R to s2
- dR write R from rin
- mux1 selects mbus/tbus to rin
- mux2 selects to in2
- alu inputs from s1, in2 and outputs to T
- mem read/write memory, data to mbus, data from tbus, ads from mar
- goto branch in microprogram
- jmp unconditional, jT jump if T = 1, jF jump if T = 0
- switchop multi-way branch on opcode
- recur, ret recursive call microprogram itself
- control
- lmar tbus->mar
- save e->ustack[usp]
- new, sys system operations, alloc mem and i/o
How eval in hardware
do recursion
In the microprogram level, doing a recursion requires saving the
microprogram counter (upc) and the local variables of eval(), e.g. e,
e1, e2. Other variables: fp, sp, rv, rt are global and need not
to be saved/restored through recursive call of eval.
A microstack data structure, ustack[.] is used to save this context:
upc, e, e1, e2. The microstack pointer, usp, is incremented by
four per one recursive call.
ustack[usp]
= upc
ustack[usp-1] = e
ustack[usp-2] = e1
ustack[usp-3] = e2
The events that control ustack are: s_recur and s_ret. s_recur
does a recursive call by saving the context and goes to the beginning
of microprogram. s_ret restores the context , hence jumps back to
the previous upc.
s_recur
usp += 4
ustack[usp] = upc
upc = a_begin
s_ret
upc = ustack[usp]
usp -= 4
e = ustack[usp-1]
The e1 and e2 are used directly from the ustack. There is no e1
e2 registers explicitly. Hence, their values are already
preserved in the ustack when the recursive call occurs. No need
to save/restore them. e is a bit more complicate. e is also a
formal parameter so it will be overwritten by the actual parameter when
the recursive call occurs. The actual parameter will be at the
input port of register bank at the time of recursive call. To
handle this parameter passing, presently we use s_save to save the
current e to the current ustack then do register transfer and
s_recur. This is clean but requires two cycles.
The following microprogram segment illustrates the action:
..
e1 = eval e1
save ;
xe1
pass1 sT de recur ;
xrv
pass1 sT de1 ;
To reduce two cycles to one cycle two approaches are possible, 1) do
s_save and rin->e at s_recur. This is not elegant as in the
microprogram there is no receiver for the value passed from the source
(at ?).
..
e1 = eval e1
xe1
pass1 sT ? recur2 ;
...
2) To make it clear that the value is sent to e, "pushe" is used.
pushe does s_save and rin->e.
..
e1 = eval e1
xe1
pass1 sT pushe recur ;
...
Be careful about which ustack frame, e is saved to. e is saved to
the "current" ustack frame before the new one is created. Hence,
restoring e is done "after" popping ustack frame.
18 Jan 2005
P. Chongstitvatana