6
\$\begingroup\$

Is there a processor that do arithmetic operations on a stack and not on registers? To keep performance, of course, that processor should cache top block of a stack in the same type of memory that is used for registers.

I read in a paper (David R. Ditzel, H.R. McLellan. Register Allocation for Free: The C Machine Stack Cache.) that a cache is slower 2 times than registers because of:

  • indirect addressing during every access to the cache;
  • cache miss when the stack grows.

The paper is old. Maybe, improvements of processor design appeared that makes stack cache viable? I feel that it will reduce complexity of compilers and optimize copying between registers and the rest of memory.

Update 2012-10-18. Because this concept was well-known (not to me), I change the question to “… Modern processors?”

Update 2012-10-18. I feel I must say explicitly that I'm not talking about “zero address machine”. Caching and “zero address” are orthogonal. My hypothetical processor may have even 5-ary addition like “r3 := r0+r2+r11+r5+r8”. “r n” means the memory cell at sp+n, where sp is a stack pointer. sp changes before and after a code block. A very unusual program changes sp at every arithmetic operation.

\$\endgroup\$
  • \$\begingroup\$ As I said in my answer, a fundamental difficulty with such machines is that it is in general hard for instruction scheduling logic to maintain any sort of coherency if the stack pointer changes. That having been said, I can imagine that it might in some cases be useful to have a special 'register save' stack for registers which will need to be preserved, but which will not need to be accessed except for purposes of restoring them. On a system with 16 32-bit "user" registers, such a stack might be e.g. 16 deep and 512 bits wide (plus some control bits). \$\endgroup\$ – supercat Oct 18 '12 at 21:17
  • \$\begingroup\$ When it's necessary to save some subset of registers, all 128 bits of the register file would be copied to the stack in parallel; if the stack is full, the "spill" would get written out to the main cache as a one or two cache lines (depending upon the cache-line size). When restoring registers, only the registers slated for restoration would be reloaded. Such an architecture could in many cases minimize the amount of register save/restore traffic going to and from the main cache, but I'm not sure the overall effect on performance would be enough to justify it. \$\endgroup\$ – supercat Oct 18 '12 at 21:21
  • \$\begingroup\$ OK, since you aren't talking about stack machines, I tracked down the paper you reference and read it. The reasons they give in the beginning for why cache is always slower than registers are architectural issues, independent of implementation technology. The explicitly-managed cache that they propose falls somewhere in between. In the 30 years since that paper was written, compiler technology has become much more sophisticated, and can take full advantage of hardware built for maximum speed (using registers). \$\endgroup\$ – Dave Tweed Oct 19 '12 at 15:21
  • \$\begingroup\$ @supercat: “I can imagine that it might in some cases be useful to have a special 'register save' stack for registers which will need to be preserved” In some cases? He-he. This is the only way for recursive functions to go. ;) \$\endgroup\$ – beroal Oct 19 '12 at 16:54
  • \$\begingroup\$ @Dave Tweed: I removed your paid link; the 1st link in Google search results is free download. \$\endgroup\$ – beroal Oct 19 '12 at 17:14
7
\$\begingroup\$

Yes, the entire line of Burroughs mainframe computers starting in 1961 with the B5000 used a stack architecture.

In this architecture, managing the data flow to and from the stack is not actually too much of a bottleneck for performance. A bigger issue is the fact that a "zero address" machine needs a lot more instructions to complete a given task than a one-, two- or three-address machine does. Instruction decoding and the execution pipeline become the primary bottleneck.

When I worked there in the early 1980s, there was an effort to build a CPU that could prefetch relatively large sequences of zero-address instructions and translate them on the fly to three-address operations that would be fed to the execution pipeline. (Think of a Java JIT compiler implemented in hardware.) It got rather complex, especially for the implementation technologies available at the time, and I don't know whether this strategy ultimately succeeded.

In case you're wondering, the "N-address" terminology refers to the number of operands that can be specified in a single instruction. All operations on a stack machine are implicitly to the top one or two locations on the stack, so there are zero operands in the instructions. A machine that has an accumulator that is used for all operations in conjunction with one other register or memory location is a one-address machine. A two-address machine can specify an arbitrary source and destination operand in one instruction, and a three-address machine can specify two source operands and put the result in an independent destination.

