Promise-Future Synchronization for Cluster Asynchronous Many-Task Runtimes via MPI One-Sided Communication
arXiv:2607.00303v1 [cs.DC] 1 Jul 2026
Mia Reitz University of Kassel, Research Group Programming Languages/Methodologies [email protected]
Abstract. Asynchronous Many-Task (AMT) runtimes use futures as placeholders for values produced by other tasks. In the ItoyoriFBC AMT runtime, the existing future-only model binds each future to its producer at creation time and requires the number of tasks that read each future to be fixed at compile time. This prevents directly expressing algorithms that create dependencies dynamically. We extend ItoyoriFBC with an implementation of a promise-future model that lifts these limitations. Thereby, our ItoyoriFBC variant supports dynamic algorithms such as Hierarchical LU factorization (HLU). We experimentally evaluated our implementation using HLU on up to 16 nodes and observed near-ideal scaling with a 15.6× speedup. Keywords: Futures · Promises · Work Stealing · Asynchronous ManyTask Programming
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.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 1.2). For example, the recent HLU algorithm requires a parent task to pass futures to child tasks before spawning the corresponding producer tasks.
2
M. Reitz
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. Listing 1.2. Promise-Future Model
Listing 1.1. Future-only Model 1 2 3
future < int , 1 > f = spawn ([=] { return 42; }); int v = f . get ();
1 2 3 4
2
promise < int > p = promise < int >:: make (); future < int > f = p . get_future (); spawn ([ p ] { p . set (42); }); int v = f . get ();
Design
As shown in Figure 1, 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. 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 2): instantly if the home process performed the final decrement, otherwise at its next shared-state allocation. Challenge 2: Suspending and Resuming Consumers If a consumer task accesses a future before its value is ready, or before the corresponding producer task Future
Future
Future
Future
Start Create promise count=1
Shared State
Create future count=2
Set value wake waiters
Shared State
Destroy future count=0 (GC) Promise
Fig. 1. Shared state object: future-only (left) vs. promise-future model (right).
Destroy promise count=1
End
Fig. 2. Reference counting of the promise-future model.
Promise-Future Synchronization for Cluster AMT Old Model Parent Task
1. spawn
New Model Child Task
Task A
2. pass promise
Task B
4. get()
3. get() 2. return
implicit make
3
3. set() 1. make
Future
Future
Promise
Fig. 3. Task interaction sequence: future-only vs. promise-future model. Listing 1.3. Pseudocode of push 1 2 3 4 5 6 7 8 9 10 11 12 13
bool push ( State * S , Continuation c ) { Node * n = new Node ( c ); Node * head = read_remote (S - > head ); while ( head != MARKED_DONE ) { n - > next = head ; Node * old = CAS_remote ( &S - > head , head , n ); if ( old == head ) return true ; head = old ; } delete n ; return false ; }
Listing 1.4. Pseudocode of wake_all 1 2 3 4 5 6 7 8 9 10 11 12 13
void wake_all ( State * S ) { Node * head = read_remote (S - > head ); while ( true ) { Node * old = CAS_remote ( &S - > head , head , MARKED_DONE ); if ( old == head ) break ; head = old ; } while ( head ) { wake ( head ); head = head - > next ; } }
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 1.3 and 1.4 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
4
M. Reitz HLU Speedup
Speedup
16
Observed Speedup Ideal Speedup
8 4 2 1
40
80
160 320 Number of Cores
640
Fig. 4. HLU speedup relative to one node on up to 16 nodes.
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 4 shows that HLU reaches 15.6× 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× 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 1. Shiina, S., Taura, K.: Itoyori: Reconciling global address space and global forkjoin task parallelism. In: Proc. of the Int. Conf. for High Performance Computing, Networking, Storage and Analytics (2023) 2. Reitz, M., Gerhards, B., Hundhausen, J., Fohry, C.: Investigating the performance difference of task communication via futures or side effects. In: Workshop on Asynchronous Many-Task Systems for Exascale (AMTE). Springer (2024) 3. Nather, R., Fohry, C.: Futures for dynamic dependencies – parallelizing the HLU factorization. In: Proc. Workshop on Asynchronous Many-Task Systems and Applications (WAMTA) (2024) 4. Nather, R., Fohry, C.: Futures in task graphs – extending taskflow with dynamic data dependencies. In: Asynchronous Many-Task Systems and Applications (WAMTA). p. 56–69. Springer-Verlag, Berlin, Heidelberg (2025) 5. TOP500.org: Goethe-NHR, https://www.top500.org/system/179588