Optimisation Architecture Elements. 4.3.4.1 Optimisation Space Definition Module (OSDM) The OSDM provides the input for the overall optimisation process by taking the original model, which contains variability elements to define the variation points of the design, and derives from this input the set of possible encodings of the optimisation search space – the Master Encoding Hierarchy, which is a structure that can be manipulated to obtain the set of all valid design candidates (also called population). This allows the Central Optimisation Engine (below) to explore the design space automatically by using an abstract structure rather than needing semantic knowledge of the design model itself. This is “abstract” in the sense that it does not include any information on the structure, behaviour or other properties of the individual candidates; it just provides a means to unambiguously denote each candidate. Unlike the other elements, which are used in each optimisation iteration, the OSDM is only required once, at the beginning of the optimisation, not iteratively in each optimisation cycle as the other elements. • A variant-rich model, i.e. one containing variability in the form of variation points. Provided as an external input. May contain both optimisation variability and product line variability (the precise distinction between the two types is still to be determined; it might be binding time or it might be something more explicit). • Master Encoding Hierarchy (MEH) of the optimisation space. This will be used by the optimisation engine to select and denote candidates to be analysed in each optimisation cycle. This notion of optimisation space corresponds exactly to what is called a configuration space in feature modeling terminology. Therefore, a feature model would be a natural fit for representing the optimisation space. However, for pragmatic implementation reasons a different form of encoding might be required to simplify the implementation of the OSDM and/or the optimisation engine or to enable the reuse of existing implementations (to be investigated). The format of the MEH is yet to be finalised but is likely to be based on XML somehow. The optimisation space definition module (OSDM) takes a model with variability and derives from that an abstract definition of the optimisation space, i.e. a structure which can be manipulated to obtain the set of all valid design candidates – the Master Encoding Hierarchy (MEH). This definition is “abstract” in the sense that it does not include any information on the structure, behaviour or other properties of the individual candidates; it just provides a means to unambiguously denote each candidate. It takes the form of a tree structure which shows each point of variability in the model; therefore it is analogous (and very similar to) an ordinary feature model. The precise mechanics are yet to be determined, but the principle is that each node represents a variability point and the nature of the node describes the type of variability. For example, assume we have a simple model with one optional component (C1) and another component (C2) that can have one of three implementations (A, B, or C). Implementation C itself is a subsystem that can be replicated upto 3 times for redundancy purposes. This model may produce a MEH like this: MASTER ENCODING + | +---> C1: 0..1 +---> Implementation 1 | +---> C2: 1 +---> Implementation A | +---> Implementation B | +---> Implementation C: 1..3 Note that the above is purely illustrative and not meant to be a definitive example of what the MEH may ultimately look like. In particular, the ‘types’ of variability we wish to include are not yet finalised. The example above uses optionality, multiple implementations, and replication, but we may decide to use other types (like k-out-of-n selections) or fewer types. Also to be determined is whether or not it is necessary (or possible) to ‘link’ variability points so that e.g. selecting one point automatically enables another variability point too, so we can model dependencies between them. Regarding product line variability, the exact handling of product line variability vs optimisation variability is yet to be determined, both in terms of how they are distinguished in the EAST-ADL model and also in terms of how they appear in the Master Encoding Hierarchy. It is likely that only ‘true’ optimisation variability will be present in the MEH, and the product line variability remains unresolved in the model; in this scenario, the VRM would then be responsible for generating all possible product line examples (resolving both optimisation and product line variability) for analysis purposes. The OSDM could also have a mode in which it strips out or hides any irrelevant variability, e.g. allowing optimisation to take place on only one product line variant. In its initial incarnation, this is likely to be the case, with future extensions to allow full product line functionality (thus we plan for the full functionality but only implement a subset initially). • Optimisation Space Definition Module (OSDM): this element provides the input for the overall optimisation process by taking the original model, which contains variability elements to define the variation points of the design, and derives from this input the possible encodings of the optimisation search space. This allows the optimisation engine (below) to explore the design space automatically by using an abstract structure rather than needing semantic knowledge of the design model itself. Unlike the other elements, which are used in each optimisation iteration, the OSDM is only required once, at the beginning of the optimisation. • Optimisation engine: this is the driver of the process, responsible for exploring the design space (by choosing which encodings to evaluate) and for collecting the best solutions so far. The likely algorithm to use for the optimisation is a genetic algorithm, but others could be used (including options to use a simple random selection or enumeration of a small design space, for example). • Variability Resolution Mechanism (VRM): this element is responsible for taking the original model (with variability) together with an encoding and then producing a new model from them, with all variability resolved. This model can then be subjected to analysis for the purposes of evaluation. • Analysis: this element is responsible for analysing the model according to the objectives given to the optimisation engine. Typically there would be a separate analysis for each objective, although in practical terms these analyses could be carried out by the same tool or in the same process. The results of the analysis/analyses are then fed back to the optimisation engine, which uses them to decide whether or not to retain that candidate model. Apart from the OSDM, the optimisation process therefore consists of a loop - from engine to VRM, to analysis tools, and back to engine - which is iterated continuously until the optimisation is complete. The OSDM is necessary to ensure that the optimisation engine itself does not need to know anything about the semantics of the models it deals with other than what variability is present in the original model and how it can be encoded. It is then job of the VRM to convert a particular encoding - i.e., a particular configuration of the variability in the model - to produce a new model in which all the variability is resolved. This can then be analysed by the tools which feed their results back to the optimisation engine, which determines whether to keep or discard that particular design candidate on the basis of those results.
Appears in 1 contract
Sources: Grant Agreement
Optimisation Architecture Elements. 4.3.4.1 Optimisation Space Definition Module (OSDM) The OSDM provides the input for the overall optimisation process by taking the original model, which contains variability elements to define the variation points of the design, and derives from this input the set of possible encodings of the optimisation search space – the Master Encoding Hierarchy, which is a structure that can be manipulated to obtain the set of all valid design candidates (also called population). This allows the Central Optimisation Engine (below) to explore the design space automatically by using an abstract structure rather than needing semantic knowledge of the design model itself. This is “abstract” in the sense that it does not include any information on the structure, behaviour or other properties of the individual candidates; it just provides a means to unambiguously denote each candidate. Unlike the other elements, which are used in each optimisation iteration, the OSDM is only required once, at the beginning of the optimisation, not iteratively in each optimisation cycle as the other elements. • A variant-rich model, i.e. one containing variability in the form of variation points. Provided as an external input. May contain both optimisation variability and product line variability (the precise distinction between the two types is still to be determined; it might be binding time or it might be something more explicit). • Master Encoding Hierarchy (MEH) of the optimisation space. This will be used by the optimisation engine to select and denote candidates to be analysed in each optimisation cycle. This notion of optimisation space corresponds exactly to what is called a configuration space in feature modeling modelling terminology. Therefore, a feature model would be a natural fit for representing the optimisation space. However, for pragmatic implementation reasons a different form of encoding might be required to simplify the implementation of the OSDM and/or the optimisation engine or to enable the reuse of existing implementations (to be investigated). The format of the MEH is yet to be finalised but is likely to be based on XML somehow. The optimisation space definition module (OSDM) takes a model with variability and derives from that an abstract definition of the optimisation space, i.e. a structure which can be manipulated to obtain the set of all valid design candidates – the Master Encoding Hierarchy (MEH). This definition is “abstract” in the sense that it does not include any information on the structure, behaviour or other properties of the individual candidates; it just provides a means to unambiguously denote each candidate. It takes the form of a tree structure which shows each point of variability in the model; therefore it is analogous (and very similar to) an ordinary feature model. The precise mechanics are yet to be determined, but the principle is that each node represents a variability point and the nature of the node describes the type of variability. For example, assume we have a simple model with one optional component (C1) and another component (C2) that can have one of three implementations (A, B, or C). Implementation C itself is a subsystem that can be replicated upto up to 3 times for redundancy purposes. This model may produce a MEH like this: MASTER ENCODING + | +---> C1: 0..1 +---> Implementation 1 | +---> C2: 1 +---> Implementation A | +---> Implementation B | +---> Implementation C: 1..3 Note that the above is purely illustrative and not meant to be a definitive example of what the MEH may ultimately look like. In particular, the ‘types’ of variability we wish to include are not yet finalised. The example above uses optionality, multiple implementations, and replication, but we may decide to use other types (like k-out-of-n selections) or fewer types. Also to be determined is whether or not it is necessary (or possible) to ‘link’ variability points so that e.g. selecting one point automatically enables another variability point too, so we can model dependencies between them. Regarding product line variability, the exact handling of product line variability vs vs. optimisation variability is yet to be determined, both in terms of how they are distinguished in the EAST-ADL model and also in terms of how they appear in the Master Encoding Hierarchy. It is likely that only ‘true’ optimisation variability will be present in the MEH, and the product line variability remains unresolved in the model; in this scenario, the VRM would then be responsible for generating all possible product line examples (resolving both optimisation and product line variability) for analysis purposes. The OSDM could also have a mode in which it strips out or hides any irrelevant variability, e.g. allowing optimisation to take place on only one product line variant. In its initial incarnation, this is likely to be the case, with future extensions to allow full product line functionality (thus we plan for the full functionality but only implement a subset initially). • Optimisation Space Definition Module (OSDM): this element provides the input for the overall optimisation process by taking the original model, which contains variability elements to define the variation points of the design, and derives from this input the possible encodings of the optimisation search space. This allows the optimisation engine (below) to explore the design space automatically by using an abstract structure rather than needing semantic knowledge of the design model itself. Unlike the other elements, which are used in each optimisation iteration, the OSDM is only required once, at the beginning of the optimisation. • Optimisation engine: this is the driver of the process, responsible for exploring the design space (by choosing which encodings to evaluate) and for collecting the best solutions so far. The likely algorithm to use for the optimisation is a genetic algorithm, but others could be used (including options to use a simple random selection or enumeration of a small design space, for example). • Variability Resolution Mechanism (VRM): this element is responsible for taking the original model (with variability) together with an encoding and then producing a new model from them, with all variability resolved. This model can then be subjected to analysis for the purposes of evaluation. • Analysis: this element is responsible for analysing the model according to the objectives given to the optimisation engine. Typically there would be a separate analysis for each objective, although in practical terms these analyses could be carried out by the same tool or in the same process. The results of the analysis/analyses are then fed back to the optimisation engine, which uses them to decide whether or not to retain that candidate model. Apart from the OSDM, the optimisation process therefore consists of a loop - from engine to VRM, to analysis tools, and back to engine - which is iterated continuously until the optimisation is complete. The OSDM is necessary to ensure that the optimisation engine itself does not need to know anything about the semantics of the models it deals with other than what variability is present in the original model and how it can be encoded. It is then job of the VRM to convert a particular encoding - i.e., a particular configuration of the variability in the model - to produce a new model in which all the variability is resolved. This can then be analysed by the tools which feed their results back to the optimisation engine, which determines whether to keep or discard that particular design candidate on the basis of those results.
4.3.4.2 Central Optimisation Engine (▇▇▇) The Central Optimisation Engine is the driver of the optimisation process, responsible for exploring the design space (by choosing which encodings to evaluate) and for collecting the best solutions so far. The ▇▇▇ will use genetic algorithms based on HiP-HOPS technology, but HiP-HOPS itself will only be used as an analysis tool. Instead the intention is to create a new implementation that can more tightly integrate with the other elements of the optimisation architecture (e.g. in the form of a Papyrus plugin). When optimisation is required, the optimisation engine receives from the OSDM a tree containing the different variation points in the model together with a set of optimisation objectives. This is the master encoding, the base DNA of the model to be optimised. To perform optimisation, the optimisation engine chooses a particular encoding (by selecting which variation points to use and which not to use according to its internal heuristics) and passes this on to the VRM. The VRM returns a version of the original model with the variability resolved (although product line variability may still be unresolved). This resolved model is then passed to the plugin interfaces to the various analysis engines (timing, safety, cost etc.), according to the optimisation objectives. Once complete, the analysis results are returned so the optimisation algorithm can evaluate them against its objectives and then repeat the cycle. For starting optimisation: A set of optimisation parameters. These should specify which analyses are to take place (e.g. safety, timing) and with which tools, which particular attributes are to be optimised (e.g. cost, reliability, schedulability etc.), and whether to maximise or minimise those objectives. Any constraints may also be included here (e.g. a minimum level of safety, a maximum cost etc.). The set of optimisation parameters comes from the user (requiring some kind of user interface). The Master Encoding Hierarchy, which describes all the variability points in the model. The master encoding tree should be provided by the OSDM. It is likely to be in XML format and provided in-memory (but there are other alternatives). During optimisation, in each iteration the engine receives: A resolved model; after passing the current encoding to the VRM, the optimisation engine receives a model with the variability resolved accordingly. It can then pass this to the analysis plugins. The set of analysis results for each objective; this is essentially a single floating point number for each of the objectives (e.g. total cost, system reliability etc.). It receives this information from each of the analysis plugins, which are interfaces to the relevant analysis tools. It is possible for multiple objectives to be analysed by the same tool, as this is transparent to the optimisation engine (which only needs to know which plugin to call for which objective). During optimisation, in each iteration the engine provides: A configuration encoding, which is passed to the VRM. The VRM can then resolve the variability in the model according to that encoding (equivalent to configuring the feature model). This is likely to be in the same format as the Master Encoding Hierarchy. Execution instructions to the analysis plugins, together with the resolved model to be analysed. Note that the model may still contain product line variability; this will be discussed later. In terms of optimisation results: When the optimisation process finishes (e.g. because it meets its time limit, or because no progress has been made for X number of iterations, or because the user manually stops the process etc.), it will output the Pareto set of all optimal encodings it has found so far, together with the evaluation results for each objective. Ultimately this would probably be presented to the user in the form of a selection dialogue; when the user selects a particular encoding (and set of evaluation results), the VRM can take that encoding and provide the user with the resolved model in question. This avoids the need to store all of the optimal models themselves. Thus the Pareto set will probably be stored as a set of XML-based model encodings, together with their analysis results.
Appears in 1 contract
Sources: Grant Agreement