Cyclic segmented prefix circuits for mesh networks

Details Cyclic segmented prefix circuits for mesh networks Cyclic segmented prefix circuits for mesh networks

2011-04-26

2011-04-26

Ngo, Chuong D (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S710000

Reexamination Certificate

active

07933940

ABSTRACT:
Parallel prefix circuits for computing a cyclic segmented prefix operation with a mesh topology are disclosed. In one embodiment of the present invention, the elements (prefix nodes) of the mesh are arranged in row-major order. Values are accumulated toward the center of the mesh and partial results are propagated outward from the center of the mesh to complete the cyclic segmented prefix operation. This embodiment has been shown to be time-optimal. In another embodiment of the present invention, the prefix nodes are arranged such that the prefix node corresponding to the last element in the array is located at the center of the array. This alternative embodiment is not only time-optimal when accounting for wire-lengths (and therefore propagation delays), but it is also asympotically optimal in terms of minimizing the number of segmented prefix operators.

REFERENCES:
patent: 5333268 (1994-07-01), Douglas et al.
patent: 5999961 (1999-12-01), Manohar et al.
patent: 6038657 (2000-03-01), Favor et al.
patent: 6609189 (2003-08-01), Kuszmaul et al.
Blelloch, Guy E., “Scans as Primitive Parallel Operations,” IEEE Trans. on Computers C-38(11):1526-1538, Nov. 1989.
Blelloch, Guy E., “Prefix Sums and Their Applications,” Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, Nov. 1990.
Leiserson, Charles E. et al., “The Network Architecture of the Connection Machine CM-5,” J. of Parallel and Distributed Computing, 33(2):145-158, Mar. 1996.
E{hacek over (g)}ecio{hacek over (g)}lu, Ömer et al., “Optimal Parallel Prefix on Mesh Architectures,” Parallel Algorithms and Applications, I:191-209, 1993.
Henry, Dana S. et al., “Cyclic Segmented Prefix Circuits,” Ultrascalar Memo 1, Yale University, Nov. 1998.
Henry, Dana S. et al., “Circuits for Wide-Window Superscalar Processors,” In 27th International Symposium on Computer Architecture, pp. 236-247, Vancouver, British Columbia, Jun. 2000.
Henry, Dana S. et al., “The Ultrascalar Processor—An Asymptotically Scalable Superscalar Microarchitecture,” In 20th Anniversary Conference on Advanced Research in VLSI, pp. 256-273, Atlanta, GA, Mar. 1999.
Ladner, Richard E., “Parallel Prefix Computation,” J. of the ACM, 27(4):831-838, Oct. 1980.
Pippenger, Nicholas, “The Complexity of Computations by Networks,” IBM J. of Research and Development, 31(2):235-243, Mar. 1987.
Cormen, Thomas H. et al., “Introduction to Algorithms,” MIT Press, 1990, p. 726, Exercise 30-1.
Leighton, F. Thomas. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann 1992, pp. 37-44.

Affiliated with

Also associated with

Rating

Cyclic segmented prefix circuits for mesh networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cyclic segmented prefix circuits for mesh networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cyclic segmented prefix circuits for mesh networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2718841