4 ms·
The vast majority of instructions by a computer are executed in loops, if you perform the translation once it's an O(1) overhead in the ideal case. Intel and A
by mhh__ 6y ago
The vast majority of instructions by a computer are executed in loops, if you perform the translation once it's an O(1) overhead in the ideal case.
Intel and AMD both perform decodes in parallel, but not as wide as M1, but having such a large and complex decoder costs silicon and power. Taking RISC-V as an example, a fixed width frontend is a project for a student, a modern x86 decoder is probably millions to write and verify.
I bet both Intel and AMD aren't exactly in love with x86 at the moment
- dragontamer 6y ago> a modern x86 decoder is probably millions to write and verify I must be missing something, because it looks pretty simple as a segmented sum problem to me. A good example of parallel segmented sum is bishop / rook (aka sliding pieces) movement. https://www.chessprogramming.org/Kogge-Stone_Algorithm https://www.chessprogramming.org/Kogge-Stone_Algorithm This segmented sum / prefix sum / Kogge Stone is taught in carry sum adder class at the undergrad level. Sure, it's non obvious that it applies to parallel decoding but id expect this sort of thing to be a student exercise at the masters level.
- mhh__ 6y agoIs it simple? Variable length encoding doesn't have to be overly difficult, but x86 is a weird ISA. I'm not entirely familiar with what you cite so I can't really comment, but x86's semi-unbounded prefixes and sheer volume of extensions make things difficult. A master's project might be to write a decoder, possibly to verify (prove - everything in a CPU has to be formally verified or generated from some other formally verified tool) it. As proof I raise that many disassemblers, which run as software and are therefore much easier to write, still disagree and struggle with x86
- dragontamer 6y agoKogge-Stone proved that ANY associative function can be parallelized with a prefix-sum arrangement. Associative defined as in f(f(x, y), z) == f(x, f(y, z)... or more commonly (A+B) + C == A + (B+C), where + is any associative operator) https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum In particular, this arrangement: https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Hillis-Steele_Prefix_Sum.svg https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Hillis-... Now "add" (or +) is associative. But it also works for *, min, max, and even weird stuff like "Can the Bishop move here" or "Can the Rook move here". So the goal is to find an associative operator that you apply byte-per-byte. ------ Okay, a brief detour. It seems obvious to me that a finite-state machine can decode x86 byte-by-byte. FSM is the "obvious" sequential algorithm that determines whether the byte is the start-of-instruction, or the middle-of-instruction, as well as what instruction it is by the end. Remember: we're just trying to make a FSM decode ONE instruction right now. That's pretty obvious how to do that. (Alternatively, imagine a RegEx that can parse an instruction from the bytestream when given the start-of-instruction. All Regular-expressions have a finite-state-machine representation). Hillis / Steele proved that finite-state machines are associative operators (!!!), and therefore can be used in parallel-prefix sum arrangements. (http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgorithms.pdf http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgori...) The page number is 1176: > Since this composition operation is associative, we may compute the automaton state after every character in a string as follows: > 1. Replace every character in the string with the array representation of its state-to-state function. > 2. Perform a parallel-prefix operation. The combining function is the composition of arrays as described above. The net effect is that, after this step, every character c of the original string has been replaced by an array representing the state- to-state function for that prefix of the original string that ends at (and includes) c. > 3. Use the initial automaton state (N in our example) to index into all these arrays. Now every character has been replaced by the state the automaton would have after that character. In short: computing the "state" of a sequential FSM applied across its inputs can be EASILY performed in parallel through the prefix-sum model. Any finite state machine can be converted into parallel prefix form through this mechanism. "Work Efficient" Parallel Prefix arrangement is O(log(n)) depth and O(n) total elements, which means that parallel decoding to any width (ie: 8-way decoder, 16-way decoder, or even 1024-way decoder) is LINEAR in terms of power-consumption and O(log(n)) with respect to time. The layout for work-efficient Parallel Prefix is: https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Prefix_sum_16.svg https://en.wikipedia.org/wiki/Prefix_sum#/media/File:Prefix_...
- mhh__ 6y agoI'll have to take your word for parts of this because I'm not familiar with this proof. I'm not sure x86 decoding is oh-so-simple, because if you bring in memory the alignment is not guaranteed so you don't even know where the instruction starts let alone where it ends. An x86 instruction can theoretically have an unbounded number of prefixes, meaningful only after decoding something after that - maybe you can do it with a FSM but an enormous one. All in all this doesn't sound like a master's project in the slightest, because remember I said design and verify not just build a never-used-again toy. There have been probably hundreds of millions of dollars spent on this over the years, and they're basically stuck on the current width and multiple pipeline stages.
- dragontamer 6y ago> An x86 instruction can theoretically have an unbounded number of prefixes All x86 instructions are strongly bounded by 15 byte lengths, otherwise processors throw an exception. I just searched StackOverflow: https://stackoverflow.com/questions/23788236/get-size-of-assembly-instructions/23843450#23843450 https://stackoverflow.com/questions/23788236/get-size-of-ass... Just as I expected: finite-state machine used to decode. Now write a FSM-compiler (which is an undergrad-level project), to automatically parallelize the implementation. The parallelization step is probably Master's level, but a very advanced undergrad student can probably accomplish it: since all the individual elements are undergrad projects (Kogge-stone applied to associative operators, finite-state machine compiler / regular expressions) The overall process is also documented by Intel in their Opcode map: https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf https://www.intel.com/content/dam/www/public/us/en/documents... As a FSM, verification is simple. Just generate all x86 instructions (there are a finite number of them after all), and ensure your FSM properly goes through all of them.
- mhh__ 6y agoThat state machine looks ahead more than one symbol and has a lot of memory even if you consider it one big state. You have to verify it decodes invalid instructions as a fault which means testing the entire search space. Hypothetically you could use a bounded model check but you need to test roughly 10^36 combinations which is still thousands of years if you can do a 1000 billion billion a second. You need a formal proof of the operation too.
- spijdar 6y ago> I bet both Intel and AMD aren't exactly in love with x86 at the moment This has been the case for, eh, decades now? To me it's almost a joke how many times Intel has tried to replace ia32 with a modernized replacement and miserably failed to make any headway. I suppose Intel doesn't want to try competing with the legion of architecturally similar RISC cores and would rather "go big" with ideas like Itanium/i860/i960/iAPX. It's funny to imagine, but maybe one day they'd release a RISC-V implementing processor. Can't imagine them licensing the rights to ARM, and going with Power or MIPS also seems out of character.