Integrated Range Comparison
for
Data-Parallel Compilation Systems

Xian-He Sun

Department of Computer Science
Louisiana State University
Baton Rouge, LA 70803-4020
sun@bit.csc.lsu.edu

Mario Pantano, Thomas Fahringer

Institute for Software Technology and
Parallel Systems, University of Vienna
Liechtensteinstr. 22 1090 Vienna, Austria
{pantano,tf}@par.univie.ac.at

Department of Computer Science
Louisiana State University
Baton Rouge, LA 70803-4020

Abstract

A major difficulty in restructuring compilation and in parallel programming in general is how to compare parallel performance over a range of system and problem sizes. Execution time varies with system and problem size, and an initially fast implementation may become slow when system and problem size scale up. This paper introduces the concept of range comparison. Unlike conventional execution time comparison in which performance is compared for a particular system and problem size, range comparison compares the performance of programs over a range of ensemble and problem sizes via scalability and performance crossing point analysis. A novel algorithm is developed to predict the crossing point automatically. The correctness of the algorithm is proved and a methodology is developed to integrate range comparison into restructuring compilations for data-parallel programming. A preliminary prototype of the methodology is implemented and tested under Vienna Fortran Compilation System. Experimental results demonstrate that range comparison is feasible and effective. It is an important asset for program evaluation, restructuring compilation, and parallel programming.