Ken Shirriff's blog post details the surprisingly complex circuitry the Pentium CPU uses for multiplication by three. Instead of simply adding a number to itself twice (A + A + A), the Pentium employs a Booth recoding optimization followed by a Wallace tree of carry-save adders and a final carry-lookahead adder. This approach, while requiring more transistors, allows for faster multiplication compared to repeated addition, particularly with larger numbers. Shirriff reverse-engineered this process by analyzing die photos and tracing the logic gates involved, showcasing the intricate optimizations employed in seemingly simple arithmetic operations within the Pentium.
The blog post "The Pentium contains a complicated circuit to multiply by three" delves into the intricate hardware implementation of a seemingly simple arithmetic operation within the Intel Pentium processor. Rather than utilizing the straightforward approach of shifting and adding (equivalent to multiplying by two and adding the original number), the Pentium employs a significantly more complex arrangement of logic gates, specifically carry-save adders and Booth recoding, to achieve multiplication by three.
The author, Ken Shirriff, reverse-engineered this circuitry through meticulous analysis of die photos of the Pentium processor, coupled with simulations using a custom-developed logic simulator. This involved tracing the connections between individual transistors within the physical layout of the chip to reconstruct the logical functions performed by different sections of the multiplication circuit. The investigation focuses specifically on the partial product generation and summation stages related to multiplying by three within the broader integer multiplication unit.
The post details how the Pentium uses Booth recoding, a technique that simplifies multiplication by reducing the number of partial products that need to be generated and summed. In the case of multiplying by three, Booth recoding transforms the multiplication into a series of additions and subtractions that can be efficiently implemented in hardware. However, instead of directly implementing the recoded operation, the Pentium utilizes a pre-calculated set of "magic numbers" hardwired into the circuitry. These magic numbers, when combined using carry-save adders—which perform addition more rapidly than traditional ripple-carry adders but produce a result in a redundant carry-save format—generate the desired multiple of three.
The author emphasizes the unexpected complexity of this multiplication-by-three circuit, noting that the numerous gates and carry-save adders involved are not intuitively associated with such a basic operation. This complexity is attributed to the Pentium's focus on maximizing performance. The employed architecture, although complex, allows for faster multiplication compared to simpler alternatives, contributing to the overall speed of the processor. The post meticulously explains each step of the multiplication process, from initial input to final output, illustrating the flow of data through the various components of the circuit. This includes detailed diagrams derived from the die photos, providing a visual representation of the hardware implementation. Ultimately, the post provides a fascinating low-level glimpse into the intricate design choices and performance optimizations implemented within a classic microprocessor.
Summary of Comments ( 62 )
https://news.ycombinator.com/item?id=43233143
Hacker News users discussed the complexity of the Pentium's multiply-by-three circuit, with several expressing surprise at its intricacy. Some questioned the necessity of such a specialized circuit, suggesting simpler alternatives like shifting and adding. Others highlighted the potential performance gains achieved by this dedicated hardware, especially in the context of the Pentium's era. A few commenters delved into the historical context of Booth's multiplication algorithm and its potential relation to the circuit's design. The discussion also touched on the challenges of reverse-engineering hardware and the insights gained from such endeavors. Some users appreciated the detailed analysis presented in the article, while others found the explanation lacking in certain aspects.
The Hacker News post titled "The Pentium contains a complicated circuit to multiply by three" generated a lively discussion with several insightful comments. Many commenters focused on the trade-offs between speed and gate count in early processor design.
One commenter pointed out the historical context, noting that in the era of the Pentium, saving even a single gate could mean substantial cost savings when multiplied across millions of chips. This reinforces the author's point about the lengths designers went to optimize for gate count, even if it resulted in complex logic for seemingly simple operations like multiplication by three.
Another commenter delved into the specifics of the "Booth recoding" technique mentioned in the article, explaining how it efficiently handles signed multiplication. They highlighted that while multiplying by three might appear simple, it becomes more complex when dealing with signed numbers represented in two's complement. Booth recoding, they argued, helps simplify the necessary logic and potentially reduce the overall gate count.
Several commenters discussed the practical implications of such optimizations, particularly in the context of performance-critical code. One pointed out that multiplication by small constants is a common operation in many algorithms. Optimizing these operations, even slightly, could lead to noticeable performance gains overall. They suggested that this kind of optimization was particularly relevant in the early days of computing when processor speeds were significantly lower than they are today.
The complexities of carry-save adders and Wallace trees were also discussed, with commenters explaining how these structures contribute to faster addition, which is a fundamental component of multiplication. One commenter explained how carry-save adders delay the handling of carry bits, allowing for faster addition of multiple numbers. Another commenter linked this back to the original article, suggesting that the Pentium's complex multiplication circuit likely incorporated these techniques to maximize performance.
Some commenters expressed a sense of admiration for the ingenuity of the engineers who designed these circuits. They acknowledged the difficulty of optimizing for both speed and gate count, especially given the limitations of the technology at the time.
Finally, a few commenters touched on the evolution of processor design, contrasting the optimizations used in the Pentium with modern approaches. They noted that with the increasing density and speed of transistors, the focus has shifted somewhat from minimizing gate count to optimizing for other factors like power consumption and thermal management. However, they also acknowledged that the fundamental principles of logic optimization remain relevant even today.