The TTC 2018 case describes the computation of an optimal mapping from software implementations to hardware components for a given set of user requests as a model transformation problem. In this paper, we show a detailed view on the reference solution which uses two main approaches: 1) transformation using attribute grammars and higherorder attributes into an integer linear programming (ILP) speci cation, and 2) solving the ILP resulting in a valid and optimal mapping. We further show evaluation results for the given scenarios.
1 ILP ::= IlpObjective IlpConstraint* IlpVariable* ; 2 TimedOutILP:ILP ::= <Reason:String> ; 3 4 IlpObjective ::= <Kind:IlpObjectiveKind> IlpLeftHandSide ; // IlpObjectiveKind is either MINIMIZE or MAXIMIZE 5 IlpConstraint ::= <Name:String> IlpLeftHandSide <ClauseComparator:ClauseComparator> <RightHandSide:double> ; 6 IlpLeftHandSide ::= IlpTerm* ; 7 IlpTerm ::= <Value:double> <Ref:IlpVariable> ; 8 9 abstract IlpVariable ::= <Name:String> <Request:Request> <Impl:Implementation> <Illegal:boolean> ; 10 IlpAllResourcesVariable:IlpVariable ; 11 IlpMappingVariable:IlpVariable ::= <Resource:Resource> ;
Listing 1: The target model describing an ILP. } // negate the term to move it to the right side for (Resource res : this.getHardwareModel().getResourceList())
reqLhs.addIlpTerm(new IlpTerm(makeNegative(rqClause.evalUsing(request, res)), getIlpVariable(request, impl, res))); result.addIlpConstraint(new IlpConstraint(reqLhs, rqClause.getClauseComparator(), 0));
Listing 2: Negotiation constraint computation. 2.1
An ILP is described by a set of constraints over variables with integer values. Its canonical form is minimize cTx subject to Ax b, x 0, and x 2 Zn where b and c are vectors, A is a coe cient matrix, and x is the solution vector of integer variables. The intermediate model used in this solution is described by the grammar shown in Listing 1. It describes a restricted set of linear programs required in this case: variables are assumed to be binary, so no bounds have to be speci ed.
The basic idea is to use binary variables for denoting the deployment of a software implementation on a hardware resource for a request. The cross product of all variants, resources, and requests yields all possible deployment variables. Additionally, there are binary implementation variables indicating the usage of a certain implementation for a request independent of its deployment. The following constraints are created. 1. Structural Constraints ensure the correct structure and the functional properties of the solution. (a) For every request, there is exactly one variant of the target component chosen. (b) For every component and request pair, there is at most one variant chosen. (c) If a component is selected, its required components must also be selected.
(d) On every resource, there can be at most one deployed component. 2. Contract Negotiation Constraints ensure non-functional requirements of requests and components. (a) The non-functional properties of a request must be met.
(b) The non-functional requirements of required components must be met.
Listing 2 shows the computation of contract negotiation constraint 2b and Listing A shows an example ILP. 2.2 To transform the given problem model into the (intermediate) ILP model, we utilize the concept of attribute grammars using the JastAdd tool. Given a grammar and a set of attribute de nitions, JastAdd produces executable Java code. Each nonterminal of the grammar is represented by a Java class, within which attributes and model navigation code is generated as methods. JastAdd attributes are exposed and invoked like ordinary Java methods, e.g., in line 6 of Listing 2. We de ned attributes ranging from simple ones, such as navigation inside the model or printing parts of the model, to more complex ones, like the evaluation of clauses or the
ILP
(cf. Listing A) ú
External
ILP Solver
ILP AST!Model Data Structure Internal ILP Solver K
Parser
(cf. Listing 4) ú
K
Data Structure Model!AST
(cf. Listing 5)
SW HW
ILP (a) Problem model ! ILP (b) ILP solution ! model solution transformation of the source model to the ILP model. The main motivation for using attributes is the ability to cache their computed values. With that, clauses need only be evaluated once for a certain con guration. The given problem model is transformed into the intermediate model shown in Listing 1 using higher-order attributes [VSK89]: the ILP model is de ned as a subtree of the problem model and is computed by an attribute.
Once the intermediate ILP model is generated, there are two possible ways to get a solution for the ILP. The rst, external way is to transform the model to a textual representation and invoke an external solver which in turn outputs a solution le. Here, the overhead of reading and writing les arises, which can be signi cant for larger models. We use GLPK2 as external solver, but the employment of a standardized ILP notation allows the use of other solvers as well. The second, internal way exploits a JNI binding3 for GLPK, the solver we use. Hence, no le needs to be written, but instead an API is used to construct the internal data structure from the intermediate model, which is straightforward4 because the model already resembles this structure. For both ways, the returned solution needs to be interpreted to construct the solution, i.e., the assignments. This is done by only considering the deployment variables with the value 1 and creating an assignment for each of them. An overview over the entire transformation process from the problem to the solution model is given in Figure 1. 2.3
To illustrate the process, consider the model de ned in Listing 3. There are three resources, one main component targeted by the request and requiring two other components. All components have two implementations each. The external ILP solver transforms this model to the ILP shown in Listing A. One might expect to see more variables in the objective function (line 2). However, during the transformation, some illegal assignments with respect to resource and quality requirements are already discarded, and, thus not show up in the ILP. Further, the constraints can be seen in lines 4-36. Finally, the variables have to be declared as binary variables in the Binaries section in lines 38-54. In this case, the solver nishes successfully, nding an optimal solution with an objective value of 23284:15. Listing 4 shows an extract of the solver output. All variables with a value of 1 are used to construct the solution as shown in Listing 5. 3
To investigate the feasibility of the approach, the implementation was tested with the scenarios provided in the case description [GMSA18]. The measurements were performed on an Intel Xeon E5-2643 machine with 32G of memory using Ubuntu 16.04 with GLPK 4.65 and Oracle Java 1.8.0 181. A maximum solving time of 15 minutes per run was allowed; each scenario was executed ve times with both solver variants. Table 1 shows the median results of the runs. The test results are only shown for the small, medium and large scenario sizes, since on the given hardware, it was not possible to nd valid solutions for the huge scenarios within the given time. The table also shows whether a valid solution has been found and whether the ILP solver can guarantee its optimality. Additionally, time measurements for the two solution steps are given. The generation time speci es the duration of the generation of the ILP including the GLPK API calls in the direct case and the time to write the serialized ILP to disk in the external case. The total solving time speci es the total time it took to generate 2GLPK is available at https://www.gnu.org/software/glpk/ 3The Java-Binding for GLPK is available at http://glpk-java.sourceforge.net/ 4The whole solve method (ILPDirectSolver.solve0) of the internal solver needs about 120 lines of code (excluding logging). o -the-shelf ILP solver. Using this approach, we got valid solutions for eight of the 13 provided scenarios, six
[EH07] of which are optimal. However, for many use cases, our achieved solving times may be too long. If an optimal solution is not required, heuristic approaches may be more adequate for this case.
Finally, the presented solution o ers some opportunities for improvement. A more advanced RAG-based analysis using partial contract evaluation or abstract contract interpretation could decrease both size and complexity of the ILP. Additionally, using a better solver and a meta-optimization of its parameters could be bene cial. This work has been funded by the German Research Foundation within the Collaborative Research Center 912 Highly Adaptive Energy-E cient Computing, 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".
Torbjorn Ekman and Gorel Hedin. The JastAdd system|modular extensible compiler construction.
Science of Computer Programming, 69(1):14{26, 2007. [GMSA18] Sebastian Gotz, Johannes Mey, Rene Schone, and Uwe A mann. Quality-based Software-Selection and Hardware-Mapping as Model Transformation Problem. In Antonio Garcia-Dominguez, Georg Hinkel, and Filip Krikava, editors, Proceedings of the 11th Transformation Tool Contest, a part of the Software Technologies: Applications and Foundations (STAF 2018) federation of conferences, CEUR Workshop Proceedings. CEUR-WS.org, June 2018.
H. H. Vogt, S. D. Swierstra, and M. F. Kuiper. Higher order attribute grammars. In Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, PLDI '89, pages 131{145, New York, NY, USA, 1989. ACM. 1 \ Integer Linear Program in the CPLEX LP Format 2 \ Format Description: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/FileFormats/topics/LP.html 3 4 5 \ Specification of the Objective 6 Minimize 7 energy: +10961.72 rq0#impl_0i0_1i0#res1 +4138.75 rq0#impl_0i1_0i0#res1 +7011.62 rq0#impl_0i1_0i1#res1 +1296.54 rq0#impl_0i1#res0 +17848.86 rq0#impl_0i1_1i0#res2 +17969.64 rq0#impl_0i1_1i0#res0
\ if no resources are valid, the implementation variable is 0 (false) 8 9 10 \ Constraints 11 Subject To 12 13 \ Define implementation variables, specifying if an implementation is selected, i.e, if a resource is mapped to the implementation. 14 \ Resources violating a contract are omitted. 15 rq0_single_impl_0i0: - rq0#impl_0i0 = 0.0 16 rq0_single_impl_0i1: + rq0#impl_0i1#res0 - rq0#impl_0i1 = 0.0 17 rq0_single_impl_0i0_0i0: - rq0#impl_0i0_0i0 = 0.0 18 rq0_single_impl_0i0_0i1: - rq0#impl_0i0_0i1 = 0.0 19 rq0_single_impl_0i0_1i0: + rq0#impl_0i0_1i0#res1 - rq0#impl_0i0_1i0 = 0.0 20 rq0_single_impl_0i0_1i1: - rq0#impl_0i0_1i1 = 0.0 21 rq0_single_impl_0i1_0i0: + rq0#impl_0i1_0i0#res1 - rq0#impl_0i1_0i0 = 0.0 22 rq0_single_impl_0i1_0i1: + rq0#impl_0i1_0i1#res1 - rq0#impl_0i1_0i1 = 0.0 23 rq0_single_impl_0i1_1i0: + rq0#impl_0i1_1i0#res2 + rq0#impl_0i1_1i0#res0 - rq0#impl_0i1_1i0 = 0.0 24 rq0_single_impl_0i1_1i1: - rq0#impl_0i1_1i1 = 0.0 25 26 \ Structural Constraint 1a: ensure the request is fulfilled 27 rq0_target: + rq0#impl_0i0 + rq0#impl_0i1 = 1.0 28 29 \ Structural Constraint 1b: Choose at most one variant per component and request. 30 rq0_opc_component_0: + rq0#impl_0i0 + rq0#impl_0i1 1.0 31 rq0_opc_component_0i0_0: + rq0#impl_0i0_0i0 + rq0#impl_0i0_0i1 1.0 32 rq0_opc_component_0i0_1: + rq0#impl_0i0_1i0 + rq0#impl_0i0_1i1 1.0 33 rq0_opc_component_0i1_0: + rq0#impl_0i1_0i0 + rq0#impl_0i1_0i1 1.0 34 rq0_opc_component_0i1_1: + rq0#impl_0i1_1i0 + rq0#impl_0i1_1i1 1.0 35 36 \ Structural Constraint 1c: ensure the required components of a selected component are also selected 37 rq0_impl_0i0_req_component_0i0_0: + rq0#impl_0i0_0i0 + rq0#impl_0i0_0i1 - rq0#impl_0i0 0.0 38 rq0_impl_0i0_req_component_0i0_1: + rq0#impl_0i0_1i0 + rq0#impl_0i0_1i1 - rq0#impl_0i0 0.0 39 rq0_impl_0i1_req_component_0i1_0: + rq0#impl_0i1_0i0 + rq0#impl_0i1_0i1 - rq0#impl_0i1 0.0 40 rq0_impl_0i1_req_component_0i1_1: + rq0#impl_0i1_1i0 + rq0#impl_0i1_1i1 - rq0#impl_0i1 0.0 41 42 \ Structural Constraint 1d: At most one component per resource. 43 one_on_res0: + rq0#impl_0i1#res0 + rq0#impl_0i1_1i0#res0 1.0 44 one_on_res1: + rq0#impl_0i0_1i0#res1 + rq0#impl_0i1_0i0#res1 + rq0#impl_0i1_0i1#res1 1.0 45 one_on_res2: + rq0#impl_0i1_1i0#res2 1.0 46 47 \ Contract Negotiation Constraint 2a: Non-functional property of the request. 48 rq0_req_quality: +37.0 rq0#impl_0i1#res0 18.0 49 50 \ Contract Negotiation Constraint 2b: Non-functional properties of required components 51 rq0_impl_0i0_reqs_quality_from_component_0i0_1: +14.0 rq0#impl_0i0_1i0#res1 0.0 52 rq0_impl_0i1_reqs_quality_from_component_0i1_0: +99.0 rq0#impl_0i1_0i0#res1 +65.0 rq0#impl_0i1_0i1#res1 -65.0 rq0#impl_0i1#res0 53 rq0_impl_0i1_reqs_quality_from_component_0i1_1: +94.0 rq0#impl_0i1_1i0#res2 +94.0 rq0#impl_0i1_1i0#res0 -94.0 rq0#impl_0i1#res0 54 55 56 \ Variable Definitions 57 Binaries \ here, all variables are binary 58 rq0#impl_0i0 rq0#impl_0i0_0i0 rq0#impl_0i0_0i1 rq0#impl_0i0_1i0 rq0#impl_0i0_1i0#res1 rq0#impl_0i0_1i1 rq0#impl_0i1 rq0#impl_0i1#res0 rq0#impl_0i1_0i0 rq0#impl_0i1_0i0#res1 rq0#impl_0i1_0i1 rq0#impl_0i1_0i1#res1 rq0#impl_0i1_1i0 rq0#impl_0i1_1i0#res0 rq0#impl_0i1_1i0#res2 rq0#impl_0i1_1i1 0.0 0.0 59 60 End
Listing A: ILP for the example model (sorted and commented).