Home build microcode design

[rstofer]

My "only" issue has been I have way more "enable" bits than I expected to have, so I am trying to reduce them with gates first, and THEN I'll assign them to microcode bits.

My IBM1130 emulation has about 80 enable bits and more than half are encoded = use 3 bits to represent 8 alternatives, etc.  That decoder is fairly cheap in an FPGA, not so cheap in discretes.  Actually, under the covers, the FPGA will assign one bit per alternative (known as one-hot encoding) so the overall word length is probably around 150 bits - just guessing, too many to count.

Adding external logic to reduce the width of the microcode word adds more chips to the design (decoders, AND, OR, etc) and really complicates the discussion.  In every case, speed, simplicity, whatever, wide is better.  Except that the usage will necessarily be sparse.

The state machine has 116 states and it is one-hot encoded.  So when I save the return state to a register, that register is 116 bits wide.  Ouch!

So, 116 words of 150 bits.  Not that bad really!  20 chips of 256x8 will do nicely.

Bigger CPUs will require more microcode.  The 1130 has a fairly limited instruction set and is essentially register-less except for those 3 index registers in RAM and the usual Accumulator, Extension, Program Counter, Memory Address Register and Memory Buffer Register.  No array of general purpose registers.

Let me show you a little about testing conditions in microcode - ok, in VHDL but the idea is the same (file attached):

When I get to the FETCH state, I first look at the DisplaySwitch and if it is set, I simply fetch the contents of memory and display it.  The address comes from the console entry switches.  You can see the A_BusCtrl field is set to select the console entry switches with the A_BUS_CES selection of the A bus MUX (29 inputs used).  I then load the Storage Address Register and head off to a MemRd.  I return to state s0c which just puts the contents just read in the Storage Buffer Register (code not shown, not important).

The point is, my microcode word would need a bit called TestDisplaySwitch which would be gated with the actual switch signal to determine whether to do those things above or continue to the next bit of code when another bit tests for a PendingInterrupt.  I can do this and still have the ability to do the actual fetch in the same FSM cycle because I can have multiple next address fields (s0c, s1a, s2).  You probably can't do it that way in microcode so you will need more cycles.  Test the DisplaySwitch and move to Test for Pending Interrupt and move to the actual Fetch.   Three cycles unless you get very creative.  But notice that each of the two tests will have a separate next address field and the logic that determines whether to get the next microcode word from the PC or next address field will have 2 more inputs.  That is going to be a very wide OR gate with LOTS of 2-input AND gates feeding in test results.  There are a lot of decisions to make and every one of them will involve selecting which address to use next.

In each of these blocks, you can see where various outputs are being manipulated.  This is just exactly what your microcode has to do.

Hope this gives you something of value!

[rstofer]

As I said above, the FPGA code will result in a very wide next address field because of one-hot encoding.  The synthesizer does this so that exactly one bit is high at each state.  In the case of microcode, the next address field will be a binary number so maybe only 8 bits wide for 256 lines of microcode.  The need for one-hot disappears because the wide microcode word already deals with selecting individual control signals.  So, maybe the memory is 256x96 or a dozen ROMs.  Maybe even less.  Don't let the numbers I posted above concern you too much, your code won't look much like the VHDL implementation.  But the ideas are the same.

You can use a MUX on the test signals if you are only testing one signal at a time.  So, if you had 16 discrete tests, you could use a 16:1 MUX and control it with 4 bits.  This replaces the large OR gate and the quantity of AND gates.  If you needed 32 tests, you could use 2 MUXen and just OR the output to the address selection MUX.  This might be a little more difficult if there are 4 inputs to the address MUX.  You might use 2 microcode bits to select one of 4 address choices and the output of the test MUX to enable the selection.  Just make sure it defaults to the program counter.

[bitman]

That decoder is fairly cheap in an FPGA, not so cheap in discretes.  Actually, under the covers, the FPGA will assign one bit per alternative (known as one-hot encoding) so the overall word length is probably around 150 bits - just guessing, too many to count.