\$\endgroup\$
  • \$\begingroup\$ +1. To put the N-addressness in today's context, the 8 bit PICs like the PIC 16 and PIC 18 have mostly one-address instructions since most operations imply the W register for one of the operands and the result is either the W register or back to the source location. The dsPIC and derivatives (PIC 24, 30, and 33) are largely 3-address machines, although the operations are limited to the set of 16 W registers. Nonetheless, many operations can be performed with two W registers as operands and the result written to a third. This is basically the RISC version of 3-address. \$\endgroup\$ – Olin Lathrop Oct 17 '12 at 13:22
  • \$\begingroup\$ If one has a specific number of bits in an opcode to encode all the addresses instructions will need, I would think that the larger working set enabled by a single- or dual-address architecture would often outweigh the advantages of a three-address one, provided that the instruction set minimized the "penalty" for the cases where going through a single register was inadequate. Zero-address doesn't work very well, but I would think a one-address stack machine could be pretty good if one weren't trying to overlap instructions too aggressively. \$\endgroup\$ – supercat Oct 17 '12 at 15:37
  • \$\begingroup\$ @OlinLathrop: I would regard something akin to the PIC's single-address instructions with selectable destination as just about ideal, if the "W" input to the ALU instead came from a register which would normally mirror W except following a "uselw" or "usefw" instruction (which would load it with a constant or the contents of another register). Instead of a dedicated two-word "movff" opcode, I'd use the sequence "usefw src / movwf dest" [after which, the temp register would be reloaded with W]. That would allow "usefw src / addwf dest,f" as a means of "dest += src" without disturbing W. \$\endgroup\$ – supercat Oct 17 '12 at 15:41
  • \$\begingroup\$ @OlinLathrop: For applications where all of the commonly-used parts of the working set can fit within the addressing range of an instruction without banking, movf src / addwf dest,f is faster than ldr r0,[src+r13] / ldr r1,[dest+r13] / add r0,r0,r1 / str [src+r13] (and performs its destination update atomically). Too bad adding one number to another while the value of W is needed for something else costs four cycles (one to save W, one to load an operand, one to do the operation, and one to restore W). Something like usefw could cut that to two. \$\endgroup\$ – supercat Oct 17 '12 at 15:46
  • \$\begingroup\$ No, I'm not talking about a “zero address” machine. E.g., the operand “R5” means the memory cell at SP+5, and this memory cell is cached because it is close to the top of stack. \$\endgroup\$ – beroal Oct 18 '12 at 15:53
3
\$\begingroup\$

I recall reading a similar paper (perhaps the same one) about 17 years ago. Such an approach might be good if one were developing a processor to execute one instruction at a time quickly. Unfortunately, it does not work well with out-of-order instruction scheduling. If one has code like:

  ldr r1,[r0]
  ... do some stuff, not involving r1, r2, or [r2]
  str r1,[r2]

An instruction scheduler is free to shift those two instructions around as it sees fit. While it may be hard for the instruction scheduler to know whether a write to some memory location could be a write to [r2], many compiled languages require programmers to indicate what things may or may not be aliased.

By contrast, the instructions were more like:

  mov.l [r0],[--sp] ; Push [r0] onto stack
  ... do some stuff, which affects sp
  mov.l [sp++],[r2] ; Pop [r2] from stack

it would much harder for an out-of-order execution engine to determine if the source operand for the latter instruction would always be the same as the destination operand of the former, and whether any intervening instructions might affect it.

\$\endgroup\$
2
\$\begingroup\$

In the past I did some work with the Saab Ericsson Space Thor, a microprocessor for space applications. It did work, but had some serious drawbacks. Just one: the instruction pipeline was exposed: the instruction that loaded a word from memory used as address the top-of-stack 2 instructions ago. I wrote a fast memory-copy routine for it, but Saab said it could not be used because interrupts would cause trouble...

\$\endgroup\$
0
\$\begingroup\$

There were dedicated Forth processors that used to be used at the boot processor for Sun/Sparc machines whose dedicated architecture mapped to the language. But not generally available.

\$\endgroup\$
0
\$\begingroup\$

The x86 is almost one of those :-) (and the x87 fp part even closer)

In modern systems, stack is terrible, though, because it may alias across cores or even NUMA nodes, so lots of slow, long-distance signalling may be involved. Or, at a minimum, more interlocks than you get with a register file and register renaming.

Consider that not even CPUs, but other devices may DMA data into your stack -- think read buffers!

\$\endgroup\$
  • \$\begingroup\$ Yeah, almost. x86 has AX, BX, CX, DX, BP, SI, DI. This list is not particularly short. :) Actually, I tested stack vs registers on AMD Athlon and found that registers are 2 times faster than stack. DMA or other processor accessing processor's stack usually is programmer's error, so the processor does not need to resolve this conflict, say “behavior is undefined” in such cases. \$\endgroup\$ – beroal Oct 21 '12 at 9:20
  • \$\begingroup\$ No, DMA accessing the stack is common -- consider buffers on the stack for calls to read() or write(). This is not a programmer error, and CPUs cannot say "behavior undefined" for that. I remember an old PowerPC motherboard where this behaviour was undefined due to a bug in the Apple hardware; that was "fun" to deal with... The x87 is a fully stack-based instruction set, although the "working stack" is farily limited and needs to spill to the "real" stack. \$\endgroup\$ – Jon Watte Oct 21 '12 at 19:35
  • \$\begingroup\$ “consider buffers on the stack for calls to read() or write()” We can get rid of this. \$\endgroup\$ – beroal Oct 23 '12 at 13:05
  • \$\begingroup\$ @JonWatte: Putting a DMA buffer on the stack seems like a bad idea when using synchronous I/O, and a really really bad idea for using asynchronous I/O. At minimum, even in the synchronous I/O case, it requires that any multi-tasking executive know how to cancel any pending DMA operations if it needs to kill a thread. And in the asynchronous I/O case, it's a recipe for disaster if the routine that sets up the DMA unexpectedly exits before the DMA completes. \$\endgroup\$ – supercat May 3 '13 at 21:55
  • \$\begingroup\$ Clearly, asynchronous I/O can't use stack buffers. UNIX isn't terribly great at async I/O, though; most programs actually use synchronous I/O. The kernel doesn't necessarily have to wait for the I/O to complete before it removes a stack mapping, as long as the physical pages still have a reference count and won't be removed until the I/O completes. Remember: DMA is typically done with physical addresses, outside the VM translation layer. I know of kernels that reference count physical pages; I dont know if they all do that. \$\endgroup\$ – Jon Watte May 4 '13 at 6:42

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.