0
\$\begingroup\$

At this link: http://en.wikibooks.org/wiki/Microprocessor_Design/Multiply_and_Divide_Blocks

It says that a wallace tree can be used to perform multiplication in a single cycle.

I'm assuming then that a technique like Booth's recoding takes multiple cycles for outputting a product?

By why exactly does a wallace tree only take one cycle to output a product?

I've read about the process on wikipedia: http://en.wikipedia.org/wiki/Wallace_tree, but I can't grasp the cycle argument.

Is wallace tree better/faster than other multiplication techniques?

\$\endgroup\$
0
\$\begingroup\$

A Wallace tree is basically a whole bunch of adders hooked up in series. If the inputs are entered by a clock edge (one cycle), no more clocks are needed until the complete output is read, so it only takes one cycle.

Of course, the cycle period must be long enough to allow the computations to propagate through the tree, and in the early days of microprocessors, adders were slow enough that a multiply operation could take several clock cycles. But the intermediate clocks were not applied to the multiplier, it was just a way of allowing the process to complete.

\$\endgroup\$
  • \$\begingroup\$ In the early days of microprocessors, this type of multiplication was not done at all. Instead, a sequential shift-and-add algorithm was used, requiring N clocks for an NxN multiply. \$\endgroup\$ – Dave Tweed Mar 1 '15 at 23:11
  • \$\begingroup\$ For certain values of early. \$\endgroup\$ – WhatRoughBeast Mar 2 '15 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.