Triggered operations and counting events or counters are building blocks used by communication libraries, such as MPI, to offload collective operations to the Host Fabric Interface (HFI) or Network Interface Card (NIC). Triggered operations can be used to schedule a network or arithmetic operation to occur in the future, when a trigger counter reaches a specified threshold. On completion of the operation, the value of a completion counter increases by one. With this mechanism, it is possible to create a chain of dependent operations, so that the execution of an operation is triggered when all the operations it depends on have completed its execution. Triggered operations rely on hardware counters on the HFI and are a limited resource. Thus, if the number of required counters exceeds the number of hardware counters, a collective needs to stall until a previous collective completes and counters are released. In addition, if the HFI has a counter cache, utilizing a large number of counters can cause cache thrashing and provide poor performance. Therefore, it is important to reduce the number of counters, especially when running on a large supercomputer or when an application uses non-blocking collectives and multiple collectives can run concurrently. Moreover, counters being a scarce resource, it is important for the MPI library to be able to estimate the number of counters required by a collective so that it can fallback to the software implementation when the number of available counters is less than the required number. In this paper, we propose an algorithm to optimize the number of hardware counters used when offloading collectives with triggered operations. With our algorithm, different operations can share and re-use trigger and completion counters based on the dependences among them and their topological orderings. We have also proposed models to estimate the number of counters required by different collectives when using the optimization algorithm. While the proposed counter optimization algorithm assumes that the dependences among various operations in a collective are represented using a Directed Acyclic Graph (DAG), there might be cases when no DAGs are provided for the collective. In this paper, we also discuss how we can optimize the usage of counters for such cases. Our experimental results show that our proposed algorithm significantly reduces the number of counters over a naïve approach that does not consider the dependences among the operations.
ASJC Scopus subject areas
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computer Graphics and Computer-Aided Design
- Artificial Intelligence