Supplementary material for our paper in the IEEE Transactions on Software Engineering (see DOI).

Taxonomy

The outline and motivation of our taxonomy is presented in the paper. Here, we describe the different values identified for each taxonomy class in detail. References are provided below in the section References

Problem

Domain

Information system (IS): includes for instance enterprise information systems, e-business applications and government information systems
Embedded system (ES): computing systems that realize one or few specific functions. They scale from small portable devices to large factories and power plants.
General: approaches that can cater for designed for both the above domains.

Phase

Design time (DT): if the architecture optimization is conducted at the design time of the system. The setting of a design-time problem is known in advance.
Run time (RT): if the optimization is conducted in systems run time. This is different from DT approaches as the setting of a run-time problem changes dynamically (e.g. new tasks can arrive during run-time task allocation).
General: if an approach is applicable to both the above phases.

Quality attributes

Area: chip area or other physical area which depends on architectural decisions [Ceriani10FLST].
Availability: is the readiness for correct service [Avizienis04LRL].
Cost: is an umbrella term to consider different cost aspects like manufacturing, raw material, maintenance, testing, installation as well as opportunity costs [Boehm00ABCCHMRB].
Energy: is the energy consumed by the system [Benini00BD].
Flexibility: is the system ability to execute new applications (e.g. to support new standard typically) [LeBeux10BNBLP].
Maintainability: is the ability to undergo modifications [Avizienis04LRL].
Modifiability: is the ease with which it can be modified to changes in the environment, requirements or functional specification [Bengtsson04LBV].
Performance: is a measurement of appropriate utilization of scares system resources by software functions under certain conditions [Florentz06H].
Reliability: is the continuity of correct service [Avizienis04LRL].
Reputation: which is a measure of trustworthiness of service invocation. Generally this measure is defined as the average ranking given to the service by end users [ElHaddad10MR].
Safety: is the absence of catastrophic consequences on the user(s) and the environment [Avizienis04LRL].
Security: is the concurrent existence of a) availability for authorized users only, b) confidentiality, and c) integrity with ‘improper’ taken as meaning ‘unauthorized’ [Avizienis04LRL].
Weight: weight of the system.
General: if an approach is applicable for any quality attribute in general.

Dimensionality

Single-objective (SOO): approaches that optimize a single quality attribute only.
Multi-objective (MOO): approaches optimize multiple quality attributes at once, so that the quality of every architecture model is a vector of values. As quality attributes often conflict, there usually is no single optimal result but a set of solutions non-dominated by the others from the point of view of the optimized qualities; i.e. solutions that are Pareto-optimal.
Multi-objective transformed to single (MTS) : approaches that encode multiple objectives into a single mathematical function (e.g.\ a weighted sum), which is then optimized as a single objective.
General: approaches that are applicable to irrespective of the dimensionality of the problem.

Constraints

Area: chip area or another physical area which depends on architectural decisions [Ceriani10FLST].
Availability: is the readiness for correct service [Avizienis04LRL].
Cost: is an umbrella term to consider different cost aspects like manufacturing, raw material, maintenance, testing, installation as well as opportunity costs [Boehm00ABCCHMRB].
Delay: min/max bounds on the time interval between initiation of execution of two operations[Gupta93D].
Delivery time: development time including testing or procurement time [Cortellessa06MP].
Dependability: an integrative concept that encompasses availability, reliability, safety, confidentiality, integrity and maintainability [Avizienis04LRL].
Design: explicit constraints on the design space of the problem [Andrews04B].
Functional correctness: satisfaction of functions requirements [Cardellini06CGM].
Latency: time spend in a job queue in the context of scheduling [Moreira07VB].
Mapping: restrictions on mapping architectural elements (eg. task to component or components to host)
Memory: memory capacity related constraints.
Path loss: transmission power loss in the path in wireless communication [Yang07EAB].
Performance: is a measurement of appropriate utilization of scares system resources by software functions under certain conditions [Florentz06H].
Physical: constraints on physical properties of the system, eg. size of the processors.
Precedence: relative order of completion in different tasks.
Processing power: processing power available on a device (processing speed).
QoS values: different quality of service metrics.
Redundancy level: constraints on maximum number of replicas in redundancy allocation.
Reliability: is the continuity of correct service [Avizienis04LRL].
Requirements: other requirements that have to be satisfied in the candidate architectures.
Response time: time taken to respond for a given service request [Menasce08CD].
Server overloading: the condition that the request rate of a service becomes higher than its average response period [Boone10HSJJTDD].
Stability: the ability to configure different arrival rates [Cardellini06CGM].
Structural: some structural constraints to ensure the feasibility of the design. Eg. mapping of a communication link must be between the nodes to which the communicating tasks have been mapped [Lukasiewycz08GHT].
Timing: time related constraints e.g., must assign three UAVs to strike a target from three different directions within 2 seconds of each other
Throughput: throughput in data communication.
Utilization: ratio of resource usage to its capacity in buses or processors.
Volume: physical volume of the system.
Weight: weight of system elements.
General: the approaches that are applicable to any constraint in general.

