Instruction Level Parallelizing Compilers
Alex Nicolau, University of California, Irvine
Monday, June 26, 1995
Recommended Background
This tutorial assumes a basic knowledge of sequential compiler development
techniques and terminology, and standard computer architecture concepts.
Abstract
This tutorial covers advanced compilation techniques for instruction
level parallel (ILP) machines and supercomputers. Emphasis will be
placed on the tradeoffs and relative advantages of various approaches
to parallelism exploitation (e.g., superscalar vs VLIW, advantages and
disadvantages of various proposed compilation techniques, etc).
Dependence analysis, interprocedural analysis, program
transformations, scheduling issues and resource allocation techniques
for ILP machines will be discussed. Several leading ILP machines will
be reviewed, and an overview of the design of an actual ILP compiler
will also be given.
Course Outline
- Introduction (5%)
- Importance of Parallelism
- Types of Parallel Extraction
- Overview of Parallel Programming Paradigms
- Characterization of Performance
- Data Dependence Analysis (5%)
- Computing dependences/disambiguation
- Symbolic and run-time dependence analysis
- Interprocedural Analysis (5%)
- In-line expansion
- Interprocedural dependences
- Anti-aliasing
- Technology for ILP Exploitation (80%)
- Auxiliary transformations and optimizations (10%)
Compiling for Simple RISC/pipelined machines
Advanced Optimizations and analysis for ILP
Transformations for Vectorization
- Instruction-level parallel machines (10%)
VLIW/superscalar/superpipelined machines
- Instruction-level Parallelization techniques (30%)
Trace Scheduling, Superblock/Hyperblock techniques, Percolation
Scheduling, single and multiple loop Software Pipelining.
- Resource allocation for ILP compilers (15%)
- Experimental results of ILP exploitation (5%)
- A case study ILP compiler (10%)
- Open Wrap-up Discussion - Guided by the Interests of Course Participants (5%)
Brief biography:
Alex Nicolau is Professor of Computer Science and Electrical and
Computer Engineering at the University of California, Irvine, where he
leads the ESP/PS parallelization project. His research interests are
in the areas of fine-grain parallelizing compilers and environments,
program transformations, and parallel architectures. He received his
Ph.D. from Yale University in 1984, where he was one of the members of
the ELI/Bulldog project. He has served on the program committees of
numerous conferences in the area, including the Workshop series on
Languages and Compilers for Parallel Architectures, International
Conference on Supercomputing, International Parallel Processing
Symposium, etc. He serves as co-editor in chief of the International
Journal of Parallel Programming.
Recommended Reading Material
Four papers in the Special Section on Languages and Compilers in
Proceedings of the IEEE, Vol.81, No.2 pp.211-304, February 1993.