6 ms·

Stack Computers: the new wave (1989)

100 points by falava 14y ago

luu 14y ago
Mini book review: On the off chance you're planning on implementing a stack machine, you must read this book. A few years ago I was working on a stack machine, and I didn't know what to read because virtually all of the references for fundamental material are decades old. Let me save you the trouble and tell you this is the one you want. There are newer papers you should read, of course, but if you're only going to read one thing, it should be this. Why would you want a stack machine in this day and age? They're small. Really, really, small. The stack processor we made was so small that it fit in an empty space in the floorplan of our "real" (x86) processor.
- daniel-cussen 14y ago
  I'm using stack machines now because, like you said, they're small. Meaning, you can fit a ton of them on a chip, and if you can get them to talk to each other, you have yourself a pretty powerful parallel processor. The chip I'm working with has 144 cores running at ~700MHz, and it costs $20. It's insane how much being small buys you.
  - jallmann 14y ago
    Chuck Moore's GreenArrays chip? (He's also the guy behind Forth, the quintessential stack-based VM.) How's that working?
    - daniel-cussen 14y ago
      The very same. It's working really well—initially I was intimidated about the chips because of a few of the constraints the chip has in order to be as good as it is. Three challenges: 1) Figuring out how to work within the very low (but reasonable) amount of RAM each core has. They're independent computers, so each core needs to store its code and its data, all within 64 18-bit bytewords, which roughly corresponds to a tweet of information if you tweeted in UTF-8. 2) Dealing with the IDE: the IDE is attacking a problem nobody's solved: parallel compilation. That being said, it has been the second greatest challenge so far, after 3) Getting the hardware set up. My co-project-doer is light-years ahead of me in the EE department and makes most of the EE decisions, with some input from me about what capabilities the chip needs to have (a minimum amount of off-die RAM, say). Sourcing parts is something I would not have been able to do on my own, so I'd say this project requires a good deal of electronic literacy, if not dexterity. That being said, though it's a bit of a prima-donna, it has every right and reason to be. It's an amazing, amazing chip. It's fast, powerful, unclocked, can work with all kinds of devices, is a crazy bargain both in hardware cost and in energy cost, and best of all, for me at least, an endless source of fun, hard problems. It's a fascinating chip.
      - tailrecursion 14y ago
        It's great to see people using Chuck's work, and in particular it's wonderful to see your reaction. I think it would be easy to recoil at the strange tools, not to mention the difficulty of programming the thing. I agree it's a fascinating device.
      - listic 14y ago
        Can you give a hint as to what we can expect to do with this chip? I was a Forth enthusiast and read the book in OP (in early 2000's) and followed Chuck's work from afar, but I am not sure what exactly I could do with this chip, given its peculiar limitations.
        daniel-cussen 14y ago
        With low RAM like that, what you want to do is math, not UI. That means electrical engineering or number crunching, AFAIK. OK, so first, it has a lot of I/O ports of different kinds on just one chip. In a lab, you could run lots of analogue knobs and many servos attached to just one chip. This means a lot less hardware debugging, which should be a Godsend. Another possibility is HPC. You can tile a motherboard with these, cool them all down to -50 very easily and cheaply, and then overclock them as you perform number crunching that you couldn't do with a GPU. After all, these cores are truly independent, and can therefore branch independently, unlike GPU cores. That opens the door to a wide variety of algorithms that aren't GPGPU accessible.
        jules 14y ago
        It sure looks like a fine chip for a very small niche, but they don't even have floating point instructions AFAIK, so you'd have to emulate them in software. So I'm extremely skeptical about their number crunching capabilities.
        listic 14y ago
        No floating point. I believe design complexity of the chip would increase manifold if it was. Emulation is not an option too with those extremely limited resources (64 words of memory). The design philosophy of this chip is that 18 bits of integer precision should be enough for your applications, period. I just feel like I'm not smart enough to figure out how to fit a useful application into that.
- chubot 14y ago
  Hmmm interesting... If it uses that much less silicon then I imagine you could save huge amounts of power. A lot of people would be interested. There must be some tradeoff then. Companies are burning huge amounts of cash buying data centers in remote areas because of power. Presumably it's not very hard to compile C to stack code. (Or maybe it won't be as efficient as... Forth?) Or maybe most applications aren't really CPU limited. I remember reading about Chuck Moore's low power processors, but they seem to have mostly specialized applications. In that case it's probably not fair to compare them to x86.
  - RodgerTheGreat 14y ago
    The book actually discusses the problems with running C code on stack machines. To sum up, yes- you absolutely can run C code on a stack machine, but you lose most of the advantages of the architecture. Stack machines make procedure calls very inexpensive and encourage the use of very short procedures with a small number of variables in scope at a given time. The stack operators that are available provide quick access to a few elements at the top of the stacks at the expense of random access to elements that are deeper. Stack-oriented languages like Forth make the programmer aware of this and encourage breaking tasks down in this manner. Idiomatic C has procedures which are at least an order of magnitude longer and have many more values in scope at a given time. This provides a compiler with a fairly uncomfortable and difficult optimization task. Speaking as someone who works with compilers and really likes stack machines, I don't think they will provide much practical value unless programmers are willing to adapt their languages and their approach to programming to the strengths and weaknesses of the paradigm.
    - thesz 14y ago
      http://repository.cmu.edu/cgi/viewcontent.cgi?article=1712&context=isr http://repository.cmu.edu/cgi/viewcontent.cgi?article=1712&#... "The algorithm have I developed for intra-block stack scheduling seems to be quite effective, eliminating 91% to 100% of redundant local variable accesses within basic blocks for the small programs studied. Hand-performed global optimization results indicate that significantly better stack scheduling can be done if variables are kept on the stack across basic block boundaries." What is also possible is to discover identical code and automatically generate procedures for it.
