Parallel prefix networks that make tradeoffs between logic levels, fanout and wiring racks

1. A circuit that performs a prefix computation, comprising:

an N-bit prefix network comprised of prefix cells arranged into L+l logic levels, wherein N is greater than 8 and an integral power of two, and wherein L=log 2 N;

wherein the N-bit prefix network computes N outputs {Y N , . . . , Y 1 } from N inputs {X N , . . . , X 1 } using an associative two-input operator ∘◯, such that Y 1 =X 1 , Y 2 =X 2 ∘X 1 , Y 3 =X 3 ∘X 2 ∘X 1 , . . . , Y N =X N ∘X N−1 ∘ . . . ∘X 2 ∘X 1 ,

wherein each prefix cell has a fanout of at most 2 f +1; and

wherein there are at most 2 t horizontal wiring tracks between each logic level;

wherein l+f+t=L−1; and

wherein l>0,f>0, and t>0.

2. The circuit of claim 1 , wherein the N-bit prefix network functions as part of one of:

an adder;

a subtracter;

a magnitude comparator;

a priority encoder; and

a circuit that finds the first two ones in an N-bit input.

3. The circuit of claim 1 ,

wherein the N-bit prefix network functions as part of a 16-bit adder; and

wherein (l,f,t)=(1,1,1).

4. The circuit of claim 1 ,

wherein the N-bit prefix network functions as part of a 32-bit adder; and

wherein (l,f,t)=(2,1,1), (1,2,1) or (2,1,1).

5. The circuit of claim 1 ,

wherein the N-bit prefix network functions as part of a 64-bit adder; and

wherein (l,f,t)=(1,1,3), (1,2,2), (1,3,1), (2,1,2), (2,2,1) or (3,1,1).

6. The circuit of claim 1 ,

wherein the N-bit prefix network functions as part of a 128-bit adder; and

wherein (l,f,t)=(1,1,4), (1,2,3), (1,3,2), (1,4,1), (2,1,3), (2,2,2), (2,3,1), (3,1,2), (3,2,1) or (4,1,1).

7. The circuit of claim 1 , wherein precomputation operations are merged into the N-bit prefix network.

8. The circuit of claim 1 ,

wherein the N-bit (l,f,t) prefix network is formed from an M-bit (0,f,t) Knowles networks by adding l stages before and after the M-bit Knowles networks;

wherein N=2 l M; and

wherein the N-bit prefix network has 2l+logM stages.

9. The circuit of claim 1 , wherein logic levels in the N-bit prefix network include:

prefix cells that perform prefix operations; and

buffers that reduce loading for subsequent logic levels.

10. A circuit that performs a prefix computation, comprising:

an N-bit prefix network comprised of prefix cells arranged into L+l logic levels, wherein N is greater than 8 and an integral power of two, and wherein L=log 2 N;

wherein the N-bit prefix network computes N outputs {Y N , . . . , Y 1 } from N inputs {X N , . . . , X 1 } using an associative operator ∘◯, such that Y 1 =X 1 , Y 2 =X 2 ∘X 1 , Y 3 =X 3 ∘X 2 ∘X 1 , . . . , Y N =X N ∘X N−1 ∘ . . . ∘X 2 ∘X 1 ;

wherein each prefix cell has a valency v and a fanout of at most (v−1)v f +1; and

wherein there are at most (v−1)v t horizontal wiring tracks between each logic level;

wherein l+f+t=L−1; and

wherein l>0,f>0, and t>0.

11. The circuit of claim 10 , wherein the valency v of each prefix cell is one of 2, 3 and 4.

12. The circuit of claim 10 ,

wherein the valency v of each prefix cell is 3;

wherein the N-bit prefix network functions as part of an 81-bit adder; and

wherein (l,f,t)=(1,1,).

13. The circuit of claim 10 wherein the N-bit prefix network includes prefix cells with different valencies.

14. A computer system including a circuit that performs a prefix computation, comprising:

