Maker Pro
Maker Pro

Basic vs. High Speed Wallace Tree

L

logjam

Jan 1, 1970
0
Yeah, I know this part probably hasn't been sold in the past 15 years,
but I can't figure out the data sheet.

The 74S275 Wallace tree has 2 versions. The high speed and basic. In
the high speed version, both C2n inputs are grounded and the carry bit
is passed through 2n+0 to an external adder. I don't understand why
this makes it "high speed" since there is supposed to be an adder
already inside the 275. Is it a "high speed" version because the built
in adders are junk? Or because the built in adders have to pass through
gated buffers?
 
J

Jonathan Kirwan

Jan 1, 1970
0
Yeah, I know this part probably hasn't been sold in the past 15 years,
but I can't figure out the data sheet.

The 74S275 Wallace tree has 2 versions. The high speed and basic. In
the high speed version, both C2n inputs are grounded and the carry bit
is passed through 2n+0 to an external adder. I don't understand why
this makes it "high speed" since there is supposed to be an adder
already inside the 275. Is it a "high speed" version because the built
in adders are junk? Or because the built in adders have to pass through
gated buffers?

I haven't been able to find the data sheet on the '275. I have some
older data books (1988), but obviously not old enough. I may be able
to find my 1970's, nicely bound TI version... but it's probably in
boxes somewhere.

In any case, it turns out that:

C.S. Wallace, "A Suggestion for A Fast Multiplier," IEEE Transactions
on Elec. Computers, vol. EC-13, pp. 14-17, (Jan or Feb) 1964.

and,

Y. Ofman, "On the algorithmic complexity of discrete functions," Sov.
Phys. Dokl. 7.7, pp. 589-591, 1963.

Spring to the fore on the subject.

Try a google search using:
wallace "A suggestion for a fast multiplier" filetype:pdf

Some hits are:
http://www.iccd-conference.org/proceedings/1998/90990122.pdf
http://www.ceet.niu.edu/faculty/reza/articles/iscas2002.pdf
http://www.ece.ucsb.edu/Faculty/Parhami/pubs_folder/parh99-asilo-opt-depth-circ.pdf
http://wwwmaths.anu.edu.au/~brent/pd/rpb055.pdf

You might like this one:
http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1288.pdf

Jon
 
J

Jonathan Kirwan

Jan 1, 1970
0
Y. Ofman, "On the algorithmic complexity of discrete functions," Sov.
Phys. Dokl. 7.7, pp. 589-591, 1963.

Or maybe that is:

Y. Ofman, "On the Algorithmic Complexity of Discrete Functions," Dokl.
Akad. Nauk SSSR 145:48–51, 1962.

Something like those, anyway. I haven't read it, of course. My wife
knows a little Russian, but I know absolutely none. Just German.

Jon
 
L

logjam

Jan 1, 1970
0
Here is a link to the datasheet from 1975:
http://www.tech-systems-labs.com/booksdata/TI-DATA-1976.pdf

Take a look at page 7-395

I'll take a look at a few of those links. I think the difference
between high speed and standard wallace tree isn't that the wallace
tree itself is slow but that since the 275 is 3 state using buffers it
might make carry propagation slightly slower. The high speed tree is
56ns and low speed 90ns, so I just can't understand how the buffers
could slow it down that much (unless the 1bit adders in the 275 are
junk).


Since the 486 requires 13-42 cycles to unsigned multiply mem32, at
50MHz my 5MHz TTL computer might actually be faster ant the 486. :)
BUT, my NOP and MULU take the same amount of time. So the 486 50MHz
gets 50 MIPS NOPping. :)
 
Top