Patent
1997-03-12
1999-11-16
Donaghue, Larry D.
395705, 39580016, G06F 944
Patent
active
059872551
ABSTRACT:
A generic adaptor for converting from a sequential iterator to a parallel iterator is provided for the parallelization of sequential algorithms. The parallel algorithm implementation of a sequential algorithm is provided by the use of a template function with one template parameter in addition to those parameters of the corresponding sequential algorithm. This additional parameter is a strategy object which is an instance of a strategy class. In the body of the parallel algorithm, the strategy object is used to convert each sequential iterator to a plurality of per-thread parallel iterators. Each per-thread parallel iterator traverses those portions of a container for which the thread corresponding to this per-thread parallel iterator is responsible. When each thread has computed a partial result, the results are composed through a reduction operation if the partial results are an associative or commutative operation for a particular work distribution. A strategy class is conceptually an iterator adaptor which provides an operator that converts a sequential iterator to a plurality of per-thread parallel iterators. For instance, given two sequential iterators `first` and `last` corresponding to the beginning and end of a container sequence, a block strategy class may provide N pairs of per-thread parallel iterators, begin.sub.i and end.sub.i, such that each of the N threads may process one of N blocks of data between `first` and `last`. Similarly, a cyclic strategy class may provide N per-thread parallel iterators that hop over an iteration space of a container by lengths of N where N is the number of threads participating.
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: 5535393 (1996-07-01), Reeve et al.
patent: 5764993 (1998-06-01), Shirdo
Halstead, Robert H., Jr. Multilisp: A Language for Concurrent Symbolic Computation. ACM Transactions on Programming Languages and Systems, vol. 7, No. 4, pp. 501-508, 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 Implementation, 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 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.
Donaghue Larry D.
Follansbee John
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-1335594