Patent
1995-12-21
1998-08-04
Voeltz, Emanuel Todd
395709, G06F 945
Patent
active
057908591
ABSTRACT:
Privatization or identification of private variables in single-entry strongly connected regions or program loops by the use of dummy identity assignment statements. Dummy identity assignment statements, V=V, are inserted in the header block and postexit blocks of each single-entry strongly connected region for each variable V with a definition in the single-entry strongly connected region (SCR). USE functions of the dummy identity assignment statements are determined. The dummy definition of a variable in an SCR header block is used to test if there exists a loop-carried flow dependence on the variable in the SCR. Dummy definitions of the variable in postexit blocks of the SCR are used to test if the variable would require to be copied out on exit from the SCR. The dummy definition of the variable in header block of the SCR is used to test if only the last iteration value of the variable needs to be copied out. A variable is ascertained to be private if there is no loop carried dependence on the variable in the SCR, and either no copy out of the variable on exit from the SCR, or copy out of the variable on exit from the SCR and only the last iteration needs to be copied. The execution time and memory required for identifying private variables in single-entry strongly connected regions are substantially reduced. The execution time to determine if a variable is private in an SCR is at worst linearly proportional to the number of definitions and uses of the variable in a control flow graph.
REFERENCES:
patent: 4773007 (1988-09-01), Kanada et al.
patent: 5396627 (1995-03-01), Iitsuka
patent: 5448737 (1995-09-01), Burke et al.
patent: 5659754 (1997-08-01), Grove et al.
Sarkar, et al., "Automatic localization for distributed-memory multiprocessors using a shared-memory compilation framework," IEEE, Proc. of 27th Hawaii Int. Conf. on Sys. Sciences, vol. II: software tech., pp. 4-13, Jan. 7, 1994.
Optimizing Supercompilers for Supercomputers, Wolfe, M., p. 82, The MIT Press, Cambridge, 1989.
Automatic Generation of DAG Parallelism, Cytron, R.; Hind, M.; Hsieh, W., ACM, 1989.
Array Privatization for Parallel Execution of Loops, Li, Zhiyuan, 1992 International Conference on Supercomputing, 1992, pp. 313-322.
Data Dependence and Data Flow Analysis of Arrays, Maydan, D.; Amarsinghe, S.; Lam, M., Languages and Compilers for Parallel Computing, 5th International Workshop Proceedings, 1993, pp. 434-448.
Automatic Array Privatization, Tu, P.; Padua, D., Languages and Compilers for Parallel Computing 6th International Workshop Proceedings, 1994, pp. 500-521.
Flow Sensitive Interprocedural Analysis Method for Parallelization, Iitsuka, T., IFIP Transactions A, Computer Science and Technology, vol. A23, 1993, pp. 65-76.
Non Linear Array Dependence Analysis, Pugh, W.; Wonnacott, D., Languages, Compilers and Run Time Systems for Scalable Computers, 1995, pp. 1-14.
Corcoran, III Peter J.
International Business Machines - Corporation
Johnson Prentiss W.
Todd Voeltz Emanuel
LandOfFree
Method of, system for, and computer program product for efficien 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 computer program product for efficien, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of, system for, and computer program product for efficien will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1189577