Future Technologies Colloquium Series

ABSTRACT:

Tiling is a well-known program optimization technique that transforms a n-deep loop nest in to a 2n-deep loop nest. Tiling is an effective mechanism to develop high performance implementations of algorithms. Tiling can be used to organize computations so that communication costs in parallel programs are reduced, and locality in sequential codes or sequential components of parallel programs is enhanced. In this talk, a data type - Hierarchically Tiled Array or HTA - that facilitates the direct manipulation of tiles is introduced. HTAs are arrays, whose elements can in turn be HTAs or scalars. The elements can be distributed among a cluster of computers or be collocated in a single processor. They can be accessed like the scalars of the conventional n-dimensional arrays. We have extended several array operations to HTAs, using which an HTA can also be assigned to or operated with another HTA. In essence, HTA is an attempt to adopt tiles as first class data types. The implementation of HTAs in sequential OO languages transforms these languages into powerful tools for the development of high-performance parallel codes and codes with high degree of locality. To support this claim, I will discuss our experience with the implementation of HTAs for MATLAB and C++, and the rewriting of the NAS benchmarks and a few other programs into HTA-based parallel form. The NAS benchmark suite consists of a wide range of challenging parallel programs - a Gaussian random deviates generator, a Multi Grid solver, a Conjugate Gradient solver, an Integer Sorting program, a Fourier Transform program and solvers for Navier-Stoke's equations. They are characterized by different forms of computation, communication and parallelism. All of these programs are expressible in HTAs, and the resulting programs are more readable than the SPMD based MPI programs.