Parallel Programming with Hierarchically Tiled Arrays

Writing high performance programs is a non-trivial task and remains a challenge even to advanced programmers. This dissertation describes a new data type, Hierarchically Tiled Array (HTA), that simplifies this task. HTAs are tiled arrays whose elements can either be HTAs or arrays or scalars. The elements can be distributed among a cluster of computers or be collocated in a single processor. They can be accessed and operated like scalars of the conventional n-dimensional arrays. They can also be assigned to one another, or passed as arguments to a function. In essence, HTA is an attempt to adopt tiles as first class data types, and to allow their direct manipulation. Augmenting existing programming languages with HTAs offers several benefits to high performance program developers. HTAs provide a global shared memory abstraction; this significantly reduces the time to develop parallel programs. The control flow of parallel HTA programs resemble sequential programs and hence are very easy to reason. HTAs naturally facilitate the development of recursive blocked algorithms aimed at exploiting deep memory hierarchies. The rich set of well defined operations and vector style expressions lead to code with high clarity and smaller size. Since HTAs are also conventional arrays, their fusion with a language will not add extra burden to programmers. Moreover, the performance benefits of tiling are preserved. To prove these claims, two popular languages, C++ and MATLAB, have been extended with HTA. In addition, the NAS benchmark suite, a set of complex computation intensive parallel programs, have been re-written using HTAs. We compare the lines of code and execution times of HTA programs with that of FORTRAN versions. Our results show that the codes written using HTAs are very readable and at the same efficient. We also show several sample code snippets to demonstrate the clarity of the HTA programs. All the experiments indicate that the explicit notion of tiles makes HTA a powerful language construct for writing a wide range of high performance programs