Many software systems face the critical challenge of meeting quality-of-service goals, expressed as constraints and objectives on metrics; e.g., request latency, energy consumption, and result accuracy. As a further complication, these goals must be met despite unpredictableÐyet inevitableÐruntime variations in workload and operating environment. To provide predictable behavior in unpredictable deployments, it is crucial to build computer systems that adapt by adjusting their configurable components, or knobs, as they execute [55,58].
Implementing adaptive systems requires an adaptation logic (AdaptLog) that can efficientlyÐat runtimeÐconvert observed metrics into knob settings that meet the goals [37,60,80,83,93]. However, implementing a reliable and robust AdaptLog is difficult. For example, when the hardware for the Samsung Galaxy S9 was upgraded for the S9+, the achieved performance and energy efficiency was worse despite the better hardware [31]. The problem was tracked down to misconfigurations in the AdaptLog of the HMP scheduler [30]. In short, a heuristic-based AdaptLog that was appropriate for one hardware architecture, was inefficient on a closely related, but different architecture.
To ease development of adaptive computing systems, researchers have proposed several adaptation frameworks in the form of libraries or language runtimes [10,15,20,21,25,33,49,51,54,56,74,96]. Using the framework's interface, developers provide an adaptation specification (AdaptSpec): a declaration of the system's goals and the knobs that can be configured to achieve it. The framework's internal AdaptLog then tunes the knobs in response to any runtime changes.
Although helpful, all existing frameworks focus on a narrow, predefined set of possible AdaptSpecs (i.e., one or two metrics and a small collection of knobs). For example, Eon [79] only supports accuracy and energy metrics using alternative method implementations as knobs. Similarly, Power-Dial [44] only supports accuracy and throughput tradeoffs using application-level parameters as knobs.
This lack of generality arises because prior adaptation frameworks develop their AdaptLog using specialized models that relate specific metrics to specific knobs. Whether the AdaptLog is based on machine learning, control theory, or heuristics, the model is essential to predict how metrics will change with changes in knobs, which then guides the AdaptLog to set the knobs to ensure the goals are met. However, because the model relates specific knobs to specific metrics, the relevant knobs and metrics need to be enumerated before the model is constructed and that model must be reconstructed for use with a different knobs and/or metrics. This reliance on a narrowly defined model makes it difficult to implement a general adaptive system that can deploy with different goals in different environments.
The use of fixed models also prevents a system from dynamically changing AdaptSpecs during execution. We define the runtime alteration of an AdaptSpec as meta-adaptation. For many applications it is not enough to just adjust knob configurations; meta-adaptation is necessary as the goals themselves must be changed in response to external conditions [35,71]. For example, consider a CCTV camera installed with a backup battery [76]. It must always meet a target frame rate to prevent data loss, but its other goals vary depending on power source. On line power the system must maximize quality, however, during a power outage, it must minimize energy to prolong battery life [1]. Running this system in either AdaptSpec for its entire execution is suboptimal, either wasting energy on battery or lowering quality on line power.
To support more general and dynamic adaptation, including meta-adaptation, this paper presents GOAL: Goal-Oriented Adaptation Language. GOAL provides novel adaptation framework implemented in Swift [5]. Its key components are its (1) runtime AdaptLog and (2) its interface for writing AdaptSpecs.
Central to GOAL's design is its AdaptLog, which takes the form of a virtualized, time-variant, adaptive control system. Unlike prior approaches, GOAL's virtual control system is independent of any specific model relating metrics to knobs; instead, it is parameterized by a model which is passed in at runtime. Furthermore, GOAL's controller continually adjusts itself at runtime while also carefully exploiting structure of optimization problems so that it can control non-linear systems with a series of linear approximations.
GOAL's AdaptSpecs are written using a novel domain specific language (DSL), which is compiled just-in-time (JIT), separating the AdaptSpec declaration from system implementation. This separation allows different AdaptSpecs to be used with the same binary for deployments with different requirements or even for changing the requirements while the system is running. GOAL also provides a Library API so users can declare knobs and metrics and alter these values during execution. These features support complex adaptive behavior that would have been difficult and inefficient to implement with existing frameworks.
To demonstrate GOAL, we re-implement seven adaptive applications from the literature. Collectively, these case studies cover a wide range of metrics (throughput, latency, accuracy, power, cost, reliability and efficiency) and knobs (at both the application and system level, including two different hardware systems with distinct knobs). Our results show that GOAL's generalized approach meets goals just as well as prior work that synthesizes AdaptLogs specifically for each application's narrow goals and knobs [26]. To highlight GOAL's benefits, we then modify each application to perform meta-adaptation. We observe that due to GOAL's ability to support a wide range of AdaptSpecs and meta-adaptation, GOAL-based applications exhibit a 1.69× average improvement in corresponding metrics after metaadaptation is performed, compared to prior approaches that cannot support meta-adaptation. Furthermore, we show that GOAL incurs negligible overhead and is robust to errors in profiling, changing workloads and operating conditions. This paper makes the following contributions:
• Motivates the benefits of support general purpose adaptation and meta-adaptation.
• Proposes a general adaptation logic and runtime that supports a wide range of knobs, metrics and goals. • Proposes a programming framework and DSL for writing adaptation specifications. • Implements GOAL and releases it as open source. 1
Adaptation is a key mechanism for building robust software systems that operate effectively despite unpredictable dynamic changes to inputs or operating environment [55,58]. This section discusses prior approaches to building adaptive software systems, and discusses how limitations of prior works motivate the need for adaptation as a first class programming construct.
Computer systems have numerous configuration parameters and settings that impact their ability to meet their quantifiable behavioral goals [55]. Improper configuration is a notorious source of performance issues and bugs [47,69,90]. Selecting a good configuration is difficult because optimal configurations depend upon dynamically varying external factors such as workload and operating conditions [36,59,87]. Adaptive systems address this problem by automatically and dynamically adjusting configuration parameters to ensure goals are met. Thus, there is a need for principled approaches to building adaptive computing systems recognized by both industry [11,32,39,45,55,58,67] and academia [24,29,46,68].
Two design patternsÐObserve-Orient-Decide-Act (OODA) [12,13,73] and Monitor-Analyse-Plan-Execute (MAPE) [55]Ð have been proposed for creating adaptive software. Both establish a control loop as the basic structure for adaptation. During a loop iteration the software first observes/monitors its environment and its own quantifiable behavior. It then orients/analyzes itself with respect to these metrics to decide/plan what should be done next. The subsequent iteration then acts/executes these decisions by changing the values of configuration parameters. Because it results in more robust and flexible software, many approaches implement adaptive loops in the OODA/MAPE pattern.
As mentioned earlier, prior work models the OODA/MAPE design pattern as a control loop and several researchers have proposed that general scheme as a basis for system [42], software [8], and language [72] design. Many existing works suggest control theory [7,27,28,40,62,75,77,81,88,94,95], machine learning [9,22,38,50,91], and combinations of the two [41,43,57,65,85] as the basis for building principled AdaptLogs that perform the orientation/analysis and 1 GOAL source code available at: https://github.com/GOAL-Adaptation. decision/planning phase of the OODA/MAPE loop to dynamically adjust configuration knobs in a running computer system. Such approaches provide formal, mathematical guarantees about the precise assumptions and operating conditions under which the goals will be met. However, a challenge is that specialized knowledge in control, learning, or both is required to successfully deploy such approaches.
To make principled adaptation easy to implement, recent work proposes adaptation frameworks that package a controlor learning-based AdaptLog into a programming language [4,6,10,15,16,54,56,74,79,96] or a library [19,21,29,33,51,65,70,78,84,90,95] runtime. Developers do not need to possess specialized knowledge in learning or control to use these frameworks. Instead, they instantiate it with an initial AdaptSpec, after which the AdaptLog monitors the metrics and independently tunes the knobs to meet the goal.
While the OODA/MAPE design patterns themselves provide a general strategy, their implementations in existing approaches have significant limitations. These limitations arise because each framework is designed to support specific metrics and knobs and their AdaptLogs do not generalize to the metrics and knobs in other works. In other words, the OODA/MAPE concepts are generalizable, but specific instantiations of these concepts are problem-specific. Table 1 illustrates this idea, showing that while there is wide support for different goals and knobs across frameworks, the support provided by any one is specific and thus limited. For example, Green uses a heuristic AdaptLog based on a specific model of how alternative function implementations affect an application's power and accuracy tradeoffs [6]. Similarly, Aeneas's reinforcement learning model uses a reward signal based on energy measurements, and introducing new metrics requires a new reward function and learning model. To the best of our knowledge, there is no single framework that generalizes across a wide range of goals and knobs. This limitation also means that existing frameworks cannot be used for meta-adaptation because they do not support any alternative AdaptSpecs.
Overcoming these limitations requires users to extend the framework's internal AdaptLog for additional AdaptSpecs. This entails reconstructing the model and reimplementing the AdaptLog and its interface to support other knobs, metrics, goals and meta-adaptation. However, doing so defeats the purpose of using an adaptation framework because it requires users to have specialized knowledge of the AdaptLog.
While prior work has also explored making adaptation components configurable [3], we believe that performing meta-adaptation using such works is difficult because such works encapsulate the application itself rather than making the adaptation framework a natural component of the application which would allow it to exert fine grained control on all aspects of adaptation. Thus, we argue that the aforementioned limitations would be best addressed through a generalized adaptation framework that allows applications to interact with all aspects of adaptation dynamically. However, developing such a framework is not trivial because it requires a uniform interface and an AdaptLog whose underlying model allows the declaration and use of AdaptSpecs that work with any user-defined measures, knobs and goals. Furthermore, to enable metaadaptation, the framework must coordinate the interface with the runtime to ensure that goals are met even when the AdaptSpec changes. This paper introduces such a framework, GOAL.
We provide a high-level overview of GOAL, later sections detail its AdaptLog (ğ 4) and interface (ğ 5). We implement a meta-adaptive video encoder for a CCTV camera that meets a target frame rate, while maximizing quality on line power and minimizing energy on battery. Figure 1 shows this example: the original Swift code without adaptation (a), the GOAL version (b), and an example GOAL AdaptSpec (c).
As shown in Figure 1a, the developer initializes the encoder and defines parameters: qp and me (quantization parameter and motion estimation algorithm, respectively), which govern tradeoffs between the video quality and frame rate. Subsequently, the system enters a while loop where it calls the encodeNextFrame method with qp and me as input. The record function logs per-frame encoding quality.
The code in Figure 1a neither meets a target frame rate, nor reacts to changes in power source. Carefully selecting static values for qp and me could ensure the frame rate; however, without adapting to frame-to-frame differences, quality will be sacrificed (e.g., set the parameters for the worst case and live with lower quality for other cases). In fact, video encoding is a challenge problem for adaptive computing because it is difficult to tune encoding parameters [63].
GOAL provides constructs that allow developers to implement all parts of the OODA/MAPE control loop with minor modifications to existing software. Concretely, the developer needs to: (1) identify and declare configurable components as Knobs, (2) specify the code segment in which to perform adaptation, and (3) report application-level metrics to the GOAL runtime using measure.
Figure 1b illustrates the CCTV system implemented with GOAL. qp and me are declared as Knobs, using a stringified name and a default value for initializing the knob. The relevant metrics to be monitored are identified using measure. For example the encoding quality is reported for the CCTV. The while loop is replaced with GOAL's optimize loop (ğ 5.1) whose inputs are the list of Knobs to tune, and the loop body. This syntax tells the GOAL runtime to iteratively execute the loop body (as in the original program) while tuning the knobs after each iteration, according to the AdaptSpec. Hence, with such minor modifications we have converted the non-adaptive application to an adaptive application that implements a complete OODA/MAPE control loop.
The next step is writing an AdaptSpec. Figure 1c shows an example, defining the knobs, allowed values for each, the measures to monitor, and the goal that formally specifies the constraints and objective. This example is how the CCTV should behave on line power: maximize quality, with a throughput of 30 iterations per second (which translates to 30 frames/s). The application-level metrics (e.g., quality) and knobs (e.g. qp and me) in the AdaptSpec must match the string arguments in calls to Knob and measure. GOAL's runtime automatically declares metrics such as throughput, energy, etc. and hardware specific knobs such as core count (numCores) and DVFS frequency (coreFreq), allowing them to be used without explicit declaration.
This AdaptSpec tells the runtime to measure quality, energy, and throughput, while tuning qp, me, numCores and coreFreq. Additionally, the AdaptSpec states that the runtime must choose configurations that meet a further constraint on the knobs: the product of numCores and coreFreq should be greater than 2400. See ğ 5.3 for a full description of the DSL's grammar and capabilities.
GOAL AdaptSpecs are compiled just-in-time (ğ 4.2) and can be written in text files independent of the application code. This allows developer's to produce a single binary that can be deployed to meet different goals by writing different AdaptSpecs. Such flexibility distinguishes GOAL from existing adaptation frameworks. Given the GOAL system and an AdaptSpec, the last step before deployment is to use GOAL's model builder (ğ 4.3), which runs the application on test inputs to learn a function the knob configurations' impact on the specified metrics. Figure 2 presents a high-level overview of the OODA/MAPE loop implemented using GOAL. During execution, GOAL monitors the metrics identified by measure, analyzes and plans which values to use for each of the Knobs to meet the goal specified in AdaptSpec, then sets the Knobs to those values and executes the loop body.
Finally, the system can dynamically change any aspect of the AdaptSpec during execution, telling GOALs runtime to meet new goals, use new knobs, or both.
The CCTV requires meta-adaptation to change goals based on power supply. GOAL's intend method uniquely supports this by dynamically changing the AdaptSpec in a running system. The intend function takes a string representation of the goal and replaces the active goal with this argument. To illustrate this, we augment the optimize loop in Figure 1b with the following code (not shown in the figure):
if getPowerSupply () == . DirectPower { intend ( to : . maximize , objective : " quality " , suchThat : [( measure : " throughput " , The code in red specifies the parameters of intend and the code in blue represents the arguments specific to the requirements of the CCTV system.
With this handful of changes, the encoder will now meet the throughput constraint while optimizing either quality or energy based on the power source. This large increase in adaptive capability for small code changes highlight how GOAL's general adaptation framework supports complex adaptive behavior and seamless meta-adaptation.
3.5 Quantitative Benefits of Using GOAL Figure 3 compares the execution of our GOAL CCTV with a version that uses prior work to synthesize a customized, Application-specific AdaptLog [26]. However, using prior work, the CCTV can only meet one goal; we begin with the goal corresponding to line power: maximize quality and meet a throughput constraint.
Both versions execute identically until a power outage (at frame 650), where the GOAL version performs metaadaptation to start reducing energy. In contrast, the Application specific version cannot change the goal, continues using high energy, and risks depleting the battery, rendering the camera inoperable. After frame 650, GOAL consumes 32% less energy than the Application-specific approach. An additional AdaptLog could have been synthesized to run the CCTV with minimal energy. However, such a version would needlessly sacrifice quality while operating on line power, and switching between independent AdaptLogs at runtime is quite costlyÐin both execution time ğ 7.3 and engineering effort ğ 7.4. This example shows the importance of providing support for general adaptation and meta-adaptation and also the ease with which this can be achieved using GOAL. 4 The GOAL Runtime 3) the Model Builder. The Glue code coordinates these three components with the rest of the software and hardware. Furthermore, some application and system level metrics such as throughput and power consumption are measured by the Glue code [48]. The AdaptLog (ğ 4.1) is implemented independently of any specific AdaptSpec; it receives the goals, the model, and current metrics and produces a schedule of configurations. The compiler (ğ 4.2) takes an AdaptSpec and produces four outputs: (1) the space of allowable knob configurations, (2) metrics to monitor, (3) any constraints on knobs and (4) the goal to meet. The goal is defined as a constrained optimization problem (COP) in GOAL's DSL (ğ 5.3). Before deployment, the model builder (ğ 4.3) samples configurations from the compiled AdaptSpec and executes the system in those configurations while observing the metrics listed in the AdaptSpec. From these observations the model builder learns a model that estimates changes in metrics as a function of knob configuration. During deployment, the AdaptLog schedules knob configurations to optimally meet the goal according to the model's estimates.
GOAL virtualizes a control theoretic adaptation logic using two key principles: relativity and translation. While typical control systems find absolute values for the knobs they configure, GOAL controls virtual values that represent the necessary change in behaviorÐrelative to the default knob configurationÐthat must be achieved to meet the goals. This virtual value by itself is not useful; it must be translated into a schedule of specific knob configurations. Critically, this translation can be done online once the metrics and knobs are known and the Model Builder (ğ 4.3) has produced the function that estimates metrics given knob configurations. [26]. We use this approach to illustrate a typical way that AdaptLogs are created, specifically building a controller for the qp knob from the CCTV example (ğ3). We begin assuming the original goal: meeting a frame rate constraint with maximum quality. Following [26], we first learn a simple linear model, relating frame rate to qp:
The constant 0.354 is specific to 𝑞𝑝. To meet a target performance, the controller monitors the current performance FPS(𝑡) at time 𝑡 and computes the error with the desired performance FPS 𝑔𝑜𝑎𝑙 : 𝑒 (𝑡) = FPS 𝑔𝑜𝑎𝑙 -FPS(𝑡). With this error and the model from Equation 1, we set qp at time 𝑡 as:
Equation 2 is a simple and efficient AdaptLog, suitable for qp. However, this AdaptLog is not general; it is entirely specific to (1) the constraint metric (frames per second in this example) and (2) the available knobs (qp).
While this example uses a control approach, similar problems occur with other techniques. For example, reinforcement learning (RL) is a popular basis for AdaptLogs [16,64,66,86,89]. However, RL requires a reward function and a set of possible actions; in existing frameworks, the reward is tied to specific metrics, while the actions are tied to sets of specific knobs (e.g., application alternatives for Aeneas [16]). We are not aware of a way to virtualize the actions in RL based AdaptLogs that is both useful for optimization and general with respect to user-defined knobs.
4.1.2 GOAL's Virtualized Control Logic. We now show how subtle changes in the above formulation implement a virtual control signal. The key here is to model relative behavior rather than absolute metrics as in typical control approaches. We then translate that relative behavior into specific knob settings. This formulation provides a layer of indirection. The controller (which only understands relative values) can be implemented independently of any specific knobs or metrics. The additional logic for translating a relative value into specific knobs settings is parameterized by the learned model that enables the translation (ğ 4.1.4).
We begin by noting that a simple equation relates the behavior in any metric 𝑚 at time 𝑡 to a scalar multiple 𝑥𝑢𝑝 (𝑡 -1) of some baseline behavior 𝑚 𝑏𝑎𝑠𝑒 :
Given this relationship, to control metric 𝑚, we first compute the error between the target behavior (𝑚 𝑡𝑎𝑟𝑔𝑒𝑡 , the constraint from the AdaptSpec) and the measured behavior (𝑚(𝑡)):
We can then control the behavior by tuning the 𝑥𝑢𝑝 (𝑡):
Equation 5 looks similar to Equation 2, but instead of a constant appropriate for one knob, Equation 5 is parameterized by the base behavior for this metric; i.e., the metric's expected value in the default knob configuration.
While independent of any specific knobs, this approach is clearly dependent on the base behavior 𝑚 𝑏𝑎𝑠𝑒 for the application in metric 𝑚; i.e., the expected metric value when the application's knobs are all set to their default values. This value will obviously vary from application to application and even as the application runs.
To adapt the controller to the current behavior in metric 𝑚 at runtime, GOAL's Adapt-Log continually estimates 𝑚 𝑏𝑎𝑠𝑒 , using a Kalman Filter [92], an approach used in prior work [52,53]. Thus, if the behavior varies during execution, this estimation compensates and ensures that the constrained metrics can still be controlled. This process is analogous to approximating a nonlinear function (in this case the application's behavior with respect to execution time) with a series of tangent lines, where 𝑚 𝑏𝑎𝑠𝑒 is the tangent's slope. More formally, GOAL's Kalman filter estimates the base behavior at time 𝑡 as 𝑚 𝑏𝑎𝑠𝑒 (𝑡) and uses this estimate in place of 𝑚 𝑏𝑎𝑠𝑒 in Equation 5. GOAL uses a standard Kalman filter formulation:
In this formulation, 𝑘 𝑏 (𝑡) is the Kalman gain for the constrained metric, 𝑚, being controlled. The 𝑚(𝑡) denotes measured behavior of the constrained metric during the last window. The 𝑚 - 𝑏𝑎𝑠𝑒 (𝑡) and 𝑚 𝑏𝑎𝑠𝑒 (𝑡) are the next to last and last estimates of 𝑚 𝑏𝑎𝑠𝑒 . Similarly, 𝑒 - 𝑏 (𝑡) and 𝑒 𝑏 (𝑡) are the next to last and last estimates of the error variance.
The Kalman Filter is useful because it provides optimal estimates of the application workload and is exponentially convergent [17]; i.e, the estimate will converge in a number of iterations proportional to the logarithm of its error. Furthermore, the user or the developer does not need to provide any additional data, these guarantees are provided using data that is available to GOAL during execution.
Even after accounting for workload changes, the virtual 𝑥𝑢𝑝 from Equation 5 is not useful by itself; it must be translated into actual knob configurations. A set of values for knobs can be represented as a vector 𝑘, and a knob configuration is an assignment of a value to each knob component in the vector. For example, our video encoder from Figure 1 has a knob vector with four components (one each for qp, me, numCores and coreFreq), and the default configuration is ⟨30, 1, 1200, 4⟩. Each knob configuration has an expected effect on each metric, as estimated by GOAL's model builder. In our example those metrics are throughput (frame rate), quality, and energy. In addition, the 𝑥𝑢𝑝 signals are continuous while the available knob settings are discrete.
We translate 𝑥𝑢𝑝 from Equation 5to discrete knob configurations by scheduling over time; i.e., spending different amounts of time in knob configurations such that the average over the time period is the desired continuous value. This scheduling problem is formulated as a constrained optimization problem (COP, which is extracted from the AdaptSpec by GOAL's compiler) where the 𝑥𝑢𝑝 value is the constraint to be met and the decision variables are the time to spend in the knob configuration vectors:
Here 𝑇 is the time window (defaults to 40 but can be set using an environment variable) over which to schedule, 𝑇 𝑘 is the time to spend in the 𝑘th knob configuration, and x𝑢𝑝 𝑘 is the expected 𝑥𝑢𝑝 for 𝑘 (from GOAL's model builder ğ4.3). 𝐹 (𝑘) is an objective function over knobs defined in the AdaptSpec and extracted by the compiler. For example, in the CCTV application (ğ 3), the objective on line power is to maximize quality. Equation 8 requires that the average of all configurations' predicted x𝑢𝑝 𝑘 values come out to the desired 𝑥𝑢𝑝 (𝑡) value, while Equation 9 requires that the sum of times spent in each configuration is equal to the total time over which we are scheduling. Equation 10 ensures that there are no negative time values. The controller sets the virtual 𝑥𝑢𝑝 (𝑡) to ensure the AdaptSpec's constraint is met, and this optimization problem ensures that virtual signal is translated into specific knob settings to deliver the desired 𝑥𝑢𝑝.
4.1.5 Handling Non-Linear Behavior. GOAL's Adapt-Log uses a linear control model (Equation 5) and solves a linear optimization problem (Equations 7ś10). Of course, most computer systems will exhibit non-linear behavior, especially when combining knobs. Thus, we discuss why this formulation suffices to handle non-linearities. Note the adaptive control (ğ 4.1.3) approximates non-linear shifts in application behavior over time. We therefore focus on non-linear interactions in knob behavior. For example, the performance of a knob configuration is likely a non-linear function of each component knob in the configuration. The key intuition is that Equations 7ś10 transform a non-linear optimization over the space of all knobs into a linear problem over an exponential search space. Fortunately, however, the problem structure makes it practical to solve.
GOAL's model builder estimates the x𝑢𝑝 𝑘 values for each knob configuration. Given that 𝑘 here is a vector of knob configurations, the total size of the configurations space is the cross product of all allowable knob settings. So, while the optimization problem in the previous section is linear, there is a nonlinear number of decision variables (the times to spend in each configuration).
However, there are only two non-trivial constraints (Equations 8 and 9). By the duality of optimization problems there is an optimal solution where exactly two of the configurations are allocated non-zero time [14]. Furthermore, those two configurations correspond to two configurations on the convex hull of the tradeoff space represented by the values of 𝐹 and 𝑥𝑢𝑝. For example, if the goal is to meet a performance constraint (𝑥𝑢𝑝) and optimize accuracy (𝐹 ), then the optimal solution will involve two configurations on the optimal frontier of performance and accuracy; specifically, the two configurations whose estimated x𝑢𝑝 𝑘 values are just below and just above the target 𝑥𝑢𝑝 (𝑡) [14]. Those two configurations can easily be found from a lookup table, so GOAL's Glue takes the model from the model builder and the AdaptSpec from the compiler and forms a lookup table that considers only the Pareto-optimal tradeoffs in the objective and constraint metrics. Sorting into the Pareto-optimal points can still be expensive (O(|𝑘 | log(|𝑘 |)), but is only done when a new AdaptSpec is made available. We evaluate the practical overhead in ğ 7.3 and ğ 7.8.
The most important guarantee is that the system converges to the constraint. Unlike AdaptLogs based on learning methods such as RL or Bayesian Optimization which do not provide guarantees of convergence to constraint, GOAL's AdaptLog uses adaptive control. It thus inherits the formal control theoretic guarantees of a typical control system [40]. GOAL's Adapt-Log will converge provided that the estimated base behavior 𝑚 𝑏𝑎𝑠𝑒 (𝑡) and the predicted speedups x𝑢𝑝 𝑘 are within a factor of 2 of their true values. This analysis is based on straightforward application of control theory [26]. Furthermore, even if the base behavior estimation is incorrect momentarily, the Kalman filter is exponentially convergent in error, meaning that estimate will be corrected in a logarithmic number of iterations. We evaluate GOAL's empirical error tolerance (ğ 7.6) and find that GOAL's practical behavior matches the theoretical analysis: GOAL tolerates extremely large overestimations of 𝑥𝑢𝑝 and tolerates under-estimations up to a factor of 0.55; e.g., predicting 16.5 frames per second when the true behavior is 30. This robustness is yet another reason we favor a control theoretic formulation for GOAL's Adapt-Log and it is consistent with prior work that shows adaptive control techniques do a better job of meeting operating constraints than learning-based techniques [61].
4.1.7 Connecting with the Rest of GOAL. GOAL's virtualized adaptation logic requires the following parameters to be supplied by the rest of the GOAL runtime:
• Target behavior 𝑚 𝑡𝑎𝑟𝑔𝑒𝑡 : Users specify this value as a constraint in their AdaptSpec and it is extracted by the JIT compiler (ğ 4.2). • Objective function 𝐹 : This too is provided by the user in the AdaptSpec, extracted by the compiler. • Expected behavior for target metrics ( x𝑢𝑝 𝑘 ): These values are stored in lookup tables, dynamically constructed by the runtime using the model learned using the model builder (ğ 4.3). • Schedule window (𝑇 ): This value is the window parameter to GOAL's optimize method. 𝑇 is provided to the AdaptLog at initialization. • Measured Behavior (𝑚(𝑡)): These measurements are provided by the runtime. This parameterized AdaptLog is general and dynamic. It is general because it works with any knobs and measures that can be specified using GOAL. It is dynamic because the runtime can rapidly change the AdaptLog by simply passing in new parameters.
The GOAL compiler extracts the following from the Adapt-Spec: (1) a list of metrics, (2) a list of all knob configurations, (3) knob constraints and (4) the goal, which includes 𝑚, 𝑚 𝑡𝑎𝑟𝑔𝑒𝑡 and 𝐹 (ğ 4.1.7). All values except for 𝐹 are used to initialize the GOAL runtime and interpret the model learned by the model builder. However, 𝐹 needs to be evaluated repeatedly when computing schedules as it is the objective function to optimize. 𝐹 cannot be precomputed because it might be an arithmetic expression over several metrics. Therefore, we adopt a two-step evaluation approach.
In the first step, all aforementioned objects from the Adapt-Spec's abstract syntax tree are translated to Swift objects using the technique proposed by Carrette et al [18]. All configurations from the extracted list are converted into knob configurations objects. A knob configuration is an object with an apply method, that sets the application and system level knobs to their corresponding values. These objects correspond to the 𝑘 from Equations 7ś10. The 𝑚 and knob constraints are used to make a lookup table containing the x𝑢𝑝 𝑘 and a configuration object for configurations, 𝑘, that meet all knob constraints. 𝐹 is translated into a Swift closure so that it can be executed by the AdaptLog with low overhead while computing schedules. In the second step, the AdaptLog continually executes the aforementioned closureÐonce the observed values for each measure are availableÐto evaluate 𝐹 as it produces the knob schedule. During execution, a GOAL application can modify the AdaptSpec which triggers recompilation (starting over from the first step).
GOAL's model builder operates in two modes. In the firstÐ pre-deploymentÐit runs user-specified test workloads and measures how changes in knobs cause changes in metrics. Specifically, it executes a sampled subset of all knob configurations and estimates the metrics for all allowable knob configurations. The model builder then learns the model using this collected data by using linear regression to compute a piecewise linear model representing the expected behavior for a metric given a knob configuration. In the second modeÐduring deploymentÐthe model builder interprets and uses the learned model to predict the impact of particular knob configurations on all metrics. Prior work could be used to replace our learner with more accurate or efficient learners [20,21,23]. However, our empirical evaluation shows that GOAL's control system is robust to substantial errors in profiling (ğ 7.6), so we use piecewise linear models as a proof of concept and leave the investigation of more advanced learning methods to future work.
While GOAL provides significant advantages over prior work, there are several aspects that deserve further discussion.
Foremost, GOAL can only manage goals that can be expressed in terms of quantifiable measures that can be used by the adaptation logic to make adaptation decisions.
GOAL's AdaptLog handles non-linear, non-convex optimization problems by exploiting problem structure and Pareto-optimality to schedule combinations of knob configurations (ğ 4.1.5). This approach works because there are a small number of possible constraints. Essentially, we have transformed a problem that would be exponential in the space of possible knob configurations into a problem that is exponential in the number of constrained metrics. In practice, we believe this is a reasonable tradeoff because there are typically many knobs that affect one constraint and there is usually only a small number of metrics for which there is required behavior. Thus, the number of constraints will be much, much smaller than the number of possible knob configurations.
GOAL actuates hardware-specific knobs on the system's behalf. While it is easy to manipulate some hardware platform specific knobs (e.g., the core usage), others (e.g., DVFS frequency) require special permissions. Hence, GOAL systems may require elevated privileges to manipulate certain knobs. ğ 7.5 shows that system and application knobs can be split into multiple modules, however.
As a proof of concept, GOAL's semantics currently only support discrete knobs. Interesting future work would be assessing the benefits of continuous knobs.
We implement GOAL as an extension to Apple's Swift [5]. GOAL consists of ∼9.5K lines of code written in a combination of Swift and C, not including third party libraries.
At a high-level, The GOAL library provides a type (Knob), and two functions (measure and optimize) to create an adaptive application. GOAL provides three additional functions: restrict, control and intend to facilitate meta-adaptation. Together these functions permit dynamic modification of the entire AdaptSpec. The semantics of Knob, optimize and intend are described in the example (ğ 3.2).
To facilitate meta-adaptation, intend can be used to modify goals, as shown in the CCTV example. Other scenarios might require manipulating knobs and knob ranges, so GOAL's Knob type also provides restrict and control methods. restrict explicitly defines a range of values for a particular Knob. The runtime uses this range to constrain the configuration space available for adaptation. Calling the method without any arguments fixes the Knob to the value it had at the time of the method call. The control method removes any limits from previous calls to restrict.
Table 2 provides a more detailed description of the GOAL library API.
In large computing systems, multiple developers might want to independently develop adaptive modules and GOAL supports this by allowing multiple optimize calls. However, the sets of knobs used by different optimize calls have to be disjoint and the GOAL runtime will throw an error if this is not the case. After initialization, the runtime manages execution and actuates knobs of each optimize independently.
During execution, one module might modify a knob that affects a metric monitored by another module. For example, a module might meet a power goal by lowering clock frequency and thus reduce throughput in a different module. The base speed of the latter module will thus be underestimated. However, GOAL's adaptive control (ğ 4.1.3) will observe and account for this change. In this example, the runtime's base speed estimation will update to account for Function/Method Prototype Description Knob(name: String, initValue: Double)
Constructor for a knob object that will be actuated during execution to meet specified goal. Knob::get() Method to retrieve the current value of the knob.
Method to tell the runtime to only use values from the provided values argument to meet the goal. If no values is provided, then the knob is fixed to value from when the method was called. Knob::control()
Method to remove all value restrictions for the knob imposed using Knob::restrict. measure(name: String, value: Double) Function to report the observed value of a metric to the runtime. The stringified name is required to identify metric for which the value is being reported. optimize(name: String, knobs: [Knob], loopBody: Fn())
Function to initialize and repeatedly run code given in loopBody while actuating given knobs to meet the goal. In case of multiple optimize blocks, each is given a unique name. intend(to: Enum[.minimize | .maximize],
objective: String, suchThat: [(measure: String goal: Double)])
Function to modify the active goal. Using the function we tell the runtime to maximize or minimize the objective while meeting the constraint provided using the suchThat argument. . GOAL Adaptation Specification Language Semantics the lowered frequency. GOAL will meet goals of all modules if they are noncompeting (i.e., GOAL cannot constrain system power in one module and minimize it in another). Supporting competing goals is an open research problem in adaptive computing. Having language support could make this problem easier and we leave that to future work.
Figure 5 shows the general template and syntax of GOAL's adaptation specification language. Concretely, An AdaptSpec consists of a constrained optimization problem (COP), the metrics to monitor and the knobs along with their valid values that can be used to meet the COP. Finally, it may also contain an optional section that defines additional constraints on the knob values. Goal This section encodes a COP, expressing required application behavior in terms of its metrics. The goal has five parts:
• The OptimizationType, can be either min or max.
• The Objective, an expression on measures.
• The Constraint, a metric (latency in our example) that is associated with constraints. • The Target, the constraint value (30.0 seconds per iteration in our example). Measures This section declares quantifiable metrics like latency, bitrate, etc., that should be observed by the runtime. The metrics are declared as a MetricList which is a newline separated list of the form 'metric name: datatype'.
Currently, metrics datatype may only have the Double type, but any totally ordered type that supports the operations used in the objective function could work. Knobs This section defines the available configuration space as KnobList which is a newline separated list of the form 'knob name = [ values ]'. Each entry is a knob definition which consists of a name, a range expression that evaluates to a list of constants, and a reference value. The name associates the knob definition with a Knob instance in the application. The list of Knobs in the AdaptSpec can be a subset of the Knobs from the code. The runtime will only use the Knobs defined in the AdaptSpec during execution. For all the Knobs not defined in the AdaptSpec, the runtime will only use the reference value in the code. Reference values in the AdaptSpec override those passed to the knob constructor. Finally, developers can optionally define a knob constraint: an arbitrary Boolean expression over the knobs. GOAL's runtime then filters out any configurations that violate these knob constraints before passing the model to the AdaptLog.
We evaluate the following:
• Generality: Can GOAL support a wide range of metrics and knobs while meeting goals as well as prior approaches designed for specific goals and knobs? • Dynamism: When meta-adaptation is performed, does GOAL converge to the new AdaptSpec while providing near-optimal behavior for the objective function? • Robustness: Does GOAL reliably meet goals even in the face of multi-module adaptation, errors in the learned model, and time varying workloads? This section details the applications, platforms, points of comparison, and metrics used to evaluate these properties.
We implement 7 adaptive applications from prior work and then augment them to perform meta-adaptation. We start each with an AdaptSpec equivalent to one used in existing literature. At runtime, however, we change the goals or knobs. Table 3 shows the details, including the number of application and system knobs, the initial objective and constraint, and the required meta-adaptation. The applications cover a wide range of system and application knobs, metrics, and goals; and they exhibit nonlinear knob interactions.
To further demonstrate generality, we use two system platforms with distinct knobs. Four applications target an embedded system: an ARMv7 based ODROID-XU3 (Exynos5422) with 2GB of RAM, running Ubuntu 16.04 (GNU/ Linux 3.10). Three target a server: an x86 (Intel i7-6700) with 8GB of RAM, running Ubuntu 18.04 (GNU/Linux 5.30). All use multithreading equal to the core count.
We compare GOAL to prior approaches including:
• Linear Control: This approach uses a single linear control model for all applications [40]. • Application-specific AdaptLogs: Using prior work, we synthesize a specialized AdaptLog for each application's specific AdaptSpec [26]. This approach can meet each application's initial AdaptSpec, but not the new one created through meta-adaptation. • Multiple Application-specific AdaptLogs: We synthesize a specialized AdaptLog for each application's AdaptSpecs both before and after meta-adaptation. At runtime, we perform meta-adaptation by shutting down the first AdaptLog and initializing the second. This approach is clearly impractical as users must know the new goals and knobs ahead of time. • Oracle: We exhaustively search the configuration space to find the best knob configuration for all AdaptSpecs.
We quantify the approaches using the following metrics:
• Mean Absolute Percentage Error (MAPE): Each application's AdaptSpec has a constraint for a particular metric. To calculate MAPE, at each call to optimize() we measure the absolute error between the constraint and the achieved metric, then take the mean over all iterations. Lower is better. • Normalized Performance: The AdaptSpecs also specify an objective, or a metric to be optimized. To measure how well GOAL optimizes the objectives we normalize to the Oracle's performance. Higher is better as the oracle will achieve an optimum performance of 1. • Iterations until Convergence: We measure the iterations required to converge to the goal after metaadaptation. This metric will be used to compare GOAL to the approach that pre-synthesizes multiple, application specific AdaptLogs. Lower is better as it represents faster convergence after meta-adaptation.
This section evaluates key aspects of GOAL, specifically: 1. Does GOAL meet user-defined constraints across a range of knobs and metrics? 2. Does GOAL achieve near-optimal objectives when performing meta-adaptation? 3. Does GOAL converge quickly after meta-adaptation? 4. How much user effort does GOAL require? 5. Does GOAL support multi-module adaptation? 6. Is GOAL robust to errors in modeling? 7. Is GOAL robust to large changes in workload? 8. How much overhead does GOAL incur?
For each, we measure the MAPE for the application-specified constraints (as listed in Table 3). Figure 6 shows the results with MAPE on the vertical axis, applications on the horizontal axis, and a bar for each AdaptLog. Due to the complicated and varied application behavior, the Linear Controller fails to reliably meet the constraint exhibiting a mean MAPE of ~29%. However, both GOAL and Application-specific AdaptLogs meet the goal reliably, exhibiting less that 4% MAPE. We note that the results for the Application-specific AdaptLogs and Multiple Application-specific AdaptLogs are the same for this experiment, so we omit the latter for clarity. In summary, GOAL provides a single AdaptLog implementation that generalizes across a range of metrics and knobs while achieving errors comparable to approaches that do not generalize.
We now consider the normalized performance when each application performs meta-adaptation, changing its Adapt-Specs as listed in Table 3. We report results for applicationspecific AdaptLogs, Multiple application-specific AdaptLogs, GOAL, and the Oracle. We omit the Linear Controller results because it fails to meet the constraints (as shown in the previous section), so its performance is not meaningful. Figure 7 shows the results. The single Application-specific AdaptLog has poor performance because it must use the initial AdaptSpec throughout execution. However, the versions using Multiple application-specific AdaptLogs and GOAL improve on relevant metrics by 1.69× over application specific AdaptLogs, while achieving ~93.7% of the Oracle's performance.
These results show that when an application's requirements change, the application performs suboptimally with prior work that does not support meta-adaptation. GOAL, however, performs as well as an approach that knows how the requirements will change ahead of time and synthesizes multiple application-specific AdaptLogs for both requirements. This demonstrates GOAL's support for dynamic changes in adaptation specifications, as it performs near optimally when applications trigger meta-adaptation.
The previous section shows that GOAL's average performance is equivalent to an approach that is custom built for a specific AdaptSpec. We now show that GOAL provides an additional benefit by measuring how quickly each approach (Multiple Application-specific AdaptLogs and GOAL) reconverges to the new constraint after meta-adaptation. Figure 8 shows the results with iterations required for convergence on the vertical axis. GOAL converges ~2.14× faster than using multiple application-specific AdaptLogs. The application-specific approach takes longer due to the expense of destroying the old AdaptLog and initializing the new one. This process incurs two sources of overhead: (1) the time required to perform these costly operations and (2) a loss of accumulated history of observed metric values, which must be collected by the new AdaptLog from scratch. Such history is crucial for any control or learning based AdaptLog and without it, convergence is delayed. This ability to retain history across multiple metrics and knobs is an advantage to a single, general adaptation framework like GOAL. GOAL converges quicker to the new goals because the runtime tracks all relevant metrics at all times, ensuring that no data is lost when performing meta-adaptation. These results support the claim of dynamism by showing that GOAL converges much quicker than combining existing AdaptLogs without explicit support for meta-adaptation.
We count the lines of code that need to be added/modified to the original non-adaptive versions of the applications. We do not count lines of code to implement the AdaptLog. Here we only compare GOAL and Multiple Application-specific AdaptLogs because these are the only two approaches which can implement meta-adaptation.
Figure 9 shows the number of lines added/modified on the vertical axis. Multiple-application specific AdaptLogs require around 1.92× more changes than GOAL. These results show that GOAL's interface facilitates adding adaptation in a wide range of applications without significant development effort, and much less than trying to dynamically switch between prior approaches. Finally, note that GOAL can support any type of meta-adaptation, while prior work takes more effort and yet only supports the AdaptSpecs specific to each application. Results so far have used a single optimize() call per application. However, in many scenarios, multiple developers may each want to contribute a module with its own optimize() method (as described in ğ 5.2). Here, we evaluate how well GOAL performs in such multi-module adaptation scenarios.
Specifically, for each application, we implement two modules: one for the application knobs and one for system knobs. The application modules meet the constraints from Table 3. The system modules meet a power constraint while delivering maximum performance. The challenge here is that both modules affect performance, meaning that even though the knobs are independent they still affect each other.
We then measure the MAPE for both the application and system modules. Figure 10 shows the results. Both the application and system modules meet their constraints reliably, exhibiting a low mean error of ~4%. These results show that GOAL effectively deals with complex, multi-module adaptation, a capability that other approaches do not support.
As mentioned in ğ 4.3, GOAL development includes modeling the application. We now evaluate how sensitive GOAL is to possible errors in the model learning step. For each application, we introduce errors by scaling all the model's estimates (i.e., the x𝑢𝑝 𝑘 values used in Equations 8ś10) by an error factor and perform the same experiments as above.
Figure 11 shows two charts with MAPE (vertical axis) for each application given a model that is scaled by the value on the horizontal axis; the left chart shows under-estimates, the right chart shows over-estimates. For underestimated models, GOAL performs reliably in the presence of large errors, producing a MAPE that stays relatively low at a value that is roughly equivalent to results from above (Figure 6) until scaled down to 0.55. Thus, the model has to be significantly underestimated before GOAL fails to meet its constraints. In contrast, MAPE is not impacted by overestimated models. This suggests that GOAL can support a wide range of learners for model building, but they should be biased slightly towards overestimates. Overall, these results illustrate that GOAL is robust to substantial errors in modeling.
Adaptive systems, in general, should meet goals despite unpredictable, external disturbances. We now demonstrate that GOAL provides this capability by adapting to different scenes for a video encoder. The first is a high-motion soccer game and the second is a low-motion news cast. Without adaptationÐi.e., with a constant knob configurationÐthe scene change causes significant changes in throughput because different levels of motion require significantly different amounts of work to encode.
Figure 12 shows the power and throughput for three different video encoder implementations: (1) Non-Adaptive, using the fixed, default knob configuration; (2) Linear Controller, similar to the one above, but now we carefully calibrate the control to meet the goal for the initial scene, and (3) GOAL. The different colored regions show two different input scenes. The impact of scene changes can be seen in the execution of Non-adaptive whose throughput and power change from scene to scene. Linear Controller and GOAL both have a throughput constraint of 30.0 frames/s. The changing workload negatively impacts Linear Controller, which, is stable only for the first scene, but then starts to oscillate after the scene change and overall has a high MAPE of 22.5%. However, GOAL copes with these changes and meets the goal reliably during all scenes, exhibiting a much lower MAPE of 2.8%. The Linear Controller fails because the difference in the base throughput (𝑚 𝑏𝑎𝑠𝑒 from Equation 5) is over a factor of 2× different from scene to scene. GOAL can handle this change, however, because it continually estimates the time-varying base behavior to account for these types of changes. These results further demonstrate the value of GOAL's adaptive control approach that adjusts the control to handle non-linearities in application workload.(ğ 4.1.2).
We evaluate the overhead of performing adaptation and metaadaptation in terms of the geometric mean of times required to perform essential operations using GOAL.
Adaptation only requires computing schedules using the AdaptLog (Equations 4ś10). The time to compute a single schedule in the embedded applications is ~0.68ms, while for server applications it is ~0.045ms. Obviously, these numbers are highly influenced by the underlying hardware. Schedules are only computed once per window (ğ 4.1.7). Hence, the total overhead per iteration becomes negligible.
Meta-adaptation requires calls to intend, restrict and control. The time required for intend in the embedded applications is ~5.14ms, while in the server applications it is ~1.07ms. The times for calls to restrict and control in the embedded applications is ~11.79ms and ~8.31ms, respectively. These times in the server applications are ~0.68ms and ~0.55ms, respectively. This overhead includes the time to recompile the AdaptSpec and compute the new lookup table (ğ 4.1.7). GOAL adjusts the goal for the window immediately after meta-adaptation is performed. For all subsequent windows, the goal is set to the value in the AdaptSpecs. This means that, GOAL accounts for its own effect on metrics and ensures constraints are met despite GOAL's own overhead. It should be noted that applications are expected to perform meta-adaptation far less frequently than they compute schedules. These results show that GOAL incurs low overhead for both adaptation and meta-adaptation.
This work motivates the benefits of supporting general purpose adaptation and meta-adaptation. We implement this idea as GOAL, a first-of-its-kind adaptation framework which, unlike prior work, is not restricted to a particular set of knobs and goals. Instead GOAL uses a virtualized AdaptLog that is parameterized by a model after the developers have declared application knobs and metrics. This allows GOAL applications to define the AdaptSpecs, using wide range of knobs and metrics, and seamlessly modify them during execution. The AdaptLog is, itself, adaptive and therefore robust to adapt to nonlinear behavior and changing workloads and operating conditions. We show that GOAL's general approach handles a diverse range of goals and knobs, while performing just as well as problem specific AdaptLogs. However, when the application requires meta-adaptation, GOAL performs significantly better than prior work. Furthermore, GOAL provides an easy-to-use interface that requires minimal effort to add adaptation and meta-adaptation to applications and even supports applications with multiple, independent adaptive modules. We believe that GOAL's generality, dynamism and robustness goes a long way to fulfilling the requirements of complex emerging systems.