1

If you were to build a processor that would be used to run any arbitrary program, what is the minimum set of instructions (ISA) you could get away with?

I was thinking:

  • ALU-ops (add, sub, mul, div)

  • Load reg,[address]

  • Store reg,[address]

  • Branch-if operation. Could have branch if not equal, if >, if < (branchif reg1, reg2, LABEL)

What do you think?

JDS
  • 16,388
  • 47
  • 161
  • 224
  • Well you are describing a register based machine, theres always a stack based machine ... it can be far simpler. Just your standard arithmetic/logical operators, with some PUSH/POP and of course JUMP/JUMPT/JUMPF ... oh and fixed instruction length. – Samy Vilar Jun 26 '12 at 05:34
  • We were taught 8085 microprocessor and it didn't had any native implementations of div and multiply..:) – Shubham Jun 26 '12 at 05:36
  • Wondering if this belongs instead on http://programmers.stackexchange.com? – Andras Zoltan Jun 28 '12 at 22:39
  • I think it is classic RISC vs CISC problem. Just look to some simple RISC, e.g. DLX. Your set is too small to run arbitrary OS (e.g. Linux or MINIX), but it can be used for simple programs without I/O. – osgx Jun 28 '12 at 22:54

3 Answers3

5

Technically, you only need One Instruction. It needs to do math and conditional branching. e.g. subtract and branch if negative.

Nathan Binkert
  • 8,744
  • 1
  • 29
  • 37
1

You don't need any instruction that can be built from other instructions.

So, no need for mul or div since you can do that with repeated addition or subtraction, and no need for sub if you have neg (negate) and numbers will wrap, such as with two's complement.

And certainly you can get away with two branch instruction, one for equal, one for less than - all the others can be built from combinations of those.

Because you have no I/O instructions, you'll probably need to use memory-mapped I/O where communications with other devices is via memory accesses.

And, without native push and pop, you'll probably need to implement your own stack with a dedicated register (and memory location since you don't appear to have a register-to-register move).

Now that won't be a very nice architecture but it should function. As the Matrix Architect stated, "there are levels of survival we are prepared to accept".

As an aside, have a look into the RCA1802 CPU (from days of yore). It had no dedicated program counter or stack pointer, instead implementing all that in software (see here for details).

Community
  • 1
  • 1
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
1

While programming in 8085 I felt there were several ways to do the same thing. So, if this is the case, you know your instruction set is not minimal.

I would propose following instructions- Add, complement, logical AND, OR, and load store. Conditional and unconditional jump.

Most of the other instructions can be performed with above instructions.

EDIT: Just to list the assembly instructions (based on 8085):

I will consider a model, wherein there are 3 registers. With operations like A = B + C

ADD B, C (A = B + C)
CMA (A = A')
OR B, C (A = B OR C) JMP xxxx (set PC to xxxx)
LDA xxxx (load A with contents at xxxx address)
STA xxxx
JZ xxxx (Jump if zero flag is set)

NOTE: I realise additional instruction to copy data between registers is quite useful. But can be omitted. Please present a case where one cannot do without it.

Vinayak Garg
  • 6,518
  • 10
  • 53
  • 80