Solution

Architecture Representation

Architecture model: an architecture model is used as the input
Quality model: a quality model is used as the input, no architecture model is used
Optimization model: an optimization model is used as the input, no architecture model or quality model is used

Note that several approaches that start with an architecture model also internally use a quality model, and that all approaches also internally use an optimization model.

Subcategories of architecture models are:

Unified Modeling Language (UML): denotes architecture models defined in any modeling formalism of the Unified Modeling Language.
Other architecture description languages (ADL): specifies other architecture description languages such as AADL or PCM.
Workflow language (WFL): A specific form of architecture description for service-based systems.
Custom architecture models (custom AM): Approaches that define a custom model to describe the architecture which, in contrast to ADLs, does not have the purpose to document the architecture but is more tailored towards a specific purpose (such as the architecture middleware PRISM-MV).
General: Approaches that allow to exchange the used architecture model, e.g. by reasoning in the metamodel level or by offering plug-ins for handling different ADLs.

Quality Evaluation

Simple additive function (SAF): The quality objective is obtained from a simple additive function of input parameters and design decision.
Nonlinear mathematical function (NMF): The objective is expressed as a function from input parameter space to quality metric, but cannot be considered as a linear function.
Model-based (MB): The quantification of the attribute is done by evaluating a specific model. Some approaches where mathematical functions are used on top of the models (for example Expected number of visits are calculated from DTMC and then, system reliability is computed as a function of this) were also put into this category.
General

Degrees of Freedom

Software selection: selecting software entities in the architecture.
Component selection: We explicitly distinguish component selection, because some domains have a certain notion of a component. For example, in embedded systems design, component selection could mean deciding between a component realizing a functionality in hardware and a component with general-purpose hardware realizing functionality in software.
Service selection: we explicitly distinguish service selection, because next to selecting the software to execute, selecting a service also includes selecting the service provider (thus including hardware aspects as well).
Hardware selection: selecting hardware entities in the architecture.
Software replication: in this category, we subsume operators that change the number of copies of software entities only. For brevity, we include both identical copies of the software and different implementations of the same functionality (e.g. n-version programming) in the term "software replication".
Hardware replication: multiplicity of hardware entities. The popular term "redundancy allocation" is also included in this category.
Software parameters: parameters in software entities (e.g number of threads of an application server) and hardware parameters (e.g. parameters for the hard disk drive).
Hardware parameters: parameters in hardware entities in the architecture. This may overlap with hardware selection, because the choice (e.g. of a CPU with different speed) can be modeled both as hardware selection or as a parameter of the hosting server.
Scheduling: is concerned with deciding about the order of execution.
Maintenance schedules
Allocation: mapping of software entities (components or tasks) to processing elements, for example to servers. A broader term to Deployment, which usually refers only to the mapping of software components to processing elements.
Clustering: putting a group of tasks together into clusters.
Partitioning: partitioning of a system specification into separate hardware and software modules.
Service composition: changes on how services are composed by changing service topology and/or the service workflow.
Architectural pattern: apply architectural patterns.
Other problem specific: we do not explicitly name degrees of freedom that are used by fewer than 3 papers, and considered them in to "problem specific" category.
General: the approaches that allow any operator in general.

Optimization Strategy

Exact: optimization strategies that guarantees exact solutions (the best available architecture design with respect to the optimized quality).
Approximative: optimization strategies that only finds approximate solutions. Among the approximate methods, we distinguish methods that guarantee a lower bound of the solution (such as some branch-and-bound approaches), methods that use problem-specific heuristics (such as heuristics to construct a solution) and methods that apply general metaheuristics (such as evolutionary algorithms).
General: the approaches that are applicable to both the above categories.

Constraint Handling

Penalty: penalize violations
Prohibit: prohibit/discourage violations
Repair: repair violations
General

Validation

Approach Validation

Experiments: experiments with randomly generated problems.
Simple example: demonstration with a simple example.
Industrial case study: a comprehensive case study from the industry.
Academic case study: a case study constructed for academic purposes which may not represent the exact industrial settings.
Benchmark problems: compare results of the approach with known benchmark problems
Mathematical proof: validation techniques that mathematically prove the validity of the approach
Literature comparison: pursue the validity of the approach by argumentation in the context of related literature.
Not presented: no information given in the validity of the approach

The difference between a simple example and an academic case study is the complexity of the example. While a simple example often uses artificial architecture entities such as components C1 to C4, a case study studies a realistic example. In contrast to industrial case studies, academic case studies only consider artificial examples (thus no real, productive system), but try to make them realistic (give a meaning to the system).

Optimization Validation

Comparison with baseline heuristic algorithm: compare the results of a specific extension of the approach with the results of baseline version.
Internal comparison: this category applies to the papers that propose multiple optimization strategies which are against with each other.
Comparison with exact algorithm: compare the results with the actual solutions produced from an exact algorithm
Comparison with random search: compare an algorithm with the naive-random search algorithm
Mathematical proof: validation techniques that mathematically prove the validity of the optimization
Not presented: no information given on the validity of the optimization

