home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 11017 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  5.7 KB
  1. Path: sparky!uunet!cs.utexas.edu!uwm.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!cc4b+
  2. From: cc4b+@andrew.cmu.edu (Christopher Brian Cox)
  3. Newsgroups: comp.arch
  4. Subject: re: MINIMUM instruction set
  5. Message-ID: <If4491i00WBOA5LGYv@andrew.cmu.edu>
  6. Date: 22 Nov 92 16:30:25 GMT
  7. Article-I.D.: andrew.If4491i00WBOA5LGYv
  8. Organization: Senior, Physics, Carnegie Mellon, Pittsburgh, PA
  9. Lines: 152
  10.  
  11. This will probably get buried in the Alpha discussions, but . . .
  12.  
  13. > So here is a challenge: design a machine that uses no more than 4 bits
  14. > per instruction (including operand fields), is Turing complete, not
  15. > terribly inefficient and which can be built using far less hardware
  16. > than current microprocessors. The latter would make it suitable for
  17. > massively parallel systems.
  18.  
  19. ( This is a modification of Doug Jones' (jones@herky.cs.uiowa.edu) work )
  20.  
  21. Note that this processor is possible, but would work the blazes out of a
  22. compiler or assembly programmer. Also, I am positive that a good FORTH
  23. hacker could come up with a more complete (and faster) set of macros.
  24.  
  25. Notation:  X = top word on stack
  26.            Y = second word on stack
  27.  
  28. Opcodes:
  29.  
  30. NOP     0000    No op
  31. ZERO    0001    X := X << 1           (zero fill)
  32. ONE     0010    X := (X << 1) + 1     (ones fill)
  33. DUP     0011    push(X)        (duplicate top word on stack)
  34. STORE   0100    M[X] := Y; pop; pop;
  35. LOAD    0101    X := M[X];
  36. ADD     0110    Y := Y+X; pop;
  37. BNEG    0111    if (X<0) then PC := Y; endif; pop; pop;
  38. SWAP    1000    exch(X,Y)      (exchange top two words on stack)
  39. OR      1001    Y := Y | X; pop;
  40. PUSHZ   1010    push(0)
  41. NOT     1011    X := !X;       (or ~X)
  42. AND     1100    Y := Y & X; pop;
  43. POP     1101    pop(X)         (removes top word on stack)
  44. BZERO   1110    if (X=0) then PC := Y; endif; pop; pop;
  45. BPOS    1111    if (X>0) then PC := Y; endif; pop; pop;
  46.  
  47.  
  48. Macros:
  49.  
  50. NOT allows one's complement with the macro NOT;PUSHZ;ONE;ADD;
  51.     this allows SUB (Y-X) to be done by NOT;PUSHZ;ONE;ADD;ADD;
  52. CALL,BRA,JMP can be done using {push address};PUSHZ;BZERO;
  53. INCR = PUSHZ;ONE;ADD;
  54. DECR = PUSHZ;NOT;ADD;
  55. XOR can be simulated (using $00) by (X|Y) & !(X&Y)
  56.     PUSHZ;STORE;DUP;PUSHZ;LOAD;AND;NOT;SWAP;PUSHZ;LOAD;OR;AND;
  57. if (X==Y) then {}
  58.     NOT;PUSHZ;ONE;ADD;ADD;{push address};SWAP;BZERO;
  59. if (X>Y) then {}
  60.     NOT;PUSHZ;ONE;ADD;ADD;{push address};SWAP;BNEG;
  61. if (X<Y) then {}
  62.     NOT;PUSHZ;ONE;ADD;ADD;{push address};SWAP;BPOS;
  63.  
  64. simple loop - do {} until (--x == 0);
  65.         {push count}
  66.     label1: loop statements
  67.         more statements (leaving count on top of stack)
  68.         PUSHZ;NOT;ADD;DUP;
  69.         {push address of label1}
  70.         SWAP;BPOS;
  71.  
  72. simple loop -  do while (x-- >0) {};
  73.         {push count}
  74.     label1: DUP;
  75.         {push end}
  76.         SWAP;BZERO;
  77.         statements (leaving count on top of stack)
  78.         PUSHZ;NOT;ADD;
  79.         {push label1}
  80.         PUSHZ;BZERO;
  81.     end: POP;
  82.  
  83. simple multiply by addition - (uses $00)
  84.         PUSHZ;STORE;        (store X)
  85.         PUSHZ;SWAP;DUP;     ( Y Y 0 . . .)
  86.         {push end}
  87.         SWAP;BZERO;         ( Y was zero )
  88.     label1: SWAP;
  89.         PUSHZ;LOAD;ADD;     ( add X to sum )
  90.         SWAP;PUSHZ;NOT;ADD; ( decriment Y )
  91.         DUP;{push label1}
  92.         SWAP;BPOS;
  93.     end: POP;               (remove Y)
  94.         (leaves result on stack)
  95.  
  96. division (with remainder) could be done similarly using subtraction and
  97. a counter.
  98.  
  99. (I'm not positive about this code)
  100. killer multiply by bit test and add - (uses $00-$02)
  101.         PUSHZ;STORE;                (store X $00)
  102.         DUP;PUSHZ;ONE;ZERO;STORE;   (store Y $02)
  103.         PUSHZ;ONE;DUP;DUP;STORE;    (store test bit $01)
  104.         AND;                        (test bit with Y)
  105.         PUSHZ;SWAP;                 (start with zero sum)
  106.         {push label2}
  107.         SWAP;BZERO;                 (if zero, nothing)
  108.         POP;PUSHZ;LOAD;             (pop zero,load X)
  109.     label2:
  110.         PUSHZ;DUP;LOAD;ZERO;SWAP;STORE;
  111.                 (left shift X)
  112.         PUSHZ;ONE;ZERO;LOAD;        (load Y)
  113.         PUSHZ;ONE;DUP;DUP;LOAD;ZERO;SWAP;STORE;LOAD;AND;
  114.                 (load test bit, rotate, store, test)
  115.         {push label3}
  116.         SWAP;BZERO;                 (if zero, nothing)
  117.         PUSHZ;LOAD;ADD;             (add shifted X)
  118.     label3:{push label2};
  119.         PUSHZ;ONE;LOAD;             (load test bit)
  120.         BPOS;                       (loop until test bit is MSB)
  121.         (leaves result on stack)
  122.  
  123.  
  124. Possible Deletions:
  125.  
  126. POP could be done by
  127.     PUSHZ;ONE;BZERO  |  PUSHZ;BNEG;  |  PUSHZ;BPOS;
  128. BNEG could be eliminated by exclusion and good code
  129.     !(BZERO | BPOS) == BNEG
  130. SWAP could be done (using $00 and $01) by
  131.     PUSHZ;STORE;PUSHZ;ONE;STORE;PUSHZ;LOAD;PUSHZ;ONE;LOAD
  132.     but SWAP is far too useful
  133. DUP could be done (using $00) by
  134.     PUSHZ;STORE;PUSHZ;LOAD;PUSHZ;LOAD;
  135.     but DUP is also too useful
  136.  
  137.  
  138. Possible Additions: (to make life easier)
  139.     MULT (useful, faster, but more difficult hardware)
  140.     SUB  (could be useful for compares and divides)
  141.     PUSHPC
  142.     LSR
  143.  
  144.  
  145. Implementation:
  146.  
  147. BPOS means high bit clear, and non zero
  148. BNEG mean high bit set
  149.  
  150. If the word size is N bits, it takes N instructions, in the worst case,
  151. to push an N bit constant.  101010... is the worst case.
  152.  
  153. Instructions are packed 2 per byte, and labels must be word aligned.
  154. NOP instructions are used to align labels to a word boundary.
  155.  
  156. Right shift doesn't exist.
  157. Arrays with arbitrary indices are difficult, but vector operations on
  158. arrays are very friendly. Procedure calls are either inline or
  159. absolutely addressed with either caller or callee cleanup. Routines can
  160. handle an RTS by using a PUSHZ;BZERO;, but calling routines will have to
  161. have their own addresses compiled in (no easy access to PC). Returned
  162. values will have to be stored in memory or on the top of the stack.
  163.