Pierre Couturier
email: pierre.couturier@mines-ales.fr

Mambaye Lô

Abdelhak Imoussaten

Vincent Chapurlat

Jacky Montmain

Tracking the consequences of design decisions in mechatronic systems engineering

Keywords: Systems engineering, Mechatronics, Evaluation, Traceability

The design of mechatronic systems involves several technical and scientific disciplines. It is often difficult to anticipate, at the outset, the consequences of design decisions on the ultimate effectiveness of such complex systems, in which case the evaluation process is required to support the designers each time engineering choices must be made or justified. Since designers may belong to different technical and scientific cultures however, their understanding of both the design stakes and the evaluation process is too often biased. Moreover, design choices take place in an uncertain context and according to multiple criteria, some of which may be contradictory. In order to track the consequences of design decisions, we are proposing a conceptual data model to perform evaluations within the MBSE framework of Systems Engineering. We then proceed by relying on the relationships demonstrated by such a model to identify the potential impacts of design choices on future product performance. Since data available during the conceptual phase of the design are typically uncertain or imprecise, an original research protocol is extended to a qualitative impact analysis for the purpose of highlighting the most promising alternative system design solutions (ASDS). An example in the mechatronics field serves to illustrate our proposals.

Introduction

Mechatronic design is an interdisciplinary activity that continually strives to integrate widespread functionality into geometrically constrained products. In the competitive marketplace, both time and finances are often lacking when it comes to studying and finalizing several mechatronic concepts and then retaining only the most satisfactory one. Engineers therefore require support in reviewing alternative system design solutions (ASDS) and in making and defending the best design choices as of the earliest product design stages [START_REF] Hehenberger | Hierarchical design models in the mechatronic product development process of synchronous machines[END_REF]. In a Systems Engineering (SE) context [START_REF]Nasa System Engineering Handbook[END_REF], such is the role of evaluation activities in assessing ASDS and in ensuring that design-related decisions take into account relevant multidisciplinary knowledge and can hence be duly justified. With this aim, various analytical approaches and methods can be applied to conduct effectiveness, cost and risk studies as well as to compare different ASDS.

The design evaluation process however faces a number of challenges, including:

1) Though the initial choices are definitely critical to ensuring a successful design project, rating the merit factors of each candidate solution during the conceptual design stage is generally subject to uncertainty and inaccuracy;

2) Designing complex mechatronic products requires multidisciplinary knowledge. Since designers tend to have narrow technical and scientific backgrounds, their understanding of system design objectives and their vision of the evaluation process are often only partial and incomplete;

3) Assessing the consequences when choosing from among several ASDS is a critical step to the process and to this day has still not been resolved effectively [START_REF] Torry-Smith | Mechatronic design -still a considerable challenge[END_REF]; 4) System requirements may at times be interpreted as contradictory when considering a given ASDS. The challenge then is to identify satisfactory ASDS that achieve an acceptable balance between these requirements, as opposed to finding the optimal ASDS.

Although the core of design problematic is how to produce solutions, design solutions synthesis is not the scope of the presented research work. This paper aims to provide some basic elements to address the issues raised in 1 through 4 above by considering just the effectiveness evaluation; due to constraints placed on the paper's length, risk and cost aspects will not be included.

After defining the role of evaluation within the design process, Section 2 will tackle the 2 nd issue raised above in proposing a conceptual data model considered herein as the abstract syntax of a possible language dedicated to evaluation within the Systems Engineering (SE) framework. The intention is for members of a multidisciplinary design team to be capable of sharing a common vision of data as a prerequisite to evaluating ASDS, regardless of their profession, objectives or specialization. Based on this proposed common view, Section 3 will contribute to resolving issue 3 by means of facilitating the identification of potential impact relations between design choices and effectiveness criteria. Once potential impacts have been identified, the consequences of such impacts on the degree of ASDS satisfaction in a multi-criteria context must be analyzed. To this end, Section 4 will formalize the interactions proposed in this research work between a behavior model of the system being designed and a model of stakeholders' expectations. Our proposal seeks to address issue 4 above by adapting a formal approach to determine the level of criterion satisfaction, which entails applying qualitative or quantitative reasoning depending on the uncertainty inherent in the design specification. Section 5 will illustrate our proposals through an example of developing the electrical assistance function for a wheelchair. Section 6 will draw a conclusion regarding future perspectives.

Evaluation in design

Let's consider, without the ambition of achieving completeness, a number of current design theories and methodologies that deal with evaluation issues [START_REF] Tomyama | Design methodologies: Industrial and educational applications[END_REF][START_REF] Sharman | Characterizing Complex Products Architectures[END_REF][START_REF] Sosa | A network approach to define modularity of components in complex products[END_REF][START_REF] Yassine | An Introduction to Modeling and Analyzing Complex Product Development Processes Using the Design Structure Matrix (DSM) Method[END_REF]. According to [START_REF] Blanchard | Systems Engineering and Analysis[END_REF], designers are making progress towards defining the systems under design in more concrete terms by iteratively performing the steps indicated in Fig. 1: • Synthesis: The creative activity by which known elements are placed together in new and more useful combinations in order to produce ASDS; • Analysis: Deriving an estimation and prediction of design parameter values;

• Evaluation: Comparison of each ASDS with other ASDS and verification of compliance with customer requirements. Mechatronic engineering combines mechanical engineering, electrical engineering and computer science within an interactive way. The VDI2206 guideline recommends conducting the design of mechatronics systems according to the so-called "V-model" pattern [START_REF] Gausemeier | VDI 2206 -a new guideline for the design of mechatronic system[END_REF]. The design process distinguishes between the problem solving process of the individual designer (micro-level) and the generic process related to design phases (macro-level). At the macro-level the system is specified functionally, working principle variants are evaluated and selected. Then sub-parts allocated to each involved discipline such as mechanics, electronics, and computer science are specified, realized and integrated to form a system. FIGURE 1: Evaluation vs. analysis and synthesis [START_REF] Gausemeier | VDI 2206 -a new guideline for the design of mechatronic system[END_REF] Several passes through the v-shaped model are necessary to obtain a mature product. Micro-level problem-solving activities are being performed during the design process to generate and then to assess candidate solutions. The present work will distinguish between the evaluation of ASDS (at the macro level) and the evaluation of the design ideas generated at the micro level (during the synthesis step of Fig. 1) in order to produce acceptable solutions (ASDS).

The Function-Behavior-Structure approach supports systematic modeling and reasoning in the systems designing [START_REF] Gero | Towards a situated Function-Behaviour-Structure framework as the basis of a theory of designing[END_REF] and attempts to explain the act of generating design solutions (thus at the synthesis step of Fig. 1). The Function-Behavior-Structure activities include: a formulation which transforms functions into a set of expected behaviors; a synthesis of a structure which exhibits the expected behavior; an analysis of the behavior produced by the structure; an evaluation between the expected and the produced behavior.

The Function-Behaviour-State modeler provides an approach for systematic modeling and reasoning in conceptual design [START_REF] Umeda | Supporting Conceptual Design Based on the Function-Behavior-State Modeler[END_REF]. In [START_REF] Komoto | A system architecting tool for mechatronic systems design[END_REF] it has been extended to incorporate a visualization of geometric information and has introduced interval-temporal logics. It then becomes possible for the system architect to evaluate the consistency between spatial relations in a Function-Behaviour-State model and the corresponding geometric model.

Another design approach is represented by the Axiomatic Design, which is a general method for facilitating the synthesis of suitable design requirements, design solutions and design processes. Two principles must be verified according to Suh [START_REF] Suh | The principles of design[END_REF]: the independence axiom indicates to 'Maintain the independence of functional requirements', while the information axiom recommends to 'Minimize the information content of the design'. The independence axiom provides the designer with a measure for rating the correctness of the design, in insisting that an independent relationship, as represented by an uncoupled or decoupled design matrix, is essential for a successful design [START_REF] Beom-Seon | Axiomatic design approach for marine design problems[END_REF]. Evaluating design solutions according to these two axioms aims at verifying that the system is well designed but does not guarantee that the solutions are the most satisfying to fulfill the stakeholder's needs.

In order to qualify a mechatronic system, a mechatronic index is presented in [START_REF] Moulianitis | A model for concept evaluation in design-an application to mechatronics designof robot grippers[END_REF] in terms of flexibility, intelligence and complexity, as these three characteristics account for much of mechatronic products. The intelligence level of a mechatronic system is determined by both its control functionality (which includes programmability, self-diagnosis, self-repair, negotiation, learning and self-organization) and its information computing ability (e.g. knowledge discovery and analysis, inference mechanism and communication) from the low-level control to the general management level. The flexibility property of a mechatronic system translates its capacity to easily change in order to fit new requirements or situations. Complexity is a consequence of the tradeoff involved when increasing the intelligence and flexibility and moreover may be observed through seven indices (including quantity of components, number of interconnections, number of design solution alternatives and number of feedback loops). The benefit of monitoring such indexes is to help mechatronic engineers in better designing their systems (i.e. a verification point of view) by taking into account the typical characteristics of mechatronic products: flexibility, intelligence, complexity, and strongly-coupled physical phenomena.

