Sender: eric@ruckus.brouhaha.com From: Eric Smith Newsgroups: alt.folklore.computers Subject: Microcode vs. state table (was Re: Interpretation of Machine Code) References: <19990114180140.27029.00000069@ng55.aol.com> <77o8s1$juo$1@roch.zetnet.co.uk> <36a062b8.10851490@news.newsguy.com> <1dlq95y.1rz3we6r7js2iN@usr225-edi.cableinet.co.uk> X-Disclaimer: Everything I write is false. Organization: Eric Conspiracy Secret Labs X-Eric-Conspiracy: There is no conspiracy. Date: 18 Jan 1999 16:39:12 -0800 Message-ID: Lines: 10 X-Newsreader: Gnus v5.5/Emacs 20.2 NNTP-Posting-Host: ruckus.brouhaha.com X-Trace: 18 Jan 1999 16:42:37 -0800, ruckus.brouhaha.com Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!isdnet!howland.erols.net!feed1.news.rcn.net!rcn!news.magicnet.net!nntp1.jpl.nasa.gov!news.spies.com!ruckus.brouhaha.com Michael Kircher writes: > http://micro.magnet.fsu.edu/chips/mos/mos6502reg.html > > OK, the ALU is clearly visible in the top half of the chip, and > there's a very regular structure at the bottom. From my memory, > this is the state-transition table of the 6502's finite automata, > and not micro-code. Why don't you consider a state-transition table to be microcode? What is the distinguishing characteristic? ###### Path: chonsp.franklin.ch!usenet From: Neil Franklin Newsgroups: alt.folklore.computers Subject: Re: Microcode vs. state table (was Re: Interpretation of Machine Code) Date: 19 Jan 1999 22:00:26 +0100 Organization: My own Private Self Lines: 30 Sender: neil@chonsp.franklin.ch Message-ID: References: <19990114180140.27029.00000069@ng55.aol.com> <77o8s1$juo$1@roch.zetnet.co.uk> <36a062b8.10851490@news.newsguy.com> <1dlq95y.1rz3we6r7js2iN@usr225-edi.cableinet.co.uk> X-Newsreader: Gnus v5.3/Emacs 19.34 Eric Smith writes: > > Michael Kircher writes: > > http://micro.magnet.fsu.edu/chips/mos/mos6502reg.html > > > > this is the state-transition table of the 6502's finite automata, > > and not micro-code. > > Why don't you consider a state-transition table to be microcode? What > is the distinguishing characteristic? A state-transition table encodes both then state -> new state and the state -> operator lines as optimized custom logic. Microcode implements both as tables in ROM or more seldom RAM. STT saves on transistors (good for 1970s single chip processors with 4 digit transistor counts) but becomes unwieldy in larger designs (_one_ of the reasons the Z8000 never really worked). Microcode gives ultimate freedom to use any combination and to easilly change it later on (new ROM or RAM reload) but it comes at an higher base price. -- Neil Franklin, Nerd, Geek, Unix Guru, Hacker, Mystic neil@franklin.ch.remove http://neil.franklin.ch/ Programming: when you stop hammering around on the computer as if it were a piece of dumb matter and instead tell it what to do for you ###### Sender: eric@ruckus.brouhaha.com From: Eric Smith Newsgroups: alt.folklore.computers Subject: Re: Microcode vs. state table (was Re: Interpretation of Machine Code) References: <19990114180140.27029.00000069@ng55.aol.com> <77o8s1$juo$1@roch.zetnet.co.uk> <36a062b8.10851490@news.newsguy.com> <1dlq95y.1rz3we6r7js2iN@usr225-edi.cableinet.co.uk> X-Disclaimer: Everything I write is false. Organization: Eric Conspiracy Secret Labs X-Eric-Conspiracy: There is no conspiracy. Date: 19 Jan 1999 16:16:15 -0800 Message-ID: Lines: 35 X-Newsreader: Gnus v5.5/Emacs 20.2 NNTP-Posting-Host: ruckus.brouhaha.com X-Trace: 19 Jan 1999 16:19:22 -0800, ruckus.brouhaha.com Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newsfeed-zh.ip-plus.net!news.ip-plus.net!news-nyc.telia.net!news.idt.net!enews.sgi.com!news.sgi.com!news.spies.com!ruckus.brouhaha.com I asked: > Why don't you consider a state-transition table to be microcode? What > is the distinguishing characteristic? Neil Franklin writes: > A state-transition table encodes both then state -> new state and > the state -> operator lines as optimized custom logic. Are you trying to describe a programmable logic array (PLA)? For a state machine that you describe, I can't imagine why your "optimized custom logic" would be anything more complex than a PLA. > Microcode implements both as tables in ROM or more seldom RAM. > > STT saves on transistors (good for 1970s single chip processors with 4 > digit transistor counts) but becomes unwieldy in larger designs (_one_ > of the reasons the Z8000 never really worked). > > Microcode gives ultimate freedom to use any combination and to easilly > change it later on (new ROM or RAM reload) but it comes at an higher > base price. A PLA is just a ROM that has some "don't care" terms in the product matrix. From your definitions I still can't see any important difference between horizontal microcode and a state-transition table, nor can I see why the state-transition table is fundamentally any more difficult to change than microcode in a masked ROM. If you wanted to change the behavior of an instruction you would modify some product terms of the PLA, and you might have to add new terms. This is not particularly different than changing a few microinstructions, and perhaps adding new ones. Since there is little difference between PLA "hardwired control" and horizontal microcode, any claim that the 6502 isn't microcoded seems to me to be somewhat misleading. ###### From: Michael Kircher Newsgroups: alt.folklore.computers Subject: Re: Microcode vs. state table (was Re: Interpretation of Machine Code) Date: 20 Jan 1999 16:55:26 +0100 Organization: CipLab - Institutes for Physics, University of Cologne, Germany Lines: 45 Message-ID: References: <19990114180140.27029.00000069@ng55.aol.com> <77o8s1$juo$1@roch.zetnet.co.uk> <36a062b8.10851490@news.newsguy.com> <1dlq95y.1rz3we6r7js2iN@usr225-edi.cableinet.co.uk> NNTP-Posting-Host: jupiter.ph-cip.uni-koeln.de X-Newsreader: Gnus v5.3/Emacs 19.34 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newsfeed-zh.ip-plus.net!news.ip-plus.net!news-nyc.telia.net!masternews.telia.net!news-feed.inet.tele.dk!bofh.vszbr.cz!newsfeed.gamma.ru!Gamma.RU!newsfeed.metronet.de!RRZ.Uni-Koeln.DE!usenet Eric Smith writes: > Michael Kircher writes: > > http://micro.magnet.fsu.edu/chips/mos/mos6502reg.html > > > > OK, the ALU is clearly visible in the top half of the chip, and > > there's a very regular structure at the bottom. From my memory, > > this is the state-transition table of the 6502's finite automata, > > and not micro-code. > > Why don't you consider a state-transition table to be microcode? What > is the distinguishing characteristic? I read this in the following document: http://www.tu-chemnitz.de/~fachat/vice/olddoc/Emulation.html and, to quote from this: "Unlike an average intel, the 6502 (at least the MOS/Commodore designs) doesn't have microcode (1), according to an authoritive source who answered a similar question in comp.sys.cbm several years ago. "Instead, a state device is utilised to enable each piece of operation at the correct time." It seems, that from a certain viewpoint, the difference between a state machine and (especially vertical) microcode indeed may blur. However, every CPU utilises a finite state machine to control its actions, and the easiest way to do this, is with a (usually *small*) lookup table. In contrast, when a CPU uses micro-code, this is like an additional layer between the hardware, and the target instruction set. It has its own microprogram counter, and the microinstructions (of a usually *large* microprogram) are executed sequentially. And it can be omitted, provided you throw enough hardware at this (witness 486 and Pentium - on the other hand, microcode seems to have a comeback on newer Intel compatible CPUs, where it's generated on the fly). The 6502 was simply too small to feature a full microcode engine. Greetings, Michael Kircher ###### Path: chonsp.franklin.ch!usenet From: Neil Franklin Newsgroups: alt.folklore.computers Subject: Re: Microcode vs. state table (was Re: Interpretation of Machine Code) Date: 20 Jan 1999 23:16:13 +0100 Organization: My own Private Self Lines: 158 Sender: neil@chonsp.franklin.ch Message-ID: References: <19990114180140.27029.00000069@ng55.aol.com> <77o8s1$juo$1@roch.zetnet.co.uk> <36a062b8.10851490@news.newsguy.com> <1dlq95y.1rz3we6r7js2iN@usr225-edi.cableinet.co.uk> X-Newsreader: Gnus v5.3/Emacs 19.34 Eric Smith writes: > > I asked: > > Why don't you consider a state-transition table to be microcode? What > > is the distinguishing characteristic? > > Neil Franklin writes: > > A state-transition table encodes both then state -> new state and > > the state -> operator lines as optimized custom logic. > > Are you trying to describe a programmable logic array (PLA)? Not. Actually I was trying to describe an other one of the 3 possible implementations (custom or PLA or ROM) of an STT. I will try to explain first these variants and then the original question of microcode/STT difference. I am trying to recall stuff from 10-15 years ago. Expect mistakes. Assume for this example an STT with 2^n states (n bits = flip-flops), i control inputs (from the instructions) and o outputs (to the system being controlled, such as select ALU op, select register to write). For each o you need an logic formula such as: the "ALU write" gate shall be on for ... followed by an list of n/i AND/OR combinations. Then the logic formula is simplified to include as little as possible of the n and i lines. To implement im ROM/PLA/custom you would then need: In an ROM STT system you would need to a) fully decode the inputs to get 2^(n+i) product terms and then b) derive from each of them n+m output signals. That requires of hardware: a) (2*(n+i)+1)*2^(n+i) transistors and b) 2^(n+i)*(n+o fuses and (2^(n+i)+1)*(n+o) transistors. Actually that would be an PROM, for real masked ROM drop the fuses in "b" and selectively remove "b" transistors to represent bits. In an PLA STT system you would decode (k) product terms, where k is significantly less than 2^(n+i). So that makes a) 2*(n+i)*k fuses and (2*(n+i)+1)*k transistors and b) k*(n+o) fuses and (k+1)*(n+o) transistors That is for PLA, for mask LA again drop all the fuses and selectively remove "a" and "b" transistors for bits. Aside: for an PAL remove all fuses in "b", leave "a" as in PLA. Mask LA is AFAIK what you will find in an 6502 or Z80. Because it saves a lot of transistors for an small enough k. In an custom STT system (as I was thinking of) you OTOH do not run an "2 grids" (a and b) shaped system. Rather you simply wire for each of the n+o output lines an AND/OR logic. This description is lousy, I know :-). But trying to describe, what for me was allways handled by visual thinking, in words is difficult :-(. Such logic can be reduced to even less transistors than the PLA/LA approach. The price for this is ... > For a state machine that you describe, I can't imagine why your "optimized > custom logic" would be anything more complex than a PLA. ... that there is no nice regular grid of fuses or transistors. You can not simply go and add/delete bits from an array. You have to rewrite and resimplify all of the logic formulas. And then relayout your chip. Quite a bit more of work than an PLA. Seems that (according to the other thread) the 6502 designers were prepared to go LA to avoid this. So the custom variant I was thinking of turns out to be irrelevant to the original discussion anyway. > > Microcode gives ultimate freedom to use any combination and to easilly > > change it later on (new ROM or RAM reload) but it comes at an higher > > base price. > > From your definitions I still can't see any important difference between > horizontal microcode and a state-transition table, nor can I see why the > state-transition table is fundamentally any more difficult to change than > microcode in a masked ROM. So back to the microcode/STT issue we were actually discussing: In an microcode (ROM or RAM) based system you for every instruction _compute_ an n = start address = s*i and then use an sequence of max s sets of o as output, n is in the mean time loaded with n+1 for each step (not by the ROM/RAM, but by an ordinary counter). One possible o action is to set an arbitrarily n (gives jumping in the microcode), but else n is not derived from the ROM/RAM. n has a large number of bits 12-20 unlike in STT where it will be in the 2-8 range. AFAIK the 80x86 and 680x0 use such an microcode ROM. Microcode gives you the freedom to change processor instruction behavior in the same way as changing an program: just change or add ROM/RAM lines and modify the jumps. This is possible because o is not derived directly from n, just indirectly via table lookup. In the STT you can not simply add new states because all outputs depend via tha a and b firmula directly on the actual n bit values. Any new n state will have random effects on o, So you need to redesign your entire logic formulas to prevent this. That is a lot more work. And the fundamental difference of STT vs microcode: not a table of bits but rather an series of formulas, one b line for each o and one a line for each AND subpart used in the formulas. You do not have an sequence of ROM/RAM lines for each instruction. You only have an line for each AND formula subpart. > If you wanted to change the behavior of an > instruction you would modify some product terms of the PLA, > and you might have to add new terms. But only after adding new states (that trigger them terms). And making sure that all the existing states still produce the same sequences. > This is not particularly different than changing > a few microinstructions, and perhaps adding new ones. Changing an STT is lot more change work, a lot more bug ridden. So STT is less flexible. Possible and cheap for simple processors, prohibitively difficult for complex processors (particularly when you need to add cycles to instructions). I suppose I should really run through an desegn example to show the difference. But that is too much for an post, and I have not got the time. But thanks for alerting me, that my book* I am writing will need such an example to make the case. * don't bother asking for finalisation date, I have been 4 years on it, still in conceptual phase. State of it on: http://neil.franklin.ch/Underst_Computers (1MByte ASCII) -- Neil Franklin, Nerd, Geek, Unix Guru, Hacker, Mystic neil@franklin.ch.remove http://neil.franklin.ch/ Programming: when you stop hammering around on the computer as if it were a piece of dumb matter and instead tell it what to do for you ###### From: lucvdv@null.net (Luc Van der Veken) Newsgroups: alt.folklore.computers Subject: Re: Microcode vs. state table (was Re: Interpretation of Machine Code) Date: Wed, 20 Jan 1999 21:28:45 GMT Organization: . Lines: 30 Message-ID: <36a7314b.1157904@news.uunet.be> References: <19990114180140.27029.00000069@ng55.aol.com> <77o8s1$juo$1@roch.zetnet.co.uk> <36a062b8.10851490@news.newsguy.com> <1dlq95y.1rz3we6r7js2iN@usr225-edi.cableinet.co.uk> NNTP-Posting-Host: pool02b-194-7-144-204.uunet.be Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Newsreader: Forte Agent 1.5/32.451 X-No-Archive: yes Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.belnet.be!newsgate.cistron.nl!het.net!news-feed.inet.tele.dk!bofh.vszbr.cz!remarQ-uK!supernews.com!diablo.theplanet.net!join.news.pipex.net!pipex!krypton.inbe.net!INbe.net!not-for-mail alt.folklore.computers << Eric Smith (19 Jan 1999 16:16:15 -0800); > I asked: > > Why don't you consider a state-transition table to be microcode? What > > is the distinguishing characteristic? > > Neil Franklin writes: > > A state-transition table encodes both then state -> new state and > > the state -> operator lines as optimized custom logic. > > Are you trying to describe a programmable logic array (PLA)? > > For a state machine that you describe, I can't imagine why your "optimized > custom logic" would be anything more complex than a PLA. It shouldn't be. Think of microcode as instructions that are being executed by a control unit, and of state transition logic as a logic gate array (even though it may be implemented in ROM technology). I used to have the data sheets of an old bit-slice processor (by Signetics, but I forgot the type number): it did't _have_ anything but microcode instructions, and making a real processor out of it was supposed to be done by putting enough slices together and adding a fast ROM to implement the 'real' instructions, as a microprogram per instruction (with 1 microinstruction executed per clock cycle).