Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-03-12
1999-11-23
Homere, Jean R.
Data processing: database and file management or data structures
Database design
Data structure types
707 3, 707100, 395731, 39580009, 39580028, G06F 1563
Patent
active
059917644
ABSTRACT:
A data structure supporting a data-parallel reduction operation performed by a group of threads, a rope, participating in a multi-level two-phase tree structure: a fan-in computation phase followed by a fan-out broadcast phase. Local reductions are performed at each subtree during the fan-in phase, and the final reduced value is broadcast to all the threads during the fan-out phase. As the reduction operation is a data-parallel operation, the reduction operation is rope specific and is provided by the use of a parallel computation skeleton defined by the data structure which is a fan-in followed by the fan-out, a data-type specific binary operation, and a final broadcast that takes place in the reduction operation. When the rope object is constructed, the parallel computation skeleton is automatically constructed from information contained in the data structure. When a reduction operation is invoked, this parallel computation skeleton is used to build a data-type specific reduction object which is used by all the threads in the rope. The threads in a rope may perform type-specific reduction operations by cloning this parallel computation skeleton to a data-type specific reduction object for that type. This data-type specific reduction object is an instance of a template instance which is parametrized on two data-types: a data-type of the values used in the reduction operation and a type of a binary operation function object.
REFERENCES:
patent: 4344134 (1982-08-01), Barnes
patent: 4347498 (1982-08-01), Lee et al.
patent: 4843540 (1989-06-01), Stolfo
patent: 4845744 (1989-07-01), Debenedictis
patent: 4860201 (1989-08-01), Stolfo et al.
patent: 5230047 (1993-07-01), Frey, Jr. et al.
patent: 5404521 (1995-04-01), Murray
patent: 5535393 (1996-07-01), Reeve et al.
patent: 5721921 (1998-02-01), Kessler et al.
patent: 5764993 (1998-06-01), Shindo
patent: 5781906 (1998-07-01), Aggarwal et al.
Olson, "Connectionist Networks for Feature Indexing and Object Recognition", IEEE, pp. 907-912, 1996.
Zang et al. "On the Parallel Complexity of Model Checking in the Modal Mu-Calculus", IEEE, pp. 154-163, 1994.
Halstead, Robert H., Jr. Multilisp: A Language for Concurrent Symbolic Computation. ACM Transactions on Programming Languages and Systems, vol. 7, No. 4, pp. 501-538, Oct. 1985.
Yokote, Yasuhiko. The Design and Implementation of Concurrent Smalltalk, World Scientific Series in Computer Science, vol. 21 1990.
Leddy, William J., and Smith, K. Stuart, The Design of the Experimental Systems Kernel. Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers and Applications, Monterey, CA, 1989, pp. 737-743.
Liskov, Barbara and Shrira, Liuba. Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems. Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implemetation, Atlanta, Georgia pp. 260-267, Jun. 1988.
Reppy, John H., Concurrent ML: Design, Application and Semantics, Concurrent ML Manual. AT&T Bell Laboratories, Feb. 1993, Version 0.9.8.
Grimshaw, Andrew S. Easy-to-use Object-Oriented Parallel Processing with Mentat. IEEE Computer, pp. 39-51, May 1993.
Lavender, R. Greg and Kafura, Dennis G., A Polymorphic Future and First-class Function Type for Concurrent Object-Oriented Programming, Sponsored in part by National Science Foundation grant CCR-9104013.
Callahan, David and Smith, Burton. A Future-based Parallel Language For a General-purpose Highly-parallel Computer. Tera Computer Company, 400 N. 34th Street, Suite 300, Seattle, WA 98103, ARPA Order No. 6512, Program Code No. E20 issued by DARPA/CMO under Contract # MDA972-89-C-0002 and Sponsored by the Defense Advanced Reseach Projects Agency Information Science and Technology Office.
Sheffler, Thomas J., The Amelia Vector Template Library, Parallel Programming Using C++, Scientific & Engineering Computation Series, 1996, pp. 43-89.
Homere Jean R.
International Business Machines - Corporation
Johnson Prentiss W.
LandOfFree
Data structure specifying differing fan-in tree and fan-out tree does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure specifying differing fan-in tree and fan-out tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure specifying differing fan-in tree and fan-out tree will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1234450