In this TTC case, we describe the computation of an optimal mapping from software implementations to hardware components for a given set of user requests as a model transformation problem. Further, contracts specify dependencies between components in terms of non-functional properties. Di erent approaches of this case can be compared in terms of their validity, performance, scalability and, quality w.r.t. the real optimal deployment.
One of the goals of software engineering is to enable the development of e cient software, i.e., software providing the best possible utility for the least possible cost. By now, this goal has been addressed at several levels of abstraction: from compiler construction [Kil73] in the 70s to cloud computing [BAB12].
To optimize the tradeo between utility and cost, at least two interrelated standard problems are typically addressed:
Resource allocation (also known as register allocation in compilers), i.e., the mapping of software implementations to hardware components leading to the least cost Variant selection (also known as instruction selection in compilers), i.e., selecting the software implementation which provides the best utility
These problems have been investigated for compilers since almost 50 years, where they are called code generator optimizations. However, both problems are strongly intertwined. Together, they form an NP-complete problem with exponential complexity, but typically are carried out in phases [WG12]. Considering both problems to be independent from each other allows to use e cient optimization approaches, running in polynomial time [HG06]. But, an immanent problem of solving variant selection and resource allocation in isolation is that invalid solutions might result. Hence, still new approaches to compute solutions for the joint selection and mapping problem, are required.
This case provides a generic metamodel for the combined problem of resource allocation and variant selection. Both problems are interrelated by user requests specifying minimum requirements on the non-functional properties provided (i.e., minimum utility), whilst searching for a selection and mapping both maximizing utility and minimizing cost. To show progress over state of the art, these approaches need to be evaluated w.r.t. their correctness, performance, solution quality and scalability. Correctness denotes that only solutions not violating the minimum requirements of the users are considered valid. The performance of an approach describes how fast Copyright c by the paper's authors. Copying permitted for private and academic purposes.
*
ResourceType * container: boolean *
0..1 General::Instance a solution can be computed for a given problem. The solution quality quanti es how close the computed solution is to the optimal solution. Finally, scalability is represented by the size of the largest problem, for which a valid solution can still be computed.
We describe a reference implementation using a reference attribute grammar as metamodel [BKWA11] to translate the above described selection and mapping problem into an integer linear program, whose solution is then translated into a deployment description. 2
In the following, we rst provide a detailed description of the case by specifying the metamodel shared by both, source and target models, thus resulting in an endogenous transformation. Afterwards, in Section 2.6, we give an overview of our reference implementation.
As mentioned in the previous section, the problem to be solved is selecting variants of software components and a mapping of those to suitable hardware resources based on user requests. To adequately cover this problem, we designed a combined metamodel comprising four views: hardware, software, expressions, and their combination. 2.1
Figure 2 shows the SoftwareModel with its main element Component representing a certain functionality (e.g., sorting). Implementations provide this functionality, requiring other components and/or resources to
General::Property
* * ful ll their work. For example, a software component sort could have the implementations Radix sort and Counting sort, where the component speci es that it requires a ReadFile and a WriteFile component to read the unordered list and write the ordered list. The in- and output components have di erent implementations, too, as sketched in Figure 4b. A ComponentRequirement states that the referenced component is called during the execution of this implementation. Requirements for components and resources are speci ed on type level (i.e., refer to components and resource types). Their relation to the runtime model is expressed by referencing a set of Instances that are either Resources or instantiated Implementations. Implementations have a contract speci ed as a number of Clauses describing provisions to and requirements on required instances. A clause comprises a left hand side (LHS), which is a designator, a comparator (one of =; 6=; ; <; >; ), a type (provision or requirement), and a right hand side (RHS), which is an expression. For example, the predicted minimum runtime of an implementation can be expressed as a provision clause coupled with a requirement clause specifying a certain CPU frequency for which the provision holds. An example contract is shown in Figure 4b. In this example contract, requirements on components as well as resource types are declared (cf. lines 8-11). Later, in line 16, a provision clause is de ned with energy as the SoftwareDesignator for the left hand side, EQ as ClauseComparator and an AddExpression as right hand side. 2.4
The class Solution is to be computed by the solvers. It contains a number of Assignment, each selecting one implementation of the given problem model and assigning every instance in the contract of the implementation to either another assignment or a resource. With this, a concrete implementation is selected for each required component along with their required resources. The value of topLevel is true if the assignment corresponds to a requested component. An example solution is shown in Figure 6.
A solution is valid, if for each request a) an implementation for the target component is deployed, b) an implementation is deployed for each required component, c) all required (non-functional) property clauses are ful lled (including the request constraints), and d) at most one implementation is deployed on each resource. A solution is optimal, if it is valid and no other solution has a better objective value. Model
Request name: String (a) General View.
(b) Solution Metamodel.
To preserve readability, the following inheritance relation was not included in the Figures 1a, 1b, 2 and 3a: All of Instance, ResourceType, Resource, Component, Implementation, Property, MetaParameter inherit from the class ModelElement, which de nes a single attribute \Name" of type String, to uniquely identify those model elements, e.g., while parsing the input model. 2.6
This section describes the reference implementation for the presented problem based on an attribute grammarbased model-to-text transformation and integer linear programming (ILP). The approach is a variant of MultiQuality Auto-Tuning [GKP+14, SGAB16], which directly uses the metamodel presented in the previous subsection.
The general approach of our reference implementation to the case is depicted in Figure 5. We rst transform the problem model into an integer linear program, whose solution is computed using a standard solver. Then, we interpret the solution of the solver, and reconstruct a Solution object as described in Figure 3b.
However, there are restrictions on the complexity of the model: Only ; ; = are permitted as expression clause comparators, resource types can only be nested to a depth of one, and no component may be required more than once per request. Models generated for this case as described in Section 3.1 adhere to those restrictions.
The textual representation of the selection and mapping problem as an ILP comprises an objective function, a set of linear constraints and a set of variables used both in the objective function and the constraints [Man87].
Each combination of a request, resource and implementation is represented by one binary variable in the ILP stating whether or not this implementation is deployed on that resource for the respective request.
The objective function is represented as minimization of either a weighted sum or the maximum of all variables, depending on Objective in the current model. The weights for each variable are the e ect the decision represented by the respective variable has on a selected non-functional property. If, for example, the objective is to optimize the performance, the weights represent the e ect on the total runtime.
Furthermore, the ILP comprises three types of constraints: Architectural constraints ensure that each request is ful lled, exactly one implementation per component is chosen and not more than one implementation is deployed on one resource.
The general task is to solve the interleaved problems of software variant selection and hardware mapping. To ease implementing an approach to solve this problem, we provide a problem generator (cf. Section 3.1), a concrete set of example problems to be solved (cf. Section 3.2) and a benchmark environment (cf. Section 3.3). The underlying metamodel is built using JastAdd [EH07], a tool to de ne Reference Attribute Grammars. Once the de nitions are parsed and built, the resulting Java classes can be used normally without any dependencies. Model elements can be manipulated using Java methods, however it is possible that caches of results from attribute evaluation are updated automatically upon changes.
RAG-based Model-2-Text Transformation ILP
Problem Model
2 Standard ILP
Solver
ILP Solution
Interpretation Number of variants per software component depth of the component dependency tree Resource ratio of the minimally required resources Value Range 1; : : : ; cmax 1; : : : ; n 0; : : : ; dmax 1; 1:1; : : : ; hmax n 3.1
For the presented case, we developed a generator that is able to create random models of arbitrary size. However, the software and hardware component structures are xed to ensure comparability and some level of realism. The resource types de ned in the hardware model are designed to resemble regular computer hardware. A compute node consists of one or more CPUs, RAM memory, disk, and a networking interface. Each of these components has properties that specify their capabilities. Figure 4a shows the resource types used in the case and their respective properties. The number of resources generated can be speci ed as a parameter represented as the ratio r of the minimally required resources.
The software model has a simple tree structure. That is, all requests have a single meta-parameter (size), refer to the same software component and each software component may require other components.
While the generator is able to create sparse trees, for simplicity and comparability reasons, we only generate dense trees with a xed branching factor of two, such that all possible solutions ful lling a request require the same number of software components. For all software components, one property, quality, is speci ed. Requirements and provisions of this property are randomly generated for each implementation.
Finally, for each software component the requirement of exactly one container is generated. Clauses in every implementation use the meta-parameter size as part of a randomly generated formula (i.e., expression). For approaches not directly using Java, our benchmark framework o ers the ability to implement visitor methods that are called by the problem generation and, thus, can be used to create another problem model representation. Alternatively, approaches can reuse the existing concrete syntax to write out the model. 3.2
To test the scalability of an approach, we generate a set of di erent problems. The di culty of a problem is scaled using a set of parameters as shown in Table 1. Naturally, the number of software variants (per software component) and the number of requests have a lower impact on the problem complexity than the depth of the component tree and the number of available resources. Since the number of problems that can be generated within the given parameter ranges is large, we propose a set of example problems listed in Table 2.
In addition to the four above mentioned parameters, the generator takes a seed as a fth parameter to ensure that for the same seed and same values for the other four parameters always the exact same problem is generated. 3.3
To simplify benchmarking, an easily adoptable process has been de ned. Our framework can be used to run the scenarios presented in Section 3.2. If the framework is used, results and timing data are automatically taken and The task is to solve the given set of scenarios listed in Table 2. Since the size of the scenarios varies, it might not be possible to nd the optimal solution, so any valid solution su ces.
The solution is to be represented within the original problem model by instantiating the respective classes (i.e., Assignment, ComponentMapping and HardwareMapping).
A possible textual representation of the solutions is shown in Figure 6. The depicted exemplary solution is to be interpreted as follows. For the request request0, the CountingSort implementation of Sort shall be used. This con guration is composed of one hardware mapping (lines 4-9) and two variant selections (lines 11-26). The hardware mapping speci es that the designator (i.e., the variable) compute resource 0 is to be mapped to the physical resource named resource0. Moreover, the designators like ram 1 de ned within the scope of compute resource 0 are mapped to the respective physical subresources. The variant selections specify that for request 0 the BufferedInputStream implementation of ReadFile and the RandomAccessFile implementation of WriteFile shall be used. For both variant selections, the respective mapping to resources is described analogously to the example in lines 4-9.
Note, that the solution not only contains the information which implementation is assigned to which hardware resources, but also how the software instances from the contract are mapped; thus, the solution describes a tree structure.
In addition to the found solution, the approach is to be evaluated as described in the following section. 4
To evaluate approaches for the above described case, the following three criteria shall be used: performance, solution quality, and scalability. While solution quality is measured on an ordinal scale, performance and scalability are measured on a rational scale. Both solution quality and performance are considered separately for each scenario, while scalability is de ned globally over all scenarios. To avoid di erences between the measures taken for evaluation due to di erent hardware, we encourage the authors to evaluate their approach in the SHARE environment4. In the following, we describe the criteria to be investigated for an approach and specify the metrics to be used. 4.1
To assess the performance of a presented approach, the time required to compute a solution for a given problem model shall be measured. Approaches translating the problem model to another technical space, must include
compute_resource_0 -> resource0 { ram_1 -> ram0 network_1 -> network0 cpu_0 -> cpu0_0 disk_1 -> disk0 ReadFile -> BufferedInputStream { compute_resource_0 -> resource1 { disk_1 -> disk1 ram_1 -> ram1 network_1 -> network1 cpu_0 -> cpu1_0 the times required to transform the problem and to interpret the solution. For this, approaches can write out the solution to disk and use the benchmark framework to check it against the initial model. As an example, for the reference implementation, the times needed to transform the model to an ILP representation, to solve the ILP and to interpret the ILP solution are summed up.
The value for this criterion is to be represented as a measured execution time. For each measured execution time, its median and standard deviation have to be shown. 4.2
The most important criterion to be met by an approach to our case is the validity of the computed solution(s). For this, the computed solutions have to be checked against the constraints described in the problem model. However, the selection and mapping problem often has multiple valid solutions, i.e., only the constraints are ful lled by the respective solutions. To compare di erent approaches, rst the validity of the computed solution is checked. Failure in this check results in zero points. All valid solutions are then compared to each other w.r.t. their objective value. The approach that has found the best solution gets the most points, depending on how many approaches exist. Others will get fewer points according to their ranking of objective value. 4.3
Quality-based Selection and Mapping is a combinatorial optimization problem and, hence, computing the best solution with an exact approach leads to a combinatorial explosion, i.e., does not scale. Approximate approaches can trade solution quality for performance and scalability, i.e., by not ensuring that the best solution is found, but maybe a near-optimal one, the solution can be found faster and larger problems can be solved at all.
To compare di erent approaches, their scalability shall be assessed in terms of the above described generator parameters. Using Table 1, the largest solvable scenario class can be determined. Approaches able to solve any problem of the class huge are awarded 4 points, and one point less per unsolvable class (large 3, medium 2 and small 1). Solving only the minimal scenario does not result in points for this category.
This work has been funded by the German Research Foundation within the Collaborative Research Center 912 Highly Adaptive Energy-E cient Computing, within the Research Training Group Role-based Software Infrastructures for continuous-context-sensitive Systems (GRK 1907) and the research project \Rule-Based Invasive Software Composition with Strategic Port-Graph Rewriting" (RISCOS) and by the German Federal Ministry of Education and Research within the project \OpenLicht". [BAB12]
Anton Beloglazov, Jemal Abawajy, and Rajkumar Buyya. Energy-aware resource allocation heuristics for e cient management of data centers for cloud computing. Future Generation Computer Systems, 28(5):755 { 768, 2012. Special Section: Energy e ciency in large-scale distributed systems. [EH07]
Torbjorn Ekman and Gorel Hedin. The JastAdd system|modular extensible compiler construction.
Science of Computer Programming, 69(1):14{26, 2007. 00000. Sebastian Hack and Gerhard Goos. Optimal register allocation for ssa-form programs in polynomial time. Information Processing Letters, 98(4):150 { 155, 2006.
Gary A. Kildall. A uni ed approach to global program optimization. In Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '73, pages 194{206, New York, NY, USA, 1973. ACM.
CPLEX User's Manual. IBM ILOG CPLEX Optimization Studio, 1987. [HG06]