Boots – shoes – and leggings
Patent
1995-02-27
1996-01-02
Black, Thomas G.
Boots, shoes, and leggings
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".
Harris Kevin W.
Noyce William B.
Black Thomas G.
Digital Equipment Corporation
Fisher Arthur W.
Maloney Denis G.
Von Buhr Maria N.
LandOfFree
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.
Profile ID: LFUS-PAI-O-244447