A CPU is a compiler
outerproduct.net
outerproduct.net
For instance there is the kind of simple interpreter that I know how to write off the top of my head which evaluates the nodes of an expression tree which is horribly inefficient.
Then there is something like Python which "compiles" code to bytecode which is then interpreted by a "virtual machine". That kind of system admits very complex optimizations about as far you as can imagine, including compiling some of the bytecode all the way to machine code the way PyPy or the JVM does it.
Note most interpretations of the Intel architectures break complex instructions up into RISC-like "micro-ops", which is a bit like bytecode interpretation.
One of the biggest concerns in a modern CPU is that memory accesses are very slow relative to a CPU cycle so you want to be executing a large number of instructions at a time to hide the latency of memory access. Intel's failed Itanium had the compiler try to explicitly schedule this but it didn't work because the compiler can't know ahead of time (for general purpose code) what is in what level of the cache and what isn't -- and in a worse case scenario this can hang up not only one instruction but many other instructions that depend on the result of that instruction, ether because they really depend on the result or because the CPU gets hung up. The CPU, on the other hand, does know, and can be opportunistic about taking advantage of available parallelism.
Isn't Apple M1 much wider than x86?
If there's a serious problem w/ the x86 architecture it's that the instructions are variable length from 1 to 14 bytes so if you wanted to build a decoder that fetches, say, 5 instructions at a time it would have to read 70 bytes. It has to run very quickly, ideally it doesn't consume a lot of power, so it is going to take up a lot of die area and if you want to make it wider still it is a challenge.
Intel and AMD do really well despite this and the long instructions mean you can build all sorts of acceleration into the CPU which can make up for this (some of why the double-pumped AVX512 is effective on AMD's latest is that even when it s getting work down at AVX256 speeds at the core, it is wasting fewer resources dealing with instructions.)
No you don't. Look at a block diagram of (say) Skylake: https://en.wikichip.org/wiki/intel/microarchitectures/skylak...
What you do is extract up to N instructions from a block of memory (in this case, 16 bytes). If there are fewer than N instructions, well, you can only issue as many as you have; if there are more than N instructions, well, you can only issue N instructions that cycle. Note that most instructions are only a few bytes length; I don't have hard data on the average instruction length of an x86-64 instruction in practice, but my guess is it's around 3-4 bytes.
The hard part about a variable-length ISA, as I understand it (hardware is not my expertise), is that you have to build essentially a mux that can steer from 16 source places to 5 outputs.
It's not just the mux, it's the control signals for the mux. If your first instruction in your 16-byte window is three bytes long, you can't realistically mux bytes 3-15 to the second decoder input, because you don't know that it needs to start decoding at byte 3 until /after/ the first instruction has decoded; so your gate delays would be the sum of the five decoders, plus muxing etc, and we're trying to do this at a single cycle.
The alternative is to have 16 decoders, each decoding what an instruction /would/ be if it started at a given byte. These all complete in parallel, but many of them might produce garbage. So we need to find the first five of these that have non-garbage outputs, and /then/ mux those sixteen possible outputs down to five channels. This is doable (and done), but it's a lot more hardware in both decoders and muxing than you might think at first.
Basically: To decode five instructions per cycle from a fixed-instruction-width stream takes five decoders. To decode up to five instructions per cycle from a variable-instruction-width stream takes number-of-possible-starts decoders and a mess of muxing. There really is a cost here.
The Thumb ISA is left as an exercise for the reader.
And of course every part of it has to be balanced. It makes no sense to decode instructions faster than the system downstream can handle it, particularly if you are wasting resources to do so.
The reason why Intel has so many different implementations of x86 is to meet the needs of different market segments.
Trade-offs are everywhere. But certainly fixed width instructions, or variable-width-but-trivial-to-determine-length (Thumb before Thumb2, RISC-V compressed) have real advantages.
I believe reading somewhere that that's pretty much how more or less recent Intel processors do that.
Well that just sounds hideously complex.
I don't think the x86 decoder is actually a particularly complex state machine (I haven't attempted to actually build it), so it's probably overall far less complex than most people assume it is.
And then add to that the complexity of speculative and out of order execution: you will want to very early decide, i.e. (pre)decode, where branch instructions are, in order to make sure your branch prediction unit has the right inputs in time, to decide where to fetch the next instructions from.
And after all that, on a branch mispredict earlier on (or pipeline flush for another reason), you might need to throw almost all of that expensively decoded instructions away and start fetching from elsewhere...
CPUs are fun :)
Section 2.2.1, Intel® 64 and IA-32 Architectures Software Developer’s Manual
Also, long instructions are infrequent, 96%+ are 7 bytes or less. That's static and dynamic is higher.
Throw in some more of context tracking (e.g. "did the left-hand side turn out to be a constant" or "are we in the (X+Y)+Z situation?" etc.) and you can start doing optimization such as constant folding and expression-tree rebalancing.
Then you can start emitting chunks of assembly instead of bytecode ("iconst X" turns into "push X", "add" turns into "pop eax; pop ecx; add eax, ecx; push eax" etc). Again, with enough context tracking (for example, what's in what registers), you can emit much less stupid assembly.
PyPI is the Python Package Index. https://en.wikipedia.org/wiki/Python_Package_Index
PyPy is the Python implementation with JIT. https://en.wikipedia.org/wiki/PyPy
(Yes, it is extremely confusing that there are two Python projects with homophonous, nearly-identical names.)
There's more than one way to name it! No, that's Raku.
Interpreters operate sequentially in time.
They take the compiler output, combine it with parameters from the world outside the cpu, and sequentially produce results that affect the physical world in some way, even if it’s just writing a result to memory.
The interpreter may use the compiled text many times.
At some point, it’s interpreters all the way down, at first in object code, then microcode. The ALU itself is a sequential hardware interpreter.
There's a historical line from a CS great (I am not sure who) that goes something like:
When you first start writing software, you will not understand the difference between an interpreter and a compiler. After you've been writing software for a certain amount of time, you will never confuse an interpreter and a compiler. But after you've been writing software for a bit longer than that, you will again not understand what the difference between them really is.
I always thought of an interpreter as a translator, while a compiler was a translator and optimizer.
So my question - can LLMs do this? They are really good at contextualizing and generating code - so why not build a compiler that is basically an LLM?
"Why no one should use AT&T syntax ever, for any reason, under any circumstances"
Every CPU manufacturing company have a compile team.
> This will never work
VLIW processors do work, and for a while now. This type of architecture performs better for data-intensive workloads, so you don't see them in the general-purpose world.
But if you are talking about Mill, yes it will never work.
Maybe Mill Computing won't pull it off, but why do you think the approach is bad? It seems sufficiently different from Itanium to not have the exact same problems.
The architecture itself looks very good. If it was built in a way similar to RISC-V, it would probably become very influential. (But then, I'm not sure you can create something that innovative by the same procedures RISC-V was created.)
And above all because there are too many choices that are too specific, outdated and too exotic. (e.g. the split-stream encoding is way too exotic)
I work in a small company that makes processors, and I know from experience that developing a processor is a very complicated subject, you have to go step by step (Mill does not). When you come up with a new design/idea, you try to simulate it, test it and implement it. You don't pile up new ideas without getting feedback on them.
Sure, but that doesn't help when all the binaries are compiled for AMD64 anyway.
Assuming you have access to the source code of course.
The one binary that does minimal to no self modification on boot is popular with users but intrinsically slower. Arm's variable length vector instructions are catering to that.
One binary that is specialised to hardware and expected arguments is the fastest you can do without optimising while the program is starting/running.
However hardware usually changes slower than software. Specifically if a program starts running on a specific x64 chip it's likely to stay on that chip until it finishes running. Linux used to patch itself on boot to pick a faster memcpy (may still do).
It seems obvious that fastest for sufficiently long running processes is to ship a compiler IR, specialise first to the hardware and second to patterns in the data. OpenCL/spir-v have a finaliser premise where you lower to a given GPU just before running on it. Specialising on program data is branded JIT compilation. I don't know of anything doing both yet.
Mill's idea for that is that compiler outputs a multi-target binary, which is specialized to the current CPU at install/first-run time, by fixing the size of the belt and other such hardware details.
> "genAsm is a dataflow language, essentially a programmable representation of a single-assignment compiler IR."
Make the chip simpler and more parallel (way more cores) Make the compiler smarter to better use the capabilities of the hardware.
Watching Jim Keller interview made me realise how much transistors are wasted because the cpu is trying to predict what the code is going to do.
There is an insane amount of complexity in chips trying to make single threaded code fast when what need the most cpu time in our code is usually parallels problem.
Maybe Triton will break that paradigm and will allow diverse parallels hardware to emerge and be used effectively.
As an example: there are so many low level ways to run a conv2D kernel on a SIMT machine, but CuDNN will pick the best option for you based on the card you have, and the tensor sizes you are using.
If x86 was Intel only, Itanium would have been eventually pushed everywhere no matter what.
> Peephole optimisations, idioms | Idioms
From the software side, what is it exactly that makes it so difficult to write a higher-level language that must be optimized, instead of a language that already exposes the optimizations in a friendly way?
("higher-level language" meaning c, not python or something)
Are your asking why we could not expose optimization feature (e.g. branch hint to replace branch-prediction) in the programming language ?
Are you asking if it's difficult for a compiler to optimize some type of high-level languages ?
Since "higher-level" language is C in your question, what the "language that already exposes the optimizations in a friendly way" ? Are you thinking the CPU µop as a language ?
Difficulty increases as the source and target languages become less similar, as more ambitious performance optimisations are attempted, as more comprehensive type/lint/warning style systems are implemented and as performance constraints on the compiler itself tighten.
So a compiler that takes imprecise scribblings, spots errors in them, and emits asymptotically perfect machine code for heterogenous distributed systems in real time is quite dramatically more complicated than cat.
A nice introduction to some similarities but the details and constraints are quite different.
Transmeta however...
and david bacon (et al) - https://files.catbox.moe/bipg79.pdf
When Sun brought out their SPARC hardware the language they run was ported to that, and ran about four times faster clock-for-clock.
You can gain some measure of the Rekursiv's success from the fact that the only complete machine known to still exist can be found on the bottom of the Forth and Clyde Canal, somewhere around the Possil Road Aqueduct.
The founders parents fled from Austria during Nazi times. In Austria we speak German. The English word "recursive" is "rekursiv" in German.
Fascinating guy.
(This whole thing also reminds me of the Intel 432... had some similar properties)
I do wonder how this CPU code looks like
ML, Lisp, and Logic derived languages are all relatively easy.
Hence why on my degree their were forbidden for compiler assignments, even though we had a strong ML and Prolog set of lectures in programming languages I and II, LP II.
We were supposed to earn the compiler design assignment, from the professor´s point of view.
Although the year I took it, it was about the time Java was being introduced, so doing it with Java, SableCC while not as easy wasn't that harder, specially following alongside the Tiger book.
There is plenty of "cred" to be earned without that; you can still be pulling your hair out debugging a compiler written in Lisp, find years-old bugs in it and so on.
I don't know anything else about your ex-prof other than what you have in the comment, but based on that, my Ouija board's planchette is edging toward "insufferable asshole".
Mental note: be sure not to be that guy if you ever turn professor.
Our Physics III was even worse, it was one of those that was proud of hard it was to go through his final semester exam.
Thankfully they tend to be a minority, I also met several that became an a good example of how teaching should be like.
With sufficient dedication, you can even cut out the bodies from the binary the compiler of your high-level implementation language produced, to piggyback on its target support. Gforth[2] among others does this in the land of Forth, but the more well-known implementation is perhaps the dyngen code generator[3] used in Qemu before the switch to TCG in version 0.10.
Generating machine code isn’t difficult, and neither is modifying a (low-level) bytecode generator to do it[4]. Generaring good machine code is difficult.
[1] http://www.bradrodriguez.com/papers/moving1.htm
[2] https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Dyn...
[3] https://gitlab.com/qemu-project/qemu/-/blob/v0.9.1/qemu-tech..., rendered as https://web.archive.org/web/20081120011949if_/http://bellard...