- petermonsson 14y ago
  How small is really, really small? Something that is small in a x86 sense is not at all small in an embedded world. If you could elaborate a bit on the performance requirements for the application I'd be really happy. I am curious how it compares to an equivalent ARM (f. x. the 12kgate Cortex-M0+) in terms of area, power, performance.
- deleted 14y ago
  [deleted]
tikhonj 14y ago
I've been playing around with some Greenarray[1] chips lately, and I have to admit that the core ideas are fascinating. Their particular variant of Forth is actually almost pleasant to use--certainly better than MIPS, which is my closest point of reference. (Ignoring crazy things like the color of identifiers controlling your program's semantics.) The chips are also extremely power efficient. [1]: http://www.greenarraychips.com/ http://www.greenarraychips.com/ I've found having a mental model of a stack-based system far easier than even a simple register-based one. However, this might also be true because the Greenarray chips themselves are far simpler than any other CPU I've ever looked at. And, of course, the fact that you have 144 cores on a tiny chip despite a cheap manufacturing process is also very neat.
- gruseom 14y ago
  Oh, please write about your experiences programming those chips. I'm sure I'm not the only one who'd like to hear all about it. I'd particularly like to know how you deploy code to the 144 cores and how they talk to one another. Edit: that request is to anyone who has programmed the GreenArrays chips.
  - batgaijin 14y ago
    Yes, please write this! I'd normally just upvote your comment, but I feel like the sorts of people who play around with GreenArray chips are not that prone to blogging, at least by my googling...
- tailrecursion 14y ago
  Are you able to boot all the cores and get them functional? I like the design of these chips too, especially how each core "blocks" on its message queue by instantly going to sleep, taking zero power -- and then instantly wakes up the moment a message appears.
zxcdw 14y ago
One domain where stack machines shine is code density because of no need for register encoding. Instruction lengths aren't measured in bytes, but rather in bits. With some form of binary coding, one can reduce code size even further, 1-7 bits per instruction is not uncommon with rather elaborate instruction set which includes a handful of "macro" instructions for common tasks such as initializing array of data and random number generation and some others. If implementing a stack based VM within a program, the stack machine has some overhead(because it has to be implemented with all the functionality and interfacing with the rest of the program) but that is mainly a curiosity - one can implement a less-well scaling ISA without binary coding and fixed opcode length with far fewer bytes for the VM, but then the cheap cost will be offset with worse code density. On the other hand a more advanced VM takes far more space, but the greater code densty pays off after certain amount of code. Where this matters is of course demoscene. ;)
- deleted 14y ago
  [deleted]
