Another detail about why a Kogge-Stone CLA is used on sillicon is due to fan-out, where the number of gates connected to an output should be minimized.
I have always thought of the patterns represented in parallel prefix addition in regards to minimizing fan-out to be a very interesting and generally applicable pattern in computing.
Strangely, the original paper by Kogge and Stone had nothing to do with addition and carries. Their 1973 paper was titled, “A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations.” It described how to solve recurrence problems on parallel computers, in particular the massively parallel ILLIAC IV. As far as I can tell, it wasn’t until 1987 that their algorithm was applied to carry lookahead, in Fast Area-Efficient VLSI Adders.
Another detail about why a Kogge-Stone CLA is used on sillicon is due to fan-out, where the number of gates connected to an output should be minimized.
I have always thought of the patterns represented in parallel prefix addition in regards to minimizing fan-out to be a very interesting and generally applicable pattern in computing.
Quoting the article, which even mentions:
Ken Shirriff used my diagrams! I nearly jumped out of my skin. I’m going to be on cloud nine for a month. :)
Thanks for making the diagram, Robey! Good thing I cited you on it :)