Electrical computers and digital processing systems: processing – Processing architecture – Distributed processing system
Patent
1998-06-30
2000-07-11
Coleman, Eric
Electrical computers and digital processing systems: processing
Processing architecture
Distributed processing system
712 36, 345423, G06F 944
Patent
active
060885114
ABSTRACT:
A nested parallel implementation of 2D triangulation method recursively sub-divides processors of a parallel computer into asynchronous processor teams. Each of the teams uses data parallel operations to compute a partitioning of the collection of points distributed to it. When each team has a single processor as a result of the recursive partitioning steps, the processors switch to a serial version of the 2D triangulation method. The nested parallel implementation has two levels of recursion: 1) one to partition a collection of points into two new sets; and 2) a second layer nested in the first to compute convex hulls used to form a border around the two new sets of points. In each layer of recursion the implementation sub-divides processors into teams and assigns a control parallel function to each team. Within each team, the processors perform data parallel operations on the collection of points distributed to the processors in the team.
REFERENCES:
patent: 5448686 (1995-09-01), Borrel
patent: 5535393 (1996-07-01), Reeve
patent: 5586326 (1996-12-01), Ryu
patent: 5706415 (1998-01-01), Kelley
patent: 5943663 (1999-08-01), Mouradian
Jonathan C. Hardwick, "An Efficient Implementation of Nested Data Parallelism for Irregular Divide-and-Conquer Algorithms," First International Workshop on High-Level Programming Models and Supportive Environments, Apr. 1996.
Guy E. Blelloch, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha, and Siddhartha Chatterjee, "Implementation of a Portable Nested Data-Parallel Language," Journal of Parallel and Distributed Computing, vol. 21, pp. 4-14, 1994.
Stephen T. Barnard, "PMRSB: Parallel Multilevel Recursive Spectral Bisection," Proceedings of Supercomputing, 1995.
Eugene D. Brooks III, "PCP: A Paradigm Which Spans Uniprocessor, SMP and MPP Architectures," SC '95 Poster Presentation, Jun. 14, 1995.
Soumen Chakrabarti, James Demmel, Katherine Yelick, "Modeling the Benefits of Mixed Data and Task Parallelism," In Proceedings of the 7.sup.th Annual ACM Symposium on Parallel Algorithms and Architectures, Jul., 1995.
Tom Axford, "The Divide-and-Conquer Paradigm as a Basis for Parallel Language Design," Advances in Parallel Algorithms, Blackwell, 1992.
Thomas J. Sheffler and Siddhartha Chatterjee, "An Object-Oriented Approach to Nested Data Parallelism," In Proceedings of the 5.sup.th Symposium on the Frontiers of Massively Parallel Computation, IEEE, Feb., 1995.
Daniel W. Palmer, Jan. F Prins and Stephen Westfold, "Work-Efficient Nested Data-Parallelism," In Proceedings of the 5.sup.th Symposium on the Frontiers of Massively Parallel Computation, IEEE, pp. 186-193, Feb., 1995.
Manuel M.T. Chakravarty, Friedrich Wilhelm Schroer, Martin Simons, "V-Nested Parallelism in C," In Proceedings of the Working Conference on Massively Parallel Programming Models, IEEE, Computer Society Press, 1995.
Jay Sipelstein, "Data Representation Optimizations for Collection-Oriented Languages," Ph.D. Thesis Proposal, Ver. 1.0, for School of Computer Science, Carnegie Mellon University,, May 12, 1992.
Jonathan Richard Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator," In First Workshop on Applied Computational Geometry, pp. 124-133, ACM, May, 1996.
Guy E. Blelloch, Gary L. Miller, Dafna Talmor, Developing a Practical Projection-Based Parallel Delaunay Algorithm, In Proceedings of the 12.sup.th Annual Symposium on Computational Geometry, ACM, May, 1996.
Timothy M.Y. Chan, Jack Snoeyink, Chee-Keng Yong, "Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three," In Proceedings of the 6.sup.th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 282-291, 1995.
Coleman Eric
Microsoft Corporation
LandOfFree
Nested parallel 2D Delaunay triangulation method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Nested parallel 2D Delaunay triangulation method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nested parallel 2D Delaunay triangulation method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-550454