- gogetter 14y ago
  In a more general sense, I see benefit outside of just demoscene. If code density makes programs small enough to fit in cache it makes diskless, RAM-based systems potentially faster.
  - zxcdw 14y ago
    One could easily think so, but it's not quite true. While x86 processors have relied on caching the instructions for some two decades now the overhead of decoding the VM bytecode instruction bitstream of the VM is certainly too high(especially if it's compressed) to outweigh the possibly reduced stalls due to instruction cache miss because of greater code density. Of course, one could translate the VM bytecode bitstream to equivalent x86 code upon running, but without some really smart heuristic optimizer there wouldn't be much to gain in speed over simple x86 implementation, although it'd very probably be faster than the VM.
    - 14y ago
justincormack 14y ago
I do hope more old technical books make it to a new life online. Otherwise whole areas will get increasingly hard to access, as there are only a limited number of library copies.
- Evbn 14y ago
  ACM has a bunch of classic books for download.
jules 14y ago
Since then the result seems to be that stack vs registers, it doesn't really matter as much as people thought. A modern processor that's out of order [1] has to reconstruct the dependencies in the dataflow graph anyway. Out of all the things going on in a processor, doing so from a register ISA or from a stack ISA is not that different. A bare bones stack machine may be smaller than a bare bones register machine, but nobody wants to run those anyway. http://en.wikipedia.org/wiki/Out-of-order_execution http://en.wikipedia.org/wiki/Out-of-order_execution
- dfox 14y ago
  One of problems of stack machines is that it is mostly impossible to build useful out-of-order stack machine (or even in-order multiple issue). Short or non-existent pipelines and low CPI of stack machines tend to offset this for certain classes of code (lots of branching and so), but cannot rival performance of modern register based designs for other classes of code (number crunching).
  - tailrecursion 14y ago
    It is straightforward to convert stack instructions to 3-address instructions, by keeping a counter -- a stack pointer -- that points into the register file. As instructions are decoded the stack pointer is read and the current reading is delivered on down the pipeline with the instruction itself. From there on, the cpu is executing an instruction that calls out explicit register numbers. The stack counter is kept with the decoder at the very start of the pipeline. This "register number decoder" needs to run sequentially, and it needs to run a faster cycle time than the rest of the cpu.
cookingrobot 14y ago
Idea: Notch should use a stack machine as the basis for his new 0x10c game. (A big part of the game involves programming an in-game 16bit computer.) It'd be a great excuse for a lot of people to explore this architecture.
- rrmm 14y ago
  They can also use the the Java VM or CLR as those are both stack machines.

100 points by falava 14y ago

luu 14y ago

Mini book review: On the off chance you're planning on implementing a stack machine, you must read this book. A few years ago I was working on a stack machine, and I didn't know what to read because virtually all of the references for fundamental material are decades old. Let me save you the trouble and tell you this is the one you want. There are newer papers you should read, of course, but if you're only going to read one thing, it should be this. Why would you want a stack machine in this day and age? They're small. Really, really, small. The stack processor we made was so small that it fit in an empty space in the floorplan of our "real" (x86) processor.

