5 ms·

For modern CPU, is microcode still used for division or there are better and faster alternatives?

rep_lodsb 3y ago
The 80186 already implemented the loop for multiplication and (unsigned) division in dedicated logic that could do 1 bit per cycle. The microcode only had to set up the registers, test for overflow, and undo the final subtraction if it underflowed (since it now used a non-restoring algorithm). Starting with the 486 there is likely no longer any microcode involved, and newer chips can handle multiple bits per step. See end of article, the first algorithm to do this comes from 1957!
bri3d 3y ago
It's way more complex than this on modern CPUs, so it's harder to explain. > is microcode still used for division? Yes, almost everything on a modern CPU uses "microcode" of some kind, although the term gets kind of hazy, since everything is out-of-order and a lot of instructions are issued in parallel. In a typical modern CPU, the "frontend" will decompose instructions into uOps, which then get pushed into a "reservation station" / "scheduler." The scheduler queues and reorders various uOps in various surprising and complicated ways to try to account for interdependencies and memory latency. Eventually, a uOp is issued into to an "execution port," which is connected to a fixed-function piece of logic that actually performs part or all of an operation (for example, an Arithmetic Unit / ALU). But, while microcode will be _involved_ still, most modern CPUs will have fixed-function hardware for the meaty parts of the division instruction - they generally speaking won't implement division _purely_ using microcode like the algorithm documented in the article. > are there better and faster alternatives? They're not "alternatives" per se, but there are a _lot_ of ways to implement division algorithmically, and a _lot_ of ways to trade size for speed. Improving integer division performance has been a fairly big focus in newer CPU microarchitectures, with major improvements arriving in the latest Intel, AMD, and Apple Silicon architectures. https://uops.info/table.html https://uops.info/table.html will show how many uOps a given x86 instruction decomposes to, what ports it uses, and rough latency estimates for the instruction's execution. Here's some reading I found, with a lot of references: * A discussion of various modern division implementations: https://stackoverflow.com/questions/71420116/why-is-there-only-little-difference-in-integer-division-throughput-with-larger-v https://stackoverflow.com/questions/71420116/why-is-there-on... * Performance comparison of integer division in modern architecutures with some implementation speculation: https://news.ycombinator.com/item?id=27133804 https://news.ycombinator.com/item?id=27133804 * An in-depth look at the division unit in mid-old Intel CPUs (Penryn), look for "Radix-16" : https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=16afaef17dfbcf074abd76ebe05f4707ae758f57 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
- monocasa 3y ago
  Sort of. uOps don't have to come out of ucode. There's fixed function hardware that cracks most instructions into uOps and only falls back to ucode for particularly complex operations.
- rep_lodsb 3y ago
  >almost everything on a modern CPU uses "microcode" of some kind, although the term gets kind of hazy µOps are different from the kind of microcode described here. Older x86 CPUs basically had a "bytecode interpreter" in microcode ROM, every instruction (except for some trivial set/clear flag operations) would go to a specific entry point, and even something simple like addition would take at least two µ-instrs. The 80486 was the first generation that could decode some opcodes directly into one-cycle µOps. edit The term "interpreter" is of course a simplified description. The decoding itself is done outside of microcode, and there is logic to select different registers or ALU operations etc. But conceptually it's similar in that almost every opcode transfers control to some sequence of microinstructions ending in "RNI", which acts like a jump back to the main interpreter loop. The 8086 is actually the closest to the "RISC-like microcode" meme, in that even address computation is done by a series of µ-instrs.
  - bri3d 3y ago
    Edit: just saw your edit, that's something I'd never really thought about before - 8086 is the "purest" microcoded processor from the x86 series, in that every instruction runs through an actual interpreter rather than some form of fixed-function instruction issue unit! In the case of integer division, I think that it's also the "true" kind of microcoded instruction on many modern CPUs. That is to say, the instruction goes through the actual microcode interpreter to issue the uOps, rather than the fixed function decoder. Although, it's been awhile since I had to worry about microcode switches, and it looks like maybe this isn't true anymore in the very newest microarchitectures? I think this is for two reasons: so that the microcode can switch between "fast" and "slow" division and issue a different uOp program for fast division, and because most division is longer than the fixed-function decoder width (I think on Intel it used to be anything longer than 4 uOps?). Anyway, I figured this was probably a bit more detail than what OP needed for their question about division algorithms, so here are my takeaways: * Yes, integer division is implemented as multiple operations on many modern CPUs, although it is increasingly moving towards hardware (fewer uOps). * Sometimes the micro-instruction programs for division are encoded in a fixed operation decoder and sometimes they are themselves generated by microcode. * But, at the same time no, division is not implemented algorithmically using purely non-division functions, there is usually some fixed-function division logic of various types. * This is a hot topic so change is rapid.

