home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / arch / 10691 < prev    next >
Encoding:
Internet Message Format  |  1992-11-13  |  2.7 KB

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