I'll go back to reading here, but I do want to point out that I'm just playing with simple 7400 series ICs here. No FPGA, no tricks up the sleve - just plain old 1970ies technology to show the basics of a processor (granted, I have RAM in my setup but let's not be that precise). FPGA is way beyond my "little" project and it's capabilities will not help here. I had the same thoughts about using the 181 because a lot of the complexity is hidden inside the chips and hard to demo - just having a simple adder and XOR for subtraction would have allowed me to show easily how things are done electronically. But I wanted more features than just those two operations so I eventually opted for the 181. Going to FPGA is overkill. Do they even make them with "thru-hole" setups?

But again I have to thank you for the tremendous amount of information here. It's very informative and I've picked up a lot of tricks I weren't aware of before.  Some of the books mentioned on this thread is on order, but won't be delivered for weeks - so in the mean time I'll fool around with my 7400 series chips.

[rstofer]

My FPGA exsmple wasn't intended to sell FPGAs, just illustrate that there will be a good deal of condition testing, even in microcode.  I was thinking that every place I have an IF or ELSIF statement, I am testing something external to the current state and making a decision on where to branch next.  The exact same thing happens in microcode.

You will most certainly have conditional instructions (JZ, JNZ, JC, JNX, JP, JNP) and potentially DJNZ.  Or maybe there are repetitive MOV statements.  All of these will require testing and branching within microcode.

It's easy to think through the simple LDA, STA, arithmetic and logical instructions, no branching is required in the microcode.  This test/branch issue will start to show up when you begin decomposing the instruction set in to steps.

[C]

I think you would gain a lot watching Video I posted.

Video talks about micro sequencing so that you can have many steps for each instruction.
This one simple idea, lets you use much simpler logic. 

Think of your microcode
If you latch the output of your EPROM microcode, then A clock can start Eprom changing to new address and you have output of latches controlling your logic for a clock cycle.
This time from start address change to latch data output sets min time for a clock cycle.

Video shows this and answers other questions you have asked.

Need to keep in mind Video is about newer CPU where the PDP-11 was built from simple TTL with the fancy chip being the 181

[rstofer]

The Video linked above mentions Patterson & Hennessy and the appendix where a microcoded MIPS is discussed.  My hardcopy of P&H doesn't have it nor does this 900+ page PDF

http://nsec.sjtu.edu.cn/data/MK.Computer.Organization.and.Design.4th.Edition.Oct.2011.pdf

This may take a while to download but it's free!

I found the appendix here:

http://www.cs.tufts.edu/comp/140/files/Appendix-D.pdf

Glossing over the material, it appears that there are only 10 states in the MIPS control unit and only a couple of dozen (less, actually) control outputs.  This is possible because the MIPS is a RISC machine.

There are other documents on the Internet that, along with the book above, work to describe the MIPS architecture.  It is notable that Microchip uses the architecture in their PIC32 processors.

Figure 2.4.6 shows a separate adder used to form microprogram_counter + 1.  I don't know (yet) if the counter could be implemented as a counter/register.

It would take some time to really understand the Appendix.

Dr. Hennessy was one of the founders of MIPS Computer Systems Inc.

[rstofer]

That video linked above is well worth the time. 

For a simple machine like the LC3b, the microcode is short (31 instructions) and directly to the point.  Note that there is no microcode PC, the next address field is used in every instruction.  This is a nice way to go when the microcode is short.  But what happens in these very compact code sequences is that the programmer has to assign specific addresses early on (like 0,1,2,...15 for the op code branches) and, necessarily, the initial microcode instruction address for the LC3b coming out of reset isn't 0, it starts at 18.  What isn't shown is how that comes to be.  It can't start at 0 because that is the branch address for instruction code 0.

Here is a description of the microarchitecture of the LC3b there is much more available on the Internet:

http://users.ece.utexas.edu/~patt/05f.360N/handouts/360n.appC.pdf

Note that the ISA for the machine is very basic but it does have 8 registers in a bank along with a distinct PC (page 7).

This is a very approachable CPU.  I would certainly be more interested in this design as a learning tool than in some truly hairy CPU like the Z80.

Other than as a notational tool, I don't care for "don't cares".  I assume that the "X"s will be replaced by "0"s when the ROM is programmed.  "Don't cares" make sense in Karnaugh Maps where I can use them to reduce the logic.


There is a C compiler available for LC3b.

[rstofer]

I have been looking for a project.  Given that there is a C compiler for LC3b, maybe I should implement it in an FPGA using the structure of a microcoded design.  That will be FUN!

[C]

 rstofer

Some people think that a RISC machine is simpler then a CISC machine.

I look at that statement as a loaded question.

For example, Today I see most designs being based on a fixed clock.
This changes what is possible in a design.

The PDP-11 is not a Fixed Clock machine.
The microcode has a field that selects what delay is needed for each microcode step!. In place of one fixed in time critical path time, you have many different times.
The PDP-11 uses a delay line as it's clock source. The selected output of this delay line becomes the next input to the delay line.
With this, you can have a microcode step where the microcode address change is the critical path time and have a critical path that adds the delay of the 181 for a second critical path time.
CPU logic is still clocked logic but clock is not a fixed time length but in many fixed time delays.

So a small change can change the design rules.
This change also lets microcode do more with less logic by using more steps.

Adding Rows & bits to microcode can be a lot cheaper for chip count then adding a bunch of logic.

To restate What I have said
The PDP-11 makes 8 registers visible to the ISA.
The PC one of the 8, is made into the PC Register by Different microcode.
Any one to the 8 registers can be a Stack Register. It's the microcode that connects the PUSH/POP instructions to the stack register.

To Make logic in CPU simpler 16 registers are used internal to CPU
The Address bus, Data bus, control bus & IR register are some of the hidden 8 registers.

So should you look at MIPS if your are building with TTL chips and not a CHIP where you have many transistors?

Microcode with micro sequencing, you can build a CPU with a lot less chips and use the 181 ALU many places for it's math & logic reducing chip count more.. 

From a Teaching point of view, starting from very simple that works with options to add more parallel processing later would be easer to teach.
 

Figure 2.4.6 shows a separate adder using to form microprogram_counter + 1.  I don't know (yet) is the counter could be implemented as a counter/register.

With micro sequencing, you can use the one  ALU to add to the PC while instruction fetch is happening.

As I see it, if you are building from TTL chips, less chips is easer to build and teach.
Using a register file where possible is much less chips then having many registers with many inputs & outputs.

If the CPU is built around an ALU based on the 181, it is smart to use the 181 as much as possible.

Need to keep in mind that LC3b is a 32-bit RISC CPU.

That video linked above is well worth the time. 

 I would certainly be more interested in this design as a learning tool than in some truly hairy CPU like the Z80.

Hairy Z80
Are you comparing apples to oranges?
An 8-bit base instruction set size has a lot of limits due to being 8-bits wide.
Think you would find that Z80 in microcode with micro sequencing is very simple.
The base instruction set is the 8080 where
D7, D6 is and instruction field used to select 4 groups of instructions.
D5,D4,D3 and D2,D1,D0 are two octal based fields.
The instruction set is simple when you use octal to look at instructions.
What Z80 added to 8080 instruction set is also simple & logical.

[rstofer]

First up, the COMPLETE LC3b takes 52 states, not just the first 31.  This is caused by interrupt and trap handling.  It is described in Appendix C.  http://highered.mheducation.com/sites/0072467509/student_view0/appendices_a__b__c__d____e.html

Second, by CISC, I mean CPUs that have complex instructions like DJNZ or REP MOV, instructions that can take a variable number of cycles (states) and require more condition testing.  Do you interrupt a complex instruction?  How do you recover?  Can a REP MOV instruction destroy interrupt latency?  That kind of thing...

The RISC term, as I intend it, is used to describe CPUs where all computing is done between registers.  Those registers are loaded and stored (LOAD and STORE architecture) but no computation is done using memory as an operand.  Operands are in registers.  Which allows overlapped fetch and, ultimately simplifies pipelining.  The registers and ALU can be doing whatever while the fetch and decode units are doing their thing.  Not that this is the only way of doing things.

I haven't had this much fun since grad school!  It's been more than 40 years but we spent a great deal of time discussing the PDP-11.  This was primarily due to it being understandable with a reasonably orthogonal ISA.  I never used a PDP-11 (sadly)...  My low end experience is with the IBM 1130 and, on the upper end, the CDC 6400.  That 6400 seemed so fast, at the time ('71), but it was only about 1 MIPS.  Lunar Lander on the console was a lot of fun!

This LC3b is a very complete CPU.  It has just about all the features of any modern CPU (ARM, etc) except for virtual memory.

[rstofer]

One of the reasons I consider the Z80 to be 'hairy' is the fact that a partial instruction decode is necessary just to determine how long the instruction is.  It can be 1,2,3 or 4 bytes.  Just the instruction fetch cycle requires a lot of thought.  And the first byte could just be an escape code (0xED) and the real op code is in the second byte.

Instructions like LDIR require the microcode to count and loop.

The register to register instructions are straightforward.  It's all the instructions around the outside that take a lot of thought.  In any event, I linked to a book earlier in the thread that breaks it all down using spreadsheets.  It's a very nice approach!

[C]

Does the Z80 have one instruction set?

If you look at problem a different way Z80 has 4 or 5 instruction sets.

0xED could be thought of a one instruction cycle switch to a different instruction set.

ARM does an instruction to switch and stay in thumb instruction set.
This costs a thumb instruction to switch back.

Instructions like LDIR require the microcode to count and loop.

Why does it have to count.
You have two memory cycles, While this is happening you need to do two adds and one subtract with the idle ALU and check Zero output of ALU one time.
Nothing new just not using an instruction to cause a conditional jump on Zero.

[bitman]

I think you would gain a lot watching Video I posted.

I'm about 30-40 minutes in. So far nothing but bullet points about stuff he's going to talk about and attempt at humor that seems to counter his capable knowledge.  I'm not done - and I'm just responding to the few issues I think needs to be addressed, in order to set expectations.
I'm by no means ignoring the advice here. I've ordered a few books, and given videos inspired me to do this, I've watched A LOT of them already and more to come.

[C]

There is a short spot in video talking about micro sequencing.

With this Idea the microcode can act like a computer with parallel tasks.

If done correctly, your ALU the 181's can be used many places in the microcode with little to no cost.

for example
During instruction fetch while waiting on memory, the ALU can be updating the PC.
You already have the ALU just sitting there, it's just some microcode to add one to PC.

Note that by using the 181 you can select one of two inputs.

You need to keep asking, "can the 181 ALU do this and save some added logic?"

In place of starting small and adding as needs arise, Try thinking huge and look at cost to reduce it more.

With an 8-bit wide ALU, which makes more sense to save chips. Adding even more hardware to get 16-bits where needed or doing two steps with 8-bits to get the 16-bits.
Proper design of an 8-bit ALU will let you any size in chunks of 8-bits.

How you look at a problem can really effect what you see as a cure to a problem.
 
I think for your project, a low chip count is important. Being able to use the ALU many places for it's math and logic can remove need for other logic.

Can your existing ALU design be used to operate on any size taking 8-bit steps?
Can your microcode set all 5-bits of control inputs?
Can your microcode direct anything to the inputs of the ALU?
Can your microcode direct the output of ALU to anyplace?

Can you microcode be changing to next state while current state is being processed?

Need to keep in mind that you are more interested in a low chip count where a lot of videos are about how is best to use the many transistors on a chip to get the best use of them.

I think you have spent a lot of time to get where you are at.
If you set it to the side, can you see a better way that uses less chips?

What often looks complicated to do in logic is at times very easy in microcode with less logic.

You have talked about reducing width of microcode.
Each 8-bits in width costs one chip. How many chips will be needed to reduce the width?

 

[rstofer]

The more places you use the 181s, the wider the ALU input MUXen will need to be.  At some point, you will have a MUX on both the A & B inputs but the question is how wide they need to be.

Again, one common operation is to increment the PC.  This can be done with the main 181s, a separate adder (only) or, even easier, by using a parallel loadable counter.  I would go with the counter.  Adding one is nearly free and you'll need a register for the PC in any event.

If, OTOH, you use a register file chip, it would seem reasonable to have the PC in the file.  This might be a mistake because it won't allow the PC value to be updated while the ALU is using other registers.  So, I would leave the PC outside of the file.  Or, you take more cycles with more microcode.

There is no reason why the 181s can't add 1 to the PC.  Just don't update the condition codes.  You need to update those only when specific instructions require the update.

One cool thing about the register file chip is that, in essence, it already has a MUX on the output.  You can select which of 16 registers are on the output pins.  You may still want to have parallel banks of registers but that depends on how you implement the microcode.

Patt & Patel Appendix C  Pages 568 and 570 (linked yesterday) shows a very diagrammatic way of approaching the FSM.  The Verilog book I linked earlier shows a very nice spreadsheet approach.  But the absolute first thing that needs to be done is to decompose each instruction into little steps - one per clock cycle.  Once that is done, the hardware requirements will be obvious.  You will know how data has to flow through the datapath and all the microcode has to do is manage the traffic.

If you try to use the approach of page 568, you don't have to leave the decode state in a star arrangement as shown.  You can take each of the sequences and draw them as parallel vertical stripes.  P&P doesn't need to do that because there are so few instructions.

The video gets better....  Still, it's only an overview of the sequencer but it does show how the various bits in the microcode control which register is gated on the bus, which register is loaded from the bus, how the next address is worked out and so on.  Remember, certain states are predeclared (0..15) so the code needs to branch all over the place.  Absolutely nothing will be sequential (look at 15,28,30).  It is up to the programmer to figure out the addresses.  Note in the video how the condition codes modify the next address.  Again, these result in fixed addresses so assigning addresses is going to be a large part of a design like this.  But the microcode is compact!  Fifty two states and 49 control signals for a full RISC CPU that handles traps, system calls, priority interrupts, IO devices, several registers and looks like every other RISC machine (ARM, MIPS, etc).

The alternative is to branch to somewhat wider spaced addresses (say 8 x op code) so that each instruction starts with 8 dedicated sequential addresses.  Then if you need more, you can branch to some pool of addresses way out yonder.  Instead of bouncing all over the place, you can organize your code in a nice linear sequence.  Since the code store is cheap and you're not looking for speed, why not see how many states the longest instruction takes, round up to a binary multiple and space all the instructions that far apart?  The only downside is that the next address field gets wider and requires a wider ROM bank and address register.

One advantage of the longer linear arrangement is that you can work on one instruction at a time.  One of the reasons my 1130 is so large is that I actually did work one instruction at a time.  I made no attempt to share common subsequences, I just took the most straight forward approach to coding the FSM.

One issue with tightly compact microcode is that you are truly screwed if you overlooked a state.  You can't simply add another inline statement, you need to branch to some empty location.  Your thought process is strung out all over the place.  Since the next address is programmer supplied, there is no need for a microcode program counter.

For my 1130 project, all of the thinking about each instruction is all in one place.  Certainly not a minimal design and clearly not a workable approach for minimal hardware.

Reading around the Internet, I see where the Z80 was random logic and the Z80A was microcoded.  Don't know if it is true.

[westfw]

I wanted to ask here what a typical design would look like

I guess that this may be stale by now, but you're essentially looking at the difference between "vertical" and "horizontal" microcode.
Vertical uses "many" shorter microoperations to execute an instruction, while "horizontal" microcode has wider microoperations that do a lot of things in parallel.   Assuming a horizontal scheme, it was common to have "very wide" microcode.  Here's a photo of one of cisco's microcoded interface cards from the late 1980s (one of quite a few similar designs):

I'm counting ... 104 bit wide microcode?  13x 8bit-wide highspeed EPROMS.
Now, probably 16bits of that was a RAM address, and 14bits or so was the "next address" field, but...
(Given the history, this was probably similar to the microcode architecture used by DEC in their 36bit mainframes...)

[rstofer]

I just finished coding up LC3 in Vivado, probably for the Nexys4_DDR (it has switches, LEDs and 8 digits of 7 segment displays).  I have only completed the basic instructions, I figure I should test those before I start on interrupts and privilege levels.  A couple of thoughts:

First, I wanted to think about the CPU in terms of microcoding but I didn't really want to put microcode in BlockRAM.  But as I coded the conventional state machine approach, I was struck by how similar the coding is to microcode written with a meta-assembler.  In true microcode, we define a wide word and break it up into named fields.  We assign a default value to either the entire word or to specific fields.  If a microcode step doesn't deliberately define a value for a field, it assumes the default value.  This is EXACTLY the case with VHDL - in the combinatorial part of the FSM, we MUST define default values to the fields to prevent the inference of latches.  Then within the Case statement each 'when' statement is a single line of microcode.  We set values to the various fields that need to be considered in the state and we leave the others as default.  The only physical difference is that I don't usually define one great big word, rather I name just a bunch of fields and I don't care how they are organized because it doesn't matter.

If, OTOH, I did define a great big word, I could break it up into fields using the 'alias' construct.  Then I could deal with individual fields exactly as I do now.

Bottom line, there is no difference between microcoding and writing FPGA code.  The very same things happen in the same cycle either way.

Second, that Appendix A & C from Patt & Patel (linked earlier) is an EXCELLENT introduction to microcoding.  Appendix A has the Op Codes and what they are supposed to do and Appendix C describes the hardware layout and the microcode transition diagram.  There is a worksheet for filling in the '1's and '0's of the microcode.  Just completing the primary instructions will be a terrific introduction to microcode.  There isn't always a direct path from one part of the system to another.  Sometimes you need to route the data through MUXen and adders (where, in a couple of cases you add 0 and in one case the main ALU just does a passthrough, HINT!).

This all ties together to become an excellent introduction to hardware design (a simple single bus multi-cycle architecture), FSM layout and microcoding.  It is well worth the time even if it isn't the appropriate target.  The video gives an overview of the process but the professor only codes about 4 states - and he did the easy ones!

Now I need to come up with a way to test it...

To those that start a similar project with Vivado, I will give a huge HINT!  There are syntax errors that cause the file to be removed from the project hierarchy and placed in a non-module status.  One example might be a missing ')'.  The JIT syntax analyzer doesn't always catch it and as soon as you save the file, it is removed from the hierarchy!  No power on earth will get it back in the source tree!  You need to go through your most recently added code and look for syntax errors.  Once corrected, the file will be automatically restored to the hierarchy.  I'll bet I spent an hour looking through Google for a solution and, if it's there, I missed it.  I eventually discovered how it came to be and I started commenting out blocks of code until it was restored and then removing the commenting until it failed.  Sure, it sounds easy now but it took me a while to figure out what was happening.  No such error ever occurred with ISE!