Parallel multiplication hardware

Question

This picture is taken from Computer Organization and Design, Fourth Edition, David A. Patterson, John L. Hennessy. Sorry for the low resolution.

I cannot get my head around it. I can see why the bits to the right become lsb's in the product (Product1, Product0), but then the same thing is done for bits to the left. What about carries? Try this for Mcand and Mplier equal to 2^31. Then the correct Product63 is 0 (because the correct result is 2^62), but this design would set Product63 to 1, which is wrong!

Is there some deep mathematical property that could rescue this design, or am I correct to think that we need progressively wider adders to the left, as we go down the levels?

Elaboration

To facilitate readers, I remind how we do pencil-and-paper multiplication (4 bit example).

            M3 M2 M1 M0 (Mcand)
          * m3 m2 m1 m0 (Mplier)
-----------------------
            a3 a2 a1 a0 (Mplier0*Mcand)
+        b3 b2 b1 b0    (Mplier1*Mcand)
+     c3 c2 c1 c0       (Mplier2*Mcand)
+  d3 d2 d1 d0          (Mplier3*Mcand)
-----------------------
p7 p6 p5 p4 p3 p2 p1 p0 (Product)

Answer 1

You are correct, and the diagram is wrong. You definitely do need wider adders as you move down the tree as shown. Each of the results from the first tier of adders is 34 bits wide, those from the second tier are 36 bits wide, etc. Third tier sums are 40 bits, and fourth tier sums are 48 bits.

By the time you get to the last (fifth) tier, you're adding together a 48-bit number (the sum of the high-order partial products) and a 32-bit number (the shifted sum of the low-order partial products).

Note that you get 1 LSB of the final product before the first tier of adders, another one from their output, two more LSBs from the second tier, and so forth. By the time you get to the input of the fifth tier, you already have 16 LSBs of the result, and the final adder gives you the remaining 48 bits.

While it is tempting at first glance to pull off MSBs in a similar manner, it is always possible to construct an example in which a carry in the final adder needs to propogate all the way to the MSB of the result.

Side note: I have a book Computer Architecture: A Quantitative Approach, 2nd edition, published in 1996 by the same two authors. I'm wondering whether my book is a predecessor of yours, or a completely different effort. It does not have the figure you show in your question in it.