System and method for controlling execution of nested loops in p

Boots – shoes – and leggings

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

3642804, 3642805, 364DIG1, G06F 945

Patent

active

054817234

ABSTRACT:
A system and method for controlling execution of nested loops in parallel in a computer including multiple processors, and a compiler for generating code therefor. The code enables the computer to operate in the following manner. Each processor processes an iteration of an outer loop in a set of nested loops. If the outer loop contains more iterations than processors in the system, the processors are initially assigned early iterations, and the later iterations are assigned to the processors as they finish their earlier iterations, until the processors have processed all of the iterations. Each processor, during processing of an outer loop iteration runs the iterations comprising the inner loop serially. In order to enforce dependencies between the loops, each processor reports its progress in its iterations of the inner loop to the processor executing the succeeding outer loop iteration. In addition, each processor, before processing the inner loop iterations of an assigned outer loop iteration, determines whether the processor computing the preceding outer loop is ahead or behind in processing its inner loop iteration by an amount which guarantees that dependencies will be enforced.

REFERENCES:
patent: 4468736 (1984-08-01), De Santis et al.
patent: 4710872 (1987-12-01), Scarborough
patent: 4794521 (1988-12-01), Ziegler et al.
patent: 4829427 (1989-05-01), Green
patent: 4833606 (1989-05-01), Iwasawa et al.
patent: 5093916 (1992-03-01), Karp et al.
S. Midkiff, et al., "Compiler Algorithms for Synchronization," I.E.E.E. Transactions on Computers, vol. 3-36, No. 12 (Dec., 1987), pp. 1485-1495.
L. Lamport, "The Parallel Execution of Do Loops," Comm. ACM vol. 17, No. 2 (Feb. 1974), pp. 83-93.
D. Callahan, A Global Approach to Detection of Parrallelism (1987) Ph. D. Thesis, Rice University (Rice COMP TR87-50, 9 Apr. 1987).
D. Reed, et al., "Synchronization With Eventcounts and Sequencers", Comm. ACM, vol. 22, No. 2 (Feb. 1979), pp. 115-123.
J. Gazdag & H.-H. Wang, Concurrent computing by sequential staging of tasks, IBM Systems Journal, vol. 28, No. 4, 1989, pp. 646-660.
Proceedings of the 1986 International Conference on Parallel Processing, 19th -22 Aug. 1986, pp. 544-551, IEEE, New York, US; S. P. Midkiff et al: "Compiler Generated Synchronization for DO Loops".

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

System and method for controlling execution of nested loops in p does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for controlling execution of nested loops in p, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for controlling execution of nested loops in p will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-244447

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.