Optimizing Compilers for Modern Architectures - 1st Edition - ISBN: 9781558602861, 9780080513249

Optimizing Compilers for Modern Architectures

1st Edition

A Dependence-based Approach

Authors: Randy Allen Ken Kennedy
Hardcover ISBN: 9781558602861
eBook ISBN: 9780080513249
Imprint: Morgan Kaufmann
Published Date: 26th September 2001
Page Count: 790
Tax/VAT will be calculated at check-out

Institutional Access


Modern computer architectures designed with high-performance microprocessors offer tremendous potential gains in performance over previous designs. Yet their very complexity makes it increasingly difficult to produce efficient code and to realize their full potential. This landmark text from two leaders in the field focuses on the pivotal role that compilers can play in addressing this critical issue.

The basis for all the methods presented in this book is data dependence, a fundamental compiler analysis tool for optimizing programs on high-performance microprocessors and parallel architectures. It enables compiler designers to write compilers that automatically transform simple, sequential programs into forms that can exploit special features of these modern architectures.

The text provides a broad introduction to data dependence, to the many transformation strategies it supports, and to its applications to important optimization problems such as parallelization, compiler memory hierarchy management, and instruction scheduling. The authors demonstrate the importance and wide applicability of dependence-based compiler optimizations and give the compiler writer the basics needed to understand and implement them. They also offer cookbook explanations for transforming applications by hand to computational scientists and engineers who are driven to obtain the best possible performance of their complex applications.

The approaches presented are based on research conducted over the past two decades, emphasizing the strategies implemented in research prototypes at Rice University and in several associated commercial systems. Randy Allen and Ken Kennedy have provided an indispensable resource for researchers, practicing professionals, and graduate students engaged in designing and optimizing compilers for modern computer architectures.

Key Features

  • Offers a guide to the simple, practical algorithms and approaches that are most effective in real-world, high-performance microprocessor and parallel systems.
  • Demonstrates each transformation in worked examples.
  • Examines how two case study compilers implement the theories and practices described in each chapter.
  • Presents the most complete treatment of memory hierarchy issues of any compiler text.
  • Illustrates ordering relationships with dependence graphs throughout the book.
  • Applies the techniques to a variety of languages, including Fortran 77, C, hardware definition languages, Fortran 90, and High Performance Fortran.
  • Provides extensive references to the most sophisticated algorithms known in research.


Programmers, designers and developers of conventional and supercomputing. Postgraduate level compiler and parallel processing courses

Table of Contents


Chapter 1 - Compiler Challenges for High-Performance Architectures

1.1 Overview and Goals

1.2 Pipelining

1.2.1 Pipelined Instruction Units

1.2.2 Pipelined Execution Units

1.2.3 Parallel Functional Units

1.2.4 Compiling for Scalar Pipelines

1.3 Vector Instructions

1.3.1 Vector Hardware Overview

1.3.2 Compiling for Vector Pipelines

1.4 Superscalar and VLIW Processors

1.4.1 Multiple-Issue Instruction Units

1.4.2 Compiling for Multiple-Issue Processors

1.5 Processor Parallelism

1.5.1 Overview of Processor Parallelism

1.5.2 Compiling for Asynchronous Parallelism

1.6 Memory Hierarchy

1.6.1 Overview of Memory Systems

1.6.2 Compiling for Memory Hierarchy

1.7 A Case Study: Matrix Multiplication

1.8 Advanced Compiler Technology

1.8.1 Dependence

1.8.2 Transformations

1.9 Summary

1.10 Case Studies

1.11 Historical Comments and References


Chapter 2 - Dependence: Theory and Practice

2.1 Introduction

2.2 Dependence and Its Properties

2.2.1 Load-Store Classification

2.2.2 Dependence in Loops

<BR id="


No. of pages:
© Morgan Kaufmann 2002
Morgan Kaufmann
eBook ISBN:
Hardcover ISBN:

About the Author

Randy Allen

Randy Allen received his A.B. summa cum laude in chemistry from Harvard University and his M.A. and Ph.D. in mathematical sciences from Rice University. After serving a research fellowship at Rice, Dr. Allen entered the practical world of industrial compiler construction. His career has spanned research, advanced development, and management at Ardent Computers, Sun Microsystems, Chronologic Simulation, Synopsys, and CynApps. He has authored or coauthored 15 conference and journal papers on computer optimization, restructuring compilers, and hardware simulation, and has served on program committees for Supercomputing and the Conference on Programming Language and Design Implementation. Mr. Allen is CEO and President of Catalytic Compilers.

Affiliations and Expertise

CEO and President of Catalytic Compilers

Ken Kennedy

p> Ken Kennedy is the Ann and John Doerr Professor of Computational Engineering and Director of the Center for High Performance Software Research (HiPerSoft) at Rice University. He is a fellow of the Institute of Electrical and Electronics Engineers, the Association for Computing Machinery, and the American Association for the Advancement of Science and has been a member of the National Academy of Engineering since 1990. From 1997 to 1999, he served as cochair of the President's Information Technology Advisory Committee (PITAC). For his leadership in producing the PITAC report on funding of information technology research, he received the Computing Research Association Distinguished Service Award (1999) and the RCI Seymour Cray HPCC Industry Recognition Award (1999).

Professor Kennedy has published over 150 technical articles and supervised 34 Ph.D. dissertations on programming support software for high-performance computer systems. In recognition of his contributions to software for high-performance computation, he received the 1995 W. Wallace McDowell Award, the highest research award of the IEEE Computer Society. In 1999, he was named the third recipient of the ACM SIGPLAN Programming Languages Achievement Award.

Affiliations and Expertise

Rice University


"Compilers are the Queen of Computing Science and Technology. They have long been the bridge from applications to systems, but now they determine which architectural features should be implemented in new hardware, as well as which new language features will be effective for software developers. The authors write from great experience as innovators and developers of the field. This book is a very comprehensive treatment of optimization for cache management, vectorization, parallelization, and more. The title refers to Modern Architectures and indeed the subject matter is applicable from desktop systems to the world's fastest supercomputers. The examples are drawn from Fortran, but the theory applies to many programming languages. I think the book will serve as an excellent textbook as well as a much used reference for software developers." —David Kuck, Intel " This book makes an extremely valuable contribution to the field of compilation by presenting the fundamental basics in compiling technology for high performance computing systems. The authors provide careful and thorough descriptions of the analyses, including data and control dependences and interprocedural analysis, and the code transformations that can be applied as a result of the analyses. The book covers a comprehensive range of important topics needed to compile for high performance systems. The organization and structure of the book as well as the clear writing style make it an excellent text book, highly valuable reference book and a useful guide for implementing the techniques." —Mary Lou Soffa, University of Pittsburgh "The much awaited book by Randy Allen, a leading practitioner and Ken Kennedy, a pioneer in compiler research provides a skillful encapsulation of the results of more than 30 years of research and development in restructuring compilers - a significant part of which was done by the authors.