Patent
1997-03-12
1999-08-10
Hafiz, Tariq R.
G06F 945
Patent
active
059371943
ABSTRACT:
A data-parallel reduction operation is 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 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. 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 parameterized 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: 5404521 (1995-04-01), Murray
patent: 5519868 (1996-05-01), Allen et al.
patent: 5535393 (1996-07-01), Reeve et al.
patent: 5632035 (1997-05-01), Goodwin
patent: 5764993 (1998-06-01), Shindo et al.
patent: 5790861 (1998-08-01), Rose et al.
patent: 5828842 (1998-10-01), Sugauchi et al.
Halstead, Robert H., Jr. Multilisp: A Language for Concurrent Symbolic Computation. ACM Transactions on Programming Languages and Systems, 7(4):501-538, Oct. 1985.
Yokote, Yasuhiko. The Design and Implementation of Concurrent Smalltalk, World Scientific Series in Computer Science, vol. 21 1990.
Leddy, Bill and Smith, Kim. The Design of the Experimental Systems Kernel. Proceedings of the Fourth Conf. on Hypercubes, Concurrent Computers and Applications, Monterey, CA, 1989, pp. 737-743.
Liskov, Barbara and Shrira, Luiba. Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems. Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation, Atlanta, Georgia pp. 260-267, Jun. 1988.
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 Research 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.
Zhang, Shipei; Sokolsky, Oleg; Smolka, Scott A.; On the Parallel Complexity of Model Checking in the Modal Mu-Calculus, Proceedings of the 1994 IEEE 9.sup.th Annual Symposium on Logic in Computer Science, pp. 154-164.
Clark F. Olson, Connectionist Networks for Feature Indexing and Object Recognition, Proceedings of the 1996 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 907-912.
Dauchet, et al., "Automata for reduction properties solving," Journal of Symbolic Computation, Academic Press, vol. 20, No. 2, ISSN: 0747-7171, pp. 215-233 (Abstract only), Aug. 1995.
Farrell, et al., "Load balanced optimisation of virtualised alogorithms for implementation on massively parallel SIMD architectures," PARLE '93 Parallel Archs. and Langs. Europe, 5th Int. PARLE Conf. Procs., ISBN: 3-540-56891-3, pp. 600-609 (abstract only), Jun. 17, 1993.
Kemp, R., "The reduction of binary trees by means of an input-restricted deque," Rairo Informatique Theorique, vol. 17, No. 3, ISSN: 0399-0540, pp. 249-284 (Abstract only), 1983.
Stevens, Al, "The Standard Template Library, Visual C+ + training, text-search wrap-up," Dr. Dobb's Journal, vol. 20, No. 4, pp. 115(7), Apr. 1995.
Corcoran, III Peter J.
Hafiz Tariq R.
International Business Machines - Corporation
Johnson Prentiss W.
LandOfFree
Method of, system for, and article of manufacture for providing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of, system for, and article of manufacture for providing , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of, system for, and article of manufacture for providing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1129046