home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!mcsun!sunic!dkuug!diku!torbenm
- From: torbenm@diku.dk (Torben AEgidius Mogensen)
- Newsgroups: comp.arch
- Subject: Re: MINIMUM instruction set
- Message-ID: <1992Nov13.113147.11856@odin.diku.dk>
- Date: 13 Nov 92 11:31:47 GMT
- References: <1992Nov10.235849.19192@fcom.cc.utah.edu> <pete.180021.12Nov92@sst.icl.co.uk>
- Sender: torbenm@freke.diku.dk
- Organization: Department of Computer Science, U of Copenhagen
- Lines: 48
-
- pete@jura.uucp (Pete Bevin) writes:
-
- >You can get away with four instructions in the following (rather
- >inefficient) Turing-Machine-equivalent architecture. Allow yourself a
- >number of registers, each of which can hold large enough numbers for
- >what you want to do. Then, you only need:
-
- > Z(register): Zero a register
- > S(register): Increment a register (`S' for `successor')
- > T(r1, r2): Transfer value from r1 to r2
- > J(r1, r2, address): Jump to address if r1 and r2 hold the same
- > value.
-
- >You wouldn't want to program it, but I guess it's fairly easy to reason
- >mathematically about it.
-
- The efficiency of such a machine is horrendous even compared to the
- one-instruction machine (reverse subtract and skip on borrow). On the
- latter you are at least able to do most arithmetic only about ten
- times slower than a "normal" processor. The main limitation of the
- latter is the lack of bitwise logic operations. Though these can be
- simulated using subtraction, this is horribly slow (though not as bad
- as on the 4 instruction machine above). If we make the single
- instruction capable of both logic and arithmtic at the same time we
- are home. A very general instruction would be
-
- x:=(a-b) and not (c>>d), skip on borrow
-
- but that has 5 addresses. We can reduce this to 4 by letting x be
- equal to one of the arguments, say b and to 3 by replacing d by a
- constant, say 1. The latter makes arbitrary shifts more expensive. One
- could consider to make the shift interact with the borrow flag, but I
- think that would only complicate things.
-
- One could consider what we the purpose of a one-instruction machine
- is, apart from proving it can be done. None of the above machines will
- be substantially smaller than normal machines if built in hardware, so
- this is not a good reason. The code density will be horrible, as you
- need more instructions and these are not very much smaller, if at all
- (as they need memory operands).
-
- So here is a challenge: design a machine that uses no more than 4 bits
- per instruction (including operand fields), is Turing complete, not
- terribly inefficient and which can be built using far less hardware
- than current microprocessors. The latter would make it suitable for
- massively parallel systems.
-
- Torben Mogensen (torbenm@diku.dk)
-