3
$\begingroup$

Please excuse my ignorance in low level things. A lot of the written below might be very wrong.

As far as I understand (and I might be very wrong), there are two types of memory locations a microprocessor can have: registers and stacks.

My question is what is the most basic set of memory locatiins a microprocessor must have to perform an arithmetic calculation of unlimited complexity, such as : 12 / (11 / (4 - 7) * 31) + 8.

For example one register is obviously not enough. What about three registers? Or one stack? Or a stack and a register? Given e.g. one stack and a register, can the CPU perform any calculation?

The CPU should be able to perform any calculation like in the example shown above.

$\endgroup$
  • 13
    $\begingroup$ One infinite strip of tape and single register should be enough for any calculation. $\endgroup$ – Euphoric Jul 25 '14 at 10:23
  • $\begingroup$ no worries abut the question. Loads of people don't understand how computers really work nowadays, which is a pity as they're so simple. (computers, not the people that is ;) ). There are online education materials in this area if you'd like to learn more, or more advanced reference $\endgroup$ – gbjbaanb Jul 25 '14 at 10:47
  • 2
    $\begingroup$ "Please excuse my ignorance in low level things." If you look at @randomA's link, you'll see the answer to this question, although simple, took a lot of effort to discover. Turing, Church and Godel were all great mathematicians. You shouldn't feel bad for not knowing this a priori. You may want to look at lambda calculus for an alternative to the Turing Machine that's equally powerful and just as simple. $\endgroup$ – Doval Jul 25 '14 at 16:53
  • 1
    $\begingroup$ The question in its current form does not admit answers of the kind you want; clearly, you can computer such expressions even with two registers and one stack (of unlimited size) -- that's the semantics of e.g. the JVM, iirc -- but more registers help, always. Maybe what you should be asking is, "Given $r$ registers, how many memory accesses are required to compute an arithmetic expression with $n$ operations?" $\endgroup$ – Raphael Jul 27 '14 at 7:31
7
$\begingroup$

unlimited complexity?

That requires unlimited memory, after all - the numbers must be stored somewhere, and the place to store them is always in memory.

