Projects

A4: Characterisation and Analysis of Invasive Algorithmic Patterns

Principal Investigators:

Prof. M. Bader, Dr. S. Wildermann

Scientific Researchers:

J. Spieck, B. Pourmohseni, A. Pöppl, M. Wille, Dr. J. Falk

Abstract

Project A4 characterises, investigates existing and develops novel invasive algorithmic patterns, which are motivated by applications from project area D. Using design space exploration (DSE), we precompute operating points to achieve desired quality numbers (performance, energy consumption, etc.) of applications.

In the second funding phase, we addressed three major research questions:

1. How can we derive knowledge about an application’s performance and pass it to the run-time system? Together with Projects A1 and C2, we developed the ActorX10 library. The use of actor-based design for InvadeX10 applications realises a separation of computation and communication and automatically serves as a design entry for a subsequent DSE. The DSE obtains multiple operating points with different trade-offs between resource requirements and achievable quality numbers. This information is passed to the run-time system.
2. How can we prepare run-time system decisions based on this knowledge, to improve the system performance w.r.t. various performance metrics? Each operating point found by DSE has Pareto-optimal quality numbers and resource claim constraints. We distil this usually huge set of Pareto-optimal operating points to a manageable and still relevant subset of points. These are passed to the run-time system, which can use the provided information for resource management.
3. How can invasion-aware algorithmic patterns be developed that benefit from invasion on heterogeneous platforms? For this purpose, we developed and examined SWE-X10, a proxy application for space- and time-adaptive tsunami simulation, and a prototypical image detection chain. Both proxy applications are written in InvadeX10 using the ActorX10 library and serve to evaluate novel invasive algorithmic patterns and how to exploit operating points distilled by DSE.

The developed design flow allows the run-time system to execute applications with predictable performance (w.r.t. upper and lower bounds on various quality numbers), where applications are statically optimised under worst-case assumptions and for hardware with known performance behaviour.

In Phase III, we will focus on programming and characterising applications with varying execution phases and changing workloads to run on hardware with uncertain performance behaviour.

Synopsis

Application execution may be exposed to diverse workload scenarios depending on varying inputs, execution phases, and environmental conditions. Rather than application mappings being tailored to the worst-case or average-case scenarios, it is necessary to provide run-time enforcement strategies that enable switching between different algorithmic patterns and resource claims dynamically to cope with such variances. Additionally, on modern hardware, such uncertain performance may already result from small variations in the manufacturing process—for example, compute core instances of the same type will have to run at slightly different clock frequencies to meet a certain power limit or energy budget. Furthermore, hardware faults are expected to occur more often thus making resources temporally or, due to manufacturing variability and ageing, even permanently unavailable. Therefore, it is our goal to provide optimised and robust application execution by dynamically adapting the application behaviour and structure (i.e. the actor model) as well as the set of allocated resources by means of re-invasion and run-time requirement enforcement (RRE) to such variances and fault scenarios. Consequently, the concept of operating points needs to be extended to include such variations and provide an operational corridor for run-time requirement enforcers in the run-time system or in the invasive hardware.

Approach

Project A4’s mission is to explore and establish application characterisation in the invasive computing paradigm and to investigate and evaluate how algorithms and applications may exploit and profit from the resulting predictability features.

A major challenge is that our study of invasive proxy applications in Phase II and the experiences gained within the embedded system and HPC communities reveal that application execution is getting increasingly dynamic:

1. Workload scenarios and execution phases of an application vary strongly, such that a static worst- or average-case characterisation for a single scenario becomes inadequate.
2. Performance behaviour on modern hardware is highly uncertain, as external influences, differences in manufacturing and measures to enforce power limits or energy budgets affect quality numbers in an unforeseeable way. For example, compute core instances of the same type will have to run at slightly different clock frequencies to meet a certain power limit or energy budget. (Intel Sandy Bridge architecture) compute nodes of the SuperMUC petascale machine. Observing the the average node power of compute nodes in the SuperMUC petascale supercomputer, one can see a Gaussian distribution of the power consumption. If we assume power capping for the compute nodes, we have to expect a similar Gaussian distribution for the achievable clock speeds.
3. Hardware faults are expected to occur more often thus making resources temporally or, due to manufacturing variability and ageing, even permanently unavailable.

Project A1 investigates the enforcement of non-functional requirements for the execution of one operating point. Such adaptations concentrate on modifications of the claimed resources, and thus always happen within a corridor defined by the respective operating point. Project A4 expands this approach beyond the boundaries of a single operating point by considering algorithmic adaptations of the application as well as modifications of the resource claim. Our goal is to provide optimised and robust application execution in the context of above aspects by characterising and enforcing adaptation of the application behaviour (e.g. algorithmic variants), the application structure (i.e. the actor model), and the set of allocated resources by means of re-invasion and run-time requirement enforcement (RRE) to such variances and fault scenarios.

A comprehensive summary of the major achievements of the second funding phase can be found by accessing Project A4 second phase website.

Publications