The J1 Forth CPU (2010)
excamera.com
excamera.com
In the first hardware implementation, integer divide had been botched, and gave wrong answers for odd-numbered divisors. There was an argument in the data sheet that most divisors are even, and a subroutine for correct divides when needed.
[1] http://www.cpushack.com/2013/02/21/charles-moore-forth-stack...
http://opencores.org/project,hive
I need to update the paper and code, the core is at v9.03 and the simulator can now parse assembly code as input.
IMO canonical stack processors aren't a good substitute for register-based processors. Hive is a stack / register hybrid that makes the 2 operand architecture more efficient. And I don't know why barrel processors aren't taking over the world - they make too much sense I suppose.
https://news.ycombinator.com/item?id=9920760
It's a thesis describing a C compiler for stack machines. (The link in the article is dead now. See https://www-users.cs.york.ac.uk/chrisb/main-pages/publicatio...)
It achieves comparable code density with gcc's x86 (albeit for a fictional architecture).
The really interesting bit is Appendix E, which proposes an architecture for a fast stack machine. It uses a fairly traditional 16-bit instruction encoding, except instead of registers each 4-bit operand slot contains an encoded stack manipulation --- a rot or a pick. This should give even better code density while still being easy to implement.
Unfortunately I've never tracked down a copy of his compiler...
Perhaps you, or someone here, would know: has anyone asked and tried to analytically answer what primitive operations an ALU ought to have? I mean, everything could be coded as a look-up-table, but given code "on average", what should be available in hardware.
It's a strange question that requires you pose it properly to even begin to answer it. For example, in the kind of stuff I do, popcnt and other "set-like" bit operations, i.e. most-significant set bit, are important enough that I just wish they were built in.
Mine you, I'm doing high-performance data processing, so perhaps it's not part of the scope of "average" code, but I disagree.
Very good question. I think this is where the "art" of computer design starts, and it generally gets short shrift. For instance, the ARM lacks a leading zero count instruction, which is a pretty wild omission because it has tons of uses (particularly for floating point) and is fairly expensive to implement in software using other primitives.
I know it's not scientific, but I learned what to put in the Hive ALU by programming various algorithms I figured I would need at some point. I just developed a bunch of floating point subroutines for Hive (cos, sin, sqrt, 2^x, log2, 1/x, etc., not in the paper yet) and, short of adding a floating point pipeline, could only really justify adding an opcode that returns +1 / -1 based on the sign bit (for use in storing sign and doing absolute value). My seat of the pants rule is that if it has broad applicability, saves time and code space, and isn't too costly in terms of hardware / speed, then I put it in. Otherwise I leave it out.
IMO, more of computer engineering should focus on what to leave out.
I don't have all the know-how, but if I had the resources, I'd like to build a system where I push compute to a node that essentially is a M.2 SSD glued to a custom core glued to 10G networking. Wire it all up in a Clos network. Use IPv6 and treat it as the address space, throw in a few routing tricks, and call the whole thing a computer.
One day I'll build it. Hopefully I can get to that scale at some point.
When I assemble a new PC I almost never increase the memory down the road, so it might as well be on the processor die.
Huh? ARM has this instruction (since v5, IIRC), it's spelled CLZ.
Do you want to go fast, or do you want to get the gate count down?
Intel does code measurement to decide which instructions have to go fast, and which don't. Typically they run Windows workloads for this. It's not an analysis from first principles.
The RISC crowd put a lot of effort into trying to reduce the instruction set. They tended to end up with simple instructions that could be hard-wired, and lots of registers. Many early microprocessors were microprogrammed to get the gate count down, and slow because of it. RISC was a reaction to that.
Early RISC thinking focused on not only making all instructions the same length, but making them all take the same time - one instruction per clock. Then superscalar came to microprocessors, with the Pentium Pro, and ordinary CPUs started getting more than one instruction per clock. (Before the Pentium Pro, only supercomputers had that kind of hardware.) This killed the basic advantage of RISC.
Most of the little Forth CPUs are one instruction per clock. Most Forth CPUs can hit the data stack, the call stack, and the main memory, which are all separate, on each cycle.
Edit: missing ooo
Appendix E describes I believe what Hive does: a separate bit associated with the operand selector is used to control pop behavior. I'll have to credit this paper in mine (nothing ever really new under the sun).
For the rest of the paper, if you look at his "optimized" code there are still a ton of stack ops going on, which are time wasters IMO. This is why three operand machines "won" the techno shootout, a very useful move is included with every instruction. In contrast, well written Hive assembly contains very few time wasting copy / move / pop instructions (for a two operand machine).
Their Java processor outperforms most of the others with small amount of space. It's open. Doesn't necessarily have to run Java as Oberon or something could probably be ported. The papers section is full of good stuff.
Why not?
Forth is the way it is mainly because Chuck Moore wants it that way. It's his preference. Tiny cores, typeless, hand-optimized to near metal, primitive VLSI tooling, 18-bit CPU's... nothing justified by scientific or engineering argument. All surpassed by other work in cost-benefit analysis. Nice write-up here by one person that delved deep into it to see good and bad of it:
http://yosefk.com/blog/my-history-with-forth-stack-machines....
It doesn't mean Forth is most convenient to write for any kind of problems, or that translator can easier optimize for Forth target... yet this at least is an opportunity to have a nicer language on the bare-bones level. Do you think it's a good enough thing?
One paper in my collection does that for IIRC Haskell to Forth by implementing a G-machine interpreter or compiler for a Forth CPU. It certainly can be done. Question is whether it's ideal vs a non-Forth CPU.
"At the same time you can have top performance with a concatenative, dense language."
I can do that with a Leon3 SPARC GPL'd with LISP or Forth extensions. It will be faster. Likewise, one can modify a simple, microcoded CPU to run Forth, Oberon, LISP, or whatever. Difference is that we're not tied to Forth's style in the process.
"yet this at least is an opportunity to have a nicer language on the bare-bones level. Do you think it's a good enough thing?"
If you have nothing else. Otherwise, no. I think, as I commented to avshalom, we can modify a flexible, simple RISC to have basic checks built-in. With microcode, you can raise abstraction to primitives of your choosing from expressions to stacks to heaps to pointer manipulation. Whatever you want.These can be composed of primitive instructions with checks enabled or disabled. You can then code in those with safe, highly-optimized primitives underneath making it fly in performance.
Further, as Intel does, you can always change underlying architecture to speed-up your model as you're leveraging microcode or ISA level. Last point, as my conversation with Alan Kay shows, is that modifying hardware to support OOP and late binding allows you productivity and code reduction of Smalltalk-style languages with still efficient, safe execution.
How much it would cost to you in terms of hardware - and maybe speed? - to have extensions which will have those nice features, especially if they are flexible, i.e. switchable? Would you need less gates than a Forth system?
That's not a fair question given Forth doesn't do crap compared to alternatives I'm pushing. More like "Does it use a reasonable number of gates for a commercial processor? For a MCU, do any schemes use a tiny number of gates to provide some protections vs existing MCU's?"
Answer to these are yes. As several people want links, here's a list of approaches ranging from safety to security, full to partial, MPU to MCU.
Two of the best for full safety are Hardbound and Watchdog, both from same group:
https://www.cis.upenn.edu/acg/papers/asplos08_hardbound.pdf
https://www.cs.rutgers.edu/~santosh.nagarakatte/papers/isca1...
One provides full spatial safety with other providing full memory safety with both having C compatibility. There are significant extra chip resources. Not a problem in a microprocessor, though, given the frivilous stuff takes up more space than this. The performance overhead is usually single-digit (under 5%) with it maxing out on 20% on Hardbound and 25% on Watchdog. For Watchdog, that's trading occasional 25% hit or buying a bit of extra CPU to get fully-compatible and safe C software. Great trade. HW experts could probably optimize it even further.
CHERI processor:
https://www.cl.cam.ac.uk/~swm11/research/papers/isca2014.pdf
CHERI processor adds capability-security to mix on MIPS processor. FreeBSD already ported. Uses 32% extra logic elements with 8% clock speed reduction and overhead similar to above designs. Recent papers added more protection, reduced some overheads, and so on. Strange enough, I used this one because the others have too much data to sift through quickly.
Sandia Secure Processor (SSP):
http://faculty.ist.unomaha.edu/winter/ShiftLab/Monarch_web/L...
For microcontrollers, Forth is a bad idea because it's typeless and dynamic. It's best to have strong typing plus static behavior so our current tooling can know exactly how it will behave. That naturally leads to things like Java. The system at jopdesign.com is just over 2,000 slices in FPGA. Idk if it has built-in safety checks or uses compiler's. However, this high-assurance CPU manages first-pass for 40,000 gates with full checks and verification. Plus can leverage Java tooling for automated unit tests, static analysis, dynamic analysis, design by contract... you name it. They even have a tool for converting regular Java to their tool.
Examples of ultra, lightweight schemes for MCU's:
http://www.icri-sc.org/fileadmin/user_upload/Group_TRUST/Pub...
Trustlite does isolation, attestation, and exception handling. It uses about 300 extra registers and 440 extra LUTS on a FPGA plus around 200 each per protected module. Tiny.
https://www.cs.utah.edu/~regehr/papers/plos06a.pdf
Works on 8-bit with TinyOS demonstration. Software method. Something like this could be hardware supported.
http://www.ece.umd.edu/~barua/simpson-CASES-2005.pdf
One for microcontrollers that averages 0.72% speed overhead (approx 10% max) and code size of 3.6%. Could be aided with HW.
http://read.seas.harvard.edu/~kohler/pubs/kumar07system.pdf
Another proven out on an ATmega with single-digit runtime effects and only a few thousands slices in MCU that's over 20,000 at start.
Note: You don't see much on 8-bit or 16-bit HW on my list as they're so constrained that a MPU or stack-overflow check is about all you can do. It's why I recommend against them most of the time. The likes of Infineon and Gemalto are stretching their capabilities far, though, in smartcard IC's with onboard crypto, MPU's, built-in checks, and usually a verified, safe OS or platform like MULTOS or JavaCard. One really just needs to use best tools and care they can on such platforms, though. 32-bit in 20,000-30,000 gate range is the lower bound so far on believable tech for assisted safety or security. I mean, you can use 8- or 16-bit with similar tech but your overall datapath and gates will be similar to 32-bit ones. Just get different tradeoffs in speed, code-size, addressing, and so on.
But a sample of the others could make for some good reading over semester break.
Thanks
https://news.ycombinator.com/item?id=11848132
I spent a lot of time on the other list. I spent at least 10 minutes for your question on variations of Forth, G-machine, and so on with Google coming up with nothing. Piece of crap search engine... I mean, just imagine one of the many G-machine compilers that have been described but whose end result are Forth operations implemented in hardware. I know seeing it is better but that's the gist. I make up for it hopefully with these two implementations of G-machine and a ML processor that I doubt you have:
http://digitalcommons.ohsu.edu/cgi/viewcontent.cgi?article=1...
https://news.ycombinator.com/item?id=10607730
Note: Use Wayback Machine at Archive.org if main PDF for SKI CPU doesn't load. Should be there.
No doubt. Many people might try to build on it for other reasons. Hence, my warning.
"A b5000-esque cpu would be much less straight forward"
Try crash-safe.org's main presentation on SAFE architecture. Narrow your focus to that one section on atomic groups. Mentally combine that with Burrough's most primitive checks. I'm talking code vs data check, pointer bounds check, pointer write-check to prevent modification, optionally stack overflow, and so on. Each one is a few lines of C code if you draw it out. I don't design HW but I've read enough of these to know there's close to zero performance and gate overhead in such simple checks. They typically run in parallel with CPU pipeline where it goes ahead with execution but doesn't actually write results unless gets a "1" (check succeeds) from parallel checkers. Simple, simple.
Academics with almost no team or budget typically start with highly-configurable, Leon3 CPU. They add the tags or checks into a few components. Synthesize for FPGA. Done. Then, compiler and/or OS modifications to make use of it. I've seen it done for RTEMS and Linux with small teams and mods. Cambridge's CHERI, with larger team, did whole capability-architecture that's C compatible and runs FreeBSD port. Changes that big have quite the performance implications, though, which is why I focus on primitive checks for interim or hobbyist use. ;)
I'm probably showing my ignorance, but I don't think anyone can convince me that in a perfect world software errors should be caught by dedicated hardware. Same with pushing software security issues to the HW.
SW needs a pottery barn rule, you broke it you pay for it. The HW is already too complicated as it is.
Software, even small stuff, has proven to be too complex to get right consistently except for the most, elite programmers. A safety net or safe by default makes more sense. It's more fundamental than that, though.
You see, certain languages in programming are closer to how we think and express our ideas as people. We find we get more productive as we abstract away from the machine. Yet, stuff close to machine is most efficient. Common machine designs were pretty arbitrary: alternatives existed with benefits. Market forces caused proliferation of specific, painful architectures.
So, the right thing seems to be to raise abstraction of underlying machine while modifying architecture to express safe or secure programs naturally. For instance, you don't want out of bounds pointers, overflowing stacks, or data treated as code. So, why does your CPU allow that in the first place all over memory and program code? Just foolish. Instead, design the CPU to include compiler-calculated bounds with pointers, to spot stack overflows in making, and to mark & treat differently code vs data. That's what Burroughs did and SAFE is doing.
Another is modular programming and OOP's takeover of modern programming. Our systems are broken down into modules with internal state, function calls operating on it, and function calls to other modules. We enforce separation between these states, expect some functions/data to stay private, and expect certain datatypes in function calls. Object-descriptor architectures divide hardware into objects with read/write/execute/access permissions enforced as CPU runs the program. Natural way to express such a system. Mapping OOP expressions & procedures onto a stack, heap, user/kernel MMU, and optionally some segments doesn't fit the use case at all. Alien to it actually.
So, the idea is to combine a language for efficient, productive, and safe-by-default expression of our intent as programmers with a CPU designed to efficiently run that plus provide low-cost checks as a safety net. That was Burroughs approach. An embedded version might be combination of Java subset with Java CPU's like jop-design.com or Sandia's Secure Processor (aka SSP or Score). Java CPU runs hardware ideal for language with some basic checks built-in that run at high speed. Language, type system, static analysis, compiler, and programmer do rest.
So, two different models. One is arbitrary machines designed for whatever Thompson or Moore preferred on minimal hardware they had with "just try harder" told to programmers. Other is carefully-designed, safe languages with CPU's built for them & checking their integrity. Option 2 makes more sense to me even if minority opinion. ;)
SW coming to HW saying "we need feature Y because our own SW process is so completely screwed up and out of control it takes an Einstein to do it right" I don't get.
Not making much sense. Part of this process you talk about is selecting tools that make job easier. Applies to CPU's as well as anything else. My research is taking it all the way down to how gates or analog circuits are done to max availability or integrity. Burroughs plus NonStop with correct by construction synthesis basically.
Except for cosmic rays flipping bits, well designed processors aren't inherently unsafe. People and the software they write are unsafe (guns don't kill people...). Why put any SW onus on HW where it will almost always be more expensive and less flexible?
Besides, empirical evidence is strongly against your statements about people's competence or bad analogies to guns. Empirical evidence, even for OpenBSD or Bernstein, show the best coders can't consistently make software work on tooling and architectures you seem to prefer. Whereas, average people using Rust and/or Java CPU's are producing software faster with few to no exploitable defects. And both can be targeted to under 10,000 gates (ARM is 30k+).
As the blog author points out, local variables are a huge issue on a stack machine because they lead to stack thrash. ANY stack manipulation must be seen as fundamentally inefficient, and they make Forth a naturally obfuscated write-only language IMO.
I understand complexity push-back, particularly in the processor / SW worlds where so much of it seems actually harmful, but the cult they've formed around Chuck Moore is kinda weird and it makes it hard for noobs to get a balanced picture of computing.
Forth routines are usually short so they don't need local variables.
> ANY stack manipulation must be seen as fundamentally inefficient
Why? I remember developing Forth code on a 6502 machine, and the code was just ten times slower than native assembler. That's not bad for a byte code interpreter. And the byte code is extremely compact which makes Forth very suitable for tiny systems.
Variables have to go somewhere. In a zero operand machine they go on the stack. Good luck finding them amidst all the confusing rolling, picking, duping, etc.
> Why?
Because the ALU is just laying there doing nothing while the stack is having it's spine manipulated (see above).
Of course you don't want to use roll or pick. That's tutorial-level knowledge that you shouldn't use them.
What you do when you see that coming is that you offload something to a global variable. The "something" is often the central topic of some part of the program, like a file handle for instance. So it makes sense to put it in a variable because it's needed in many places.
I think the opposite is true. Basic, Assembler and Forth were my first languages. Forth was the one that was the most powerful, and it showed me best on bare metal how a computer works.
As I already mentioned, in Forth you barely need variables. Everything happens on the stack. The rest is global.
Forth requires a radical shift in thinking about programming. You should read Leo Brodie's book "Thinking Forth".
http://thinking-forth.sourceforge.net/
> Good luck finding them amidst all the confusing rolling, picking, duping, etc.
Good Forth code style uses comments all the time. For instance:
( swap the two top values )
: myswap ( x y -- y x) <= x y is input, y x is output
swap ( y x ) ;
By the way, I would never use Forth for big software. Forth is particularly powerful in tiny systems where every byte matters.
This is one issue I have with them. Real machines have local, fast storage you address directly with stores or functions operating on them. They have a remote storage, RAM, that you might work on directly with a CISC or move to local storage with many RISC's. In any case, the fundamental mechanisms are functions operating on individual data or function pointers. Best to map a high-level abstraction or low-level language directly to that. Whereas, a stack that flows this way, heap that flows that way... all this stuff isn't anything like how a computer fundamentally works. Except the stack-oriented architectures of course. :)
An alternative assembler might have variables, expressions, and function calls. Maybe differentiate between pointers and non pointers. Compile can handle (or help handle) mapping of that to non-stack machines. Looks a lot closer to Modula-2 or Oberon in the process once you consider ability to read, protect, and optimize the source code. Even though Wirth prefers stack machines for them. Another showed you could directly compile a subset to hardware:
One wonders why a company like GreenArray is trying to sell his designs. Must be a band of lunatics. A PhD paper from 2007 is certainly more serious than a company spending millions to get Moore's ideas on wafers.
Meanwhile, the products he hopes to displace are still selling well without the built-in drawbacks of his.
The J1 was an interesting processor to work with. The speed was very impressive. They produced a pretty nice dev environment to process the code with the Arduino.
I think we know now that tailoring a processor to a particular language isn't particularly efficient (though the opposite i.e. assembly is).
And yet, given the way C exploits have plagued the industry, Intel, ARM, CHERI are actually adding tagged instructions that allow C compilers to generate code that validates array and pointer accesses at hardware level.
Just like the language specific processors that you state as not being efficient.
Early on there were efforts to build custom Lisp machines, etc. which were abandoned when CPUs became good enough and general purpose enough. Using a stack processor as a stack language target seems natural until you see all the inefficient stack gymnastics that go on at the lowest level.
Even I that usually bash C here, do use it when customers or a specific project requires it. I just try to follow all best practices to make it as safe as I can, ignoring third party code.
However I can convinced that Lisp Machines, Xerox PARC and Burroughs micro-architectures, Rational Ada Machines, i432, could have been much better.
Many times technology solutions fail not because they aren't good, rather the people aren't willing to invest the time they require to become good enough.
For example JavaScript JITs, if it wasn't for the research money that Google and other vendors are willing to invest, no one would believe they would achieve the execution speed they have nowadays.
I also remember when Z80 coders could easily outperform C, Pascal, Basic and Modula compilers for 8 bit micros.
Better to code however is the most efficient at the top level, implement the HW however is the most efficient at the bottom level, and automate the middle ground.