Patent
1997-06-24
2000-05-02
MacDonald, Allen R.
395706, 395708, G06F 945
Patent
active
060582669
ABSTRACT:
An integer programming formulation for weighted loop fusion is presented. Loop fusion is a well-known program transformation that has shown to be effective in reducing loop overhead and improving register and cache locality. Weighted loop fusion is the problem of finding a legal partition of loop nests into fusible clusters so as to minimize the total inter-cluster edge weights. Past work has shown that the weighted loop fusion problem is NP-hard. Despite the NP-hardness property, the present invention provides optimal solutions that may be found efficiently, in the context of an optimizing compiler, for weighted loop fusion problem sizes that occur in practice. An integer programming formulation for weighted loop fusion with a problem size (number of variables and constraints) that is linearly proportional to the size of the input weighted loop fusion problem is also presented. The integer programming formulation may be solved efficiently using a general integer programming package. Alternatively, a custom branch-and-bound procedure for the integer programming formulation is presented that is more efficient than the procedures used in general integer programming.
REFERENCES:
patent: 5822593 (1998-10-01), Lamping et al.
Ju et al., "The classification, fusion and parallelization of array language primitives", IEEE Trans. on Parallel and Distributed Systems, vol. 5, Issue 10, pp. 1113-1120, Oct. 1994.
Choudhary et al., "Compiling Fortran 77D and 90D for MIMD Distributed-Memory Machines", Fourth Symp. on ITN Frontiers of Massively Parallel Computation, 1992, pp. 4-11, Oct. 1992.
Manjikian et al., "Fusion of Loops for Parallelism and Locality", IEEE Trans. On Parallel and Distributed Systems, vol. 8 No. 2 pp. 193-209, Feb. 1997.
Sha et al., "Polynomial-time Nested Loop Fusion with Full Parallelism", International Conf. on Parallel Processing, IEEE, pp. 9-16, 1996.
Megiddo et al., "Optimal Weighted Loop Fusion for Parallel Programs", Proc. of ACM Symp. On Parallel Algorithms and Architectures, pp. 282-291, 1997.
Allen, J.R., Dependence Analysis for Subscripted Variables And Its Application to Program Transformation, PhD Thesis, Rice University, Houston, TX 1983.
Allen, R.; Kennedy, K., Automatic Translation of FORTRAN Programs to Vector Form, ACM Transactions on Programming Languages and Systems, vol. 9, No. 4 (Oct. 1987), pp. 491-542.
Banerjee, U., Dependence Analysis for Supercomputing. Kluwer Academic Publishers, Boston, MA, 1988. Pp. 1-152.
Callahan, D., A Global Approach to Detection of Parallelism. PhD Thesis, Rice University, Apr. 1983. Rice COMP TR87-50.
Chow, J-H.; Lyon, L.; Sarkar, V., Automatic Parallelization for Symmetric Shared-Memory Multiprocessors, CASCON 96 Conference, Nov. 1996, pp. 76-89.
Ferrante, J.; Ottenstein, K.J.; Warren, J.D., The Program Dependence Graph and its Use in Optimization, ACM Transactions on Programming Languages and Systems, vol. 9, No. 3 (Jul. 1987), pp. 319-349.
Ferrante, J.; Sarkar, V.; Thrash, W., On Estimating and Enhancing Cache Effectiveness, Lecture Notes in Computer Science, (589):328-343, 1991. Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, Santa Clara, California, USA, (Aug. 1991), pp. 328-343.
Gao, G.R.; Olsen, R.; Sarkar, V.; Thekkath, R., Collective Loop Fusion For Array Contraction, Springer-Verlag Lecture Notes in Computer Science, 757. Proceedings of the Fifth Workshop on Languages and Compilers for Parallel Computing, Yale University, Aug. 1992, pp. 281-294.
Goldberg, A.; Paige, R. Stream Processing, 1984 ACM Symposium on Lisp and Functional Programming, Austin, TX. (Aug. 1984), pp. 53-62.
IBM Optimization Subroutine Library (OSL) User Guide and Reference, Version 1, Release 2.1. International Business Machines, Feb. 1995. Pub. No. SC23-0519-04. (also see http://www.research.ibm.com/osl/osl).
Irigoin, F.; Triolet, R.; Supernode Partitioning, Conference Record of Fifteenth ACM Symposium on Principles of Programming Languages, 1988, pp. 319-329.
Kennedy, K., McKinley, K.S., Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Springer-Verlag Lecture Notes in Computer Science, 768. Proceedings of the Sixth Workshop on Languages and Compilers for Parallel Computing, Portland, Oregon, Aug. 1993, pp. 301-320.
Kennedy, K.; McKinley, K.S., Typed Fusion with Applications to Parallel and Sequential Code Generation, Technical Report, Department of Computer Science, Rice University, 1993.
Metcalfe, M.; Reid J., Fortran 90 Explained, Oxford Science Publishers, 1990, pp. 66-71, 105-123, 173.
Nemhauser, G.L.; Wolsey L.A., Integer and Combinatorial Optimization, Wiley Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, 1988, pp. 3-5, 205-258.
Sarkar, V., Determining Average Program Execution Times and Their Variance, Proceedings of the 1989 SIGPLAN Conference on Programming Language Design and Implementation, vol.24 No.7 (Jul. 1989), pp. 298-312.
Sarkar, V., Partitioning and Scheduling Parallel Programs for Multiprocessors, Research Monographs in Parallel and Distributed Computing, Pitman Publishing, London and The MIT Press, Cambridge, Massachusetts, 1989.
Sarkar, V., Automatic Partitioning of a Program Dependence Graph into Parallel Tasks, IBM Journal Of Research and Development, vol. 35, No.5/6 (Sep./Nov. 1991), pp. 779-804.
Sarkar, V., Automatic Selection of High Order Transformations in the IBM XL Fortran Compilers, IBM Journal of Research and Development, vol.41, No.3 (May 1997), pp. 263-264.
Sarkar, V.; Thekkath, R., A General Framework for Iteration-Reordering Loop Transformation, Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, Jun. 1992, pp. 175-187.
Gupta, M.; Midkiff, S.; Schonberg, E.; Seshadri, V.; Shields, D.; Wang, K-Y.; Ching, W-M.; Ngo, T., Improving the Performance of HPF Compilers Proceedings of the Fifth Workshop on Compilers for Parallel Computers (CPC'95), Malaga, Spain, Jun. 1995, pp. 22-39.
Wolf, M.E.; Lam, M.S.; A Data Locality Optimization Algorithm, Proceedings of the ACM SIGPLAN Symposium on Programming Language Design and Implementation, Jun. 1991, pp. 30-34.
Wolf, M.E.; Lam, M.S.; A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed System, vol.2, No. 4 (Oct. 1991), pp. 452-471.
Wolfe, M.V., Optimizing Supercompilers for Supercomputers, Research Monographs in Parallel and Distributed Computing, Pitman Publishing, London and the MIT Press, Cambridge, Massachusetts, 1989.
Allen, J.R.; Kennedy, K., Vector Register Allocation. Technical Report TR86-45, Rice University, Houston, TX, Dec. 1986. Also in IEEE Transactions on Computers, vol. 41, No. 10 (Oct. 1992), pp. 1290-1317.
Callahan, D.; Carr, S.; Kennedy, K.; Improving Register Allocation for Subscripted Variables, ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, White Plains, NY., vol. 25, No. 6 (Jun. 1990), pp. 53-65.
Kuck, D.J.; Kuhn, R.; Padua, D.; Leasure, B.; Wolfe, M., Dependence Graphs and Compiler Optimizations, 8th ACM Symposium on Principles of Programming Languages, Jan. 1981, ACM Order No. 549810, pp. 207-218.
Padua, D.A.; Wolfe, M.J. Advanced Compiler Optimizations for Supercomputers, Communications of the ACM, vol. 29, No. 12 (Dec. 1986), pp. 1184-1201.
Sarkar, V.; Gao, G.R., Optimization of Array Accesses By Collective Loop Transformations, 1991 ACM International Conference on Supercomputing, Cologne, Germany, Jun. 1991, pp. 194-205.
Sarkar, V., The PTRAN Parallel Programming System. Parallel Functional Programming Languages and Environments. McGraw-Hill Series in Supercomputing and Parallel Processing, 1990. Also PTRAN--The IBM Parallel Translation System, Paraallel Functional Languages and Compilers, ACM Press New York, Ny, pp. 309-391.
Warren, J., A Hierachical Basis for Reordering Transformations, Eleventh ACM Principles of Programming Languages Symposium, Salt Lake City, Utah, Jan. 1984, pp. 272-282.
Megiddo Nimrod
Sarkar Vivek
Chaki Kakali
International Business Machines - Corporation
Johnson Prentiss W.
MacDonald Allen R.
LandOfFree
Method of, system for, and computer program product for performi 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 performi, 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 performi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1601007