Using integer sets for data-parallel program analysis and optimization

Vikram Adve, John Mellor-Crummey

Research output: Contribution to conferencePaper

Abstract

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)
Pages186-198
Number of pages13
StatePublished - Jan 1 1998
Externally publishedYes
EventProceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI - Montreal, Can
Duration: Jun 17 1998Jun 19 1998

Other

OtherProceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI
CityMontreal, Can
Period6/17/986/19/98

Fingerprint

Communication

ASJC Scopus subject areas

  • Software

Cite this

Adve, V., & Mellor-Crummey, J. (1998). Using integer sets for data-parallel program analysis and optimization. 186-198. Paper presented at Proceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, Montreal, Can, .

Using integer sets for data-parallel program analysis and optimization. / Adve, Vikram; Mellor-Crummey, John.

1998. 186-198 Paper presented at Proceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, Montreal, Can, .

Research output: Contribution to conferencePaper

Adve, V & Mellor-Crummey, J 1998, 'Using integer sets for data-parallel program analysis and optimization' Paper presented at Proceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, Montreal, Can, 6/17/98 - 6/19/98, pp. 186-198.
Adve V, Mellor-Crummey J. Using integer sets for data-parallel program analysis and optimization. 1998. Paper presented at Proceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, Montreal, Can, .
Adve, Vikram ; Mellor-Crummey, John. / Using integer sets for data-parallel program analysis and optimization. Paper presented at Proceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, Montreal, Can, .13 p.
@conference{1ddce374391d412d9b414a2991723084,
title = "Using integer sets for data-parallel program analysis and optimization",
abstract = "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.",
author = "Vikram Adve and John Mellor-Crummey",
year = "1998",
month = "1",
day = "1",
language = "English (US)",
pages = "186--198",
note = "Proceedings of the 1998 Annual ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ; Conference date: 17-06-1998 Through 19-06-1998",

}

TY - CONF

T1 - Using integer sets for data-parallel program analysis and optimization

AU - Adve, Vikram

AU - Mellor-Crummey, John

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031623811&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031623811&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0031623811

SP - 186

EP - 198

ER -