The approach of evaluation exposed in this paper is complementary to the above research works as it focuses on how to rank ASDS outputted from the synthesis activities and how to select the most satisfying for the stakeholders (i.e. more of a validation point of view than of a verification point of view). For this purpose, we adopt the Systems Engineering framework which guides the engineers throughout the macro-level design phases without imposing any specific method to synthesize solutions. The specificity of evaluating mechatronic design lies in taking into account, at the earliest possible stage in the design development cycle, the many relevant discipline requirements, in addition to the system architect requirement, in order to design a product.

The evaluation process within the SE framework

Systems Engineering (SE) is an interdisciplinary and collaborative approach based on the standards ISO/IEC 15288 [START_REF]IEEE Standards 15288.2008, Systems engineering -System life cycle processes[END_REF], ANSI/EIA 632 and IEEE 1220, as well as on conceptual guidelines, e.g. SEBoK [START_REF]System Engineering Book of Knowledge[END_REF] and best practice guidelines, e.g. INCOSE handbook [START_REF]INCOSE, System Engineering (SE) Handbook Working Group, System Engineering Handbook, A Guide For System Life Cycle Processes And Activities, Version 3.2.1[END_REF] or Nasa handbook [START_REF]Nasa System Engineering Handbook[END_REF]. SE promotes vocabulary, concepts and a comprehensive approach that facilitates communication within a design team, regardless of the underlying technological field, and moreover relies on a set of standardized processes and activities that have become widely and successfully applied across various industrial fields [START_REF] Kopach-Konrad | Applying Systems Engineering Principles in Improving Health Care Delivery[END_REF][START_REF]System Engineering guide book for transportation systems[END_REF][START_REF]Programme management -Guide for the management of Systems Engineering[END_REF].

Among the aforementioned components, five technical processes run in an iterative manner when engineering a system. These processes, identified in Fig. 2, are [START_REF]System Engineering Book of Knowledge[END_REF]: Mission analysis, Stakeholders' needs and requirements, System requirements, Logical architecture, and Physical architecture. They are supported by three services, namely: System verification, System validation, and System analysis. Thus this paper addresses the set of System Analysis issues and focuses in particular on evaluating the product under design. The next section will present the generic activities associated with the evaluation process.

Activities composing the evaluation process

An evaluation is requested each time engineering choices must be made or justified, e.g. choice of major operations and solution concepts, research and resolution of inconsistencies between requirements, choice of logical vs. physical architecture. The criteria required to evaluate design progress actually evolve in the same manner as design model criteria [START_REF] Maier | The Art of System Architecting[END_REF]. This evaluation process includes generic activities, as summarized in Fig. 3. The main activities composing the evaluation process consist of: defining the evaluation objectives ("why" and "what"), preparing the job ("how"), producing and analyzing results ("do" and "check"), and finally delivering outcomes ("conclude"). Briefly summarized below are the individual tasks relevant to these successive stages. After specifying the scope, objectives and means available to perform the requested evaluation, only the ASDS that satisfy the non-negotiable technical and economic criteria are to be selected for more in-depth analysis. It is generally recommended that the number of alternatives be limited (in the range of 3 to 7) and moreover that all candidate solution characteristics be sufficiently distinct.

'How' activities: Since the evaluation process constitutes the backbone of the decision-making process, the decision-making model must be specified. Such a model takes into account core elements, e.g. evaluation criteria, stakeholders' preferences, the scoring function used to assign desirability levels to system attributes, and the aggregation methods chosen to provide ASDS with the overall desirability levels used to classify or rank design solutions [START_REF] Moulianitis | A model for concept evaluation in design-an application to mechatronics designof robot grippers[END_REF].

Regarding the evaluation of product effectiveness, three main families of multi-criteria decisionmaking methods can be distinguished [START_REF] Fülöp | Introduction to Decision Making Methods[END_REF]: total aggregation methods [START_REF] Keeney | New Industrial Product Design and Evaluation Using Multiattribute Value Analysis[END_REF], paired comparison methods [START_REF] Saaty | On the invalidity of fuzzifying numerical judgments in the Analytic Hierarchy Process[END_REF], and outranking approaches [START_REF] Roy | The outranking approach and the foundations of electre methods[END_REF]. The aggregation methods most frequently used in design are based on Multi-Attribute Utility Theory according to which local 'utility functions' are defined so as to quantify on a standardized scale (e.g. [0 1]) stakeholders' preferences about the 'attributes' of the designed artifact. These local utility values are then aggregated into an overall utility through application of a mathematical formalism (usually additive or multiplicative). The paired comparison methods (such as Analytical Hierarchical Process) are employed to both model stakeholders' preferences and rank alternatives. The primary outranking methods assume datasets similar to those assumed by the Multi-Attribute Utility Theory, yet allow defining just a partial ranking on the set of alternatives, which contains the most promising alternatives of the decisionmaking problem. In 'Electre III', an outranking degree is computed that reflects outranking credibility among several alternatives [START_REF] Fülöp | Introduction to Decision Making Methods[END_REF].

Since the characteristic values of ASDS are not directly measurable from the product, they need to be predicted from models (referred hereafter as behavior model). At the conceptual design stage, behavior models tend to be coarse whereas at the detailed design stage, more specialized and precise models must be taken into consideration in order to derive product feature data. Some activity within the evaluation process thus consists of identifying which level of modeling granularity is required and then ordering additional modeling and analysis work. More generally speaking, evaluation relies on relevant knowledge based on engineering rules, standards, expert reports, simulations and analysis reports from previous completed projects or from measurements carried out on prototypes. In any event, it is necessary to estimate the degree of uncertainty associated with collected data and perform the evaluation accordingly [START_REF] Wood | Computations with imprecise parameters in engineering design: background and theory[END_REF].

'Do and check' activities: ASDS are assessed or ranked according to the selected multi-criteria analysis method. Sensitivity analyses are also conducted to determine whether the resulting classification or ranking is sufficiently robust, e.g. if the classification/ranking remains unchanged in the event of small input data variations. If the evaluation objectives are not met or if results lack adequate differentiation or show excessive dependence on the evaluation methods, then the evaluation process should return to one of its previous steps.

'Conclude' activity: When the objectives are met, a report is produced and delivered to decisionmakers; this report includes: information on assessment objectives, the selected ASDS, the data sources along with their degrees of uncertainty, the decision-making model, evaluation results with their sensitivity analyses, and justifications of every choice made during the evaluation process.

The conceptual data model shown in Fig. 4 allows characterizing and describing the relevant concepts and relationships from the SE context that must be taken into consideration throughout the evaluation activities, from the conceptual design phase to the detailed design phase. As displayed in a UML class diagram, each class describes a requested concept from the domain and is characterized by a set of typical attributes and relations. Each relation in turn describes and formalizes a link (i.e. dependence relationship) between two concepts. As such, this conceptual data model corresponds to the abstract syntax, i.e. the vocabulary and basic grammar of the meta-model of the so-called 'evaluation language' proposed herein. Moreover, this language is indeed an extension or enrichment of Systems Engineering (SE) vocabulary and thus of the engineering language currently proposed in an MBSE context [START_REF]INCOSE, Survey of Model-Based Systems Engineering (MBSE) Methodologies[END_REF]. The section (2.2) presents the main classes of concepts and relations being considered among the three domains involved in the evaluation process: technical requirements, candidate solutions, and evaluations.

A conceptual data model for evaluation data characterization within the SE framework

According to Blanchard and Fabricky [START_REF] Blanchard | Systems Engineering and Analysis[END_REF], the 'Design Consideration' concept designates any element of the complete set of attributes and characteristics potentially exhibited by: a system being engineered, a product, or a service. 'Design Considerations' are involved during the customer requirement analysis to facilitate the stakeholders' needs expression. They are also proved to be useful in analysis activities for the purpose of fully characterizing the product being designed and hence revealing the expected, as well as unexpected, behavior or properties. Among the set of 'Design Considerations', let's distinguish the 'Design Dependent Parameters', which are controlled by the designers (e.g. geometric dimensions, weight, reliability, maintainability or other-ilities [START_REF] De Weck | Investigating Relationships and Semantic Sets amongst System Lifecycle Properties (Ilities)[END_REF]). Each instance of 'Design Dependent Parameters' generates a design candidate solution. 'Input Design Dependent Parameters' (iDDPs) are 'Design Dependent Parameters' the values of which are chosen by the designers and determine other 'Design Dependent Parameters' values. The iDDPs which can be coded numerically referred to as design variables. Design variables include optimization variables used to improve a satisfactory solution even further. 'Output Design Dependent Parameters' (oDDPs) are 'Design Dependent Parameters' the values of which are generally computed from behavior models and iDDPs values. 'Output Design Dependent Parameters' are parameters of interest for the stakeholders and are used to evaluate an ASDS. Energy autonomy is an example of 'Design consideration' for an electrical wheelchair. Then an oDDP can be the 'number of km travelled without reloading in energy' and an iDDP can be the 'battery capacity'.

