4
\$\begingroup\$

I'm trying to implement multiplication in a cpu I designed. I'm trying to achieve this with some conditions. I only two general purpose registers Rx and Ry and these instructions:

  • Add Rx, Ry [Add take Rx and Ry to ALU and returns result to Rx]
  • LD Rx, address [Load takes the data in RAM from address and loads to Rx]
  • STR Rx, address [Store takes data from Rx and stores to address in RAM]
  • BZ Rx, Ry, Address [Branch compares the data in two registers. Jumps if equal]
  • Jump Address [Jumps to address]

If I only have 2 registers and RAM, is there a way to implement multiplication? I know the general way to implement it is by using shifts but I don't have the implemented and would prefer not to. I was thinking of looping an addition call but I can't seem to get that work since I only have 2 registers.

EDIT: You can select which register by addressing them either 0 or 1. Also, my RAM is only 16 bytes large and the bus is only 8 bits within the CPU.

  • Add Rx, Ry [Rx <= Rx + Ry]
  • LD Rx, address [Rx <= RAM(address)]
  • STR Rx, address [RAM(address) <= Rx]
  • BZ Rx, Ry, Address [Branch to Address If Rx == Ry ]
  • Jump Address [Jumps to address]

The address is a 4-bit constant stored in the instruction. Rx or Ry are 1 bit. OPCODE is 4 bit with the exception of LD and STR where 4th bit of OPCode refers to register selection.

|improve this question
\$\endgroup\$
  • 2
    \$\begingroup\$ tell us more about your architecture... where do the results of Add Rx, Ry go (presumably they overwrite Rx or Ry)? Are addresses immediates (i.e. constants stored in the instruction)? \$\endgroup\$ – vicatcu Apr 8 '13 at 17:54
  • \$\begingroup\$ Added info to OP. I'm a bit confused about the address immediate thorough. What do you mean by constant stored in the instruction? \$\endgroup\$ – John Smith Apr 8 '13 at 18:02
  • \$\begingroup\$ Express your instruction semantics using a high level Register Transfer Language... for example Add Rx, Ry might be Rx <= Rx + Ry... it sounds like "address" is a 4-bit constant stored in the instruction since you've said you have a 16 possible addresses in your RAM. An "immediate" is just what you call a constant that is embedded in an machine instruction. \$\endgroup\$ – vicatcu Apr 8 '13 at 18:14
  • \$\begingroup\$ Edited. The address is definitely a constant within the instruction. \$\endgroup\$ – John Smith Apr 8 '13 at 18:23
  • \$\begingroup\$ Since jumps and branches use the same size addresses as load and store, I presume that both code and data are stored in the 16-byte RAM. That doesn't leave much room to implement multiplication. \$\endgroup\$ – Dave Tweed♦ Apr 8 '13 at 18:38
1
\$\begingroup\$

At minimum, you need a branching instruction which can determine whether the previous addition generated a carry. Also, performance will be improved enormously if you expand your register set to three or four registers.

Start with one operand in R0 and the other in R1. Start with R2 zero.

Repeat the following sequence eight times (first ADD may be skipped on first pass)

  Add R2,R2
  Add R0,R0
  Bnc Skip
  Add R2,R1
Skip:

Note that if the instruction set includes an add-with-carry instruction, using it for the second instruction would cause this instruction sequence to yield a 16-bit result in R0:R2. Further, if R2 starts non-zero, its value times 256 will be added to the outgoing result.

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

I don't think Add, Load/Store, and Branch If Zero, and Jump are a "Turing Complete" instruction set or whatever. That is to say I don't think you can construct multiplication (among other things) using only these instructions. Just a guess though.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ What would it take for it to become turing complete? Shift? \$\endgroup\$ – John Smith Apr 8 '13 at 18:25
  • \$\begingroup\$ I believe they are Turing-complete, compare en.wikipedia.org/wiki/One_instruction_set_computer \$\endgroup\$ – pjc50 Apr 8 '13 at 18:58
  • \$\begingroup\$ Note that the one instruction computer requires unlimited resources. \$\endgroup\$ – Kaz Apr 8 '13 at 19:11
  • \$\begingroup\$ @pjc50 i mean you could trivially implement multiplication for two eight bit numbers with a 2^16 entry table of 16-bit values... \$\endgroup\$ – vicatcu Apr 8 '13 at 19:35
  • \$\begingroup\$ @YamatoC Shift would at least allow you to emulate multiplication iteratively in 'the natural way'... I'm not much of a theoretician so I was just guessing that it is not Turing Complete... \$\endgroup\$ – vicatcu Apr 8 '13 at 19:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.