daniel-cussen 14y ago
I'm using stack machines now because, like you said, they're small. Meaning, you can fit a ton of them on a chip, and if you can get them to talk to each other, you have yourself a pretty powerful parallel processor. The chip I'm working with has 144 cores running at ~700MHz, and it costs $20. It's insane how much being small buys you.
- jallmann 14y ago
  Chuck Moore's GreenArrays chip? (He's also the guy behind Forth, the quintessential stack-based VM.) How's that working?
  - daniel-cussen 14y ago
    The very same. It's working really well—initially I was intimidated about the chips because of a few of the constraints the chip has in order to be as good as it is. Three challenges: 1) Figuring out how to work within the very low (but reasonable) amount of RAM each core has. They're independent computers, so each core needs to store its code and its data, all within 64 18-bit bytewords, which roughly corresponds to a tweet of information if you tweeted in UTF-8. 2) Dealing with the IDE: the IDE is attacking a problem nobody's solved: parallel compilation. That being said, it has been the second greatest challenge so far, after 3) Getting the hardware set up. My co-project-doer is light-years ahead of me in the EE department and makes most of the EE decisions, with some input from me about what capabilities the chip needs to have (a minimum amount of off-die RAM, say). Sourcing parts is something I would not have been able to do on my own, so I'd say this project requires a good deal of electronic literacy, if not dexterity. That being said, though it's a bit of a prima-donna, it has every right and reason to be. It's an amazing, amazing chip. It's fast, powerful, unclocked, can work with all kinds of devices, is a crazy bargain both in hardware cost and in energy cost, and best of all, for me at least, an endless source of fun, hard problems. It's a fascinating chip.
    - tailrecursion 14y ago
      It's great to see people using Chuck's work, and in particular it's wonderful to see your reaction. I think it would be easy to recoil at the strange tools, not to mention the difficulty of programming the thing. I agree it's a fascinating device.
    - listic 14y ago
      Can you give a hint as to what we can expect to do with this chip? I was a Forth enthusiast and read the book in OP (in early 2000's) and followed Chuck's work from afar, but I am not sure what exactly I could do with this chip, given its peculiar limitations.
      - daniel-cussen 14y ago
        With low RAM like that, what you want to do is math, not UI. That means electrical engineering or number crunching, AFAIK. OK, so first, it has a lot of I/O ports of different kinds on just one chip. In a lab, you could run lots of analogue knobs and many servos attached to just one chip. This means a lot less hardware debugging, which should be a Godsend. Another possibility is HPC. You can tile a motherboard with these, cool them all down to -50 very easily and cheaply, and then overclock them as you perform number crunching that you couldn't do with a GPU. After all, these cores are truly independent, and can therefore branch independently, unlike GPU cores. That opens the door to a wide variety of algorithms that aren't GPGPU accessible.
        jules 14y ago
        It sure looks like a fine chip for a very small niche, but they don't even have floating point instructions AFAIK, so you'd have to emulate them in software. So I'm extremely skeptical about their number crunching capabilities.
        listic 14y ago
        No floating point. I believe design complexity of the chip would increase manifold if it was. Emulation is not an option too with those extremely limited resources (64 words of memory). The design philosophy of this chip is that 18 bits of integer precision should be enough for your applications, period. I just feel like I'm not smart enough to figure out how to fit a useful application into that.
chubot 14y ago
Hmmm interesting... If it uses that much less silicon then I imagine you could save huge amounts of power. A lot of people would be interested. There must be some tradeoff then. Companies are burning huge amounts of cash buying data centers in remote areas because of power. Presumably it's not very hard to compile C to stack code. (Or maybe it won't be as efficient as... Forth?) Or maybe most applications aren't really CPU limited. I remember reading about Chuck Moore's low power processors, but they seem to have mostly specialized applications. In that case it's probably not fair to compare them to x86.
- RodgerTheGreat 14y ago
  The book actually discusses the problems with running C code on stack machines. To sum up, yes- you absolutely can run C code on a stack machine, but you lose most of the advantages of the architecture. Stack machines make procedure calls very inexpensive and encourage the use of very short procedures with a small number of variables in scope at a given time. The stack operators that are available provide quick access to a few elements at the top of the stacks at the expense of random access to elements that are deeper. Stack-oriented languages like Forth make the programmer aware of this and encourage breaking tasks down in this manner. Idiomatic C has procedures which are at least an order of magnitude longer and have many more values in scope at a given time. This provides a compiler with a fairly uncomfortable and difficult optimization task. Speaking as someone who works with compilers and really likes stack machines, I don't think they will provide much practical value unless programmers are willing to adapt their languages and their approach to programming to the strengths and weaknesses of the paradigm.
  - thesz 14y ago
    http://repository.cmu.edu/cgi/viewcontent.cgi?article=1712&context=isr http://repository.cmu.edu/cgi/viewcontent.cgi?article=1712&#... "The algorithm have I developed for intra-block stack scheduling seems to be quite effective, eliminating 91% to 100% of redundant local variable accesses within basic blocks for the small programs studied. Hand-performed global optimization results indicate that significantly better stack scheduling can be done if variables are kept on the stack across basic block boundaries." What is also possible is to discover identical code and automatically generate procedures for it.
petermonsson 14y ago
How small is really, really small? Something that is small in a x86 sense is not at all small in an embedded world. If you could elaborate a bit on the performance requirements for the application I'd be really happy. I am curious how it compares to an equivalent ARM (f. x. the 12kgate Cortex-M0+) in terms of area, power, performance.
deleted 14y ago
[deleted]

tikhonj 14y ago

I've been playing around with some Greenarray[1] chips lately, and I have to admit that the core ideas are fascinating. Their particular variant of Forth is actually almost pleasant to use--certainly better than MIPS, which is my closest point of reference. (Ignoring crazy things like the color of identifiers controlling your program's semantics.) The chips are also extremely power efficient. [1]: http://www.greenarraychips.com/ http://www.greenarraychips.com/ I've found having a mental model of a stack-based system far easier than even a simple register-based one. However, this might also be true because the Greenarray chips themselves are far simpler than any other CPU I've ever looked at. And, of course, the fact that you have 144 cores on a tiny chip despite a cheap manufacturing process is also very neat.