a processor;

a memory;

a functional unit within the processor;

an N-bit prefix network within the functional unit comprised of prefix cells arranged into L+l logic levels, wherein N is greater than 8 and an integral power of two, and wherein L=log 2 N;

wherein the N-bit prefix network computes N outputs {Y N , . . . , Y 1 } from N inputs {X N , . . . , X 1 } using an associative two-input operator ∘◯, such that Y 1 =X 1 , Y 2 =X 2 ∘X 1 , Y 3 =X 3 ∘X 2 ∘X 1 , . . . , Y N =X N ∘X N−1 ∘ . . . ∘X 2 ∘X 1 ;

wherein each prefix cell has a fanout of at most 2 f +1; and

wherein there are at most 2 t horizontal wiring tracks between each logic level;

wherein l+f+t=L−1; and

wherein l>0,f>0, and t>0.

15. The computer system of claim 14 , wherein the N-bit prefix network functions as part of one of:

an adder;

a subtracter;

a magnitude comparator;

a priority encoder; and

a circuit that finds the first two ones in an N-bit input.

16. The computer system of claim 14 ,

wherein the N-bit prefix network functions as part of a 16-bit adder; and wherein (l,f,t)=(1,1,1).

17. The computer system of claim 14 ,

wherein the N-bit prefix network functions as part of a 32-bit adder; and

wherein (l,f,t)=(2,1,1), (1,2,1) or (2,1,1).

18. The computer system of claim 14 ,

wherein the N-bit prefix network functions as part of a 64-bit adder; and

wherein (l,f,t)=(1,1,3), (1,2,2), (1,3,1), (2,1,2), (2,2,1) or (3,1,1).

19. The computer system of claim 14 ,

wherein the N-bit prefix network functions as part of a 128-bit adder; and

wherein (l,f,t)=(1,1,4), (1,2,3), (1,3,2), (1,4,1), (2,1,3), (2,2,2), (2,3,1), (3,1,2), (3,2,1) or (4,1,1).

20. The computer system of claim 14 , wherein precomputation operations are merged into the N-bit prefix network.

21. The computer system of claim 14 ,

wherein the N-bit (l,f,t) prefix-network is formed from an M-bit (0, f, t) Knowles network by adding l stages before and after the M-bit Knowles network;

wherein N=2 l M; and

wherein the N-bit prefix network has 2l+logM stages.

22. The computer system of claim 14 , wherein logic levels in the N-bit prefix network include:

prefix cells that perform prefix operations; and

buffers that reduce loading for subsequent logic levels.

23. A computer system including a circuit that performs a prefix computation, comprising:

a processor;

a memory;

an functional unit within the processor;

an N-bit prefix network within the functional unit comprised of prefix cells arranged into L+l logic levels, wherein N is greater than 8 and an integral power of two, and wherein L=log 2 N;

wherein the N-bit prefix network computes N outputs {Y N , . . . , Y 1 } from N inputs {X N , . . . , X 1 } using an associative operator ∘◯, such that Y 1 =X 1 , Y 2 =X 2 ∘X 1 , Y 3 =X 3 ∘X 2 ∘X 1 , . . . , Y N =X N ∘X N−1 ∘ . . . ∘X 2 ∘X 1 ;

wherein each prefix cell has a valency v and a fanout of at most (v−1)v f +1; and

wherein there are at most (v−1)v t horizontal wiring tracks between each logic level;

wherein l+f+t=L−1; and

wherein l>0,f>0, and t>0.

24. The computer system of claim 23 , wherein the valency v of each prefix cell is one of 2, 3 and 4.

25. The computer system of claim 23 ,

wherein the valency v of each prefix cell is 3;

wherein the N-bit prefix network functions as part of an 81-bit adder; and

wherein (l,f,t)=(1,1,1).

26. The computer system of claim 23 , wherein the N-bit prefix network includes prefix cells with different valencies.