home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / arch / 10610 < prev    next >
Encoding:
Text File  |  1992-11-11  |  3.9 KB  |  108 lines

  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!news.uiowa.edu!news
  3. From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
  4. Subject: Re: MINIMUM instruction set
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1992Nov11.144304.10494@news.uiowa.edu>
  7. Date: Wed, 11 Nov 1992 14:43:04 GMT
  8. References: <1992Nov10.235849.19192@fcom.cc.utah.edu>
  9. Nntp-Posting-Host: pyrite.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 95
  12.  
  13. From article <1992Nov10.235849.19192@fcom.cc.utah.edu>, by val@news.ccutah.edu (Val Kartchner):
  14. > I've heard that it is possible to implement all programming languages with
  15. > seven instructions.
  16.  
  17. What is an instruction?  Ignoring I/O, the following CISC instruction does
  18. the job:
  19.  
  20.     DB <op1> <op2> <op3>
  21.         Decrement <op1> by <op2> and branch to <op3> if the result
  22.         is less than zero.  All operand fields address memory.
  23.  
  24. This can be modified to a tighter form:
  25.  
  26.         DAB <op1> <op2>
  27.         Decrement <op1> by the value in the accumulator, leaving the
  28.         result in both the accumulator and <op1>; branch to <op2>
  29.         if the result is negative.
  30.  
  31.         To load the accumulator, first zero it, then decrement
  32.         something by it.
  33.  
  34.         To zero the accumulator, decrement the same location twice
  35.         in a row (leaving both AC and the location zeroed).
  36.  
  37.         To add, first negate then subtract.
  38.  
  39.         To negate, subtract from zero.
  40.  
  41.         To store, first zero the destination memory location and
  42.         negate the value to be stored, then store it.
  43.  
  44. Further modifications are possible.  For example, if the program counter
  45. is memory-mapped, then this instruction can be reduced to a one address
  46. instruction:
  47.  
  48.     DA <op1>
  49.         Decrement <op1> by the value in the accumulator, leaving
  50.         the result in the accumulator and <op1>.
  51.  
  52.         To branch, decrement the program counter by the negated
  53.         relative address of the destination.
  54.  
  55.         Conditional branches are tricky.
  56.  
  57. Even though the above approaches all reduce the instruction set to a single
  58. instruction, the instruction is complex -- these are not RISC machines.
  59.  
  60. An alternate approach to this is the "move machine" or Ultimate RISC.  Here,
  61. the CPU has one instruction set and no ALU or accumulator.
  62.  
  63.     MOV <op1> <op2>
  64.         Move <op1> to <op2>.
  65.  
  66.         To do arithmetic, add a memory mapped accumulator and a
  67.         memory mapped ALU.  The only essential operations are
  68.         load and store accumulator, subtract from accumulator,
  69.         and inspect sign of accumulator
  70.  
  71.         To branch, make the program counter memory mapped and
  72.         move the destination address to it.
  73.  
  74.         To do a conditional branch, move the sign of the accumulator
  75.         to the accumulator, subtract the destination address
  76.         (producing one of two addresses), and move that to the
  77.         program counter.
  78.  
  79. The 7 or 8 instruction minimum you suggest could come from the DEC PDP-8,
  80. a machine that had only a 3 bit op-code field (see alt.sys.pdp8 for more
  81. than you ever wanted to know about that system), or it could come from
  82. my Minimal CISC, a stack machine with the following instructions:
  83.  
  84.     NOP     Do nothing.
  85.     S1    Shift a 1 into the stack top,
  86.     S0    Shift a 0 into the stack top,
  87.             A sequence of S1 and S0 instructions will shift
  88.             any constant into the word on the stack top.
  89.     DUP    Duplicate the stack top.
  90.     POP    Store the value in the stack top in the memory location
  91.             pointed to by the value below it on the stack,
  92.             then pop both values from the stack.
  93.     FETCH    Replace the value on the stack top by the memory location
  94.             it points to.
  95.     SUB    Subtract the top element of the stack from the element
  96.             below it, popping both and pushing the difference.
  97.     BRNEG    Branch to the address on the stack top if the value below
  98.             it is negative.  Always pop both whether or not
  99.             the branch is taken.
  100.  
  101. Note that these instructions have no operand field, so each instruction
  102. is exactly 3 bits.  They can be packed 5 to a 16 bit word, for example.
  103. Branches are always to a word boundary, so NOP instructions are frequently
  104. needed to pad out to a word boundary.
  105.  
  106.                     Doug Jones
  107.                     jones@cs.uiowa.edu
  108.