Method and compiler for parallel execution of a program

Patent 5852734 Issued on December 22, 1998. Estimated Expiration Date:

June 9, 2015. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

System and method for compiling a fine-grained array based source program onto a course-grained hardware
Patent #: 5274818
Issued on: 12/28/1993
Inventor: Vasilevsky, et al.

Loop optimization system
Patent #: 5303357
Issued on: 04/12/1994
Inventor: Inoue, et al.

Integrated register allocation, instruction scheduling, instruction reduction and loop unrolling
Patent #: 5367651
Issued on: 11/22/1994
Inventor: Smith, et al.

Compiler with delayed conditional branching
Patent #: 5450585
Issued on: 09/12/1995
Inventor: Johnson

Optimizer for program loops
Patent #: 5457799
Issued on: 10/10/1995
Inventor: Srivastava

Array variable transformation system employing subscript table mapping to scalar loop indices
Patent #: 5485619
Issued on: 01/16/1996
Inventor: Lai, et al.

Loop scheduler
Patent #: 5491823
Issued on: 02/13/1996
Inventor: Ruttenberg

Vectorization system for vectorizing loop containing condition induction variables Patent #: 5522074
Issued on: 05/28/1996
Inventor: Endo

Inventors

Application

No. 489196 filed on 06/09/1995

US Classes:

717/156, Using flow graph717/149For a parallel or multiprocessor system

Examiners

Primary: Voeltz, Emanuel T.
Assistant: Corcoran, III, Peter J.

Attorney, Agent or Firm

Gonzalez; Floyd A.

Foreign Patent References

61-182161 JP 08/13/1986
04-184540 JP 07/13/1992
05-158895 JP 06/13/1993

International Class

G06F 009/45

Foreign Application Priority Data

1994-07-06 JP

Abstract

To increase the speed of program execution by decomposing a loop onto a plurality of processors and executing them in parallel. First, a loop in a source program is located which is to be executed in parallel. This loop is then analyzed for data dependence. The result of the analysis is used for calculating data dependence vectors. Then all areas of the index executed in the loop are decomposed and assigned to a number of processors. Further, it is determined whether data needs to be transferred between processors. Based on the array index space, communication vectors are calculated. Data dependence vectors and communication vectors are ANDed to calculate communication dependence vectors. Then, the manner of communication of operands and loop execution are determined based on the values of communication dependence vectors.

Other References

Mercer, R., "The Convex Fortran 5.0 Compiler," IEEE, ICS '88, vol. 2, pp 164-175, May 20, 1988
Hiranandani et al., "Compiling Fortran D for MIMD distributed-memory machines," Comm. of ACM, v35, n8, p. 66(15), Aug. 1992
Choudhary et al., "Compiling Fortran 77D and 90D for MIMD distributed-memory machines," IEEE, 4th Symp. on the Fronts. of Mass. Para. Comp., pp. 4-11, Oct. 21, 1992
Ramanujam et al., "Tiling multidimensional iteration spaces for multicomputers," IEEE, Jour. of Para. and Dist. Comp., vol. 16, No. 2, pp. 108-120, Oct. 1992
Hiranandani et al., "Preliminary experiences with Fortran D compiler," IEEE, Supercomputing '93, pp. 338-350, Nov. 19, 1993
Kennedy et al., "Context optimization for SIMD execution," IEEE, Proc. of the Scale. HP Comp. Conf., pp. 445-453, May 25, 1994
Choudhary et al., "Compiling Fortran 77D and 90D for MIMD Distributed-Memory Machines," IEEE Comp. Soc. Press, Los Alamitos, CA, pp. 4-11, Oct. 19, 1992
Kennedy et al., "Context Optimization for SIMD Execution," IEEE Comp. Soc. Press, Los Alamitos, CA, pp. 445-453, May 23, 1994
IEEE Transactions on Parallel and Distributed Systems, vol. 2, No. 4, Oct. 1991 A Loop Transformation Theory and an Algorithm to Maximize Parellelism