Hacker News Reader

Comment by luu | Hacker News Reader

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.

View on HN

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.

Chuck Moore's GreenArrays chip? (He's also the guy behind Forth, the quintessential stack-based VM.) How's that working?

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.

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.

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.

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.

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.

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.

I've always thought it was a nifty chip, but one I couldn't think of an application for. Things like the 18-bit word size can throw some developers off -- the last time I looked at the chip some audio application guys were kvetching that they really need 24 bits for their applications. I'm skeptical that the architecture is a good fit for number crunching, but perhaps I'm just blind to all the numeric apps that 18-bit integers are nifty for.

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.

A very peculiar kind of number crunching that would be. With 64 words, that should be some finely selected numbers :)

I'd love to be able to do some useful work with that, of course.

Don't think of the F18 computers in isolation- think about doing stream processing with a network of them. You probably can't fit your application on one F18, but you could easily fit one or two functions in 64 words, especially given that a single machine word can contain up to four instructions.

By IDE, do you mean Color Forth? Are you using Color Forth? If that's totally wrong, could you talk more about the IDE anyway?

Yes, I'm using Color Forth. It's not the best part of the package...it took a really long time to learn, and I had to learn its keyboard layout to do so. My philosophy, in general, is, "do whatever you want, but don't change my editor or keyboard." After all, I spent several weeks being unable to type because I was learning Dvorak, years ago. And emacs had a steep learning curve too.

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.

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.

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.

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.

Yeah that makes sense. I think programming is becoming more and more heterogeneous. So it's possible that stack machines will make a resurgence for some applications, driven by huge power savings.

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.

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.

Reply on news.ycombinator.com