References

[Avizienis04LRL] Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, and Carl E. Landwehr. Basic concepts and taxonomy of dependable and secure computing. IEEE Trans. Dependable Sec. Comput., 1(1):11-33, 2004.

[Andrews05B] JD Andrews and LM Bartlett. A branching search approach to safety system design optimisation. Reliability Engineering & System Safety, 87(1):23-30, 2005.

[Bengtsson04LBV] PerOlof Bengtsson,Nico Lassing, Jan Bosch and Hans van Vliet, Architecture-level modifiability analysis (ALMA), Journal of Systems and Software, 69(1-2):129-147, 2004.

[Benini00BD] Luca Benini, Alessandro Bogliolo, and Giovanni De Micheli. A survey of design techniques for system-level dynamic power management. IEEE Trans. VLSI Syst, 8(3):299-316, 2000.

[Boehm00ABCCHMRB] Barry W. Boehm, Chris Abts, A. Winsor Brown, Sunita Chulani, Bradford K. Clark, Ellis Horowitz, Ray Madachy, Donald J. Reifer, and Bert Steece. Software Cost Estimation with Cocomo II. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2000.

[Boone10HSJJTDD] Bas Boone, Sofie Van Hoecke, Gregory Van Seghbroeck, Niels Jonckheere, Viviane Jonckers, Filip De Turck, Chris Develder, and Bart Dhoedt. SALSA: QoS-aware load balancing for autonomous service brokering. Journal of Systems and Software, 83(3):446-456, 2010.

[Cardellini06CGM] Valeria Cardellini, Emiliano Casalicchio, Vincenzo Grassi, and Raffaela Mirandola. A framework for optimal service selection in broker-based architectures with multiple QoS classes. In Services computing workshops (SCW'06), pages 105-112. IEEE computer society, 2006.

[Ceriani10FLST] Marco Ceriani, Fabrizio Ferrandi, Pier Luca Lanzi, Donatella Sciuto, and Antonino Tumeo. Multiprocessor systems-on-chip synthesis using multi-objective evolutionary computation. In Martin Pelikan and Jürgen Branke, editors, Genetic and Evolutionary Computation Conference, GECCO 2010,, pages 1267-1274. ACM, 2010.

[Cortellessa06MP] Vittorio Cortellessa, Fabrizio Marinelli, and Pasqualina Potena. Automated selection of software components based on cost/reliability tradeoff. In Volker Gruhn and Flávio Oquendo, editors, Software Architecture, Third European Workshop, EWSA 2006, volume 4344 of Lecture Notes in Computer Science, pages 66-81. Springer, 2006.

[ElHaddad10MR] Joyce El Haddad, Maude Manouvrier, and Marta Rukoz. TQoS: Transactional and qoS-aware selection algorithm for automatic web service composition. IEEE T. Services Computing, 3(1):73-85, 2010.

[Florentz06H] Bastian Florentz and Michaela Huhn. Embedded systems architecture: Evaluation and analysis. In QoSA:Quality of Software Architectures, Second International Conference on Quality of Software Architectures, (QoSA'06), volume 4214, pages 145-162. Springer, 2006.

[Gupta93D] Rajesh K. Gupta and Giovanni De Micheli, Hardware-software cosynthesis for digital systems, IEEE Design & Test of Computers, 10(3):29-41, 1993.

[LeBeux10BNBLP] Sébastien Le Beux, Guy Bois, Gabriela Nicolescu, Youcef Bouchebaba, Michel Langevin, and Pierre G. Paulin. Combining mapping and partitioning exploration for noC-based embedded systems. Journal of Systems Architecture - Embedded Systems Design, 56(7):223-232, 2010.

[Lukasiewycz08GHT] Martin Lukasiewycz, Michael Glaß, Christian Haubelt, and Jürgen Teich. Efficient symbolic multi-objective design space exploration. In ASP-DAC 2008, pages 691-696. IEEE, 2008.

[Menasce08CD] Daniel A. Menascé, Emiliano Casalicchio, and Vinod Dubey. A heuristic approach to optimal service selection in service oriented architectures. In Alberto Avritzer, Elaine J. Weyuker, and C. Murray Woodside, editors, Proceedings of the 7th International Workshop on Software and Performance, WOSP 2008, pages 13-24. ACM, 2008.

[Moreira07VB] Orlando Moreira, Frederico Valente, and Marco Bekooij. Scheduling multiple independent hard-real-time jobs on a heterogeneous multiprocessor. In Proceedings of the 7th ACM & IEEE International conference on Embedded software, EMSOFT 2007, pages 57-66. ACM, 2007.

[Yang07EAB] Erfu Yang, Ahmet T. Erdogan, Tughrul Arslan, and Nick Barton. Multi-objective evolutionary optimizations of a space-based reconfigurable sensor network under hard constraints. In Symposium on Bio-inspired, Learning, and Intelligent Systems for Security (BLISS'07), pages 72-75. IEEE Computer Society, 2007.