So you need 1 memory 'cell' for each number, and another for each operation. You also need a counter to keep track of the next number or operation. Add to that a register to perform the calculation (only 1 is needed as you can use it to store the results in-place. In reality you'll use another register to notify you of errors such as overflow or division by zero).

Or to put it another way: you need sufficient RAM, an accumulator and a program counter. You can get away without the counter if the memory are streamed in sequentially on a specialist computing machine (eg on tape as per Euphoric's comment).

$\endgroup$
  • $\begingroup$ "requires unlimited memory, after all - the numbers must be stored somewhere [...] put it another way: you need sufficient RAM" You're assuming the program is stored in the RAM. In a simple pocket calculator it isn't the case (there it's effectively like @metacubed said, "an input tape"). $\endgroup$ – Niccolo M. Jul 25 '14 at 11:58
  • 1
    $\begingroup$ @NiccoloM. Complex calculations on pocket calculators often require auxiliary storage: calculator memory or a piece of paper. A simple calculator (no parentheses) can't handle ab + cd because there is no where to store ab while calculating cd. $\endgroup$ – kevin cline Jul 25 '14 at 17:05
3
$\begingroup$

There are many types of processing machines. The most "famous" among these is the Turing machine. But for the example at hand, we can use a much simpler model, called a pushdown automaton. Each model has its own trade-off with regards to memory, performance and expressiveness.


Memory Requirement

Our required machine has two possible input types: numbers and operators + - * /. Note that we are assuming that multiplication and division are "known" operations for the processor. If not, we can always convert them into a sequence of add and subtract operations.

  1. A tape of input symbols: The size is equal to the length of the input. This is typically external.
  2. A stack with push-pop access: The size is equal to the level of nested operations i.e. roughly the amount of nested brackets. More on this in the "notation" section.
  3. One (or more) register(s): The size of a single register should be enough to store a single symbol i.e. either a number or an operator.

Note that this computation may require other registers for storing the second operand, overflow and carryover values, exception handling, etc. depending on the actual implementation. But the core requirement is a stack and a register, fed by an input tape.


Notation

If we limit ourselves to the basic arithmetic operations (which have two operators and an operand), we can represent your complex operation in postfix notation. So your example:

12 / (11 / (4 - 7) * 31) + 8

becomes:

12 11 4 7 - / 31 * / 8 +

This is a canonical form which can be easily consumed by some types of stack-based processing machines. It does not require operator precedence, brackets, etc. because the order of operations is encoded in the order of the symbols.


Operation

You start feeding in the post-fix symbols left to right. As long as the symbols are numbers, the machine keeps adding them to a stack. When the first operator symbol - is hit, the stack looks like this:

12 11 4 7

the machine pops the top of the stack 7 into a working register. It also pops the next element 4, computes the result of 4 - 7 and pushes it back to the stack.

So the stack is now:

12 11 -3

The next symbol / is now read, and the process continues.

$\endgroup$
  • $\begingroup$ For completeness' sake, here's a sub question: do we need an unlimited stack size for "unlimited complexity"? $\endgroup$ – Niccolo M. Jul 25 '14 at 12:00
  • $\begingroup$ @NiccoloM. yes. $\endgroup$ – kevin cline Jul 25 '14 at 17:06
  • $\begingroup$ @NiccoloM. I've added that info in. Does the answer seem complete to you now? $\endgroup$ – metacubed Jul 25 '14 at 17:18
  • $\begingroup$ Why do you need a register at all? If the processor can perform an operation on 1 register + 1 value on stack, why can't it perform an operation on 2 values on stack? $\endgroup$ – Jason Goemaat Jul 25 '14 at 19:12
  • $\begingroup$ @JasonGoemaat This simple automation only has access to the top element of the stack. The first element has to be popped and stored in a register before it can access the second. There are other automata which use random access memory instead of a stack. $\endgroup$ – metacubed Jul 26 '14 at 22:42
2
$\begingroup$

To answer this question one needs quite some theory. This topic was studied in detail around WWII. You should read and understand the theory of Turing machine, and understand that what you are asking is basically: what resources are needed for a Turing machine.

Note that there are many famous tasks that are not solveable with a Turing machine, so you might want to reconsider and rephrase your question.

$\endgroup$
0
$\begingroup$

To complement some of the other answers, I'll try to give you some "real-world" examples, using microcontrollers way way smaller than you would find running OS's like Windows or Linux..

First of all, there is no practical limit to the complexity of the expressions such as the one you wrote, since the compiler (C, C++, C#, Java, etc.) evaluates the expression and turns into a set of instructions similar to the example in metacubed's answer (calculating the inner expression first, on out to the top level). Typical compilers may have limits on parentheses levels, but they are typically 32 or more. Anyhow, essentially infinite in all practical terms.

So on to your example. If you were to input your expression into a compiler, and then compile the code, it would mostly likely not use hardly any code or data space at all. The reason is that any decent compiler will evaluate constant expressions at compile time as much as possible. In your case, the entire expression is constant, so the line

result = 12 / (11 / (4 - 7) * 31) + 8;

would be replaced by

result = 8;

8? Why 8 and not 7.8944? That's what I got on my calculator?

By default, virtually all microprocessors/microcontrollers (I'll use MCU from now on) perform integer arithmetic instead of floating point. (In fact only high end MCUs, for example the Intel chips used in your desktop/laptop, have hardware floating point.)

After calculating the inner part of your expression, you end up with 12 divided by -93, which is 0 in integer arithmetic. Adding that to 8 gives 8. Whereas in the floating point case, you have 12 / -113, which is -0.1056 , added to 8 gives 7.8944.

So to make the example non-trivial, one needs to assign all the constants to variables, and then calculate the expression.. Something like this (I'm using C):

char result, a, b, c, d, e, f;
a = 12; b = 11; c = 4; d = 7; e = 31; f = 8;
result = a / (b / (c - d) * e) + f;

Now that will compile into real code. How much? Depends on the MCU.

On a 32-bit MCU, like the PIC32 (which uses the RISC instruction set called MIPS), it takes 12 instructions (2 per variable) to put all the variables on the stack (since C, by default, puts all local on the stack). It then takes another 20 instructions to calculate the expression. Since the PIC32 has both hardware multiply and divide, those operations take only one instruction. Running at 80 MHz, each of these instructions takes 12.5 ns to execute, so the entire expression is calculated in 0.25 µS.

Each PIC32 instruction takes four bytes, so the entire "program" takes 128 bytes of code space, and 28 bytes of stack space (since there are seven variables).

How much is that? Well, an MCU like the PIC32 typically has several hundred thousand bytes bytes of program space (the one I'm using has 512K), and anywhere from 4K to 128K of RAM. So this program is fairly trivial. And of course compared to an 80x86 micrprocessor running on your desktop, with several GB's of RAM (used for both program and data storage), this program is microscopic in comparison.

When this version of the program is run, the value of "result" printed out is the 8, due to the integer arithmetic discussed earlier.

If one were to change the "char" to "float" in the first line of the code example, this changes thing a lot. The code for storing the variables and calculating the expression doesn't go up very much -- from 32 to 38 instructions; but the main difference is now this code is calling all sorts of floating point subroutines in the C library to do the "real" work. As far as I can tell from the map file (one of the outputs of the compiler), these library routines take up another 532 bytes of code space.

When this version of the program is run, the value of result printed out is the desired value of 7.8944.

Now let's look at a small 8-bit MCU, particularly the PIC16F946. The code to save off the variables and then calculate the result (which took 32 instructions the PIC32) now takes 82 instructions. But wait, the PIC16F946 only has a 8x8 hardware multiply but no hardware divide, so there are helper routines for each.

So you have to add 39 instructions for the multiply routine, and 90 for the divide routine, for a total of 211 instructions. Each of these instructions takes 14 bits (how weird is that?), so to be able to compare with other architectures this would be 185 bytes. Actually that is not all that much larger than the PIC32's 128 bytes, even with the helper routines added in. The 14-bit length of the PIC16 instructions vs the 32-bit length of the PIC32 makes a difference.

However if I change to "char" to "float" as we did for the PIC32, the code size almost quadruples.

A PIC16F MCU has anywhere from 768 bytes to 28KB of program space, and just 25 bytes to 2K bytes of RAM. So unlike the PIC32, this example code will stretch the limits of the lowest end PIC16Fs, and the floating point version of the code would not even fit.

So these very small PICs like this run very small programs -- perhaps performing only one function. But they can cost less than 25Ȼ. A typical car today has over a hundred microcontrollers -- some tiny, some rather sophisticated.

The PIC16F946 series, as well as all other 8-bit PICs, actually has only one register dedicated to arithmetic and logical (AND, OR, NOT) operations and shifts; it is called WREG. Such registers are typically called accumulators. There are 15 additional registers, but they are just used to hold temporary variables, like the initial parameters and intermediate results of our expression.

So you really can do a lot with just one register performing arithmetic and logical operations, because the compiler has unrolled all the complexities of the expression to make it as easy for the target machine to calculate as possible. Many of the original microprocessors in the 1970s, like the 6800, 6502, and 8080 had just one accumulator often called A. The 6809, a follow-up to the 6800, had two named A and B.

$\endgroup$
-1
$\begingroup$

"any" calculation, well that cannot be answered with a finite solution, but so long as the calculation can be resolved combinatorially then you dont need any memory at all. If you cant do it combinatorially then you need some latches memory...But you will NEVER actually need "memory" as in ram to PERFORM math operations. You might like to have some memory in order to feed the math operation and have a place to put the result, but switches and lights/leds work just fine as well...

You have to be very specific about he processor and the set of operations it supports and the choices for source and destination for those operations. That determines quite heavily how much memory, registers, stack, etc are required to perform a specific operation, since there is no possible answer to this question for "any" operation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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