Compiler transformations for high-performance computing

ABSTRACT

In the last three decades a large number of compiler transformations for optimizing programs have been implemented. Most optimizations for uniprocessors reduce the number of instructions executed by the program using transformations based on the analysis of scalar quantities and data-flow techniques. In contrast, optimizations for high-performance superscalar, vector, and parallel processors maximize parallelism and memory locality with transformations that rely on tracking the properties of arrays using loop dependence analysis.This survey is a comprehensive overview of the important high-level program restructuring techniques for imperative languages, such as C and Fortran. Transformations for both sequential and various types of parallel architectures are covered in depth. We describe the purpose of each transformation, explain how to determine if it is legal, and give an example of its application.Programmers wishing to enhance the performance of their code can use this survey to improve their understanding of the optimizations that compilers can perform, or as a reference for techniques to be applied manually. Students can obtain an overview of optimizing compiler technology. Compiler writers can use this survey as a reference for most of the important optimizations developed to date, and as bibliographic reference for the details of each optimization. Readers are expected to be familiar with modern computer architecture and basic program compilation techniques.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: Walid Abdul-Karim Abu-Sufah, Improving the performance of virtual memory computers., 1979
• 3: ABU-SUFAH, W., KUCK, D. J., AND LAWRIE, I). 1981 On the performance enhancement of paging systems through program analysis and transformations IEEE Trans. Comput. C-30, 5 (May), 341-356.
• 4: ACKERSLAXq, W B. 1982. Data flow languages. Computer 15, 2 (Feb.), 15-25.
• 5: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 6: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• 8: Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
• 9: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 10: ALLEN, F. E. 1969. Program optimization. In Annual Rewew ~n Automatic Programming 5. International Tracts in Computer Science and Technology and their Application, vol. 13. Pergamon Press, Oxford, England, 239-307.
• 11: ALLEN, F. E. AND COCKE, J. 1971. A catalogue of optimizing transformations. In Design and Opt~m~zat~on of Compilers, R Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1-30.
• 12: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 13: John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
• 14: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• 15: F. Allen , M. Burke , R. Cytron , J. Ferrante , W. Hsieh, A framework for determining useful parallelism, Proceedings of the 2nd international conference on Supercomputing, p.207-215, June 1988, St. Malo, France [doi>10.1145/55364.55385]
• 16: ALLEN, F. E., COCKE, J., AND KENNEDY, K. 1981. Reduction of operator ~trength. In Program Flow Analysis: Theory and Apphcations, S. S. Muchnik and N. D. Jones, Eds., Prentice-Hall, Englewood Cliffs, N.J., 79-101.
• 17: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 18: Donald Alpert , Dror Avnon, Architecture of the Pentium Microprocessor, IEEE Micro, v.13 n.3, p.11-21, May 1993 [doi>10.1109/40.216745]
• 19: AMERICAN NATIONAL STANDARDS INSTITUTE. 1987. An American National standard, IEEE standard for binary floating-point arithmetic SIGPLAN Not. 22, 2 (Feb.), 9-25.
• 20: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, ACM SIGPLAN Notices, v.28 n.6, p.112-125, June 1993
• 21: Steven Anderson , Paul Hudak, Compilation of Haskell array comprehensions for scientific computing, ACM SIGPLAN Notices, v.25 n.6, p.137-149, Jun. 1990
• 22: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 23: Bruce W. Arden , Bernard A. Galler , Robert M. Graham, An Algorithm for Translating Boolean Expressions, Journal of the ACM (JACM), v.9 n.2, p.222-239, April 1962 [doi>10.1145/321119.321121]
• 24: Arvind , David E. Culler, Dataflow architectures, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
• 25: ARWND, KATHAIL, V., AND PINGALI, K. 1980. A dataflow architecture with tagged tokens. Tech. Rep TM-174, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass.
• 26: David F. Bacon , Jyh-Herng Chow , Dz-ching R. Ju , Kalyan Muthukumar , Vivek Sarkar, A compiler framework for restructuring data declarations to enhance cache and TLB effectiveness, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.3, October 31-November 03, 1994, Toronto, Ontario, Canada
• 27: BAILEY, D. H. 1992. On the behavior of cache memories with strided data access. Tech. Rep. RNR- 92-015, NASA Ames Research Center, Moffett Field, Calif., (May).
• 28: BAILEY, D. H., BARszcz, E., BARTON, J. T., BROWNING, D. S., CARTER, R. L., DAGUM, L., FATOOHI, R. A., FREDERICKSON, P. 0., LASINSKI, T. A., SCHREIBER, R. S., SIMON, H. D., VENKATAKRISHNAN, V., AND WEERATUNGA, S. K. 1991. The NAS parallel benchmarks. Int. J. Supercomput. Appl. 5, 3 (Fall), 63-73.
• 29: Vasanth Balasundaram, A mechanism for keeping useful internal information in parallel programming tools: the data access descriptor, Journal of Parallel and Distributed Computing, v.9 n.2, p.154-170, June 1990 [doi>10.1016/0743-7315(90)90043-O]
• 30: BALASUNDARAM, V., Fox, G., KENNEDY, K., AND KREMER, V. 1990. An interactive environment for data partitioning and distribution. In Proceedtngs of the 5th D~strzbuted Memory Computer Conference (Charleston, South Carolina, Apr.). IEEE Computer Society Press, Los Alamitos, Calif.
• 31: V. Balasundaram , K. Kennedy , U. Kremer , K. McKinley , J. Subhlok, The parascope editor: an interactive parallel programming tool, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.540-550, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76323]
• 32: J. Eugene Ball, Predicting the effects of optimization on a procedure body, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.214-220, August 06-10, 1979, Denver, Colorado, United States
• 33: B~NE~EE, U. 1991. Unimodular transformations of double loops. In Advances in Languages and Compilers for Parallel Processing, A. Nicolau, Ed. Research Monographs in Parallel and Distributed Computing, MIT Press, Cambridge, Mass., Chap. 10.
• 34: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 35: BnNERJEE, U. 1988b. An introduction to a formal theory of dependence analysis. J. Supercomput. 2, 2 (Oct.), 133-149.
• 36: Utpal Banerjee, Speedup of ordinary programs, 1979
• 37: BANERJEE~ U., CHEN, S. C., KUCK, D. J., AND TOWLE, R. A. 1979. Time and parallel processor bounds for Fortran-like loops. IEEE Trans. Comput. C-28, 9 (Sept.), 660-670.
• 38: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 39: R Bernstein, Multiplication by Integer constants, Software—Practice & Experience, v.16 n.7, p.641-652, July. 1986 [doi>10.1002/spe.4380160704]
• 40: BERRY, M., CHEN, D., Koss, P., KUCK, D., Lo, S., PANG, Y., POINTER, L., ROLOFF, R., SAMEH, A., CLEMENTI, E_. CHIN. S.. SCHNEIDER. D.. FOX. FT., MESSINA, P., WALKER, D., HSIUNG, C., SCHWARZMEIER, J., LUE, K., ORSZAG, S., SEIDL, F., JOHNSON, O., GOODRUM, R., AND MARTIN, J. 1989. The Perfect Club benchmarks: Effective performance evaluation of supercomputers. Int. J. Supercomput. Appl. 3, 3 (Fall), 5-40.
• 41: G. E. Blelloch, Scans as Primitive Parallel Operations, IEEE Transactions on Computers, v.38 n.11, p.1526-1538, November 1989 [doi>10.1109/12.42122]
• 42: Mark Bromley , Steven Heller , Tim McNerney , Guy L. Steele, Jr., Fortran at ten gigaflops: the connection machine convolution compiler, ACM SIGPLAN Notices, v.26 n.6, p.145-156, June 1991
• 43: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• 44: BURNETT, G. J. AND COFFMAN, E. G., JR. 1970. A study of interleaved memory systems. In Proceedings of the Spring Joint AFIPS Computer Conference. vol. 36. AFIPS, Montvale, N.J., 467-474.
• 45: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 46: Michael Butler , Tse-Yu Yeh , Yale Patt , Mitch Alsup , Hunter Scales , Michael Shebanow, Single instruction stream parallelism is greater than two, ACM SIGARCH Computer Architecture News, v.19 n.3, p.276-286, May 1991
• 47: David Callahan , Ken Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Journal of Parallel and Distributed Computing, v.5 n.5, p.517-550, October 1988 [doi>10.1016/0743-7315(88)90011-1]
• 48: CALLAHAN, D. AND KENNEDY, K. 1988b. Compiling programs for distributed-memory multiprocessots. J. Supercomput. 2, 2 (Oct.), 151-169.
• 49: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.25 n.6, p.53-65, Jun. 1990
• 50: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 51: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
• 52: Steven Mark Carr, Memory-hierarchy management, Rice University, Houston, TX, 1993
• 53: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 54: CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COOKE, J., HOPKINS, M. E., AND MARKSTEIN, P. W. 1981. Register allocation via coloring. Comput. Lang. 6, 1 (Jan.), 47-57.
• 55: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
• 56: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber, The Alignment-Distribution Graph, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.234-252, August 12-14, 1993
• 57: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Automatic array alignment in data-parallel programs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-28, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158517]
• 58: CHEN, S. C. AND KUCK, D. J. 1975. Time and parallel processor bounds for linear recurrence systems. IEEE Trans. Comput. C-24 7 (July), 701-717.
• 59: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 60: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 61: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 62: Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
• 63: William D. Clinger, How to read floating point numbers accurately, ACM SIGPLAN Notices, v.25 n.6, p.92-101, Jun. 1990
• 64: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 65: COCKE, J. AND MARKSTEIN, P. 1980. Measurement of program improvement algorithms. In Proceedrags of the IFIP Congress (Tokyo, Japan, Oct.). North-Holland, Amsterdam, Netherlands, 221-228. Also available as IBM Tech. Rep. RC 8111, Feb. 1980.
• 66: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 67: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace Scheduling Compiler, IEEE Transactions on Computers, v.37 n.8, p.967-979, August 1988 [doi>10.1109/12.2247]
• 68: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 69: COOPER, K. D., HALL, M. W., AND KENNEDY, K. 1993. A methodology for procedure cloning. Comput. Lang. 19, 2 (Apr.), 105-117.
• 70: Keith D. Cooper , Mary W. Hall , Linda Torczon, Unexpected side effects of inline substitution: a case study, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.22-32, March 1992 [doi>10.1145/130616.130619]
• 71: Keith D. Cooper , Mary W. Hall , Linda Torczon, An experiment with inline substitution, Software—Practice & Experience, v.21 n.6, p.581-601, June 1991 [doi>10.1002/spe.4380210604]
• 72: CRAY RESEARCH 1988 CFT77 Reference Manual. Publication SR-0018-C. Cray Research, Inc., Eagan, Minn.
• 73: CYTRON, R. 1986. Doacross: Beyond vectorization for multiprocessors. In Proceedings of the Internatwnal Conference on Parallel Processing (St. Charles, Ill., Aug.). IEEE Computer Society, Washington, D.C., 836-844.
• 74: CYTRON, R. AND FERRANTE, J. 1987. What's in a name? -or- the value of renaming for parallelism detection and storage allocation. Proceedings of the Internatwnal Conference on Parallel Processing (University Park, Penn., Aug.). Pennsylvania State University Press, University Park, Pa., 19-27.
• 75: DANTZIG, G. B. AND EAVES, B. C. 1974. Fourier- Motzkin ehmination and sits dual with application to integer programming, in Combinatorial Programming: Methods and Applications (Versailles, France, Sept.). B. D. Roy, Ed. D. Reidel, Boston, Mass., 93-102.
• 76: DENNIS, J. B. 1980 Data flow supercomputers_ Computer 13, 11 (Nov.), 48-56.
• 77: Kaivalya M. Dixit, New CPU benchmark suites from SPEC, Proceedings of the thirty-seventh international conference on COMPCON, p.305-310, January 1992, San Francisco, California, United States
• 78: DONGARRA, J. AND HIND, A. R. 1979. Unrolling loops in Fortran. Softw. Pratt. Exper. 9, 3 (Mar.), 219-226.
• 79: S. J. Eggers , R. H. Katz, Evaluating the performance of four snooping cache coherency protocols, ACM SIGARCH Computer Architecture News, v.17 n.3, p.2-15, June 1989
• 80: Rudolf Eigenmann , Jay Hoeflinger , Z. Li , David A. Padua, Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.65-83, August 07-09, 1991
• 81: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 82: A. P. Yershov, ALPHA—An Automatic Programming System of High Efficiency, Journal of the ACM (JACM), v.13 n.1, p.17-24, Jan. 1966 [doi>10.1145/321312.321314]
• 83: FEAUTRIER, P. 1991. Dataflow analysis of array and scalar references. Int. J. Parall. Program. 20, 1 (Feb.), 23-52.
• 84: P. Feautrier, Array expansion, Proceedings of the 2nd international conference on Supercomputing, p.429-441, June 1988, St. Malo, France [doi>10.1145/55364.55406]
• 85: FERRARI, D. 1976. The improvement of program behavior. Computer 9, 11 (Nov.), 39-47.
• 86: FISHER, J.A. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July), 478-490.
• 87: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 88: FLOATING POINT SYSTEMS. 1979. FPS AP-120B Processor Handbook. Floating Point Systems, Inc., Beaverton, Ore.
• 89: FREE SOFTWARE FOUNDATION. 1992. gCC 2.X Reference Manual. Free Software Foundation, Cambridge, Mass.
• 90: Stefan M. Freudenberger , Jacob T. Schwartz , Micha Sharir, Experience with the SETL Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.26-45, Jan. 1983 [doi>10.1145/357195.357197]
• 91: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 92: M. Gerndt, Updating distributed variables in local computations, Concurrency: Practice and Experience, v.2 n.3, p.171-193, Sep. 1990 [doi>10.1002/cpe.4330020303]
• 93: D. H. Gibson , G. S. Rao, Design of the IBM System/390 computer family for numerically intensive applications: an overview for engineers and scientists, IBM Journal of Research and Development, v.36 n.4, p.695-711, July 1992
• 94: M. Gikar , C. Polychronopoulos, Compiling issues for supercomputers, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.164-173, November 12-17, 1988, Orlando, Florida, United States
• 95: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, ACM SIGPLAN Notices, v.26 n.6, p.15-29, June 1991
• 96: Susan L. Graham , Steven Lucco , Oliver Sharp, Orchestrating interactions among parallel computations, ACM SIGPLAN Notices, v.28 n.6, p.100-111, June 1993
• 97: Torbjörn Granlund , Richard Kenner, Eliminating branches using a superoptimizer and the GNU C compiler, ACM SIGPLAN Notices, v.27 n.7, p.341-352, July 1992
• 98: Manish Gupta, Automatic data partitioning on distributed memory multicomputers, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 99: GUPTA, M., MIDKIFF, S., SCHONBERG, E., SWEENEY, P., WANG, K. Y., AND BURKE, M. 1993. PTRAN II: A compiler for High Performance Fortran. In Proceedings of the 4th International Workshop on Compilers for Parallel Computers (Delft, Netherlands, Dec.). 479-493.
• 100: Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126055]
• 101: HARRIS, K. AND HOBBS, S. 1994. VAX Fortran. In Optimization in Compilers, F. E. Allen, R. Cytron, B. K. Rosen, and K. Zadeck, Eds. ACM Press, New York, chap. 16. To be published.
• 102: HATFIELD, D. J. AND GERALD, j. 1971. Program restructuring for virtual memory. IBM Syst. J. 10, 3, 168-192.
• 103: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 104: HEWLETT-PACKARD. 1992. PA-RISC 1.1 Architecture and Instruction Manual. 2nd ed. Part Number 09740-90039. Hewlett-Packard, Palo Alto, Ca}i~
• 105: HIGH PERFORMANCE FORTRAN FORUM. 1993. High Performance Fortran language specification, version 1.0. Tech. Rep. CRPC-TR92225, Rice University, Houston, Tex.
• 106: C.-W. Tseng , S. Hiranandani , K. Kennedy, Preliminary experiences with the Fortran D compiler, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.338-350, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169747]
• 107: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 108: Paul Hudak , Benjamin Goldberg, Distributed execution of functional programs using serial combinators, IEEE Transactions on Computers, v.34 n.10, p.881-891, Oct. 1985
• 109: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, ACM SIGARCH Computer Architecture News, v.17 n.3, p.242-251, June 1989
• 110: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 111: IBM. 1992. Optimization and Tuning Gutde for the XL Fortran and XL C Compilers. 1st ed. Publication SC09-1545-00, IBM, Armonk, N.Y.
• 112: IBM. 1991. IBM RISC System~6000 NIC Tuning Guide for Fortran and C Publication GG24- 3611-01, IBM, Armonk, N.Y.
• 113: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 114: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 115: Ken Kennedy , Kathryn S. McKinley, Loop distribution with arbitrary control flow, Proceedings of the 1990 conference on Supercomputing, p.407-416, October 1990, New York, New York, United States
• 116: KENNEDY, K., MCKINLEY, K. S., AND TSENG, C.-W. 1993. Analysis and transformation in an interactive parallel programming tool. Concurrency Pract. Exper 5, 7 (Oct.), 575-602.
• 117: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 118: Kathleen Knobe , Venkataraman Natarajan, Automatic data allocation to minimize communication on SIMD machines, The Journal of Supercomputing, v.7 n.4, p.387-415, Dec. 1993 [doi>10.1007/BF01206043]
• 119: Kathleen Knobe , Joan D. Lukas , Guy L. Stelle, Jr., Data optimization: allocation of arrays to reduce communication on SIMD machines, Journal of Parallel and Distributed Computing, v.8 n.2, p.102-118, February 1990 [doi>10.1016/0743-7315(90)90086-5]
• 120: KNOBE, K., LUKAS, J D., AND STEELE, G. L., JR 1988. Massively parallel data optimization. In The 2nd. Symposium on the Frontiers of Massively Parallel Computation (Fairfax, Va., Oct.). IEEE, Piscataway, N.J., 551-558.
• 121: KNUTH, D. E. 1971. An empirical study of Fortran programs. Soflw. Pract. Exper. 1, 2 (Apr.-June), 105-133.
• 122: Charles Howard Koelbel, Compiling programs for nonshared memory machines, Purdue University, West Lafayette, IN, 1991
• 123: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 124: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 125: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 126: David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977 [doi>10.1145/356683.356686]
• 127: KUCK, D. J. AND STOKES, R. 1982. The Burroughs Scientific Processor (BSP). IEEE Trans. Comput. C-31, 5 (May), 363-376.
• 128: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 129: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 130: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 131: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 132: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 133: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
• 134: J. R. Larus, Loop-Level Parallelism in Numeric and Symbolic Programs, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.812-826, July 1993 [doi>10.1109/71.238302]
• 135: Gyungho Lee , Clyde P. Kruskal , David J. Kuck, An empirical study of automatic restructuring of nonnumerical programs for parallel processors, IEEE Transactions on Computers, v.34 n.10, p.927-933, Oct. 1985
• 136: Zhiyuan Li, Array privatization for parallel execution of loops, Proceedings of the 6th international conference on Supercomputing, p.313-322, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143426]
• 137: J. Li , M. Chen, Compiling Communication-Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.361-376, July 1991 [doi>10.1109/71.86111]
• 138: LI, J. AND CHEN, M. 1990. Index domain alignment: Minimizing cost of cross-referencing between distributed arrays. In The 3rd Symposium on the Frontiers of Massively Parallel Computation, J. Jaja, Ed. IEEE Computer Society Press, Los Alamitos, Calif., 424-433.
• 139: LI, Z. AND YEW, P. 1988. Interprocedura} analysis for parallel computing. In Proceedings of the International Conference on Parallel Processing. F. A. Briggs, Ed. Vol. 2. Pennsylvania State University Press, University Park, Pa., 221-228.
• 140: Z. Li , P. C. Yew , C. Q. Zhu, An Efficient Data Dependence Analysis for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.26-34, January 1990 [doi>10.1109/71.80122]
• 141: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 142: Steven Lucco, A dynamic scheduling method for irregular parallel programs, ACM SIGPLAN Notices, v.27 n.7, p.200-211, July 1992
• 143: Mary E. Mace, Memory storage patterns in parallel processing, Kluwer Academic Publishers, Norwell, MA, 1987
• 144: MACE, M. E. AND WAGNER, R. A. 1985. Globally optimum selection of memory storage patterns. In Proceedings of the International Conference on Parallel Processing, D. DeGrott, Ed. IEEE Computer Society, Washington, D.C., 264-271.
• 145: MARKSTEIN, P., MARKSTEIN, V., AND ZADECK, K. 1994. Strength reduction. In Optimizatmn in Compilers. ACM Press, New York, Chap. 9. To be published.
• 146: Henry Massalin, Superoptimizer: a look at the smallest program, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.122-126, October 1987, Palo Alto, California, United States
• 147: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• 148: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, ACM SIGPLAN Notices, v.26 n.6, p.1-14, June 1991
• 149: Scott McFarling, Procedure merging with instruction caches, ACM SIGPLAN Notices, v.26 n.6, p.71-79, June 1991
• 150: McGRAw, J. R. 1985. SISAL: Streams and iteration in a single assignment language. Tech. Rep. M-146, Lawrence Livermore National Laboratory, Livermore, Calif.
• 151: MCMAHON, F. M. 1986. The Livermore Fortran kernels: A computer test of numerical performance range. Tech. Rep. UCRL-55745, Lawrence Livermore National Laboratory, Livermore, Calif.
• 152: MICHIE, D. 1968. "Memo" functions and machine learning. Nature 218, 19-22.
• 153: Robert E. Millstein , Charles A. Muntz, The ILLIAC IV FORTRAN compiler, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.1-8, March 18-19, 1975, New York, New York
• 154: R. Mirchandaney , J. H. Saltz , R. M. Smith , D. M. Nico , K. Crowley, Principles of runtime support for parallel processors, Proceedings of the 2nd international conference on Supercomputing, p.140-152, June 1988, St. Malo, France [doi>10.1145/55364.55378]
• 155: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 156: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 157: MUm~OKA, Y. 1971. Parallelism exposure and exploitation in programs. Ph.D. thesis, Tech. Rep. 71-424, Univ. of Illinois at Urbana-Champaign.
• 158: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 159: Alexandru Nicolau, Loop quantization: a generalized loop unwinding technique, Journal of Parallel and Distributed Computing, v.5 n.5, p.568-586, October 1988 [doi>10.1016/0743-7315(88)90013-5]
• 160: NICOLAU, A. AND FISHER, J. A. 1984. Measuring the parallelism available for very long instruction word architectures. IEEE Trans. Comput. C-33, 11 (Nov.), 968-976.
• 161: NIKHIL, R. S. 1988. ID reference manual, version 88.0. Tech. Rep. 284, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass.
• 162: H. Nobayashi , C. Eoyang, A comparison study of automatically vectorizing Fortran compilers, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.820-825, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76356]
• 163: O'BRIEN, K., HAY, B., MINISH, J., SCHAFFER, H., SCHLOSS, B., SHEPHERD, A., AND ZALESKI, M. 1990. Advanced compiler technology for the RISC System/6000 architecture. In IBM RISC System/6000 Technology. Publication SA23- 2619. IBM Corporation, Mechanlcsburg, Penn
• 164: Wilfried Oed, Cray Y-MP C90: system features and early benchmark results, Parallel Computing, v.18 n.9, p.947-954, Aug. 1992 [doi>10.1016/0167-8191(92)90039-A]
• 165: Richard R. Oehler , Michael W. Blasgen, IBM RISC System/6000: Architecture and Performance, IEEE Micro, v.11 n.3, p.14-17, 56-62, May 1991 [doi>10.1109/40.87565]
• 166: PADUA, D. A. AND PETERSEN, P. M. 1992. Evaluation of paralleIizing compilers. Parallel Computing and Transputer Applications, (Barcelona, Spain. Sept.). CIMNE, 1505-1514. Also available as Center for Supercomputing Research and Development Tech Rep. 1173.
• 167: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 168: PADUA, D. A., KUCK, D. j. AND LAWRIE, D. 1980. High-speed multiprocessors and compilation techniques. IEEE Trans. Comput. C-29, 9 (Sept.), 763-776.
• 169: Paul M. Petersen , David A. Padua, Static and dynamic evaluation of data dependence analysis, Proceedings of the 7th international conference on Supercomputing, p.107-116, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165961]
• 170: Karl Pettis , Robert C. Hansen, Profile guided code positioning, ACM SIGPLAN Notices, v.25 n.6, p.16-27, Jun. 1990
• 171: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• 172: C. D. Polychronopoulos, Advanced loop optimizations for parallel computers, Proceedings of the 1st International Conference on Supercomputing, p.255-277, March 1988, Athens, Greece
• 173: POLYCHRONOPOULOS, C. D. 1987b. Loop coalescing: A compiler transformation for parallel machines. In Proceedings of the International Conference on Parallel Processing (University Park, Penn., Aug.). Pennsylvania State University Press, University Park, Pa., 235-242.
• 174: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 175: POLYCHRONOPOULOS, C. D., GIRKAR, M., HAGHIGHAT, M. R., LEE, C. L., LEUNG, B., AND SCHOUTEN, D. 1989. Parafrase-2: An environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors. In Proceedings of the International Conference on Parallel Processing. Volume 2. Pennsylvania State University Press, University Park, Pa., 39-48.
• 176: David L. Presberg, The Paralyzer: Ivtran's Parallelism Analyzer and Synthesizer, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.9-16, March 18-19, 1975, New York, New York
• 177: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 178: William Pugh, Uniform techniques for loop optimization, Proceedings of the 5th international conference on Supercomputing, p.341-352, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109108]
• 179: B. Ramakrishna Rau , Joseph A. Fisher, Instruction-level parallel processing: history, overview, and perspective, The Journal of Supercomputing, v.7 n.1-2, p.9-50, May 1993 [doi>10.1007/BF01205181]
• 180: B. Ramakrishna Rau , David W. L. Yen , Wei Yen , Ross A. Towie, The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs, Computer, v.22 n.1, p.12-26, 28-30, 32-35, January 1989 [doi>10.1109/2.19820]
• 181: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 182: RISEMAN, E. M. AND FOSTER, C. C. 1972. The inhibition of potential parallelism by conditional jumps. IEEE Trans. Comput. C-21~ 12 (Dec.), 1405-1411.
• 183: Anne Marie Rogers, Compiling for locality of reference, 1990
• 184: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 185: Gary Sabot , Skef Wholey, CMAX: a Fortran translator for the connection machine system, Proceedings of the 7th international conference on Supercomputing, p.147-156, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165965]
• 186: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 187: Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, ACM SIGPLAN Notices, v.27 n.7, p.175-187, July 1992
• 188: Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
• 189: Z. Shen , Z. Li , P. C. Yew, An Empirical Study of Fortran Programs for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.356-364, July 1990 [doi>10.1109/71.80162]
• 190: SINGH, J. P. AND HENNESSY, J. L. 1991. An empirical investigation of the effectiveness and limitations of automatic parallelization. In Proceedings of the International Symposium on Shared Memory Multiprocessing, (Apr.). 213-240.
• 191: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 192: Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
• 193: Gurindar S. Sohi, Instruction Issue Logic for High-Performance, Interruptible, Multiple Functional Unit, Pipelined Computers, IEEE Transactions on Computers, v.39 n.3, p.349-359, March 1990 [doi>10.1109/12.48865]
• 194: Guy L. Steele, Arithmetic shifting considered harmful, ACM SIGPLAN Notices, v.12 n.11, p.61-69, November 1977 [doi>10.1145/956641.956647]
• 195: Guy L. Steele, Jr. , Jon L. White, How to print floating-point numbers accurately, ACM SIGPLAN Notices, v.25 n.6, p.112-126, Jun. 1990
• 196: Per Stenström, A Survey of Cache Coherence Schemes for Multiprocessors, Computer, v.23 n.6, p.12-24, June 1990 [doi>10.1109/2.55497]
• 197: SUN MICROSYSTEMS. 1991. SPARC Architecture Manual, Version 8. Part No. 800-1399-08. Sun Microsystems, Mountain View, Calif.
• 198: Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
• 199: Zhixi Fang , Peiyi Tang , Pen-Chung Yew , Chuan-Qi Zhu, Dynamic Processor Self-Scheduling for General Parallel Nested Loops, IEEE Transactions on Computers, v.39 n.7, p.919-929, July 1990 [doi>10.1109/12.55693]
• 200: THINKING MACHINES. 1989. Connection Machine, Model CM-2 Technical Summary. Thinking Machines Corp., Cambridge, Mass.
• 201: TJADEN, G. S. AND FLYNN, M. J. 1970. Detection and parallel execution of parallel instructions. IEEE Trans. Comput. C-19, 10 (Oct.), 889-895.
• 202: J. Torrellas , H. S. Lam , J. L. Hennessy, False Sharing and Spatial Locality in Multiprocessor Caches, IEEE Transactions on Computers, v.43 n.6, p.651-663, June 1994 [doi>10.1109/12.286299]
• 203: Ross Albert Towle, Control and data dependence for program transformations., 1976
• 204: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, ACM SIGPLAN Notices, v.21 n.7, p.176-185, July 1986
• 205: Chau-Wen Tseng, An optimizing Fortran D compiler for MIMD distributed-memory machines, Rice University, Houston, TX, 1993
• 206: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 207: Reinhard v. Hanxleden , Ken Kennedy, Relaxing SIMD control flow constraints using loop transformations, ACM SIGPLAN Notices, v.27 n.7, p.188-199, July 1992
• 208: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• 209: Ko-Yang Wang, Intelligent program optimization and parallelization for parallel computers, Purdue University, West Lafayette, IN, 1991
• 210: WANG, Ko AND GANNON, D. 1989. Applying AI techniques to program optimization for parallel computers, in Parallel Processing for Supercomputers and Artificial Intelligence, K. Hwang and D. Degroot, Eds. McGraw Hill, New York, Chap. 12.
• 211: Dorothy Wedel, Fortran for the Texas Instruments ASC system, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.119-132, March 18-19, 1975, New York, New York
• 212: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 213: Michael Weiss, Strip mining on SIMD architectures, Proceedings of the 5th international conference on Supercomputing, p.234-243, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109083]
• 214: Skef Wholey, Automatic data mapping for distributed-memory parallel computers, Proceedings of the 6th international conference on Supercomputing, p.25-34, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143377]
• 215: Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
• 216: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
• 217: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 218: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 219: M. Wolfe , C. W. Tseng, The Power Test for Data Dependence, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.591-601, September 1992 [doi>10.1109/71.159042]
• 220: ZIMA, H. P, BAST, H. J, AND GERNDT, M. 1988. SUPERB. A tool for semi-automatic S1MD/MIMD parallelization Parall. Comput 6, 1 (Jan.J, 1-18.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Languages, Performance

Keywords:
compilation, dependence analysis, locality, multiprocessors, optimization, parallelism, superscalar processors, vectorization