Hitmap

Our group is developing a library for hierarchical tiling and mapping of arrays and sparse structures called Hitmap. Hitflow is an extension of Hitmap to exploit dataflow parallelism for both shared and distributed memory systems. You can find this libraries in the download section.

Hitmap

Hitmap is a highly-efficient library for hierarchical tiling and mapping of arrays and sparse structures. It is designed to be used with an SPMD (Single Process, Multiple Data) parallel programming language and it aims to simplify parallel programming, providing functionalities to create, manipulate, distribute, and communicate tiles and hierarchies of tiles.

Hitmap features

Hitmap has many features to perform hierarchical tiling and mapping of arrays. This library is designed to simplify the use of a global or local view of the parallel computation, allowing the creation, manipulation, distribution, and efficient communication of tiles and tile hierarchies. In Hitmap, data-layout and load-balancing techniques are independent modules that belong to a plug-in system. The techniques are invoked from the code and applied at runtime when needed, using internal information of the target-system topology to distribute the data. The programmer does not need to reason in terms of the number of physical processors. Instead, it uses highly abstract communication patterns for the distributed tiles at any grain level. Thus, coding and debugging operations with entire data structures are easy.

The Hitmap library supports functionalities to:

  • Generate a virtual topology structure arranging the available physical processors.
  • Mapping the data to the different processor with chosen partitioning and load-balancing techniques.
  • Automatically determine inactive processors at any stage of the computation, preventing the active processors may be affected.
  • Identify the neighbor processors to use in point-to-point or collective communications.
  • Build communication patterns to be reused across algorithm iterations.

These functionalities are organized in three different categories: Tiling, Mapping, and Communications.

 Hitmap architecture

Hitmap was designed with an object-oriented approach, although it is implemented in the C programing language. The classes are implemented as C data structures with associated functions.

Hitmap currently supports different types of indexed data-structures: Dense arrays; Sparse matrices; and Graphs.

HitFlow

HitFlow is a parallel programming framework implemented in C++ that exploits dataflow parallelism for both shared- and distributed-memory systems making the program correctness independent of the mapping policy applied at runtime. The HitFlow model allows generic networks of computational elements (transitions) to be created that produce or consume tasks (tokens) which are stored in shared containers (places). A transition takes one token from each one of its inputs and performs some activity with them. It may then add tokens to any/all of its output places. This activity is repeated while there are tokens in the input places.

The network can be self-reconfigured when transitions receive special tokens that indicate a mode change. In the Figure, transition B has two modes. In the blue mode its outputs are directed to transition C. On the green mode they are directed to transticion D. This functionality can be used, for example, to exploit locality fixing different behaviours to the same transition, which is mapped to the same processing element along the whole computation.