Parallelizing Dense Linear Algebra Operations with Task Queues in

Antonio J. Dorta, José M. Badía, Enrique S. Quintana-Ortí, Francisco de SandePVM/MPI 2007 · DOI

TL;DR

This paper presents a novel approach to parallelizing dense linear algebra operations using the llc language and its Task Queues implementation. By extending OpenMP's tasking model, llc enables efficient parallelization of irregular computations on both shared and distributed memory systems, offering a compelling alternative to traditional MPI and OpenMP programming.

What Problem Does This Paper Address?

The paper tackles the challenge of effectively utilizing High-Performance Computing (HPC) hardware. While hardware has advanced rapidly, software tools for expressing parallel computations have lagged, creating a bottleneck for widespread HPC adoption. Existing tools like MPI offer portability and efficiency but demand deep knowledge of low-level parallelism, while OpenMP simplifies parallelization but is limited to shared-memory architectures. The authors aim to bridge this gap by providing a tool that combines the ease of OpenMP with the portability and performance of MPI, specifically for complex, irregular parallel tasks.

Methods

The core of the paper revolves around the llc language and its implementation of the Workqueuing Model using Task Queues. llc allows programmers to start with sequential code and incrementally add parallel directives, similar to OpenMP. The llc compiler (llCoMP) translates these directives into efficient MPI code, making it suitable for both shared and distributed memory systems.

A key innovation is the adaptation of OpenMP's Task Queues concept within llc. While OpenMP's tasking requires explicit captureprivate clauses to manage data sharing, llc leverages its underlying MPI model where each processor inherently has private memory. This simplifies the programming model by removing the need for explicit private data management. The paper demonstrates this by parallelizing the symmetric rank-k update (SYRK) operation, a fundamental linear algebra routine, using both OpenMP's tasking and llc's tasking directives. The llc implementation involves a master-slave paradigm where a master processor manages task distribution and slaves execute the computations, with specific llc directives (task_master_data, task_slave_set_data, task_slave_rnc_data) used to efficiently communicate necessary data.

Datasets

Not discussed in the paper. The evaluation uses synthetic workloads for the SYRK operation with specific matrix dimensions (e.g., m=10000, k=7000 for Bull; m=6000, k=3000 for SGI).

Key Insights and Ideas

  • Bridging the Gap: llc effectively combines the ease of OpenMP with the portability and performance of MPI, offering a more accessible path to parallel programming for distributed memory systems.
  • Task Queues for Irregularity: The Workqueuing Model with Task Queues is particularly well-suited for parallelizing irregular computations, such as those found in the FLAME library, where explicit loop indexing is avoided.
  • Simplified Data Management: llc's inherent private memory model for each processor simplifies data management compared to OpenMP's explicit captureprivate clauses, especially in distributed environments.
  • Efficient Communication: The llc master-slave approach, coupled with specialized directives, allows for efficient communication of modified data and handling of non-contiguous memory access, crucial for performance in distributed systems.
  • Portability Pays Off: While llc might introduce more directives than OpenMP for shared-memory systems, the gained portability to distributed systems is a significant advantage, especially when considering the development effort.

Key Results

The paper demonstrates that the llc implementation of Task Queues achieves performance comparable to OpenMP on shared-memory systems. On hybrid clusters (distributed memory), llc shows a speed-up that increases faster than OpenMP as the number of processors grows, eventually yielding better performance. This is attributed to llc being less affected by memory bandwidth limitations in larger configurations. For instance, on a hybrid system with 36 processors, a maximum speed-up of over 25 was achieved for the SYRK operation. The second variant of the SYRK algorithm, which generates finer granularity tasks, consistently outperformed the first variant.

Limitations and Future Work

Limitations:

  • The llc implementation for shared-memory systems might involve a slightly higher number of directives compared to OpenMP, impacting readability for simpler cases.
  • The performance advantage of llc over OpenMP on distributed systems becomes more pronounced with a larger number of processors, suggesting that for small-scale distributed systems, OpenMP might still be competitive.

Future Work:

  • Investigate other parallelization strategies for SYRK, such as using multiple tasks per iteration or splitting the main loop.
  • Extend the approach to other FLAME operations, starting with matrix-vector products.
  • Apply the llc parallelization methodology to a broader range of scientific and engineering applications.
  • Evaluate the performance on a wider variety of machines and architectures to further validate llc's portability and scalability.

Summary updated

BibTeX
@inproceedings{dorta2007parallelizing,
  author = {Antonio J. Dorta and José M. Badía and Enrique S. Quintana-Ortí and Francisco de Sande},
  title = {{Parallelizing Dense Linear Algebra Operations with Task Queues in}},
  booktitle = {PVM/MPI},
  year = {2007},
  doi = {10.1007/978-3-540-75416-9\_18},
}
Figure