Using Integer Sets for Data-Parallel Program Analysis and Optimization

Vikram Adve, John Mellor-Crummey

Research output: Contribution to journalArticlepeer-review


In this paper, we describe our experience with using an abstract integer-set framework to develop the Rice dHPF compiler, a compiler for High Performance Fortran. We present simple, yet general formulations of the major computation partitioning and communication analysis tasks as well as a number of important optimizations in terms of abstract operations on sets of integer tuples. This approach has made it possible to implement a comprehensive collection of advanced optimizations in dHPF, and to do so in the context of a more general computation partitioning model than previous compilers. One potential limitation of the approach is that the underlying class of integer set problems is fundamentally unable to represent HPF data distributions on a symbolic number of processors. We describe how we extend the approach to compile codes for a symbolic number of processors, without requiring any changes to the set formulations for the above optimizations. We show experimentally that the set representation is not a dominant factor in compile times on both small and large codes. Finally, we present preliminary performance measurements to show that the generated code achieves good speedups for a few benchmarks. Overall, we believe we are the first to demonstrate by implementation experience that it is practical to build a compiler for HPF using a general and powerful integer-set framework.

Original languageEnglish (US)
Pages (from-to)186-198
Number of pages13
JournalSIGPLAN Notices (ACM Special Interest Group on Programming Languages)
Issue number5
StatePublished - May 1998
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Using Integer Sets for Data-Parallel Program Analysis and Optimization'. Together they form a unique fingerprint.

Cite this