A large number of quality properties need to be addressed in nowadays complex embedded systems by architects. Evolutionary algorithms can help architects to nd optimal solutions which meet these con icting quality attributes. Also, architectural patterns and antipatterns give the architect knowledge of solving design bottlenecks. Hence, antipatterns heuristics have been used as domain-speci c search operators within the evolutionary optimization. However, these heuristics usually improve only one quality attribute and using them in multiobjective problem is challenging. This paper studies the extent to which heuristic-based search operators can improve multiobjective optimization of software architecture for embedded systems. It compares various combinations of heuristic-based operators in a real world automotive system case study.
The architecture has deep impact on non-functional properties of a system such as performance, safety, reliability, security, energy consumption and cost. Due to the complexity of today's software systems, designing a system which meets all its quality requirements becomes increasingly complex. Hence, system architects have to employ optimization techniques to be able to explore more design possibilities and to nd optimal architectural solutions. Metaheuristic approaches frame the challenge of designing architectures as an optimization problem and iteratively try to improve a candidate solution with regard to the given quality attributes. Evolutionary Algorithms (EA), as a well-known metaheuristic approach, is a common optimization technique for solving system architectural problems. However, EA for generating new solutions uses generic search operators, such as Crossover or Mutate, which are blind to the problem and do not take into account the domain knowledge. To overcome this issue, domain-speci c search operators have been proposed. The downside of using domain-speci c search operators, is that the algorithm might nd local optimal solutions. In addition, each domain-speci c operator is usually useful only for one speci c objective, and this is a threat to the optimality of results in multiobjective problems.
This paper studies and compares various combinations of EA search operators (both domain-speci c and generic) for multiobjective optimization of software architecture. The domain-speci c operators are motivated by software architectural antipatterns. However, each heuristic-based search operator improves only one quality attribute of the solution, which is challenging for multiobjective problems. We apply various combination of operators to a case study, which is derived from a real world automotive embedded system.
The paper is organized as follows: Firstly, Section 2 discusses related work. Then, Section 3 describes our optimization framework, how we de ne heuristicbased search operators for optimization of software architecture, and the proposed combinations of these heuristic-based search operators. The case study that we applied our approach on, is represented in Section 4. Finally, The paper concludes in Section 5. 2
In the following, the state of the art of approaches which employ software design heuristics for optimizing architecture design are discussed: 2.1
Koziolek et al. [
Turbiani et al. [
Multiobjective Optimization of Software Architecture According to the studies in the related work, it is known that using domainspeci c operators is bene cial for software architecture optimization. However, by increasing the number of objectives for architecture optimization, we face new challenges. The rst challenge is that each heuristic technique usually improves only for one speci c quality attribute and as a result it may deteriorate other objectives. The second challenge is that in multiobjective optimization problems (more than 3 objectives) comparing the results of two optimization processes is di cult because the solutions are mostly non-dominated compared to each other. So, it is not trivial to gure out what is the best way of combining the heuristic-based search operators for multiple objectives.
In this paper, we de ned an experiment to compare various combinations of heuristic-based search operators for an embedded system architecture problem with four objectives based on a measurement called `Averaged Hausdor distance`. For this reason, we used a real world case study from automotive industry. Our optimization framework, with heuristic-based operators based on various combinations, was applied on that case study.
In this section, sub-section 3.1 describes brie
y the AQOSA optimizationframework
(The details of the AQOSA framework is reported by authors in [
AQOSA is a framework which uses a metaheuristic optimization approach based on generic algorithms for automated software architecture design. The framework supports analysis and optimization of multiple quality attributes including response time, utilization, safety and cost. It uses an architectural Intermediate Representation (IR) model for describing the architectural design problem. The AQOSA framework takes as input:
i) an initial functional part of the system (i.e. components that provide the needed functionality and their communications), ii) a set of typical usage scenarios (including triggers to create workloads), iii) an objective function (implying which architecture properties should be optimized),
iv) a repository that contains a set of speci cations of hardware and software components.
Then, AQOSA iterates through the following steps: 1. Generate a new set of candidate architecture solutions: Hence, AQOSA uses a representation of the architecture where it knows which are the degrees of freedom in the design and how to generate alternative architecture. 2. Evaluate the new set of candidate architecture solutions for multiple quality properties: This works by generating analysis models from the architecture model using model transformations and then analysing these models. 3. Select a set of optimal solutions. It is based on the chosen evolutionary algorithm. 4. Iterate to step 1 until some stopping criterion holds. This can be a maximum number of generations or a criterion on the objective function.
Below we brie y present the framework modules:
Architecture Modelling Because AQOSA is designed to optimize
architectures in a wide range of domains, it aims to be independent of speci c
modelling languages. Therefore, it uses its own internal architecture
representation, AQOSA intermediate representation (AQOSA-IR). The IR-model
integrates multiple quality modelling perspectives for the architectural level
optimization purpose. However, it is possible to transform well-known architectural
models like AADL or UML/MARTE to this intermediate representation.
Architecture Optimization The AQOSA optimizer tries to optimize the
software architecture with respect to potentially con icting quality attributes based
on Genetic Algorithm (GA). To this end, it automatically generates new
architectural design alternatives. It has been implemented based on the Opt4J
optimization framework [
Degrees of Freedom When an architect nalizes an architectural design for a system, generally there are still some ways in which the solution can be varied without changing the functionality. We call them Degrees of Freedom(DoF). The component-based paradigm that underlies our approach, allows us to recompose components in di erent topologies without changing the functionality of the system. We support the following degrees of freedom in the AQOSA framework: (1) Number of hardware nodes, (2) Number of connections between hardware nodes, (3) Network topology, (4) Software on hardware allocation, (5) Software components replacement, (6) Processor nodes replacement, (7) Communication lines replacement.
Evolutionary Algorithms AQOSA is compatible with well-known Evolutionary
Multi-Objective Algorithms (EMOA). For the experiment of this paper we
employed the famous algorithm NSGA-II (proposed by Deb [
Architecture Evaluation The AQOSA evaluation sub-system gets an
evaluation model which is transformed from an AQOSA-IR and a decoded genotype for
speci c evaluation purpose (e.g Response Time or Safety). It feeds these models
to each evaluator and returns the results to the optimization module. In this
experiment, we evaluated four quality attributes: Response time, processor
utilization, safety, and cost. Performance attributes (response time and utilization)
have been implemented by extending the JINQS [
Software architecture design patterns look at the positive and constructive
features of a software system, and suggest common solutions. In contrast,
antipatterns look at the negative and destructive features of a software system, and
present common solutions to the problems that make negative consequences [
Component Movement According to Concurrent Processing Systems antipattern, non-balanced assignment of processes to processors can make the system slow and cause a performance bottleneck. Hence, this operator moves the most intensive component deployed on the highest utilized processor to the least utilized processor in the architecture.
Processor Change for Performance When there is a processor with high utilization in the architecture, a solution to reduce utilization is replacing it with a better processor. In AQOSA, there is a repository of available hardware resources. A processor with higher clock rate can reduce the overall utilization of the system, so it can be selected for replacement.
Processor Change for Cost The former operator tackles processor utilization bottleneck. However, cost is another quality attribute and optimization objective. Replacing a processor with higher clock rate (probably more expensive) to solve utilization makes a deterioration for cost objective. Conversely, this operator replaces the less utilized processors with cheaper ones and probably lower clock rate.
Processor Change for Reliability This operator is designed to decrease failure probability, and consequently increase reliability. There may be some nodes in an architectural solution which have processors with the high probability of failure. They should be identi ed and replaced by the processors with lower probability of failure. 3.3
Each heuristic-based search operator is useful for the relevant quality attribute that is made for. However, it might have no e ect on the other quality properties, or might deteriorate them. For example, the \Component Movement" operator is bene cial for response time and \Processor Change for Performance" operator is bene cial for processor utilization while they are not useful for cost and failure probability. \Processor Change for Cost" and \Processor Change for Reliability" operators act the same way in favour of di erent objectives. In this paper, the extent to which heuristic-based search operators can improve multiobjective optimization of software architecture is studied.
To de ne the experiment in this study, we overrode the mating procedure of GA as follows: Two parents are needed to be operated by the search operators and they generate two o springs. Calling the search operators could be done in various calling orders which we called 'Combinations'. The following combinations of operators are considered for calling search operators to act on a pair of parents and generate two o springs for the next generation: Random For both o springs, the mating procedure picks heuristic-based operators randomly.
Sequential For both o springs, the mating procedure picks heuristic-based operators sequentially. It means that it uses the round robin ordering for operators. Random-Sequential For one o spring, the mating procedure picks a heuristicbased operator in the random order, and for the other one, it picks the operator sequentially.
Half-Random For one o spring, the mating procedure picks a heuristic-based operator randomly, and for the other one, it uses the generic operators (Crossover and/or Mutate).
Half-Sequential For one o spring, the mating procedure picks a heuristicbased operator in the round robin order, and for the other one, it picks the generic operators (Crossover and/or Mutate).
Half-Random-Sequential For one o spring, the mating procedure picks the generic operators (Crossover and/or Mutate), and for the other one, it switches between random and sequential ordering from generation to generation. 4 4.1
To compare the aforementioned combinations of operators, we applied them to a
real case study from automotive industry. The case study was conducted at Saab
Automobile AB and has been reported in the previous authors' work [
TripStemBut on ReadDriverDoor AjarSwitch
ReadTripStemButton AjarSwitchValue
StemBut onValue
OATSensor
LeverPstnSensor
LowWasherFluidLevelSwitch ReadOATSensor
TransmissionVehicle
Interface
ReadLowWasherLevel OutsideAirTemp
TransShLeverPstn
WasherFluidLow VehicleOdometer
ControlOdometer
ControlOutAirTemp
ControlGearSelected
Indication
OdometerDisplayValue OATDisplayValue GearDisplayValue WasherDisplayValue ProvidePowerModeInfo SystemPowerMode WheelSpeedSensor (4 Wheels)
SensorsValues ControlWheelSpeed WheelRotation
EngineVehicleInterface
CrankShaftSensorEngineCoolantTempSensor EngineSpeed
VehicleSpeed
EngineCoolantTemp ControlEngineSpeed
Gauge
ControlVehicleSpeed
Gauge
ControlCoolantTemp
Gauge EngineSpeedDisplayValue
VehicleSpeedDisplayValue
CoolantDisplayValue
Gauge_Engine
WriteEngineSpeedGaugWeriteVehicleSpeedGaugWeriteCoolantTempGauge
system represents the Saab 9-5 Instrument Cluster Module ECU (Electronic
Control Unit, a node in a network) and the surrounding sub-systems. It
consists of 18 components as depicted in Figure 1. The Instrument Cluster Module
is responsible for 8 concurrent user functions. Hence, for providing these
functionalities, it should be able to response 6 sporadic tasks and 4 periodic tasks
concurrently. Details of these tasks have been reported in [
For generating new architectural solutions, the repository of hardware components contains these elements: { 28 Processors: ranging over 14 various processing speeds from 66MHz to 500MHz; Each of them has two levels of failure rate. A processor is more expensive if it has less chance of failure and vice versa. { 4 Buses: with bandwidths of 10, 33, 125, and 500 kbps, and latencies of 50, 16, 8, and 2 ms. A bus is more expensive if it supports higher bandwidth.
As an estimate of the size of the design space in this case study, consider the following reasoning: Assume we omit architecture topology changing and x an architecture with six processors and three bus lines for their interconnections (exactly like the current realization in the industry). For these constraints there are 286 43 di erent possibilities, which is more than 30 billion architectures. When also considering variations in the architecture topologies, this number would be even considerably higher. The goal of the experiment is to compare the combinations of operators, in terms of achieving optimal solutions faster. To this end, we de ned the experiment with these steps: 1. We run the optimization process with high number of generations. So, with giving enough time to the algorithm, it could achieve optimal solutions. We used this set of solutions as the reference Pareto front in comparison with other Pareto fronts. 2. We run optimization with generic operators (without heuristic-based search operators) and also with six various combinations of optimization operators, all of them with low number of generations (each optimization process 20 times). In this situation, better combination can achieve optimal results within few number of generations. 3. We measured the distance between the results from step1 and step2. Shorter distance between the Pareto fronts, or in other words, closer result from step2 to the results of step1 means that combination could achieve better results in few number of generations. We interpret that combination as a better combination.
For the step1, we run the optimization with the following parameter settings: number of generations=200, initial population size( )=1000, parent population size ( )=250, number of o spring( )=500, archive size=50, crossover rate is set to 0.95.
For the step2, we run 20 times for each combination with these settings: number of generations=15, initial population size( )=100, parent population size ( )=25, number of o spring( )=50, archive size=20, heuristic rate and crossover rate are both set to 0.95.
At the step3, to calculate the distance between two set of Pareto front results
which achieved from step1 and step2, we used a measurement called `Averaged
Hausdor distance`. Schutze et al. [
X dist(xi; Y )p N i=1 !1=p ; 1 M
X dist(yi; X)p M i=1 !1=p1
A (1) Where X = x1; x2; :::; xn and Y = y1; y2; :::; ym are two Pareto fronts with the size of N and M . We set p = 1 for this experiment.
Figure 2 depicts the di erence between the results of optimization with (white boxes) and without (gray box) heuristic-based search operators. It shows the boxplot chart of the distance between 20 runs of each combination of operators as described in Section 3.3 and the step1. In the chart, lower values indicate better combination because it represents the distance with optimal results. For calculating the distance between Pareto fronts, we normalized the values of four dimensions and then we used Equation 1 to calculate the averaged Hausdor distance of two Pareto fronts. Therefore, vertical axis in Figure 2 represents the averaged Hausdor distance.
The plots in Figure 2 show that combinations with one generic operator generated o spring (Half-*) cause wider boxplots, or in other words, they are more dependent on luck for nding optimal results. They are more similar to the results of running with generic operators. Instead, combinations with tighter boxplots represent better combinations. Among them, Sequential and RandomSequential combinations perform best. Because, they show lower median values and tight boxes. 5
In this paper we introduced a comparison between various approaches for combinations of heuristic-based search operators in a model-based tool that integrates multiple quality analysis of software architecture. We implemented knowledge of architecture antipatterns as the domain-speci c search operators within an evolutionary algorithm. We de ned an experiment based on a real world case study and we applied it for a 4-objective software architecture optimization problem. We showed that search operators for improving one objective can be used in multiobjective optimization context. The results showed that proper combination of heuristic-based search operators can lead optimization algorithm to optimal solutions faster. However, for preventing not trapping in suboptimal solutions, rooms for randomness should always be considered in the optimization parameters settings.
As the future work, it is interesting to study e ects of weighting heuristicbased search operators on the results of optimization process, especially when number of operators which forcing each objective are unbalanced. 6
This work has been supported by the Netherlands national project OMECA (Optimization of Modular Embedded Computer-vision Architectures).
Also, authors thank Noushin Khaki for her contribution in implementation of these operators for AQOSA framework.