The 80186 already implemented the loop for multiplication and (unsigned) division in dedicated logic that could do 1 bit per cycle. The microcode only had to set up the registers, test for overflow, and undo the final subtraction if it underflowed (since it now used a non-restoring algorithm). Starting with the 486 there is likely no longer any microcode involved, and newer chips can handle multiple bits per step. See end of article, the first algorithm to do this comes from 1957!

bri3d 3y ago

It's way more complex than this on modern CPUs, so it's harder to explain. > is microcode still used for division? Yes, almost everything on a modern CPU uses "microcode" of some kind, although the term gets kind of hazy, since everything is out-of-order and a lot of instructions are issued in parallel. In a typical modern CPU, the "frontend" will decompose instructions into uOps, which then get pushed into a "reservation station" / "scheduler." The scheduler queues and reorders various uOps in various surprising and complicated ways to try to account for interdependencies and memory latency. Eventually, a uOp is issued into to an "execution port," which is connected to a fixed-function piece of logic that actually performs part or all of an operation (for example, an Arithmetic Unit / ALU). But, while microcode will be _involved_ still, most modern CPUs will have fixed-function hardware for the meaty parts of the division instruction - they generally speaking won't implement division _purely_ using microcode like the algorithm documented in the article. > are there better and faster alternatives? They're not "alternatives" per se, but there are a _lot_ of ways to implement division algorithmically, and a _lot_ of ways to trade size for speed. Improving integer division performance has been a fairly big focus in newer CPU microarchitectures, with major improvements arriving in the latest Intel, AMD, and Apple Silicon architectures. https://uops.info/table.html https://uops.info/table.html will show how many uOps a given x86 instruction decomposes to, what ports it uses, and rough latency estimates for the instruction's execution. Here's some reading I found, with a lot of references: * A discussion of various modern division implementations: https://stackoverflow.com/questions/71420116/why-is-there-only-little-difference-in-integer-division-throughput-with-larger-v https://stackoverflow.com/questions/71420116/why-is-there-on... * Performance comparison of integer division in modern architecutures with some implementation speculation: https://news.ycombinator.com/item?id=27133804 https://news.ycombinator.com/item?id=27133804 * An in-depth look at the division unit in mid-old Intel CPUs (Penryn), look for "Radix-16" : https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=16afaef17dfbcf074abd76ebe05f4707ae758f57 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

monocasa 3y ago
Sort of. uOps don't have to come out of ucode. There's fixed function hardware that cracks most instructions into uOps and only falls back to ucode for particularly complex operations.
rep_lodsb 3y ago
>almost everything on a modern CPU uses "microcode" of some kind, although the term gets kind of hazy µOps are different from the kind of microcode described here. Older x86 CPUs basically had a "bytecode interpreter" in microcode ROM, every instruction (except for some trivial set/clear flag operations) would go to a specific entry point, and even something simple like addition would take at least two µ-instrs. The 80486 was the first generation that could decode some opcodes directly into one-cycle µOps. edit The term "interpreter" is of course a simplified description. The decoding itself is done outside of microcode, and there is logic to select different registers or ALU operations etc. But conceptually it's similar in that almost every opcode transfers control to some sequence of microinstructions ending in "RNI", which acts like a jump back to the main interpreter loop. The 8086 is actually the closest to the "RISC-like microcode" meme, in that even address computation is done by a series of µ-instrs.
- bri3d 3y ago
  Edit: just saw your edit, that's something I'd never really thought about before - 8086 is the "purest" microcoded processor from the x86 series, in that every instruction runs through an actual interpreter rather than some form of fixed-function instruction issue unit! In the case of integer division, I think that it's also the "true" kind of microcoded instruction on many modern CPUs. That is to say, the instruction goes through the actual microcode interpreter to issue the uOps, rather than the fixed function decoder. Although, it's been awhile since I had to worry about microcode switches, and it looks like maybe this isn't true anymore in the very newest microarchitectures? I think this is for two reasons: so that the microcode can switch between "fast" and "slow" division and issue a different uOp program for fast division, and because most division is longer than the fixed-function decoder width (I think on Intel it used to be anything longer than 4 uOps?). Anyway, I figured this was probably a bit more detail than what OP needed for their question about division algorithms, so here are my takeaways: * Yes, integer division is implemented as multiple operations on many modern CPUs, although it is increasingly moving towards hardware (fewer uOps). * Sometimes the micro-instruction programs for division are encoded in a fixed operation decoder and sometimes they are themselves generated by microcode. * But, at the same time no, division is not implemented algorithmically using purely non-division functions, there is usually some fixed-function division logic of various types. * This is a hot topic so change is rapid.