Comment by kragen
19 hours ago
Hmm, I thought you explained the FDIV bug was (in part) because the Boron† used carry-save adders to generate quotient digits? I don't see how you'd combine carry-save adders and Kogge–Stone carry lookahead. This post does mention the carry-save adder and link the other post, but doesn't explain the relationship between the two adders (are they the same in some galaxy-brain way I can't imagine? does one of them feed the other?)
______
The short answer is that a large carry-save adder feeds into this 8-bit carry-lookahead adder to generate the table index for division. In more detail, the division algorithm uses a ≈64-bit carry-save adder to hold the partial remainder during a division. The problem is that a carry-save adder holds the result in two pieces, the sum bits and the carry bits, which is what makes it fast. However, the division algorithm needs to use the top 7 bits as an index into the infamous division table, but this won't work if the value is in two pieces. The solution is to add the two pieces together using the carry-lookahead adder and then you have the table index.
The obvious question is why didn't they just use a carry-lookahead adder in the first place? The answer is that a carry-lookahead adder works better for smaller words (e.g. 8 bits), since its size is O(N^2) or O(N log N), depending on how you implement it. So you're better off with a large carry-save adder and a small carry-lookahead adder.
I see. I guess I had the impression that the carry and sum bits had been used directly to index the table, which is of course a thing you can do; it's just that 7 bits in the carry-save adder is the equivalent of ≈3 bits.