Invasive Computing enables a resource-aware programming style, which includes adapting to external resource changes similar to malleability. We introduce asynchronously-malleable applications, which can adapt at any time without synchronizing the whole application, in contrast to speci c synchronization points. We show how master-slave applications meet the requirements for asynchronous malleability and how Invasive Computing supports it.
1.1 1.2
Malleability
There has been a considerable amount of work on malleable applications in high-performance computing, roughly
starting with the work by Feitelson et al. [
We demonstrated [
However, algorithms exist that are even more exible regarding recon guration. Flick et al. [
We argue that applications following a master-slave pattern always have this option, if creating and destroying slaves has low cost. Additionally, we propose an asynchronous programming style for handling recon guration. 2
In an asynchronously-malleable invasive application, the system can decide at any time to resize a claim. The system is only required to meet the invasion constraints. For example, requiring an asynchronously-malleable claim of 4 to 10 PEs, means the system can resize to 5 or 9 PEs at any time. In contrast to normal claims, an asynchronously-malleable claim must be adaptable even within an active infect phase. The application is responsible for starting and terminating i -lets with respect to added and removed PEs.
Figure 1 shows an example application. The resize handler is a function, which takes a list of PEs that were added and a list of PEs that will get removed. It does not return a value but adapts the application as a side e ect. When the system calls the handler in the example, it rst starts additional i -lets according to its input. Then the PEs to remove get signaled. The i -let code checks this signal and just stops executing jobs if needed.
When the application has adapted to the change order, it noti es the system of the successful adaptation by returning from the handler function. The system updates its resource state and operating system. From the application programmer's point of view, the system 1) adds additional resources to the claim, 2) executes the resize handler, and 3) removes resources from the claim as planned. This means the resize handler can assume to own the union of the claim resources before and after resizing. This is necessary, because it must terminate i -lets on PEs to remove and also must start i -lets on new PEs. Also, infect must not nish while resizing. If infect nishes, the main activity will continue and for example retreat the claim. Meanwhile, there must be no resize handler running, which starts additional i -lets. Thus, the claim must track how many child activities are running and the resize handler counts as one of them. So, infect waits for all child activities to terminate before it returns.
We considered to let the application decide which PEs to free, but dropped the idea. The system should handle such resource decisions exclusively, otherwise we end up with duplicated code and con icting decisions. The system has a global view of resource needs and thus is in the best position for de nitive decisions. It is the application's responsibility to receive information about the system's decisions and to adapt.
Our example contains a subtle circular dependency. A claim object requires constraints which in turn require the resize handler as an argument. This ensures via the type system that the programmer provides a resize handler whenever he declares malleability. However, the resize handler requires the claim object to start more i -lets. In Figure 1, we break this cycle via the global queue, which stores the claim it gets via adaptTo and provides the addWorker method.
The system shall handle errors in the resize handler in a safe manner. The handler might fail to adapt to the decided changes, e.g. by not terminating i -lets on PEs to remove. If the system ignores this \sit-in", it could give the PEs to another application, which nds itself unable to use them. Alternatively, the system could kill the blocking i -lets, but this might result in a deadlock of the whole application. So, the only sensible reaction is to kill the whole application, which failed to adapt to the decided changes. For another source of error, the (X10) resize handler might fail by throwing an exception. The system is not implemented in X10, so handling the exception is not an option. Like the rst case, the application state is unknown at this point, so recovery is impossible and the system must kill the application. These error cases show the crucial role of the resize handler. Reproducing and debugging errors is hard, because a call to the resize handler depends on the behavior of other applications and is e ectively non-deterministic.
Our system does not support virtualization (preemption, address spaces, etc) and inter-tile migration of i -lets so far. Thus, the system cannot remove an application from a tile during reinvade. The application would lose tile-local data without a chance to copy it elsewhere. So, the system ensures that at least one processing element per tile remains. However, the resize handler provides a migration chance, so asynchronously-malleable claims can lose tiles. 3
Adaptive MPI [
Leopold et al. [
Maghraoui et al. [
In contrast to this work, we do not constrain ourselves to iterative applications, as shown by the asynchronously-malleable sorting example, nor do we have to support legacy MPI applications. Furthermore, we look at malleable applications in the context of many-core architectures on a single chip whereas prior work focused distributed high-performance computing. 4
Our design proposal is improvable. For example, much of the application boilerplate or even the whole queue implementation should be generalized into the framework.
The termination signal in our example is setting a ag across a distributed system. It might pay o to use special (hardware or OS) mechanisms to speed this up. Furthermore, should the resize handler wait for the termination to succeed? If a PE keeps executing code, while the system assigns it to another application, this might or might not pose a problem. This work was supported by the German Research Foundation (DFG) as part of the Transregional Collaborative Research Center \Invasive Computing" (SFB/TR 89). Special thanks go to Jochen Speck, Sebastian Kobbe, and Martin Schreiber for extensive discussions about this. We also thank the anonymous reviewers for their suggestions.