The Hierarchically Tiled Arrays programming approach

Basilio B. Fraguela, Jia Guo, Ganesh Bikshandi, María Jesús Garzarán, Gheorghe Almási, José E. Moreira, David A. PaduaLcr 2004 · DOI

TL;DR

This paper introduces Hierarchically Tiled Arrays (HTAs), a novel programming construct designed to simplify the development of parallel applications for distributed-memory systems. By encapsulating parallelism within array objects and overloading standard operators, HTAs allow programmers to write code that looks sequential while executing in parallel, easing development and maintenance.

What Problem Does This Paper Address?

Developing parallel programs for distributed-memory machines is notoriously difficult. Programmers face challenges in managing data distribution, synchronization, and debugging complex communication patterns. Existing approaches, like MPI, require explicit management of these aspects, leading to intricate and hard-to-maintain code. While some languages offer higher-level abstractions, they often fall short in compiler support or flexibility. This paper aims to bridge this gap by providing a more intuitive and manageable way to express parallelism, particularly for numerical computations.

Methods

The core of this work is the Hierarchically Tiled Array (HTA) data structure. An HTA is essentially an array that is recursively partitioned into smaller "tiles." These tiles can themselves be HTAs or basic arrays. The key idea is to distribute the outermost tiles across processors for parallelism, while using inner tiles for data locality.

The HTA approach is implemented as a MATLAB toolbox. It achieves its goal by:

  • Encapsulating Parallelism: HTAs act as objects that hide the underlying parallelism. A single-threaded client program interacts with HTAs, and the toolbox handles the distribution of operations to servers (processors) that hold the HTA tiles.
  • Operator Overloading: Standard operators (like * for multiplication) and array functions are overloaded to work with HTAs. This allows programmers to use familiar syntax for parallel operations, making the code resemble sequential MATLAB.
  • Hierarchical Structure: The recursive tiling allows for natural mapping of data and tasks onto hierarchical machine architectures.
  • Execution Model: A client process manages the overall program flow and broadcasts commands to servers. Servers execute operations on their local tiles, requesting data from other servers if needed.

Datasets

Not discussed in the paper. The paper focuses on evaluating the HTA approach using standard benchmarks.

Key Insights and Ideas

  • Bridging the Abstraction Gap: HTAs offer a compelling middle ground between low-level explicit message passing (like MPI) and high-level, potentially less flexible, parallel languages. They aim to provide the ease of use of sequential programming with the performance of parallel execution.
  • MATLAB as a Prototyping Platform: Using MATLAB as the host language for the HTA toolbox is a strategic choice. It leverages MATLAB's widespread use in scientific computing and its extensibility, allowing researchers and engineers to experiment with parallel programming without leaving their familiar environment.
  • Readability and Maintainability: The operator overloading and object-oriented nature of HTAs significantly improve code readability and maintainability compared to traditional MPI programs. This is a crucial factor for complex parallel applications.
  • Performance Trade-offs: While HTAs offer significant advantages in ease of programming, the current implementation incurs overheads (e.g., broadcasting commands, MATLAB's interpreted nature) that can impact performance, especially for fine-grained parallelism. However, these are identified as implementation-specific issues rather than fundamental limitations of the HTA concept.

Key Results

The paper presents experimental results comparing HTA implementations with traditional MPI+C/Fortran and serial versions for several benchmarks, including simple kernels (sparse matrix-vector product, Cannon's algorithm, Jacobi relaxation, matrix multiplication) and NAS benchmarks.

  • Speedup: For many benchmarks, HTA implementations achieved speedups comparable to or even better than MPI+C/Fortran, particularly for operations like matrix multiplication.
  • Ease of Programming: HTA programs consistently required significantly fewer lines of code than their MPI counterparts, demonstrating a substantial improvement in development effort and maintainability. For example, for the smv benchmark, HTA used 9 lines of code compared to 176 for MPI.
  • Performance Overhead: The HTA implementations showed higher execution times than MPI for some benchmarks (e.g., smv, jacobi, lu, cg), attributed to overheads like command broadcasting and MATLAB's internal mechanisms. However, the absolute execution times were often within a factor of two of MPI, indicating that the parallelization of computation was effective.
  • Super-linear Speedup: The ft kernel exhibited super-linear speedup in the HTA version, possibly due to cache and TLB misses in the serial MATLAB program.

Limitations and Future Work

The authors acknowledge several limitations and outline future directions:

  • Implementation Overheads: The current implementation's reliance on broadcasting commands from the client and MATLAB's pass-by-value semantics for function arguments introduce performance overheads.
  • Lack of Destructor in MATLAB: This hindered the proper destruction of distributed HTAs, requiring a custom garbage collection mechanism.
  • Scalability: The current client-server model with point-to-point communication can become a bottleneck. Future work includes improving scalability, potentially through a compiler that generates code for servers directly.
  • More Flexible Mapping: The current implementation supports cyclic distribution of top-level tiles. Future work aims to provide more flexible mapping policies, including hierarchical processor organizations.
  • Compiler Development: Developing a compiler for HTAs could further optimize performance by eliminating the need for explicit broadcasting and potentially generating more efficient server-side code.
  • Open-Source Alternatives: Replacing MATLAB in the servers with freely available open-source software is suggested to reduce implementation costs.

Summary updated

BibTeX
@inproceedings{fraguela2004hierarchically,
  author = {Basilio B. Fraguela and Jia Guo and Ganesh Bikshandi and María Jesús Garzarán and Gheorghe Almási and José E. Moreira and David A. Padua},
  title = {{The Hierarchically Tiled Arrays programming approach}},
  booktitle = {Lcr},
  year = {2004},
  doi = {10.1145/1066650.1066657},
}
Figure