Stack Computers: the new wave (1989)
ece.cmu.edu
ece.cmu.edu
[1]: 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.
Edit: that request is to anyone who has programmed the GreenArrays chips.
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.
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.
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.
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.
yet like said at the beginning, it doesn't stop me from wishing I had an excuse to play with them. Blazing speed with lots of cores, there ought to be some applications that for that sort of parallel horsepower.
I'd love to be able to do some useful work with that, of course.
The UI, I have to say, would not pass Apple's muster. It is a completely different way of programming, and I preferred to program on paper for the longest time rather than learn all the weird controls.
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.
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.
"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.
I like Forth but feels a bit "old" to me, i.e. in that it doesn't have common data structures like hash tables. I wonder if a higher level stack language like Joy would run better on a stack machine vs. x86.
But once you are higher level, the procedure call time doesn't really matter. I haven't ever programmed any application where procedure call time is a factor... it almost seems like the last thing to optimize.
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. ;)
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.
Let's say you have a diskless RAM-based system. Swapless.
Now you launch a large program, say firefox or some other "modern web browser". That is going to require page caching, correct? This program cannot fit into the CPU cache, specifically what the Wikipedia entry (to use a common point of reference) calls the "data cache" (cf. what it calls the "instruction cache").
Now say you launch another large program. Depending on how much main memory you have, the OS is going to have to do some decision-making. Which program (or parts thereof) need to be "immediately available"?
Now imagine you have a small program constructed from very dense code, say a few K in size, and it fits entirely within the data cache. Correct me if I'm wrong, but in that case there is no page caching or OS decision-making. The program is "immediately available" as long as it's in the data cache.
OK, now I'm sure someone will take this comment apart piece by piece. But keep in mind the general idea I am suggesting is: code density lends itself to smaller programs, smaller programs lend themselves to fitting in the data cache, and fitting entirely within the CPU's data cache lends itself to running faster in a diskless RAM-based system. If this is wrong, then you need to explain why, specifically.
Secondly, there is no signifcant address translation overhead and the os doesn't need to do any decision making (or well, it does, but it is cached in the TLB and code TLBs are so efficienct nowadays that you can expect the cost to be null) so long as the resident set fits in the main ram -- whether it fits in the cache or not is irrelevant.
Thirdly, just how does the disklessness of the system have any influence? I am not entirely sure but it seems you are somehow mixing up the page cache and the CPU cache, which are completely different things.
x86 is now considered to be extremely hard to decode because it's byte-aligned instructions, and basically all modern instruction sets prefer fixed-width instructions. ARM used to tout how space-efficient it's THUMB-2/ARMv7 instruction set was compared to other RISC instruction sets because it had 2 possible instruction lengths (16b and 32b), but now that they got to (had to) reboot the ISA for 64-bit, ARMv8 is fixed-width.
For clarity for those who aren't exactly clear with all this, this only applies when the instruction set is actually compressed somehow - not for stack based machines in general.
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.