The team, working as Automatic Parallel Designs Ltd. (AutoPD) from a base in Oxford, England, claims to be able to offer up to a doubling of processor performance while saving die area and power just by redesigning the basic math circuitry in the line with its research. The company also claims to have a leading chip maker as a customer.

"The main thing is we have found is a new way of counting numbers," said Tony Curzon Price, chief executive officer and a cofounder of the company.

AutoPD is pursuing an intellectual property licensing business model and its claims hinge on the 3-bit input, 2-bit output "full adder" circuit which the Oxford-based company reckons to have generalized into a more extensible, scalable form. In multipliers, which require addition as an internal part of their operation, this can result in a doubling of speed, combined with a reduction in power consumption of around 50 percent, when compared with "conventional" designs, the company claims. These benchmarks are based on 0.13 micron process technology libraries from Artisan Components Inc. Curzon Price said.

As both addition and multiplication are fundamental to nearly all digital electronics operations the research team expects its work to be applied to microprocessors, digital signal processors, graphics processors and encryption engines.

Indeed, according to reports, AutoPD is already working on a floating point multiplier for "one of the largest CPU companies" and its algorithms are under evaluation at two other CPU companies. AutoPD is also said to be in negotiations with a "large FPGA company". Xilinx would be a leading candidate with its interest in embedding multiplier-accumulators in its FPGA matrix architecture under the XtremeDSP name.

Curzon Price, declined to give details of licensees already signed up or of any customer discussions in progress.

On its web site www.autopd.com the company states that it is undertaking silicon implementations with its first customers.

AutoPD was originally formed by mathematician Sunil Talwar and game theorist Curzon Price in 1998 to exploit U.K. university work on efficient state encoding. AutoPD produced and patented a new state machine encoding algorithm that it calls Karakoram, which they claimed doubled the performance of previous work.

Talwar and Curzon Price went to the Design Automation Conference in New Orleans in 1999 to talk with EDA companies, but the pair found people more interested in a by-product of their research; the potential for the speed-up and die area reduction of hardware multipliers. So they returned to England to refine their research in that area.

The bit-counting problem

The work centers on the circuit used to count the number of highs, or lows, in a bundle of wires. For three wires it is well-known to design engineers as the full-adder. It is a logically efficient circuit in that the two binary digits required to count up to three are computed in parallel. Neither result depends on the other.

Two full-adders can be combined to build a similarly efficient 4-to-2 "compressor". However, when it comes to counting more than 3 or 4 numbers, traditional solutions become inefficient, Curzon Price said.

"You can always concatenate full adders to get to higher orders but it's expensive. As soon as you concatenate you introduce delay," said Curzon Price.

"Our approach is to develop independent forumulae for each output of a generalized adder. It has the advantage of scaling and requires fewer logic levels than a traditional full adder approach." Curzon Price said the AutoPD solution tiles nicely so that chip layout can be accommodated easily.

"Counting the number of ones in a word is a well known problem," commented Steve Furber, professor of computer engineering at the University of Manchester in England. Furber declined to comment on AutoPD's particular solution but agreed that Wallace trees, a conventional approach to the bit-counting problem, do not map well into silicon and scale poorly.

Mary Jane Irwin, distinguished professor of computer science and engineering at Pennsylvania State University, said that work has been done on building counters out of blocks other than 3:2 full adders or 4:2 compressors and that, in any case, pipelining of stages can be used to deliver performance and that 4:2 compressors can fit neatly with pipelining.

"It appears to me that these guys need to do a little more digging into the literature and make sure, when they are doing their comparisons, that they are comparing to what people use these days. If they are comparing to old-style Wallace trees, that do have the deficiency they claim, then I'm not at all surprised with the 50% speed improvement."

Curzon Price argued that in terms of using other blocks the amount of published work was relatively scarce. AutoPD is aware of some IBM research and some Russian work both done in the 1970s, he said, but this work is hampered by problems with fan-out. And although pipelining multipliers can be used to improve performance it is associated with additional die area and power consumption, he argued.

"We have benchmarked against what seems to us to be the best 3:2 and 4:2 implementations today. Our tier-1 licensee, un-nameable but known for their semiconductor engineering prowess, could double the speed of their prior-art, DSP-style, un-pipelined design," concluded Curzon Price.

AutoPD received $2.5 million of finance from Quester, a venture capital firm, in March 2001 plus a further $550,000 from a group of investors. It remains to be seen whether AutoPD can add to, or multiply, those original investments.

Patents granted and applied for

U.S. patent number 6,367,054: "Method of generating finite state data for designing a cascade decomposed logic circuit"

U.S. patent application 2001/0044708: "Method and apparatus for binary encoding logic circuits"

U.S. patent application 2002/0026465: "Parallel counter and a multiplication logic circuit"