gruseom 14y ago
Oh, please write about your experiences programming those chips. I'm sure I'm not the only one who'd like to hear all about it. I'd particularly like to know how you deploy code to the 144 cores and how they talk to one another. Edit: that request is to anyone who has programmed the GreenArrays chips.
- batgaijin 14y ago
  Yes, please write this! I'd normally just upvote your comment, but I feel like the sorts of people who play around with GreenArray chips are not that prone to blogging, at least by my googling...
tailrecursion 14y ago
Are you able to boot all the cores and get them functional? I like the design of these chips too, especially how each core "blocks" on its message queue by instantly going to sleep, taking zero power -- and then instantly wakes up the moment a message appears.

zxcdw 14y ago

One domain where stack machines shine is code density because of no need for register encoding. Instruction lengths aren't measured in bytes, but rather in bits. With some form of binary coding, one can reduce code size even further, 1-7 bits per instruction is not uncommon with rather elaborate instruction set which includes a handful of "macro" instructions for common tasks such as initializing array of data and random number generation and some others. If implementing a stack based VM within a program, the stack machine has some overhead(because it has to be implemented with all the functionality and interfacing with the rest of the program) but that is mainly a curiosity - one can implement a less-well scaling ISA without binary coding and fixed opcode length with far fewer bytes for the VM, but then the cheap cost will be offset with worse code density. On the other hand a more advanced VM takes far more space, but the greater code densty pays off after certain amount of code. Where this matters is of course demoscene. ;)

deleted 14y ago
[deleted]
gogetter 14y ago
In a more general sense, I see benefit outside of just demoscene. If code density makes programs small enough to fit in cache it makes diskless, RAM-based systems potentially faster.
- zxcdw 14y ago
  One could easily think so, but it's not quite true. While x86 processors have relied on caching the instructions for some two decades now the overhead of decoding the VM bytecode instruction bitstream of the VM is certainly too high(especially if it's compressed) to outweigh the possibly reduced stalls due to instruction cache miss because of greater code density. Of course, one could translate the VM bytecode bitstream to equivalent x86 code upon running, but without some really smart heuristic optimizer there wouldn't be much to gain in speed over simple x86 implementation, although it'd very probably be faster than the VM.
  - 14y ago

justincormack 14y ago

I do hope more old technical books make it to a new life online. Otherwise whole areas will get increasingly hard to access, as there are only a limited number of library copies.

Evbn 14y ago
ACM has a bunch of classic books for download.

jules 14y ago

Since then the result seems to be that stack vs registers, it doesn't really matter as much as people thought. A modern processor that's out of order [1] has to reconstruct the dependencies in the dataflow graph anyway. Out of all the things going on in a processor, doing so from a register ISA or from a stack ISA is not that different. A bare bones stack machine may be smaller than a bare bones register machine, but nobody wants to run those anyway. http://en.wikipedia.org/wiki/Out-of-order_execution http://en.wikipedia.org/wiki/Out-of-order_execution

dfox 14y ago
One of problems of stack machines is that it is mostly impossible to build useful out-of-order stack machine (or even in-order multiple issue). Short or non-existent pipelines and low CPI of stack machines tend to offset this for certain classes of code (lots of branching and so), but cannot rival performance of modern register based designs for other classes of code (number crunching).
- tailrecursion 14y ago
  It is straightforward to convert stack instructions to 3-address instructions, by keeping a counter -- a stack pointer -- that points into the register file. As instructions are decoded the stack pointer is read and the current reading is delivered on down the pipeline with the instruction itself. From there on, the cpu is executing an instruction that calls out explicit register numbers. The stack counter is kept with the decoder at the very start of the pipeline. This "register number decoder" needs to run sequentially, and it needs to run a faster cycle time than the rest of the cpu.

cookingrobot 14y ago

Idea: Notch should use a stack machine as the basis for his new 0x10c game. (A big part of the game involves programming an in-game 16bit computer.) It'd be a great excuse for a lot of people to explore this architecture.

rrmm 14y ago
They can also use the the Java VM or CLR as those are both stack machines.