The 'Design Independent Parameters' are known as "incurring" factors (for example: labor costs, variation of raw material characteristics, the market entry of a new competing product, energy cost, a new regulation etc.). 'Design Independent Parameters' are not controlled by the designers but they must be taken into account by decision-makers when selecting the most promising design solutions. Considering multi-criteria decision-making methods (such as the ones cited in section 2.1 or the proposed one in section 4) the evaluation process establishes the level of adequacy between a consistent set of technical requirements (e.g. translations of stakeholders' needs by designers in considering the entire product life cycle) and ASDS . The evaluation criteria determine the principles or rules introduced to judge the level of adequacy. The evaluation criteria are specified by technical indicators (TIs), whose attributes comprise: the rating scales, objectives, target levels, and current level. A TI objective is specified by a single performance requirement or a single constraint.

While defining needs, attention turns to identifying MOEs (Measures Of Effectiveness), which are mandatory TIs to ensure system success. Inability to reach an MOE objective is considered a cause of failure [START_REF]Nasa System Engineering Handbook[END_REF].

Not directly estimable during the design, MOEs can be decomposed into MOPs (Measures of Performance), which are TIs associated with the product's physical or functional properties. MOPs may in turn be broken down into 'Technical Performance Measures' (TPMs) or characteristics, which are measured from attributes inherent to the designed product [START_REF] Blanchard | Systems Engineering and Analysis[END_REF]. Current TPM values are in fact derived from oDDP values. For instance let us define some MOE, MOP and TPM when designing an electrical assistance for a wheelchair. According to the stakeholders, the 'type of job that such assistance allows to practice in outside conditions' is a MOE (the MOE objective is to be able to work as a roundsman in a company). Such a MOE can be decomposed in several MOPs, the 'capacity to drive outside' is one of them (the MOP objective is to be able to drive on unsurfaced roads). The MOP can be decomposed in several TPMs, the 'capacity to climb sloping road' is one of them (the TPM objective is to be able to climb 10% slopes with a 120 kg total charge).

ASDS are described by their functional and physical architectures models (generated by SE activities) and also by behavior models built up to lead analysis studies and to calculate oDDP values. The knowledge elements needed to perform such analysis and the results of evaluation reports are collected in the 'Evaluation repository'.

In order to be able to analyze the impacts of design choices on criteria TI current values, it is first necessary to identify which TI current value (i.e. oDDP values) can be (adversely or positively) affected by iDDPs and then to determine the magnitude of such impacts. The next two sections are intended to propose some resolution to these issues conforming to the conceptual data model shown in Fig. 4.

Identification of potential impacts

In complex system design, it is not altogether obvious whether or not an iDDP exerts potential impact on an oDDP. The following section will analyze how traceability relations stemming from both SE models and the conceptual data model (Fig. 4) can actually help detect potential influence relations between DDPs.

Without imposing restrictive constraints on system architects, we are able to postulate that (Fig. 4):

• Any evaluation criterion is expressed using at least one technical requirement; • Any criterion is specified by at least one technical indicator(TI); • Any TI is associated with one and only one non-functional requirement (more precisely with one performance requirement or with one constraint).

Based on these assumptions and by utilizing the traceability relationships between SE elements in system models, the influence relations between TIs and iDDPs can be underscored so as to identify what might generate some impact. The formalization of such a notion will be provided hereafter.

Traceability relations

Traceability is defined as the ability to describe and track the life of a requirement from its origin (in the design phase) to deployment (in the operations phase) [START_REF] Berenbach | An Introduction to Project and Product Traceability, Incoce Insight[END_REF][START_REF] Königs | Traceability in Systems Engineering -Review of industrial practices, State-of-the-art technologies and new research solutions[END_REF]. The main needs behind introducing traceability in SE are summarized in Table 1.

Need

Description Coverage analysis

Are all requests for features in the delivered product? Do test cases exist for all functional and non-functional requirements? Impact analysis

Tracing from the impacted features to the actual system design to determine the extent of eventual modifications Derivation analysis Help discover the origin and rationale of a function; alternatively, a component requirement is traced back to the original rationale for its creation TABLE 1: Traceability needs in an SE process A more formal definition can be provided for:

• A 'traceability relation', denoted ℑ on ΕxΕ, with Ε a set of artefacts, is a partial relation on ΕxΕ that is non-reflexive, non-symmetric and non-transitive. For example, the SE relation 'refines' (requirement b refines requirement a) defines a 'traceability relation' on RxR where R is the set of the artefacts 'system requirements'. SE relations have distinct semantics (refines, built from, specifies…); traceability relations have not.

{ } ) ( ) ( a b b a I k k τ = =
, where τ k (a) is τ (τ k-1 (a)); the coverage of element a is:

) ( ) ( 1 a I a I k q q C U = =
Such formalization is used to compute the set of artefacts that can potentially impact or be impacted by others as proposed in next section.

Using traceability relations to identify potential impacts

Table 2 presents examples of relationships between entities according to an example of an SE metamodel (i.e. a model proposed by one of the MBSE solution providers; other meta-models derived from other providers may also be used) [START_REF]A primer for Model Based Systems Engineering[END_REF]. To these SE relationships, are associated 'traceability links' as defined above.

According to the conceptual data model shown in Fig. 4, we propose adding the relationships between criteria, requirements and Technical Indicators (TIs) to the basic relationships listed in Table 2, with the outcome shown in Table 3. Thus, if the value of some iDDP (attribute of a component) is changed, traceability links _ , , , _ , , !" spread the possibility of impact to the evaluation criteria (Fig. 5). Similarly, from traceability links, _#$ , % _#$ , & _#$ , _#$ , '_ () it is possible to identify the functions and components potentially impacted by a change in some TI objective value of one criterion.

Source / Target

The TI value reached by an ASDS is derived from an oDDP value. According to available knowledge, the transformation between iDDPs and oDDPs may be either a quantitative model with a low level of uncertainty or a qualitative one with higher uncertainty. The latter case is critical during product design since it occurs at the very earliest stage of the design development cycle, when both the future success and cost issues of the design project are being determined in full. For this reason, Section 4 will focus on this SE analysis, which often remains inadequate in its methodology.

Decision-making aid in designing complex products in an SE context

Linking a predictive system model with a decision-making model

A number of notations will be introduced in this subsection. Let's also consider that the system may be described by n oDDPs relative to the decision-making criteria. Each oDDP is assigned values from the set denoted i Y , with 1,..., i n = and with

: i i T X Y → ,
1,..., i n = (Fig. 6).

T may be a formal transformation deduced either from physical laws or from validated knowledge in the field. For example, a dynamical model of the wheelchair can compute the 'Current consumption' from the values of iDDPs such as 'nominal torque of the engine', 'diameter of the wheel', 'reduction ratio of the gearbox' and others impacting iDDPs. In general however, T is not explicitly known and, in the most favorable case, it can be approximated by a predictive model [START_REF] Quirante | Multiobjective optimization including design robustness objectives for the embodiment design of a two-stage flash evaporator[END_REF].

The oDDPs must then be interpreted in terms of satisfaction with respect to the stakeholders' goals. The Multi-Attribute Utility Theory allows expressing the degree of satisfaction of an oDDP by a realvalued utility function in [0,1] [START_REF] Fishburn | Utility Theory for Decision-Making[END_REF][START_REF] Fishburn | The foundations of expected utility[END_REF][START_REF] Keeney | Decisions with Multiple Objectives Preferences and Value Tradeoffs[END_REF]]. Let's denote therefore for {1,..., } i n

∈ , i u ( : [0,1] i i u Y → ) the real-valued utility function for oDDP i . For i i y Y ∈ , ( ) i i
u y reflects the extent to which the goal associated with the TPM i is satisfied by the value i y .

Then the satisfaction level of a higher-level TI, in the hierarchy of criteria, e.g. a MOP or a MOE, in the decomposition tree containing TPM, should be computed using some aggregation operator U (Fig. 6).

According to the Multi-Attribute Utility Theory, the weighted arithmetic mean can be the operator used to compute the global utility from the local utilities ( )

i i u y .
As noted above, transformation T is typically unknown or marred by uncertainty, and this mainly arises during the preliminary (or conceptual) design phase. The scenario is then often played out where experts or senior engineers are asked to advise on ASDS and judge the qualitative effect of design choices on stakeholder satisfaction. To properly treat this kind of model, we have relied on the research work presented in [START_REF] Imoussaten | Multi-criteria improvement of options[END_REF] regarding qualitative analyses.

Qualitative analyses

The notion behind the qualitative model in [START_REF] Imoussaten | Multi-criteria improvement of options[END_REF] is that an expert can express the impact of an iDDP instance directly as a degree of satisfaction of an oDDP. Our attention here is thus focused on the transformation u o8 ,

1,... i n =

, which is approximated by a qualitative model (Fig. 7). Figure 7 has to be generated by the designer team in agreement with the stakeholders. Two scales are used in this context: a positive ordinal scale PS and a negative ordinal scale NS . If the impact of a given instance j x of iDDP j X on the ith oDDP is positive, its values are taken from PS (ex: strong, medium, low, etc.) and the notation + ij δ is introduced. On the other hand, if the impact is negative, its values are derived from NS (ex: strong, medium, low, etc.) with use of the notation - ij δ . Should the expert not be able to decide, the unknown impact is denoted u ij δ . This paper has assumed that PS NS = and an absence of impact is represented by the value 0 (which corresponds to the lower value on the PS scale). To assign the degree of impact of an ASDS 1 ( ,..., )

m x x x X = ∈
on an oDDPi, [START_REF] Keeney | Decisions with Multiple Objectives Preferences and Value Tradeoffs[END_REF] introduced two aggregation operators along with two propagation constraints. Each combination of an aggregation operator with a propagation constraint yields a decision-maker's attitude. The following pessimistic or optimistic attitude of the decision-maker can serve as a guide. Indeed, the estimation of the ASDS 1 ( ,..., )

m x
x merged impact on oDDPi naturally depends on system behavior, as well as on the decision maker's decisional behavior: a pessimistic attitude (whereby a risk aversion position will lead to concluding the most highly negative merged impacts) vs. an optimistic attitude (whereby risk acceptance will conclude the most highly positive merged impacts).

Let's denote x i, δ the impact of ASDS x on oDDP i. We also consider that ,

i x PS NS δ ∈ ×
and can be represented by the pair ( , , at i x δ + , , , at i x δ -), as proposed [38], where , , at i x δ + (resp. , , at i x δ -) corresponds to an aggregation of positive impacts (resp. negative impacts) and {1, 2} at ∈ corresponds to the decisionmaker's attitude ("1" encodes the pessimistic attitude and "2" the optimistic attitude). In the following, ( , , at i x δ + , , , at i x δ -) will be explained for both these attitudes.

The pessimistic attitude (at=1 in , , at i x δ + and , , at i x δ -) is modeled by assigning the least positive impact as the aggregation of positive impacts (less favorable case) and the worst negative impact as the aggregation of negative impacts (less favorable case again), in which case the propagation constraint consists of comparing the least positive impact value with the worst negative impact value on oDDP i, resulting in:

     > = - ∈ + ∈ + ∈ + - + + otherwise if ij S j ij S j ij S j x i x i x i x i 0 max min min , , , 1 , , δ δ δ δ      > = - ∈ - ∈ + ∈ - - - + otherwise if ij S j ij S j ij S j x i x i x i x i δ δ δ δ , , , max max min 0 1 , , (1)
In this case, an unknown impact corresponds to a negative impact and is equal to the top of the NS scale.

The optimistic attitude (at=2 in , , at i x δ + and , , at i x δ -) is modeled by assigning the highest positive impact as the aggregation of positive impacts and the worst negative impact as the aggregation of negative impacts. In this case, the propagation constraint consists of comparing the highest positive impact value with the worst negative impact value on oDDP i, hence:

     > = - ∈ + ∈ + ∈ + - + + otherwise if ij S j ij S j ij S j x i x i x i x i 0 max max max , , , 2 , , δ δ δ δ      > = - ∈ - ∈ + ∈ - - - + otherwise if ij S j ij S j ij S j x i x i x i x i δ δ δ δ , , , max max max 0 2 , , (2)
For this latter case, an unknown impact corresponds to an absence of impact and is equal to the bottom of the PS scale. as the impact of the m_tuple x of iDDP on the n oDDPs. Then, in order to avoid risky choices, it can be reasonably stated:

)) ( max ), (

i i at x i i at x at x at x - + - + = = δ δ δ δ δ min ( ) , ( , , , , , , at x
Note that veto and dictator effects of some criteria through min and max operators can be smoothed when a weights distribution is assigned to the oDDPs as suggested in [START_REF] Montmain | Preference and causal fuzzymodels for manager's decision aiding in industrial performance improvement[END_REF].

According to expressions (1) and ( 2), one of the values

at x , + δ or at x , - δ is equal to zero.
The most promising ASDS would then be the one with the highest positive impact or otherwise the lowest negative impact on the n oDDP:

The most promising ASDS:

     ≠ ∃ - ∈ + + ∈ otherwise i if at x ASDS x at x i at x ASDS x , , , , min arg 0 : max arg δ δ δ (4)
Section 5 will illustrate this type of qualitative analysis through designing an electrically-assisted device for a wheelchair.

Illustrations

This section will illustrate the proposed approach in the context of designing of a power-assisted wheelchair. Such an assisted wheelchair has been developed by a pluridisciplinary team on the mechatronics platform of Ecole des Mines d'Ales. The purpose of this electrical assistance is to promote employment opportunities for the mobility impaired. The system is being made available firstly to allow a person with reduced mobility to perform an outdoor job without undue fatigue and secondly to enable driving the wheelchair as if it were a manual device. The objectives adopted refer to the capability of moving on uneven ground and under exterior conditions. Constraints regarding maximum allowable speed, maximum dimensions and safety have been defined in the relevant set of regulations [START_REF] Cerah | Spécifications Techniques Vehicules pour Handicaps Physiques[END_REF].

Once stakeholders' needs have been translated into a set of technical requirements (which should subsequently be enhanced as the design process progresses), the main principles of electrical assistance are to be analyzed and a concept of electrical assistance selected [START_REF] Lô | Needs for tracing the consequences of decisions in mechatronics design[END_REF]. The selected product concept chosen in [START_REF] Lô | Needs for tracing the consequences of decisions in mechatronics design[END_REF] is the concept of motor-wheel consisting in measuring the pushing force of the mobility-impaired individual on the handrail and then delivering additional torque on each wheel in proportion to the measured force.

During the preliminary design stage, a set of evaluation criteria and associated TIs are defined in accordance with the technical requirements; these elements are partially displayed in Fig. 8. The mission of the assistance system is to help reduced mobility persons to be maintained in their job or to access to a new one. It is the real motivation of the customers (big firms which have obligation to employ reduced mobility persons). So the assistance system has to improve such persons mobility (needed, for instance, to practice a roundsman profession) but it must be quite easy and intuitive to use (as a manual wheel chair) in order the person to be able to do the job efficiently. So 'Employability' criterion must be satisfied to ensure success of this assistance system. As per the agreement with clients, this criterion is associated with the MOE 'Ability to perform a roundsman's job'. Such an 'Employability' criterion has been broken down into both a 'Mobility criterion' (with its associated MOP: 'Outside drive possibility') and a 'User Friendliness' criterion (with its MOP: 'Just an assistance'). Another lower level of the criterion hierarchy with associated TPM indicators is correlated with a set of more elementary oDDPs (such as the ability to: climb, overcome an obstacle, maintain average speed etc. as shown in Table 4). Let us remark that such a criteria hierarchy is not unique and may be different depending on the design team, but each criterion is expressed from technical requirements (according to the conceptual data model in Fig. 4). vs. smart), tuning facilities (with or without), and system status feedback to the user (rich or poor) as seen in Table 5. The iDDPs of table 5 have been identified by the designers within the development team. They result from the SE activities performed by the team and depend also upon the designers' experience. The example has been adapted for the sake of explanation but we have done the effort to stick the reality as well as possible. We do not focus in the paper on how ASDS are generated by the designers but on how choices can be made rationally between them within a multidisciplinary context. According to the identified iDDPs, the whole proposed method is all about to selecting some solutions from all possible combinations. As there is no incompatibility between iDDPs, the number of possible ASDS is 3 2 x2 6 = 576. The question is which ASDS are the most promising relatively to the main criteria: mobility, user friendliness and employability? where N denotes a zero impact (0), L denotes low impact, M denotes medium impact, H denotes high impact and U an unknown impact (i.e. an impact is present, yet its strength raises doubts).

3) +M +M +M N N -L -M -M -M (1) -L N N +M N -H U1 (2) N +L -L +H -L -L U2 (3) N +L -M -L -M -M U3 (1) +L +L +L -M -M +L (2) N +L +H +H -L -L +M (1) +L N -L +M +H -L -L -H -H (2) +M +L +L +L +L N N -L -L (1) +M +L +M +M +L -H -M +M (2) +L N +L +L +M -L -L +L (1) +M +L +H +H (2) +L -L +L -L (1) -L N N +L N N N (2) +M +M +L +M +L N +L -L +L (1) -M N N +L N N N (
For instance, equipping the motor wheel with one CC motor, the impact on the 'total wheelchair width' (oDDP4) satisfaction level is (-L) due to the motor large diameter while it is (+L) if equipped with smaller diameter motors. 'Tuning facility' increases satisfaction level for 'climbing capacity' (+M) or 'overcoming obstacles capacity' (+M) because of the possible adaptation of the assistance to the context but decreases 'manual usage' (-L) since the user has to adjust assistance parameters.

To be able to fulfill Table 6 automatically using more fundamental or partial knowledge is quite a challenging issue. A way to overcome this difficulty is to trust experts. Even if Table 6 was the most pertinent, it is not so clear how to aggregate such data and so how to select the most satisfying solutions. It is the purpose of this study case to illustrate hereafter how the method developed in section 4 can help designers make their choice rationally from Table 6.

Thanks to the qualitative analysis developed in Section 4, we can now compute the impacts of the various ASDS on the satisfaction level on criteria.

For instance, let's consider the particular ASDS defined by the 8_tuple x={x 1 :3,x 2 :2,x 3 :2,x 4 :1,x 5 :1,x 6 :2,x 7 :2,x 8 :2} (i.e. the gray case in Table 6), oDDPs i , iЄ{1,..,7} the oDDPs linked with the 'Mobility' criterion and oDDPs i, iЄ{8,..,11} the oDDPs linked with the 'User Friendliness' criterion.

• Applying expression (1) in assuming a pessimistic attitude, the impact of ASDS x on oDDP6 (autonomy) is (0,L) and (0,H) on oDDP10 (manual usage) since : min < =+ > + = min ?, @, @, ?, @, @ = ?; max • Applying expression (2) in assuming an optimistic attitude, the impact of ASDS x on oDDP6 (autonomy) is (M,0) and (0,H) on oDDP10 (manual usage) since : max < =+ > + = max ?, @, @, ?, @, @ = @ > max + < =+ D = max ?, ? = ? so < =," >K = M and < =," DK = 0 max < EG+ > + = 0 < max + < EG+ D = max @, ?, ?, H, @, ? = H so < EG," >K = 0 and < EG," DK = H

The results of table 7 do not show any incoherence, and illustrate how the qualitative method proposed in Section 4 can be applied on a mechatronic study case. Even if Table 6 could have been fulfilled by experts in different disciplines, the proposed qualitative evaluation method allows to synthetize their advices in a rational, reproducible and traceable way.

Remarks:

• It must be clarified that these results depend on any translation of the impact value on the PS or the NS scale. As a matter of fact, translating these values means that the current state y of the oDDP has changed. For instance, any component added to the product adversely affects the total wheelchair weight (so no choice could feature a positive impact!). In assuming a nonzero total weight however, choosing between the two solutions may modify this weight either positively or negatively. • As seen in Section 2, a sensitivity analysis must be performed. In pursuing this goal, we have not yet investigated any approaches other than that consisting of testing an array of impact values. As an example, changing U2 values from U2 = -L to U2 = -M does not change the most promising ASDS for 'Employability', although changing U2 = -M to U2 = -H actually eliminates all ASDS. It is obvious that the experts need to be truly trusted professionals.

• For a more flexible attitude, we could assign a weighting distribution to the oDDPs related to the customer preference [START_REF] Montmain | Preference and causal fuzzymodels for manager's decision aiding in industrial performance improvement[END_REF].

Conclusion and outlook

Mechatronic design is an interdisciplinary activity that always tends to integrate more functionality into geometrically-constrained products. What makes mechatronic design quite specific is the need for an interdisciplinary problem solving approach at the earliest of the preliminary design stages. The role of the evaluation process therefore is to support designers each time engineering choices need to be made or justified. However it is often difficult to anticipate, during these earlier stages, the consequences of design decisions on the effectiveness of such complex products. Thus the designers should be able to evaluate the system properties that result from design changes in the functional and physical architectures of the system even when models of the system are still coarse. The proposed evaluation method aims at achieving this objective.

By adopting the MBSE framework in Systems Engineering, we have proposed a meta-model of evaluation so that designers from different technical backgrounds can share a common vision of the evaluation process. Based on the relationships exhibited by such a meta-model, we have also proposed a protocol for identifying the potential impact relations of design choices on future product performance. Depending on the accuracy and precision of the models introduced to advance the design, a quantitative or qualitative analysis of such impacts must be performed. During the conceptual design phase, given that the data are quite uncertain or imprecise, we have extended an original qualitative impact analysis in order to detect the most promising alternative system design solutions. Our proposals have been illustrated through the design of a mechatronic system.

The proposals we've presented are complementary to current design approaches, which focus on ensuring that mechatronic products are well-designed, since our scope is more oriented around design validation (to satisfy stakeholder requirements) than design verification (to follow the best design practices in ensuring highest product quality). Both of these focuses are indeed necessary.

Although the design of an electrical assistance for a wheelchair is a typical example of mechatronic interdisciplinary design on which we successively applied our proposals, the method is not necessarily unique to mechatronics product development but may be applied in other interdisciplinary field of engineering.

FIGURE 2 :

 2 FIGURE 2: Technical and support processes in SE Evaluation, is indeed an important activity of System Analysis in SE since according to standards (EIA 632, l'IEEE 1220, SEBok 2013) technical performance assessment and tradeoff studies are necessary activities of SE.

FIGURE 3 :

 3 FIGURE 3: Flowchart of activities in the Evaluation Process 'Why and what' activities:After specifying the scope, objectives and means available to perform the requested evaluation, only the ASDS that satisfy the non-negotiable technical and economic criteria are to be selected for more in-depth analysis. It is generally recommended that the number of alternatives be limited (in the range of 3 to 7) and moreover that all candidate solution characteristics be sufficiently distinct.

FIGURE 4 :

 4 FIGURE 4: A Conceptual Data Model for characterizing evaluation data in an SE context

  • A 'traceability link', denoted τ, is an oriented link between two artefacts; it is associated with a traceability relation between one source artefact 'a' and one target artefact 'b', such that b = τ(a). So, if ℑ (a,b) is true then it exists τ such as b = τ(a). The set of artefacts connected by traceablity links forms a digraph. • If ℑ 1 and ℑ 2 are two traceability relations defined on ΕxΕ, then ℑ 1 o ℑ 2 is a traceability relation on ΕxΕ. Any artifact a, with a Є Ε, can display an impact δ ba on other artefacts b of Ε if and only if a is the source of at least one traceability link τ with b = τ(a). The set of artefacts that are in relations by k successive compositions of a traceability relation ℑ is thus expressed as:

FIGURE 5 :

 5 FIGURE 5: Identifying potential impact from traceability links Using compositions of the traceability links presented in Tables 2 and 3 can serve to highlight potential impacts between any function parameter (an instance of an iDDP) or any component

  Let's start by considering a situation with m iDDPs. Each iDDP is assigned a value from the set denoted of the j th iDDP. * + may be a set of nominal, discrete or continuous values. Each element of X represents an ASDS.

FIGURE 6 :

 6 FIGURE 6: Merging a system predictive model with a decision-making modelFor instance let's consider the design of a motor-wheel for a wheelchair: the diameter of the wheel in inches, the nominal torque provided by the electrical engine in N.m, the reduction ratio of the

1 (

 1 assigned to the i th oDDP. 2 may be a set of nominal, discrete or continuous values. For instance the oDDP i 'Current consumption' may take its values , in the interval 2 = -1, 514.Each input configuration in X corresponds to an output in Y representing the system characteristics of interest. Let's indicate this correspondence by the transformation:

FIGURE 7 :

 7 FIGURE 7: Influence digraph (δ + : improvement, δ -: degradation, δ u : unknown)

Let

FIGURE 8 :

 8 FIGURE 8: Decomposition of Criterion (Cr) and associated TIs (MOE,MOPs,TPMs)

TABLE 2 :

 2 Traceability relations between SE entities[START_REF] Fülöp | Introduction to Decision Making Methods[END_REF] One criterion and one TI may be correlated with the same requirement if and only if this requirement specifies the TI objective in its formulation. The inability to link any of the TIs with a single performance requirement or with a single constraints attests to a certain level of incompleteness in the set of requirements.

		Target /	SE relations and their associated
		Source	(traceability links)
	Functional requirement	Function	Basis of ( _ ) / Based on ( _ )
	Performance requirement Function	Specifies ( / Is specified by ( _
	Performance requirement,	Component	Specifies (	/ Is specified by ( _
	Constraint
	Function	Component	Is allocated to ( _ ) / Performs (
	Function	Function	Decomposes ( )/ Decomposed by ( _ )
	Component	Component	Built from ( _	) / Built in ( _ )
	Requirement	Requirement Refines ( ) / Is refined by ( _ )
	Requirement	Interface	Specifies ( / Is specified by ( _
	Interface	Component	Joins ( / Joined to ( _ )
	Interface	Link	Comprised of (	/ Comprises ( _
	Link	Item	Transfers ( )/ Is transferred by ( _
	Source /Target	Target /	SE relations and their associated
		Source		traceability links
	Criterion	Criterion	Decomposes		/Decomposed by	_
	TI	Criterion	Precises (	/ Is precised by ( _
	Requirement	Criterion	Expresses (		/ Expressed from (

_ TI non-funct. requirement Traces ( / Is traced by ( _

TABLE 3: Extension of traceability relation between SE entities

TABLE 4 :

 4 output DDPs i, iЄ{1,..,7} relative to 'Mobility' and output DDPs i, iЄ{8,..,11} relative to 'User friendliness'As the design progresses, these chief concerns must be handled, namely choices of: mechanical transmission and reduction (gears vs. rack and pinion), number of electric motors (one or more per wheel), location of the battery and electronics board (on the wheel vs. the chair), control type (reflex

	Easy ass. disassembly Time <5'	Drive easiness As if manual

TABLE 5 :

 5 input DDPs j, jЄ{1,…8)

TABLE 6 :

 6 Example of impacts of instances of input DDPs xj on output oDDP i

	iDDP1 Reduction type	iDDP2 Motors	iDDP3 Battery location	iDDP4 Wheel structure rigidity
	motor (1) on board (1) iDDP5 rack and pinion (2) on wheel (2) Electronics board location oDDP1 oDDP2 oDDP3 oDDP4 oDDP5 oDDP6 oDDP7 oDDP8 oDDP9 oDDP10 oDDP11 mixed (3) 1 motor (1) 3 motors (2) >3 motors (3) battery location (1) package on chair (2) high (1) some flexibiity (2) smart control (1) reflex control (2) no tuning possibilty (1) tuning posibility (2) no feedback (1) feedback to user (2) iDDPs iDDP6 Control type iDDP7 Setting iDDP8 Feedback to user (1) +M +M +M -L -L -M -L -H -H (H: High, M: Medium, L: Low, N: null (0), U gear on (2) +L +L +M +L +L -L -H -L -L

k : unknown)

No behavior model being available at this stage of the design process to compute how iDDPs values impact the oDDps the analysis relies on the expertise of a senior designer who provided advices relative to the impacts of such choices on the degree of utility of elementary oDDPs, as summarized in Table

6

. The ordinal scale on which the impacts are assigned their values is PS=NS={H,M,L,N,U},

In addition to incorporating most of the recent research on decision theory (in the aim of increasing the level of trust designers can show in the evaluation process), our research has been intended to improve the consistency between successive and more refined evaluation results through conducting the SE process in successive layers, thus yielding detailed insight into the design and taking advantage of both inter and intra SE-level traceability relations.

According to [START_REF] Torry-Smith | Mechatronic design -still a considerable challenge[END_REF] and with the optimistic attitude assumption:

• the impact of ASDS x on all oDDPs relative to 'Mobility' is:

• the impact of ASDS x on all oDDPs relative to 'User Friendliness' with U1 = -H, U2 = -L, U3 = -H (Table 6) is:

Under the optimistic attitude assumption , the most promising ASDS relative to 'Mobility' on one side and 'User friendliness' on the other side can be determined by applying expression [START_REF] Tomyama | Design methodologies: Industrial and educational applications[END_REF]. Out of the total 576 ASDS, 20 are the most promising as regards 'Mobility' (the colored iDDPs choices on line 'Mobility' in Table 7) and 8 are the most promising as regards 'User friendliness' (the colored iDDPs choices on line 'User friendliness' in Table 7). Ultimately, under the optimistic attitude assumption, most promising ASDS for 'Employability' are those that maximize the minimum positive impacts of ASDS on both oDDPs relative to 'Mobility' and to 'User friendliness' provided such a minimum is nonzero or, otherwise, that minimize the maximum negative impacts of ASDS on oDDPs relative to (Mobility' and 'User Friendliness').

Therefore, by computing the following:

The so found 16/576 most promising ASDS are shown in Table 7 (colored iDDPs choices on line 'Employability'). In this particular case, the number 16 is obtained because whatever the choices of iDDP6, iDDP7, iDDP8 (2x2x2 possibilities) these solutions are the most satisfying. It can be noted that the set of ASDS with a higher degree of utility for the 'Employability' criterion is larger than the intersection of the set of ASDS with a higher degree of utility for the 'Mobility' criterion and the set of ASDS with a higher degree of utility for the 'User Friendliness' criterion.

From the sixteen most promising ASDS for the 'Employability' criterion, four are also the most promising for the 'Mobility' and 'User-friendliness' criteria. They are those corresponding to (the darkest iDDPs choices): mixed reduction type (gearbox and rack and pinion), 3 motors on each wheel, battery and electronics boards on wheel, not too a rigid structure, feedback provided to the user. As regards control type and tuning facilities choices remain opened.


Patricia Derler

Klaus Schneider

Jean-Pierre Talpin

on Formal Methods and Models for System Design (MEMOCODE 2017)

This is a special issue of ACM TECS consisting of selected papers of the 15th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE 2017). MEMOCODE's general objective is to bring together researchers and practitioners interested in formal methods and models for system design and development to exchange ideas, research results, and lessons learned. System design covers the design and development of hardware, firmware, middleware, and application software for systems ranging from single embedded devices to highly networked CPS and systems in the internet of things (IoT). MEMOCODE emphasizes the importance of formal models and methods in correct system design in all aspects of computer system development. In particular, MEMOCODE focuses on research contributions and formal foundations, engineering methods, tools, and experimental case studies.

MEMOCODE 2017 took place in Vienna (Austria) and was co-located with the conference on Formal Methods in Computer-Aided Design (FMCAD) as in some previous years. Among the 48 papers submitted to MEMOCODE 2017, we have selected the following six papers for inclusion in this special issue that show the broad spectrum of MEMOCODE's field of interest which covers all phases of system design:

-Modeling: 'Stochastic Assume-Guarantee Contracts for Cyber-Physical System Design' by Jiwei Li, Pierluigi Nuzzo, Alberto Sangiovanni-Vincentelli, Yugeng Xi, and Dewei Li presents an assume-guarantee contract framework for the design of cyber-physical systems under probabilistic requirements. System behaviors, assumptions, and guarantees are described by a stochastic signal temporal logic. For certain systems, the approach can check contract compatibility, consistency, and refinement, and can generate a controller to guarantee that a contract is satisfied. -Verification: 'Mining Missing Assumptions from Counter-Examples' by Guillaume Plassan, Katell Morin-Allory, and Dominique Borrione observed that in formal verification of register-transfer level hardware designs, one often experiences false failures due to under-constrained models. The approach extracts the missing assumptions from counterexamples to help the designers to correct their models. -Testing: 'Model-based, mutation-driven test case generation via heuristic-guided branching' by Andreas Fellner, Willibald Krenn, Thorsten Tarrach, Georg Weissenbacher, and Rupert Schlick introduces an algorithmic framework for parallel heuristic-guided searches for test case generation of action systems. Since no single heuristic is able to find all the mutants that are found by the others, the best result is achieved by running multiple heuristics independently and combining their results.

-

  Synthesis: 'Compositional Dataflow Circuits' by Stephen A. Edwards, Richard Townsend, and Martha A. Kim presents a technique for implementing dataflow networks as compositional hardware circuits. Based on a first abstract dataflow model with unbounded buffers that supports data-dependent blocks (mux, demux, and nondeterministic merge), it is shown how to faithfully implement such networks with bounded buffers and handshaking in a compositional synthesis procedure. Insert-ing or removing buffers only affects the performance but not the functionality of the generated networks.-Provable Correctness/Security: 'The Mechanized Marriage of Effects and Monads with Applications to High Assurance Hardware' by Thomas N. Reynolds, Adam Procter, William L. Harrison, and Gerard Allwein presents a core calculus of secure hardware descriptions with its formal semantics, security type system and mechanization in Coq. This work is the core of the functional HDL ReWire and supports a full-fledged, formal methodology for producing high assurance hardware. -Quantified Security: 'Quantifying the Information Leakage in Cache Attacks via Symbolic Execution' by Sudipta Chattopadhyay, Moritz Beck, Ahmed Rezine, and Andreas Zeller present their CHALICE framework that is able to determine by symbolic simulation the amount of information that can actually leak through cache timing attacks for a given program, a cache model, and an input. The core of CHALICE is a novel approach to quantify information leaks that can highlight critical cache sidechannel leaks on arbitrary binary code.

ACM Transactions on Embedded Computing Systems, Vol. V, No. N, Article A, Publication date: January YYYY.

We are happy the the authors of these papers agreed to extend their already published MEMOCODE papers which were again checked by the usual review process or ACM TECS. We are proud that all of the papers that we suggested were finally accepted and are now included in this special issue.

We would like to thank many people who contributed to the success of this special issue. In particular, we thank the reviewers for their valuable feedback to the authors. We would also like to thank the editor-in-chief, Prof. Sandeep K. Shukla for suggesting this special issue, and Ms. Laura Lander for her support in the review and publication process. Patricia Derler, National Instruments Klaus Schneider, TU Kaiserslautern Jean-Pierre Talpin, INRIA Rennes (Guest Editors and Organizers of MEMOCODE 2017)


Hai Nam Tran
email: hai-nam.tran@inria.fr

Shuvra S Bhattacharyya

Thierry Gautier
email: thierry.gautier@inria.fr

Toward Efficient Many-core Scheduling of Partial Expansion Graphs

Transformation of synchronous data flow graphs (SDF) into equivalent homogeneous SDF representations has been extensively applied as a pre-processing stage when mapping signal processing algorithms onto parallel platforms. While this transformation helps fully expose task and data parallelism, it also presents several limitations such as an exponential increase in the number of actors and excessive communication overhead. Partial expansion graphs were introduced to address these limitations for multi-core platforms. However, existing solutions are not well-suited to achieve efficient scheduling on many-core architectures. In this article, we develop a new approach that employs cyclo-static data flow techniques to provide a simple but efficient method of coordinating the data production and consumption in the expanded graphs. We demonstrate the advantage of our approach through experiments on real application models.

INTRODUCTION

The data flow programming paradigm is commonly used to model signal processing or control applications in embedded system design. Its simplicity allows implementing code generation techniques to limit the problematic and error-prone tasks of programming realtime parallel applications. Among data flow models of computation, synchronous data flow (SDF) [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF] is one of the most popular in the community. This model is deterministic regarding communications: the topology and the amount of data sent and received are known (fixed). Communications between processing elements are isolated through well identified FIFO channels. Task parallelism [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF] in SDF can be exploited systematically: tasks can be mapped to available processing elements (cores), dependencies can be enforced, and independent tasks can run in parallel.

Transformation of synchronous data flow graphs (SDF) into their equivalent homogeneous SDF (HSDF) forms has been applied extensively as a preprocessing stage when mapping signal processing algorithms onto parallel platforms. While HSDF expansion helps fully expose both task and data parallelism [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF], it also presents several limitations. First, there is no polynomial bound for the size of the produced graph in terms of the size of the original graph. In particular, highly multirate SDF graphs can lead to exponential increases in size [START_REF] Pino | A Hierarchical multiprocessor Scheduling System for DSP Applications[END_REF]. In some cases, this expansion may not be beneficial because it may overwhelm the number of available processors. Besides, the increase in data parallelism has the hazard of increasing buffering requirements and introducing excessive communication overhead.

Partial expansion graphs (PEG) [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF][START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF][START_REF] Zaki | Implementation, scheduling, and adaptation of partial expansion graphs on multicore platforms[END_REF] are proposed to address these limitations. This approach allows the designer or design tool to control the degree to which each actor is expanded rather than expanding actors based on their SDF repetition counts. It presents an interesting design space exploration problem with the objective of finding an optimal mapping from actors into expansion rates.

Problem statement: Existing PEG solutions are not well adapted to achieve efficient scheduling on many-core architectures. They involve the use of shared buffers [START_REF] Zaki | Implementation, scheduling, and adaptation of partial expansion graphs on multicore platforms[END_REF] or the addition of split/join actors [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF]. The first solution requires the implementation of a buffer manager to coordinate data production and consumption of expanded actors on shared buffers. It can introduce additional communication overhead and result in a bottleneck (communication through the buffer manager) that gets worse as the number of processors increases. The second solution increases the number of actors and the buffer size requirement significantly because of split/join actors. Besides, one has to account for the overhead introduced by adding these actors.

Contribution: In this article, we present an approach that employs cyclo-static data flow techniques to coordinate the production and consumption of expanded actors. Our PEG solution involves a transformation of the original SDF graph to a cyclo-static data flow (CSDF [START_REF] Bilsen | Cycle-static dataflow[END_REF]) graph. The advantage of our solution is that it neither requires the use of buffer managers nor split/join actors. Experiment results have shown that our approach can have a significantly lower buffer space and number of added actors when compared to the split/join solution.

BACKGROUND AND RELATED WORKS

A synchronous data flow graph (SDF) is a directed graph G = (V , E) consisting of a finite set of actors V = {v 1 , ..., v N } and a finite set of edges (or channels) connecting them: E. A channel e ab = (v a , v b , p, q) ∈ E connects the producer v a to the consumer v b . The production and consumption rates of e ab are given by the integers p ∈ N and q ∈ N, respectively.

In the form of SDF that we consider in this paper, an actor v i has a worst-case execution time (WCET) of C i representing the workload of one firing. An essential property of SDF graphs is that every time an actor fires, it consumes a fixed number of tokens from incoming channels and produces another fixed number of tokens on its outgoing channels. An actor can only fire when there are sufficient tokens to consume and buffer spaces to produce.

In cyclo-static data flow graphs (CSDF), the production (resp. consumption) rate is defined by an infinite periodic sequence p ω = (v) in which v is a finite sequence of integers. The term "()" indicates that v is repeated infinitely. The number of tokens produced (consumed) by the j t h firing of an actor is given by the value at position [j mod |v |] of the sequence (|v | denotes the length of v) .

The buffer size (δ ab ) of a channel is in principle unbounded, i.e., it can contain arbitrarily many tokens. However, in practice storage space must be bounded. There can be a number of initial tokens that induces an offset in the execution of the consumer to the producer [START_REF] Bhattacharyya | Software synthesis from dataflow graphs[END_REF]. In this article, we study only delayless SDF graphs -that is, graphs in which the number of initial tokens on all channels is 0.

We consider a model of many-core architecture that consists of several compute clusters such as the commercial platform Kalray MPPA-256 [START_REF] De Dinechin | Time-critical computing on a single-chip massively parallel processor[END_REF]. In this Kalray platform, each cluster consists of 16 homogeneous processing cores. Each core has access to a private cache memory and to a limited shared memory of 2 MB. Actors on the same cluster can communicate rapidly via shared memory while tasks that run on different clusters communicate via more expensive means such as Network-on-Chip. Ideally, SDF applications should have a low buffer size requirement so that they can fit in the local shared memory.

Tasks are instantiations of actors when we schedule SDF graphs on many-core architectures. One assumption is that tasks are statically mapped to a processing core, and that task migration between cores is not allowed. This context is considered as non-auto concurrency: two firings of an actor cannot execute in parallel. Non-auto concurrency limits the exploitation of data parallelism. However, allowing auto-concurrency would lead to a complex scheduling problem because of contention on memory accesses and task migration costs.

The PEG approach has been introduced as a solution to exploit data parallelism in the context of non-auto concurrency. Expanded actors can be mapped to tasks that have their own software code blocks. Gordon et al. [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF] present a heuristic to adjust the granularity of an SDF graph by fusing actors with small loads, and then expanding the fused regions based on data parallelism. Then, software pipelining is implemented to balance the load on different processors. Kudlur and Mahlke [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] describe an integrated expanding and partitioning approach based on integer linear programming that expands actors as needed with the objective of maximizing the total workload on processors. Both solutions include the addition of split/join actors. They require adding channels to coordinate expanded actors and split/join actors, which, in general, leads to increased buffer size requirements. The two methods above target applications where offline scheduling is performed and the execution time of the actors can be accurately modeled. In the dynamic scheduling context, Zaki et al. [START_REF] Zaki | Implementation, scheduling, and adaptation of partial expansion graphs on multicore platforms[END_REF] present a PEG solution in which each data parallel actor is expanded to a number of instances that is bounded by the number of cores in the platform. Instead of introducing split/join actors as the previous work, buffer managers are implemented to coordinate actor firings.

APPROACH

The approach we propose employs CSDF techniques to provide a method for coordinating data production and consumption in expanded graphs. We exploit periodic sequences in order to allow each actor firing to consume from or produce onto different channels. Section 3.1 presents an example to motivate our approach and illustrate the application of cyclo-static rates. Then, we formulate our solution in section 3.2.

Motivational example

Let us start by considering the scheduling of an SDF graph on two processing cores (P 1 and P 2 ). Figure 1 illustrates the graph of the example, buffer sizes of channels and WCETs, production rates and consumption rates of actors. The graph consists of two stateless actors (v a , v b ) and one stateful actor (v c ). Figure 3a illustrates the only valid schedule for a single iteration of the graph given the assumption on non-auto concurrency. We can see that this schedule cannot take advantage of two processing cores.

We partially expand the original SDF graph as illustrated in Figure 2. The following observations can be made regarding our solution. Actor v a is the source actor thus it cannot be expanded. We assume that source actors represent data acquisitions with fixed frequencies. Actor v b can be expanded with the expansion rate of two to take advantage of 2 cores. A higher expansion rate leads to poor trade-off concerning buffer size and performance gain. Actor v c cannot be expanded because it is a stateful actor. In other words, a firing of v c must be completed before the next firing. Tokens produced by actor v a are split into two channels. Actor v a produces the first half of the original data to the top channel (e ab 1 ) then the second half to the bottom channel (e ab 2 ). For every firing of v a , actor v c must consume data produced by two firings of v b 1 before consuming any data from firings of v b 2 .

P 1 P 2 (a) va v b vc v b vc v b vc v b vc 0 450 (t) P 1 P 2 (b) vavb1 vcvb1 vc vc vc v b2 v b2 0 350 (t) P 1 P 2 (c) vavb1 vc vcvb1 vc vc v b2 v b2 0 250 (t)
We model this type of scheduling constraint using cyclo-static data flow rates, as illustrated in Figure 3. Our PEG solution effectively transforms the original SDF graph into a CSDF graph.

The makespan is shortened by 100 units as we can see in Figure 3b. In this Figure, we also observe that the second firing of v b 2 must wait for the third firing of v c because the buffer for channel e b 2 c is full. If we double the buffer size of channel: δ b 2 c = 128, we can have a shorter makespan as illustrated in Figure 3c. It allows the second firing of v b 2 to be fired immediately after the first firing.

In this example, we have shown that the application of cyclostatic rates can help us achieve data flow control without the need to add split/join actors or buffer managers. In the next section, we formulate rules for expanding actors in our proposed PEG construction approach, and we show how to derive the resulting cyclo-static production/consumption rates.

Expansion formulation

This section focuses on PEG solution for the simplest acyclic delayless SDF graph made of a single edge G = v a p q ----→ v b . We present constraints for expansion rates and provide exact formulas for expanding either the producer (v a ) or the consumer (v b ). We show that the application of cyclo-static data flow techniques, even for such simple graphs, is quite involved. Later in the section, we discuss how these techniques can be applied to general SDF graphs.

We apply the following rules to our PEG solution. First, actors in expanded graphs must produce and consume the same number of tokens per firing as the original actors that they are expanded from. For instance, in the previous example, the number of tokens -----------→ ( n ← ---→ p .. .p , .. .0 , 0) q (0 , 0, .. ., p .. .p -----------→ ( n ← ---→ q .. .q , .. .0 , 0)

v a v b 1 v b m (Case 1) p m q p m q v a v b 1 v b m (Case 2) n• m ← -
← ---→ n ) ← -------------→ n •m q v b v a 1 v a m (Case 3) p q m p q m v b v a 1 v a m (Case 4) n• m ← -
p (0 , 0, .. ., q .. .q ← ---→ n ) ← -------------→ n •m p Figure 4: Four cases of PEG.
produced and consumed per firing of all actors is not changed. Second, the order of data consumed by stateful actors in the expanded graphs is identical to the order in the original SDF graph. In addition, we assume that there is a predefined ordering of accesses across an actor's ports. In our illustrations, an actor produces and consumes tokens from its incident channels in a top-to-bottom order.

Our expansion techniques are illustrated in Figure 4. We study firstly the expansion of actor v b while keeping actor v a intact (unexpanded). The expansion depends on the relation between the production rate p and the consumption rate q. There are two cases:

Case 1: p > q, p = q • n, n ≥ 2. We expand actor v b by an expansion rate m such that m | n (n is divisible by m). By the rule of transitivity: m | n, n | p =⇒ m | p. We can divide p tokens produced by v a to m expanded actors of v b equally. In the expanded graph, one firing of v a still produces p tokens in total, and one firing of expanded v b consumes q tokens. In this case, we exploit data parallelism by allowing data produced by v a to be consumed faster.

Case 2: p ≤ q, q = p • n, n ∈ N * . We expand actor v b by an expansion rate m ∈ N * . Here, we apply cyclo-static rates to v a in the expanded graph For each expanded actor of v b , v a produces q = p • n tokens after n firings. The length of the periodic sequence is m • n as corresponding to m expanded actors v b . In this case, the application of PEG can be an advantage if C b (the WCET of v b ) is significantly larger than C a . The reason is that it allows data to be produced and consumed without waiting for the completion of actor v b in the original SDF graph.

Next, we study the expansion of actor v a while keeping actor v b intact. We have two cases that are the duals of cases 1 and 2.

Case 3: p < q, q = p • n, n ≥ 2. This case is the dual of Case 1. We expand actor v a by an expansion rate m such that m | n.

Case 4: p ≥ q, p = q • n, n ∈ N * . This case is the dual of Case 2. We expand actor v a by an expansion rate m ∈ N * and apply cyclo-static rates to v b . In all cases, we limit the expansion rate m to be no greater than number of processors available to schedule the SDF graph Our observation is that expanding an actor beyond the number of processors does not provide better exploitation of parallelism. Cases 1, 2 are applied to the expansion of the consumer while cases 3, 4 are applied to the producer. In practice, for general SDF graphs, an actor can be both a producer and a consumer with respect to other actors As a result, we need to apply the combinations of the four cases. There are only four combinations (1-3), (1-4), [START_REF] Bilsen | Cycle-static dataflow[END_REF][START_REF] De Dinechin | Time-critical computing on a single-chip massively parallel processor[END_REF] and [START_REF] Bilsen | Cycle-static dataflow[END_REF][START_REF] De Dinechin | Time-critical computing on a single-chip massively parallel processor[END_REF][START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF]. For each combination, the expansion rate must satisfy the conditions of both cases.

A limitation of our solution is that, if p q or q p, we cannot divide tokens equally to expanded actors. As a result, we can neither expand v a or v b . This limitation also applies to the PEG solution with split/join actors. A possible solution would be to associate an actor with a vectorization factor [START_REF] Lin | Memory-constrained Vectorization and Scheduling of Dataflow Graphs for Hybrid CPU-GPU Platforms[END_REF] to get divisible rates.

If the order of data consumed by actors does not need to be enforced, we can apply the expansion formulas presented in the four cases. Otherwise, we need to take into account the top-to-bottom ordering and adjust the rates accordingly. The exact formulas are not presented in this article due to space limit. The intuition is to employ cyclo-static rates to delay the production or consumption of tokens on specific channels.

EVALUATION

We have conducted experiments with a subset of signal processing applications taken from the STR2RTS benchmark [START_REF] Rouxel | STR2RTS: Refactored StreamIT benchmarks into statically analysable parallel benchmarks for WCET estimation & real-time scheduling[END_REF], which is a refactored version of the StreamIT benchmark. We evaluate our PEG solution by two metrics: number of actors (NB) and buffer size requirement (BS). The PEG solution with split/join actors is generated by the StreamIt compiler. Then, we implement our PEG solution which allows us to effectively remove split/join actors. A small maximum expansion rate of 4 was chosen to allow fast prototyping.

The results of our experiments are shown in Table 1. The first column shows the number of actors in the original SDF graphs. We also give the number of actors and buffer size requirements of expanded graphs produced by the split/join solution and ours.

The results show that our PEG solution has a smaller number of actors and buffer size requirements compared to the split/join solution. On average, our PEG approach results in 21% fewer actors and requires 41% less buffer cost. Comparing to the original SDF graph, the addition of split/join actors can be quite costly. One of our observations is that the increase in the number of actors also depends on the implementation of the original SDF graphs For example, the SDF graphs of "des" and "dcal" in the benchmark are partly parallelized with the existence of split/join actors. As a result, there is not a significant increase in the number of actors with these applications compared to "FFT2" or "matmult".

We also evaluate the overhead of our PEG solution by manually implementing the expanded graphs of "cfar" and "FFT2". We use the WCET analyzer Heptane [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] to derive a bound on the execution time of one iteration of the graph on one processing core. For each of the two benchmarks, we derive this bound both with and without the use of cyclo-static data flow control, as defined by our expansion approach. From this experiment, we find that the overhead due to the implementation of cyclo-static rates is less than 5%. Indeed, manual implementation of expanded graphs is time-consuming and only applicable to small applications. We plan to integrate the proposed PEG solution in a code generator for SDF graphs.

CONCLUSIONS & FUTURE WORK

In this article, we present an approach that employs cyclo-static data flow techniques in partial expansion graphs. Our approach requires neither buffer managers nor split/join actors to coordinate the production and consumption of actors in expanded graphs. Experimental results have shown that our approach has a lower buffer space requirement and a lower number of actors when compared to the split/join solution. In the context of clustered many-core architectures, a key advantage of our PEG solution is that it requires less memory, scheduler and communication overhead because of a smaller number of actors. In addition, the lower buffer space requirement implies that it is easier to fit the expanded graphs in a local shared memory of a compute cluster.

For future works, we are developing an algorithm that allows us to optimizing the assignment of expansion rates to actors. In addition, we plan to integrate the proposed approach in a code generator with the aim of automatically generating expanded graphs from SDF graphs. Furthermore, we intend to study the problem of scheduling PEGs on many-core architectures by integrating our approach in a scheduling framework.

Figure 1 :Figure 2 :

 12 Figure 1: An SDF of 3 actors: v a and v b are stateless actors, v c is a stateful actor.

Figure 3 :

 3 Figure 3: (a) Schedule of the SDF with makespan = 450. (b) Schedule of the PEG with makespan=350. (c) Schedule of the PEG with δ b 2 c = 128 with makespan=250.

Table 1 :

 1 Comparison between PEG solutions.

		SDF PEG Split/Join	PEG CSDF
		NB	NB	BS	NB	BS
		(#)	(#)	(byte)	(#)	(byte)
	CFAR	4	9	1792	7	1296
	dcal	84	128	14144	110	7632
	des	423	591	57772	523	27144
	FFT2	26	111	53760	79	24576
	matmult	23	69	131488	49	67968