XARK
Authors:
Open Access
- 30 October 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 30 (6) , 1-56
Abstract
The recognition of program constructs that are frequently used by software developers is a powerful mechanism for optimizing and parallelizing compilers to improve the performance of the object code. The development of techniques for automatic recognition of computational kernels such as inductions, reductions and array recurrences has been an intensive research area in the scope of compiler technology during the 90's. This article presents a new compiler framework that, unlike previous techniques that focus on specific and isolated kernels, recognizes a comprehensive collection of computational kernels that appear frequently in full-scale real applications. The XARK compiler operates on top of the Gated Single Assignment (GSA) form of a high-level intermediate representation (IR) of the source code. Recognition is carried out through a demand-driven analysis of this high-level IR at two different levels. First, the dependences between the statements that compose the strongly connected components (SCCs) of the data-dependence graph of the GSA form are analyzed. As a result of this intra-SCC analysis, the computational kernels corresponding to the execution of the statements of the SCCs are recognized. Second, the dependences between statements of different SCCs are examined in order to recognize more complex kernels that result from combining simpler kernels in the same code. Overall, the XARK compiler builds a hierarchical representation of the source code as kernels and dependence relationships between those kernels. This article describes in detail the collection of computational kernels recognized by the XARK compiler. Besides, the internals of the recognition algorithms are presented. The design of the algorithms enables to extend the recognition capabilities of XARK to cope with new kernels, and provides an advanced symbolic analysis framework to run other compiler techniques on demand. Finally, extensive experiments showing the effectiveness of XARK for a collection of benchmarks from different application domains are presented. In particular, the SparsKit-II library for the manipulation of sparse matrices, the Perfect benchmarks, the SPEC CPU2000 collection and the PLTMG package for solving elliptic partial differential equations are analyzed in detail.Keywords
Funding Information
- Galician Government (PGIDIT05PXIC10504PNPGIDIT06PXIB105228PR)
- FEDER Funds of the European Union (TIN2004-07797-C02TIN2007-67537-C03)
This publication has 27 references indexed in Scilit:
- A unified symbolic evaluation framework for parallelizing compilersIEEE Transactions on Parallel and Distributed Systems, 2000
- Symbolic analysis for parallelizing compilersACM Transactions on Programming Languages and Systems, 1996
- Parallel programming with PolarisComputer, 1996
- Beyond induction variablesACM Transactions on Programming Languages and Systems, 1995
- A framework for source code search using program patternsIEEE Transactions on Software Engineering, 1994
- Program concept recognition and transformationIEEE Transactions on Software Engineering, 1992
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- Automated program recognitionArtificial Intelligence, 1990
- The Perfect Club Benchmarks: Effective Performance Evaluation of SupercomputersThe International Journal of Supercomputing Applications, 1989
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972