1 Introduction↩︎

Asynchronous Many-Task (AMT) runtimes (e.g., HPX and Legion) divide computations into fine-grained tasks and often express dependencies through futures: placeholders for values that producer tasks create and consumer tasks read later. A runtime typically assigns the tasks dynamically to worker processes through work stealing, where idle workers steal tasks from others.

Itoyori [1] is a cluster AMT runtime combining work stealing with MPI one-sided communication for nested fork-join programs, and ItoyoriFBC extends it with support for futures [2]. The futures in ItoyoriFBC follow a future-only model that binds each future to its producer task during task creation and requires a compile-time fixed consumer count (see Listing 1). The future-only model works when dependencies are known at task creation, but not when tasks discover dependencies dynamically while building the task graph such as in a recent algorithm for the LU factorization of hierarchical matrices (HLU) [3].

The promise-future model separates the producer side from the consumer side: a promise provides the value, while futures consume it (Listing [lst:new]). For example, the recent HLU algorithm requires a parent task to pass futures to child tasks before spawning the corresponding producer tasks.

Realizing this model in ItoyoriFBC creates two challenges. First, the runtime must know when it is safe to reclaim the memory of task results, even though the number of futures may vary during execution. Second, a consumer task may access a future before the corresponding producer task exists, so the runtime must be able to pause and later resume a variable number of consumers (called waiters). This work investigates how the promise-future model can be realized in ItoyoriFBC. Our contributions are: (1) a data structure design to handle the two challenges, (2) its implementation in ItoyoriFBC, and (3) an evaluation of our implementation with HLU on up to 16 nodes.

2 Design↩︎

As shown in Figure 2, futures in ItoyoriFBC use a shared state object that stores the produced value and tracks tasks that may access or wait for it. In our extension, each promise and its corresponding futures refer to this shared state (see Figure 3), stored on a home process, i.e., the MPI process responsible for it. The home process creates the promise; ideally, it also accesses the future data, since each access may require MPI one-sided communication.

2.0.0.1 Challenge 1: Reclaiming Shared State

Because futures may be created dynamically (e.g., by copying a future), the runtime can no longer statically know when a shared state becomes unreachable. We therefore attach a reference counter to each shared state: creating a future or promise increments it, and destroying one decrements it. When the counter reaches zero, no task can access the shared state, so the home process may reclaim it (Figure [fig:refcount]): instantly if the home process performed the final decrement, otherwise at its next shared-state allocation.

2.0.0.2 Challenge 2: Suspending and Resuming Consumers

If a consumer task accesses a future before its value is ready, or before the corresponding producer task exists, the runtime must suspend the consumer and later resume all waiters. The runtime stores the consumer’s continuation, i.e., the information needed to resume the consumer later, in a waiter list attached to the shared state. Because the producer may run on a different process than the home process, the waiter list is a lock-free linked list accessed via MPI one-sided communication without involvement of the home process. Listings 4 and [lst:wake95all] provide pseudocode of the above two waiter list procedures:

push: When a waiter suspends itself, the waiter allocates a list node (Line 2) and uses remote atomic Compare-And-Swap (CAS) to push it onto the waiter list (Lines 6–7); if the producer has already fulfilled the value, the CAS fails and the consumer resumes immediately (Line 8).

wake_all: When a producer writes a value to its shared state, the producer uses CAS to detach the waiter list, replacing the head with MARKED_DONE (Lines 4–5), and then traverses the detached list to wake suspended tasks (Lines 9–12).

3 Experiments↩︎

We evaluated our implementation with the HLU benchmark from [4], using a full quadtree of height \(7\) (21 845 tasks) and calibrated busy-waits to model 100 seconds of numerical work. Smaller instances ran too briefly to be meaningful, and larger ones exceeded cluster memory. Experiments ran on the Goethe cluster [5] of University of Frankfurt with Open MPI 5.0.5 and g++ 11.4.1 (-O3), using 1–16 nodes (40–640 cores) and 10 runs per configuration. We ran one worker per core. Here, speedup is defined as the one-node running time divided by the running time on \(n\) nodes. Figure 5 shows that HLU reaches \(15.6\times\) speedup on 16 nodes with our variant; the variance across the 10 runs was low.

4 Conclusions↩︎

We realized the promise-future model in ItoyoriFBC using distributed reference counting and an MPI one-sided waiter list, and demonstrated that HLU reaches \(15.6\times\) speedup on 16 nodes with our variant. Future work should improve the reference counting to aggregate increments and decrements and only inform the home process when needed, and compare against the original future-only implementation.

Acknowledgements: This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under project number 512078735. The author gratefully acknowledges the computing time provided to them on the Goethe-NHR cluster at the Frankfurt Center for Scientific Computing. We also thank John Hundhausen for his assistance with code refactoring.

References↩︎