=Paper=
{{Paper
|id=Vol-2066/seerts2018paper01
|storemode=property
|title=Improving the Efficiency of Dislocality Constraints for an Automated Software Deployment in Safety-Critical Systems
|pdfUrl=https://ceur-ws.org/Vol-2066/seerts2018paper01.pdf
|volume=Vol-2066
|authors=Robert Hilbrich,Michael Behrisch
|dblpUrl=https://dblp.org/rec/conf/se/HilbrichB18
}}
==Improving the Efficiency of Dislocality Constraints for an Automated Software Deployment in Safety-Critical Systems==
https://ceur-ws.org/Vol-2066/seerts2018paper01.pdf
Improving the Efficiency of Dislocality Constraints
for an Automated Software Deployment in
Safety-Critical Systems
Dr. Robert Hilbrich Dr. Michael Behrisch
German Aerospace Center German Aerospace Center
Rutherfordstr. 2 Rutherfordstr. 2
12489 Berlin, Germany 12489 Berlin, Germany
Email: robert.hilbrich@dlr.de Email: michael.behrisch@dlr.de
Abstract—Mapping software components to hardware re- achieved, if critical software components are deployed ac-
sources is a central part of the systems engineering process. This cordingly. Deploying software components is a very intricate
task can be automated by formalization and transformation into a task with zero tolerance for errors as they may jeopardize
Constraint Satisfaction Problem and the subsequent application
of a constraint solver. The toolsuite ASSIST demonstrates the the correctness of the system. At the same time, it requires
feasibility of this concept. In ASSIST, dislocality requirements a detailed understanding of the requirements of all software
can be specified for software components to constrain the set of components and the capabilities of all hardware resources in
valid mapping solutions and to ensure reliability and fault toler- the system. Due to the sensitivity and complexity of this task,
ance of the system. Three approaches to model these dislocality its formalization and automation is a valuable research goal.
requirements with constraints are presented. They are compared
to each other based on twenty synthetic mapping examples. II. AUTOMATED C ONSTRUCTION OF D EPLOYMENTS
I. I NTRODUCTION In order to achieve an automated construction of a de-
Engineering complex and safety-critical systems, such as ployment and to argue its correctness, a formalization of the
flight control systems aboard an airplane, is still challenging mapping problem is required. For smaller mapping problems,
and costly. Despite recent advancements in our model-based this has been successfully achieved based on Linear Integer
tool suites and engineering methods, the design of these Programming [3], [4], SMT-based solvers [5] or evolutionary
systems still bears risk and uncertainties with regard to its algorithms [6]. However, these approaches reach their limits
outcome. when larger, real-world mapping problems are considered.
The formalization and automation of crucial engineering On the one hand, methods based on integer programming
tasks appears to be a promising approach to tackle these techniques are typically unable to provide solutions in a short
challenges [1], [2]. Systems in these areas are engineered to timespan (20 minutes), when the complexity of the system
implement a complex interplay between mechanical elements, reaches the level of real-world systems. Heuristic approaches
electronic components, as well as (embedded) software. There- based on evolutionary algorithms on the other hand are usually
fore, their design has to mirror this interplay and requires the unable to cope with limited gradient information to guide a
development of a hardware and software architecture. search process, because the design space of real-world systems
In practice, these architectures can often be developed often contains many discontinuities.
independent of each other, but their integration in the final The authors instead chose to transform a mapping problem
system requires a link between the software components and into a semantically equivalent Constraint Satisfaction Problem
their hardware resources. Creating this link is referred to as (CSP) [7] and solve this CSP with Constraint Programming
the deployment of the software components. Constructing a techniques [8]. The advantages of using Constraint Program-
deployment requires the systems engineer to map software ming in comparison to other techniques lie in the availability
components to resources and to schedule the access to shared of powerful modeling elements, such as an allDifferent
resources. Therefore, mapping refers to a spatial allocation, constraint, and the ease with which custom search heuristics
while scheduling refers to a temporal allocation of software can be implemented.
components.
The construction of a deployment is an engineering task, A. Constraint Satisfaction Problems
which not only affects the fulfillment of functional require- Constraint Programming refers to a set of techniques in ar-
ments by providing the necessary resources, but also affects tificial intelligence and operations research. These techniques
the satisfaction of non-functional requirements, such as safety assist in finding solutions for problems based on variables,
and reliability. Redundancy and fault tolerance can only be which are affected by constraints. Each constraint defines valid
SEERTS 2018: Workshop on Software Engineering for Applied Embedded RealTime Systems @ SE18, Ulm, Germany 90
or invalid solutions for a subset of these variables. In this to. For example, a simple redundancy requirement between
paper, a subclass of constraint satisfaction problems is used two software components, may force the systems engineer
to express mapping problems: finite domain integer constraint to allocate these software components to different processing
satisfaction problems in which each variable has a finite inte- boards in different locations aboard an airplane. Furthermore,
ger domain. Solutions for this problem class can be obtained systematic errors and undetected design flaws in hardware
by applying a combination of search techniques – including components may be addressed by choosing dissimilar hard-
backtracking – and constraint propagation techniques for value ware resources, processors or memory blocks from different
elimination. vendors for example.
To illustrate the modeling approach of Constraint Satis- Due to the importance of choosing “different” resources
faction Problems, consider the well-known Map Coloring for fault tolerance and reliability in safety-critical systems,
problem as an example. This problem asks, whether it is engineering tools for an automated construction of deploy-
possible to color a map with only four colors in such a way, ments need to be able to fully support these choices. ASSIST
that neighboring countries have different colors. It can be supports the engineer by offering dislocality and dissimilarity
formulated as a CSP by assigning an integer variable xi for requirements as part of the domain specific language. They can
each country with the index i. The domain of each variable be used to enforce “differences” for the choice of resources
corresponds to the four colors: Dxi = {0, 1, 2, 3}. In order to during the mapping process. Finding an efficient formulation
model the restrictions of this problem, a constraint is added to express the semantics of each requirement as a Constraint
for each pair of adjacent countries. If country xi is adjacent Satisfaction Problem is challenging, but also essential in order
to country xj , then xi 6= xj is required. The search algorithm to provide an effective toolsuite for the engineering of safety-
is now responsible to select a variable and test a value of its critical systems.
domain. Assuming a simple “first variable, first value” strategy, In order to illustrate the challenges and to present specific
the variable x0 would be chosen and set to the value 0 as a test. modeling improvements, the dislocality requirement is used
This would be propagated to all variables which are directly as an example in this paper. Please note, that the concepts
linked to x0 by a constraint, so that the value 0 gets removed developed for dislocality requirements can also be applied to
from their domains. This removal may lead to other value dissimilarity requirements.
removals in indirectly linked variables and is processed until The semantics of a dislocality requirement can be illustrated
a fix point is reached. If a contradiction is encountered or the with the following deployment problem (see Figure 2). In
domain of a variable becomes empty, backtracking is initiated, this example system, there are three applications consisting
so that the next value of the variable x0 is tested. Otherwise, of one or more tasks. Each task has to be mapped to exactly
the search algorithm continues with the next uninstantiated one of the processors in the system. It is assumed, that
variable. the processor contains multiple cores, so that multiple tasks
This example also shows, that the propagation of the can be mapped to a single processor. However, in order to
N OT E QUAL constraint is weak, because it affects only two ensure fault tolerance, a dislocality requirement is added for
variables and invalidates only 4 out of the 16 possible value all applications. This means, that the applications must not
combinations between two variables. share a processor, so that a faulty processor affects only one
application.
B. Toolsuite ASSIST Expressing the basic deployment problem with constraints
As a proof of concept for the ongoing research toward an is straight forward. Each task i in the system is represented
automated construction of deployments based on Constraint by an integer variable Xi . The domain of each variable Xi
Satisfaction Problems, the toolsuite Architecture Synthesis corresponds to the indices of the n processors in the system
for Safety-Critical Systems (ASSIST) was developed by the (Xi 2 {0, 1, . . . , n 1}). In order to add the constraints
authors. It is publicly available and uses the constraint solver for the dislocality requirements, two cases have to be distin-
Choco 4.0.6 [9] internally. guished. In the simple case, in which all applications consist
ASSIST allows a systems engineer to automatically con- of only one task, a dislocality can be enforced with a single
struct and optimize mappings based on textual specifications of allDifferent constraint (see [10]) over all task variables
the software components and hardware resources, dislocality, Xi . This case is depicted in Figure 2 (a). Fortunately, Choco 4
dissimilarity and colocality requirements, and also optimiza- already contains an implementation for an allDifferent
tion goals. The textual specifications in ASSIST conform to a constraint based on the algorithm of Rgin [11], so that the
domain-specific language which allows to hide the intricacies simple case can be implemented.
of a formal specification. In real-world systems, applications usually consist of more
than one task. Furthermore, tasks of the same application
III. E NSURING FAULT T OLERANCE BY R EQUIRING usually share the same processor. This situation is more com-
D ISLOCALITY plex and depicted in Figure 2 (b). Unfortunately, in this case,
In order to achieve fault tolerance and reliability, it is the previous approach of applying a single allDifferent
essential to support “significant differences” in the choice of constraint over all task variables Xi can no longer be used.
resources to which critical software components are deployed It would prevent solutions in which a processor is shared by
SEERTS 2018: Workshop on Software Engineering for Applied Embedded RealTime Systems @ SE18, Ulm, Germany 91
Fig. 1. Screenshot of the ASSIST User Interface
App A App B App C App A App B App C
Task A.1 Task B.1 Task C.1 Task A.1 Task B.1 Task C.1
Task A.2 Task B.2
Processor 1 Processor 2 Processor 3 Processor 4 Processor 1 Processor 2 Processor 3 Processor 4
(a) Simple Case (b) Complex Case
Fig. 2. An Example Deployment Problem - Mapping Tasks to Processors
multiple tasks of the same application. Before continuing with the description of possible imple-
The existing allDifferent constraint simply ensures, mentations, the semantics of an advanced allDifferent
that values for a list of variables are different. However, constraint should be described more precisely. For this pur-
the complex case requires an advanced allDifferent pose, consider the example system in Figure 2 (b). It consists
constraint working with a list of a list of variables and ensuring of the applications A, B and C. Each of these applications
that the combined values for each list of variables are disjunct. contains one or more tasks, i.e. A = {A1 , A2 }, B = {B1 , B2 }
Unfortunately, such a constraint is neither part of the Global and C = {C1 }. An advanced allDifferent for all
Constraint Catalog [10] nor available in Choco 4. applications would be working with a list of a list of variables,
for example:
IV. M ODELING C OMPLEX D ISLOCALITY R EQUIREMENTS allDifferent {{A1 , A2 }, {B1 , B2 }, {C1 }}
This section introduces three alternative implementations for Assuming that A? combines the values for each task in
the semantics of an advanced allDifferent constraint. application A:
Their performance and impact on resolution time will be [
analyzed and compared to each other in the next section. A? 2 P(N) = {Ai : Ai 2 A} (= A1 [ A2 )
SEERTS 2018: Workshop on Software Engineering for Applied Embedded RealTime Systems @ SE18, Ulm, Germany 92
and B ? and C ? do the same for the applications B and C, Based on the description of these three approaches to
then the advanced allDifferent constraint would ensure, implement the semantics of an advanced allDifferent
that the sets A? , B ? and C ? are pairwise disjunct. constraint, the next sections will describe experiments con-
ducted by the authors and preliminary results to assess and
Element-wise Approach compare the performance and efficiency of each approach.
One option to implement the advanced allDifferent
constraint semantic is to apply the already existing V. E XPERIMENTS
allDifferent constraint for every subset s with Benchmarking the performance and efficiency of these
approaches requires several example to work on. For this
s = {a, b, c | a 2 A, b 2 B, c 2 C}
purpose, the authors developed a generator for synthetic
For systems with a large amount of applications and more than mapping problems that resemble the typical characteristics
one task within each application, the amount of constraints, of mapping problems encountered in safety-critical systems.
that will be added to the constraint solver by this approach, Twenty randomized examples with at least one solution were
may significantly prolong the resolution time. However, this generated for the experiments. They exhibit the following
approach can be realized with the tools already available in properties.
Choco 4 and does not require any additional implementation In each example, there are two compartments, each contain-
of custom propagators and constraints. ing between four and six boxes. Each box contains between
four and six processing boards and every processing board
Instantiation-only Approach is equipped with one or two processors each comprising of
In order to address the drawbacks of the first approach, up to four cores. The examples contain between 16 and 24
another option is to implement a custom constraint and prop- applications and each of these applications have between two
agator for Choco 4, that is able to operate on a list of a list and eight tasks that need to be mapped to the cores on the
of variables. For the sake of simplicity, the propagator should processors. All tasks of an application are required to be
only react on instantiation events for any of its variables. If placed on the same processing board to allow for memory-
an instantiation is detected, then the value of the instantiated based communication (colocality requirement). Finally, every
variable will be removed from the values of all variables in example features between 24 and 32 dislocality requirements
all of the other lists. This approach has the advantage, that and each of these requirements refers to at least four and up
only one constraint needs to be added to the constraint solver to six applications.
for each dislocality requirement. However, this instantiation- Every example was benchmarked on an Apple iMac 5k with
only approach leads to a weak propagation as it only removes 64GB of RAM by using ASSIST 2.3 and Choco 4.0.6. The
values, when one of the variables is instantiated. experiments were done with the Domain over Weighted Degree
as a variable selector strategy and Minimum Value First as a
Combined Union-Variables and Instantiation-Only Approach value selector strategy. The examples are publicly available in
the ASSIST repository.
The third approach tries to build upon the instantiation-only
approach and improve the strength of its propagation. For this
VI. R ESULTS
purpose, a new integer variable X ? will be added for each list
of task variables X = {X1 , . . . , Xn } that were provided to the The amount of constraints and variables are depicted for
advanced allDifferent constraint. The new variable X ? each example and each approach in Figure 3 and Figure 4.
will contain the union of the remaining values of all variables The results show, that the element-wise approach leads to a
in X. This can be achieved with a custom propagator similar to substantial increase in the amount of constraints in the solver
the already existing PropSetIntValuesUnion propagator in comparison to the other two approaches. However, the
in Choco 4. With these new “union variables” being available, increase of the variable count due to the addition of union-
adding a simple allDifferent constraint, which links all variables for the implementation of the third approach appears
of the union variables, should improve the effectiveness of the to be rather negligible.
propagation. The total resolution time until the first solution has been
Please note, that these “union variables” must not be added reached is depicted in Figure 5. Please note the logarithmic
to the list of variables for branching as part of the search scale on the y-axis. The results demonstrate, that the resolution
strategy in Choco 4 as they will not always be resolved to time can be significantly reduced in all examples by adopting
only one value if tasks of an application are deployed to the instantiation-only approach.
different processors. This approach will be combined with Further improvements to the instantiation-only approach
the instantiation-only approach from the previous section. In can be achieved by applying the combined approach, but the
comparison to the instantiation-only approach, the handling of additional gains are significantly smaller. In some examples,
union-variables requires the addition of a new variable and a the combined approach requires slightly more time for a
propagator for each list of variables, so there is some overhead resolution. However, the time differences in these cases are
to be expected. so small, that they may also be induced by external effects,
SEERTS 2018: Workshop on Software Engineering for Applied Embedded RealTime Systems @ SE18, Ulm, Germany 93
Fig. 3. Amount of constraints in the Choco solver in each example
Fig. 4. Amount of variables in the Choco solver in each example
Fig. 5. Resolution time (in ms) to reach the first solution in each example
Fig. 6. Amount of backtracking occurring in each example
SEERTS 2018: Workshop on Software Engineering for Applied Embedded RealTime Systems @ SE18, Ulm, Germany 94
such as garbage collection in Java or scheduling interferences does not always lead to the lowest rate of backtracks in the
in the operating system. examples.
Backtracking occurs, when the search process in the con-
straint solver encounters a fail event, i.e. a variable has an ACKNOWLEDGMENT
empty domain after value propagation or one of the constraints
The authors acknowledge the financial support for this
determines a contradiction. Figure 6 shows the amount of
work by the Federal Ministry of Education and Research of
backtracking that occurred before finding the first solution
Germany (BMBF) in the project “ARAMiS II” (DLR, grant
in each example. One would assume, that the element-wise
identifier 01IS16025D).
approach exhibits the strongest propagation due to the large R EFERENCES
amount of additional allDifferent constraints, so that the
amount of fails and backtracks might be smaller compared to [1] R. Chapman, “Correctness by construction: putting engineering (back)
into software,” in Proceedings of the 2007 ACM international
the other approaches. In fact, the results are not as clear-cut. conference on SIGAda annual international conference, ser. SIGAda
Some examples show, that the propagation of the element- ’07. New York, NY, USA: ACM, 2007, pp. 100–100. [Online].
wise approach is significantly stronger compared to the other Available: http://doi.acm.org/10.1145/1315580.1315605
[2] R. Hilbrich, Platzierung von Softwarekomponenten auf Mehrkernprozes-
approaches. However, there are also other examples in which soren: Automatisierte Konstruktion und Analyse für funktionssichere
the situation is reversed. Systeme. Springer Fachmedien Wiesbaden, 2015. [Online]. Available:
https://books.google.de/books?id=qu5rCgAAQBAJ
VII. S UMMARY AND C ONCLUSIONS [3] W. Damm, A. Metzner, F. Eisenbrand, G. Shmonin, R. Wilhelm, and
S. Winkel, “Mapping Task-Graphs on Distributed ECU Networks:
Ensuring significant differences in the choice of resources Efficient Algorithms for Feasibility and Optimality,” in Embedded and
to which software components in safety-critical systems are Real-Time Computing Systems and Applications, 2006. Proceedings.
deployed to, is essential for satisfying safety requirements and 12th IEEE International Conference on, 2006, pp. 87–90.
[4] S. Kugele, W. Haberl, M. Tautschnig, and M. Wechs,
facilitating fault tolerance. ASSIST is a toolsuite for system “Optimizing Automatic Deployment Using Non-functional Requirement
engineers, which aims to automate the deployment of soft- Annotations,” in Leveraging Applications of Formal Methods,
ware components to hardware resources by transforming this Verification and Validation, ser. Communications in Computer and
Information Science, T. Margaria and B. Steffen, Eds. Springer
mapping problem into an equivalent Constraint Satisfaction Berlin Heidelberg, 2009, vol. 17, pp. 400–414. [Online]. Available:
Problem. In ASSIST, there are several means to require “dif- http://dx.doi.org/10.1007/978-3-540-88479-8 28
ferences” in the choice of resources. Dislocality requirements [5] S. Voss and B. Schatz, “Deployment and Scheduling Synthesis for
Mixed-Critical Shared-Memory Applications,” in Engineering of Com-
are one of those means and they are used as an example in puter Based Systems (ECBS), 2013 20th IEEE International Conference
this paper to illustrate the challenge of finding an efficient and Workshops on the, 2013, pp. 100–109.
constraint model. [6] J. White, B. Dougherty, C. Thompson, and D. C. Schmidt, “ScatterD:
Three different approaches to implement the intended se- Spatial deployment optimization with hybrid heuristic/evolutionary al-
gorithms,” TAAS, vol. 6, no. 3, p. 18, 2011.
mantics of dislocality requirements are presented. They specif- [7] K. R. Apt, Principles of constraint programming. Cambridge University
ically address complex use-cases in which applications consist Press, 2003.
of multiple tasks. While one of these approaches can be [8] F. Rossi, P. van Beek, and T. Walsh, Eds., Handbook of
Constraint Programming. ELSEVIER SCIENCE & TECHNOLOGY,
realized without any customized constraints or propagators, 2006. [Online]. Available: http://www.ebook.de/de/product/5834373/
the other two approaches rely on custom implementations of handbook of constraint programming.html
constraints and propagators as well as additional variables in [9] C. Prud’homme, J.-G. Fages, and X. Lorca, Choco Documentation,
TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S.,
the third approach. 2016. [Online]. Available: http://www.choco-solver.org
Experiments conducted with twenty synthesized mapping [10] N. Beldiceanu, M. Carlsson, and J.-X. Rampo, “Global Constraint
examples for ASSIST show, that the implementation of custom Catalog,” online, SICS, Technical Report T2012:03, Feb. 2014, iSSN:
1100-3154. [Online]. Available: http://www.emn.fr/z-info/sdemasse/
constraints and propagators is well worth the effort. They lead gccat/
to a substantial reduction in the resolution time with only min- [11] J.-C. Régin, “A filtering algorithm for constraints of difference in
imal overhead due to the additional constraints and variables. csps,” in Proceedings of the Twelfth National Conference on Artificial
Intelligence (Vol. 1), ser. AAAI ’94. Menlo Park, CA, USA: American
The results also indicate, that the element-wise approach, Association for Artificial Intelligence, 1994, pp. 362–367. [Online].
which requires the highest amount of additional constraints, Available: http://dl.acm.org/citation.cfm?id=199288.178024
SEERTS 2018: Workshop on Software Engineering for Applied Embedded RealTime Systems @ SE18, Ulm, Germany 95