3 ms·
In terms of length and density at least, the optimal solution is something like compression with Huffman coding, as it is fundamentally a compression question,
by retrac 4y ago
In terms of length and density at least, the optimal solution is something like compression with Huffman coding, as it is fundamentally a compression question, where we want to represent the most frequent operations and operands with the fewest bits, on average. As with any question of compression, the optimal format will depend on the nature of the compressed data. So at least in that domain, there is no truly ideal solution, only approximately ideal solutions. (The approximately ideal solution is quite good though -- in practice Huffman-encoded instructions for stack machines with a rich operation set based on an average instruction mix, come around 4 bits per instruction on average, IIRC. I've seen the approach used with a VM interpreter on a memory-constrained embedded system to pack in more code.) I suspect the same is true of other criteria you might select for what makes an ideal instruction set; it's always going to be some compromising trade-offs, some of which depend on runtime properties like actual instruction mix.
- zogomoox 4y agoWould it be possible to have fast stack machine CPUs nowadays? (let's say, competing with x64 cpu's) or is there some inherent benefit to register machines?
- Taniwha 4y agoI think that one of the main issues with stack machines is that the order of instructions in the original instruction stream is constrained by the instruction format - you can't as easy software schedule instructions (harder to express "I have all the information required to load that value from memory around now, I'll start it now because it might take a while"). Now any high performance stack machine is likely to decompose stack code to register renaming and micro-ops so some of that stuff is going to happen anyway (as it would in a register machine) and some stack ops (like dup) are going to disappear into the renamer (but then a compiler would do that as a CSE on a register machine)
- kragen 4y agoI'm pretty sure a GA144 can do more additions or ANDs per second than any comparably-sized register-machine microcontroller: IIRC it's about a million transistors (comparable to an 80486, seven AVRs, or nine ARM9TDMIs) and can do about a hundred billion 18-bit additions per second on a few milliwatts. It definitely doesn't decompose stack code to register renaming and micro-ops. Unfortunately you can't program it either in C or in Verilog, and it doesn't have multipliers, so it hasn't seen significant adoption. But its problem is that it's hard to program, not that its performance is poor.
- sitzkrieg 4y agowould eg, transpiling C to forth address this adequately?
- kragen 4y agoNo, the problem is that each of the 144 processors in the GA144 has 64 18-bit words of RAM, which are not byte-addressable. Each word holds 3-4 5-bit instructions, so that's 256 machine instructions if you don't use any RAM for data. Even if you had C-friendly features like a stack pointer and stack-pointer-relative addressing modes, 64 words is just not very much memory for a C program. You might be able to compile a C program to a floorplan of processors passing messages to one another, but it would be similar to writing a SystemC compiler which compiles C to, ultimately, a circuit netlist. The impedance mismatch is severe.
- userbinator 4y agoThat seems closer to the architecture of a GPU than a CPU.
- kragen 4y agoThey definitely have some things in common, but the GA144 doesn't have multipliers, doesn't do SIMT, doesn't do SIMD, doesn't have texture mapping units, and doesn't have any globally accessible RAM or routing, so I don't think it's very close.