Nelson Lossing
email: nelson.lossing@mines-paristech.fr

Pierre Guillou
email: pierre.guillou@mines-paristech.fr

Francois Irigoin
email: francois.irigoin@mines-paristech.fr

Effects Dependence Graph: A Key Data Concept for C Source-to-Source Compilers

Optimizations, transformations and analyses are applied to programs by compilers at the intermediate representation level, which usually does not include explicit variable declarations. This description level is fine for middle-ends and for source-to-source optimizers of simple languages. Meanwhile, the C language has become much more flexible since the C99 standard, and let variable and type declarations appear almost anywhere in source code. We present in this paper a new concept to manage C99 declarations in a source-to-source compiler: the Effects Dependence Graph, which is an extension of the classical Data Dependence Graph. It deals particularly efficiently with user-defined type declarations or dependent types like Variable-Length Array. It is also interesting because no legal scheduling transformation is hindered and because existing algorithms are either not or slightly modified. Finally it reduces the need for variable, struct and array privatization or live range analyses in automatic parallelizers. To the best of our knowledge, the declaration issue is ignored in the literature: existing C source-to-source compilers either do not support C99, or accept only restricted portions of code, and production compilers use low-level intermediate representations, possibly with annotations. In this way our solution addresses a wider range of compiler analysis issues.

I. Introduction

Program optimizations, transformations and analyses are applied to intermediate representations (IR), traditionally built with basic blocks of three-address code and a control flow graph. These representations usually do not include explicit variable declarations, because these have been processed by a previous pass and have generated constant addresses in the static area or offsets for stack allocations. Typing information is lost or preserved in annotations. This description level is used, for instance, in the Optimization chapter of the Dragon Book [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]. Although it is fine for middle-ends and for source-tosource optimizers of simple languages, such as Fortran 77, which separate declarations from executable statements, parallelizers must revisit variable allocations using a privatization phase or a live-range analysis.

Meanwhile, the C language, especially its C99 standard [START_REF]ISO/IEC 9899:1999 -Programming Languages -C[END_REF], is now much more flexible than in the K&R era. Variable and type declarations, which include expressions int foo () { int i , result =0; for ( i =1; i <10; i ++) { int a [ i ]; result += bar (a , i ); } return result ; } Listing 1: C99 VLA Example 1 to define initial values and dependent types, can appear almost anywhere in the source code to improve readability and locality at no stack space expense. Listing 1 shows an example of Variable-Length Array declaration that we want to address at the source level in this article. After transformation, the output source code has to be as close as possible to the input code and easy to read by a programmer. Thus source-to-source compiler passes that schedule statements, such as loop parallelization, distribution, interchange or polyhedral optimization, have necessarily to deal with type and variable declarations.

However, these statements have no or little impact in terms of the classical def-use chains or data dependence graphs [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF][3] [START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF], which deal only with store memory accesses. As a consequence, C declarations would be (incorrectly) moved away from the statements that use the declared variables, with no respect for the scope information. We propose in this paper a method to fix this problem without modifying the classically-used compilation algorithms.

We have explored three main techniques applicable for a source-to-source framework. The first one is to move the declarations at the main scope level. The second one is to mimic a conventional binary compiler and to transform typedef and declaration statements into memory operations, which is, for instance, what is performed in Clang. The third one is to extend def-use chains and data dependence graphs to encompass effects [START_REF] Lucassen | Polymorphic effect systems[END_REF] on the environment and on the mapping defining named types.

Our contributions consist in this extended dependence graph, a discussion about its implementation, and its impact on traditional source-to-source transformations.

In Section II, we motivate the use of C source-to-source compilation and the differences between source-to-source and classical compilers. We then provide in Section III some background information about the semantics of a programming language. We review in Section IV the standard use-def chains and Data Dependence Graph, and discuss some solutions for source-to-source compiler to manage declarations. We introduce in Section V our proposed extension, the Effects Dependence Graph (FXDG), to replace the Data Dependence Graph (DDG) as argument to existing scheduling compilation passes. We look at its impact on passes in Section VI and observe that the new effect arcs are sometimes detrimental, and must be filtered out, or insufficient. The related work is discussed in Section VII. The paper contributions are recalled and future work is presented in Section VIII.

II. Motivation

We motivate below the use of source-to-source compilation for C programs. First, we describe a list of nonexhaustive compilation schemes where using a source-tosource compiler is relevant. We present then the advantages of source-to-source compilation and finally, we show how the C99 standard interferes with traditional sourceto-source code transformations.

A. When To Use Source-to-Source Compilers or High-Level Intermediate Representations?

Source-to-source C compilers are useful to postprocess C code generated by DSL compilers because these compilers may generate very peculiar C codes, unexpected by C production compilers. The postprocessing is thus factored out of DSL compilers, without impacting production compilers. Since the common user of a DSL is not forcefully its implementer and may not have the knowledge to tinker with the DSL compiler, using source-to-source compilers may be a good choice to apply new analyses and transformations not implemented in the DSL compiler. For instance, the PGAS compiler of Chapel [START_REF] Chamberlain | Chapel (Cray Inc. HPCS Language)[END_REF] uses C as output language.

Source-to-source C compilers are also useful to preprocess application C code and to isolate automatically or semi-automatically specific parts that require a special treatment, for instance to offload them to a hardware accelerator, be it GPU-or FPGA-based [START_REF] Amini | Static compilation analysis for host-accelerator communication optimization[END_REF] [START_REF] Guelton | Building source-to-source compilers for heterogenous targets[END_REF]. Only one version of the source code can be used for application development on a homogeneous machine.

High-level IR could also be used in a compiler to deal with the same issues and to provide more information about types and memory management to some optimization passes, especially when IR support explicitly parallel constructs. Currently, the IR used by GCC and LLVM are too low-level for direct loop parallelization. Loops are not preserved in their CFG-based representation. Neither are multidimensional array accesses, nor local variable declarations. All this information must be either carried by annotations or rebuilt. It might be better to use two IR, a high-and a low-level one.

Finally source-to-source compilers are useful to develop complex passes, because their high-level IR can be converted back to C and be executed at any step. For the same reason, they have a pedagogical interest both for students and for the feedback provided to users.

B. Why Use C Source-to-Source Compilers?

DSLs often are niche projects which concentrate on a narrow set of applications. Hence it can be difficult for anyone but the maintainers to implement new optimizations in a DSL compiler. Using a source-to-source compiler as a backend to a DSL compiler can lead to optimized code without the need of the DSL developers. This solution is also resilient to a suspension of the DSL project.

The output code of a source-to-source compiler is more readable than a classical compiler. For a developer's point of view, it is more convenient to have source and output code in the same language when the output code has to be reused, contrary to assembly code or low-level intermediate representation such as LLVM-IR, especially in the case of tricky declarations such as Variable Length Arrays (VLA).

void foo ( int n ) { int a [ n ]; /* ... */ } Listing 2: VLA Example 2
Listing 2 shows a simplified example of VLA used in a declaration written in C, typical of scientific or signal processing programs, where a temporary array can be allocated on the stack although its size is unknown at compile time and possibly varying during the execution. Listing 4 is a printout of the internal representation of our initial VLA example in LLVM. It is more readable that in assembly code. But due to its three-address code representation, many temporary variables are created. Moreover, internal built-ins have to be used to save the stack and reload it. Listing 5 is the translation of the LLVM-IR to C, performed by LLVM version 3.0, because more recent versions of LLVM do not support anymore the regeneration of C code. The resulting generated code is quite different from the initial code and its simple VLA. It has been translated into a stack allocation, supported by many variables. Additional built-ins are used to save and restore the stack as the generation of LLVM-IR does.

Using good C source-to-source compilers, the programmer can easily compare the initial code and the resulting code after transformation. He/she can also execute the transformed code. Therefore the validation of changes, an essential stage in a production environment for critical codes, is facilitated. Moreover, the new code can be reanalyzed and new transformations can be applied as many times as necessary. Specific binary compilers, targeting particular architectures, can still be used in a second phase, if necessary.

The choice to make a source-to-source compiler for C is justified because C code is stable and portable; therefore maintenance is easier. Some other compilers for C++ and Objective-C, for PGAS or DSL languages even choose the C language as target or as intermediate language [START_REF] Kreinin | C as an intermediate language[END_REF]. In this way, developing a C source-to-source compiler may even help to improve the results of these other compilers targeting C.

C. A Pedagogical Example void example () {

int i ; int a [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF] , b [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF]; for ( i =0; i <10; i ++) { a [ i ] = i ; typedef int mytype ; mytype x ; x = i ; b [ i ] = x ; } return ; } Listing 6: C99 for loop with a typedef statement and a variable declaration inside the loop body Consider the C99 for loop example in Listing 6. It has been designed to highlight all issues linked to type and variables declarations. This code contains in its loop body declarations for a type and a variable at Lines 6-7. When loop fission/distribution [1][4] is applied blindly onto this loop, the typedef and the variable declaration are also distributed, as shown in Listing 7.

void example () { int i ; int a [10] , b [10]; for ( i =0; i <10; i ++) a [ i ] = i ; for ( i =0; i <10; i ++) typedef int mytype ; for ( i =0; i <10; i ++) mytype x ; for ( i =0; i <10; i ++) { x = i ; b [ i ] = x ; } return ; } Listing 7: After (incorrect) loop distribution of List- ing 6
The loop distribution algorithm relies on the Data Dependence Graph (see Section IV) to detect cyclic dependencies between the loop body statements. Yet the type and variable declarations carry no data dependencies towards the following statements or the next iteration, thus causing an incorrect loop distribution.

The Data Dependence Graph (DDG) of Listing 6 is represented in Figure 1. W → R arcs represent flow dependences, R → W are anti-dependences and W → W are output dependences. According to this traditional DDG, no data dependence exists between the type declaration (typedef int mytype;), the variable declaration (mytype x;) and the two statements referencing Variable x (x = i; b

[i] = x;).
This example is contrived but it highlights the inadequacy of the Data Dependence Graph for some classic transformations when applied to C99 source codes containing declarations anywhere. The dependence arcs required by type and declaration are missing. A similar example with VLA is presented in Listing 10. Somewhat extreme examples could combine declarations of new types and VLA as in int size = x; struct mystruct { int member1[size]; };.

One can objects that a compiler should not take declarations into account in the first place, but a source-tosource compiler has to regenerate declarations at some point. Moreover, a VLA declaration always depends on a computation statement and thus has to be treated separately by the compiler.

III. Background and Notations

We have based our work on some code transformation passes of the PIPS compiler [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF] [START_REF]PIPS[END_REF] and on its highlevel intermediate representation. Aiming at automatic interprocedural code parallelization, optimization and offloading, it features a wide range of analyses and transformations over Fortran and C code. It is also interfaced with polyhedral compilers.

To carry out its analyses, PIPS relies on the notion of memory effects, which reflect how a code statement interacts with the computer memory.

To explain how we deal with declaration statements, we have to introduce several basic concepts used to define the semantics of imperative programming languages.

In Fortran and C, variables are linked to three different concepts: an Identifier is the name given to a specific variable; a Memory Location is the underlying memory address, usually used to evaluate Identifier; and a Value is the piece of data effectively stored at that memory address. For instance, a C variable declaration such as int a; maps an Identifier to a Memory Location, represented by &a, and usually allocated in the stack.

To link these concepts, two functions are also defined [START_REF] Gordon | The denotational description of programming languages -an introduction[END_REF] Equation 1 to 4 provide the formal representation of the concepts defined above.

ρ ∈ Env = Identifier → Loc (1) σ ∈ Store = Loc → V alue (2) S : Store × Env → Store × Env (3) E : Statement → (Store × Env → P(Loc)) (4)
Note that named types are not modeled here to simplify the presentation; their declaration and uses are equivalent to variable declarations and references.

Memory effects are divided into two categories: READ effects represent a set of Memory Locations whose Values are used, but not modified, whereas WRITE effects represent Memory Locations whose Values are defined during the execution of S on a given Memory State. A statement's READ and WRITE effects, usually overapproximated for safety by static analyses, satisfy specific properties [START_REF] Irigoin | Polyèdres et Compilation[END_REF], which can be used to show that Bernstein's conditions [START_REF] Bernstein | Analysis of Programs for Parallel Processing[END_REF] are sufficient to exchange two statements without modifying their combined semantics.

Many analysis and transformation passes in PIPS are based on these memory effects, called effects for simple scalar variables or array regions for convex set of array elements. In particular, effects are used to build use-def chains and the Data Dependence Graph between statements. More information about effects and regions can be found in [START_REF] Creusillet | Array region analyses and applications[END_REF].

IV. Data Dependence Graph

The Data Dependence Graph is used by compilers to schedule statements and loops. A standard Data Dependence Graph [1][4] exposes essential constraints that have to be met to prevent incorrect reordering of operations, statements, or loop iterations. A Data Dependence Graph is composed of three different types of constraint arcs: flow, anti-and output dependencies.

Note that the Data Dependence Graph is based on store memory read and write operations, a.k.a. uses and definitions. C declaration statements may perform reads and writes when variables are initialized by expressions and allocated in the stack. However initializations of static variables should not generate such effects. Furthermore, the declaration of dependent types with a typedef statement also requires memory read effects. Finally, accesses to variables with dependent types may require implicit read accesses to the definition of their types, either to check that an array access is within bounds, or to generate the element address computation.

So, to take into account the mechanisms used by the compiler, implicit memory accesses have to be added to obtain sufficient READ and WRITE effects. We want to keep these new accesses implicit to make further analyses and transformations easier, and to be able to regenerate a source code as close as possible to the original. Standard high-level use-def chains and DDG are unaware of these implicit dependencies. However, these are key features when distributed loops [START_REF] Wolfe | High Performance Compilers for Parallel Computing[END_REF] or when performing a statement isolation [START_REF] Guelton | Beyond Do Loops: Data Transfer Generation with Convex Array Regions[END_REF].

A. Limitations

The problem with the standard Data Dependence Graph is that the ordering constraints are only linked to memory accesses. A conventional Data Dependence Graph does not take into account the addresses of the variables, and even less the declaration of new types, even when they are necessary to compute a location. More precisely, a Data Dependence Graph only considers constraints on the Store function, and not on the Environment function. In fact, when the C language, especially the C99 standard, is considered, many features imply new scheduling constraints for passes using the Data Dependence Graph.

• Declarations anywhere is a new feature of C99, also available in C ++ . This feature implies for a source-to-source compiler to consider these declarations and to regenerate the source code with the declarations at the right place within the proper scope. or typedef can also be defined anywhere inside the source code, creating dependences with the following uses of this type to declare new variables or new types.

B. Workarounds

A possible approach for solving these issues in a sourceto-source compiler is to mimic the behavior of a standard compiler that generates machine code with no type definitions or memory allocations. In this case, we can distinguish two solutions.

The first one works only on simple code, without dependent types. The declarations can be grouped, at the expense of stack size and name obfuscation, at the beginning of the enclosing function scope.

The second one is more general. The memory allocations inserted by the conventional binary compiler can be reproduced. Analyses and code transformations are performed on this low-level IR. Then the source code is regenerated without the low-level information.

1) Flattening Code: Code flattening is designed to move all declarations at the beginning of functions in order to remove as many environment extensions, introduced by braces in C, as possible, to have only one scope and to make basic blocks as large as possible. As a consequence, all the variables end up in the function main scope, and declaration statements can be ignored when scheduling executable statements. Some alpha-renaming may have to be performed during this scope modification: if two variables share the same name but have been declared in different scopes, new names are generated, considering the scope, to replace the old names while making sure that two variables never have the same name.

This solution is easy to implement and can suit a simple compiler.

The result of Listing 6 after calling flatten code is visible on Listing 8 1 . Listing 9 is the result of a loop distribution performed on Listing 8. Note that the second loop is no longer parallel and that a privatization or symbolic evaluation pass is necessary to reverse the hoisting of the declaration of x.

However, this solution only works on simple programs without dependent types, because dependent types imply a flow dependence between some computation statements and the declaration statement. For instance, a VLA using a previously computed quantity as size. As a consequence, the declarations cannot be moved up systematically anymore.

Besides, even in simple programs, the operational semantic of the code can be changed. In our above example, flatten code implies losing the locality of the variable x. As a consequence, the second loop cannot be parallelized, because of the dependence to the shared variable x. Without flatten code, the variable x is kept in the second loop, which remains parallel.

Furthermore, code flattening can produce an increase in stack usage. For instance, if a function has s successive scopes that declare and use an array a of size n, the same memory space can be used by each scope. Instead, with code flattening, s declarations of different variables a1, a2, a3. . . are performed, so s×n memory space is used.

Code flattening also reduces the readability of the code, which is unwanted in a source-to-source compiler. The final code should be as close as possible to the original code.

2) Frame Pointer and Low Level Representation: Another solution is to reproduce the assembly code generated by a standard compiler, e.g. GCC. A hidden variable, called the current frame pointer (fp), corresponds to the location where the next declared variable will be allocated. At each variable declaration, the value of this hidden variable is updated according to the size of the variable type. In x86 assembly code, the stack base pointer ([e|r]bp) with an offset is used. Moreover, for all user-defined types, hidden variables are also added to hold the sizes of the new types. In this way, the source-to-source compiler performs like a binary compiler.

However, this method would lead to the addition of many hidden variables. All of these hidden variables must have a special status into the internal representation of the source-to-source compiler. Moreover, this solution adds constraint arcs that do not exist. Since all declarations depend on the frame pointer, which is modified after each declaration, no reordering between declarations is legal, for instance. With the special status of these new variables, the generation of the new source code is also modified and can be much harder to perform.

Instead of reproducing the assembly code, a low level representation like the LLVM-IR introduces built-ins and makes use of the low-level alloca instruction. Using a low-level intermediate representation has the advantages of being easier to implement and to understand than the frame pointer solution discussed above. However, applying some source-to-source transformations such as loop distribution onto this kind of intermediate representation is much harder, and the handling of the custom types is lost.

For instance, the loop distribution of Listing 10 may result in Listing 11. With an LLVM-IR as Listing 12, this transformation implies to successfully add a new stack save and stack restore built-ins for the two different loops. That will be difficult.

Nevertheless, the regeneration of a high-level source code from these new internal representations has to be redesigned completely so as to ignore the hidden variables or to manage the new built-ins while considering the type and program variable declarations. Thus this solution is not attractive for a source-to-source compiler.

V. Effects Dependence Graph

Instead of modifying the source code or adding hidden variables, we propose to use the code variables, including the type variables, to model the transformations of the environment and type functions. For this purpose, we extend the memory effects analysis presented in Section III by adding an environment function for read/write on variable memory locations, and a type declaration function for read/write on user-defined types. By extending the effects analysis with two new kinds of reads and writes, we define a new dependence graph that extends the standard Data Dependence Graph. We name it the Effects Dependence Graph (FXDG).

Definition (Effects Dependence Graph). The Effects Dependence Graph is an extension of the Data Dependence Graph taking into account the environment and the type declaration functions.

A. Environment function ρ

The effects on the environment function ρ, read and write, are strictly equivalent to the effects on the store function σ, a.k.a. the memory. A read environment (RE) effect is an application of ρ, which returns the location of an identifier. A write environment (WE) effect updates the function ρ and maps a newly declared identifier to a new location or removes it from the function domain. Thus when a variable is declared, a new memory location is allocated, which implies a WE effect on the function ρ. Its set of bindings is extended by the new pair (identifier, location) in the same way that an affectation statement binds a pair (location, value). Similarly, when a variable is accessed within a statement or an expression, be it for a read or a write, the environment function ρ is used to obtain the corresponding location resulting in a RE effect.

As a consequence, effects on the environment function ρ track all applications and modifications of ρ without ever taking into account the value that σ maps to a location.

Effects on the environment function correspond to the use of the symbol Listing 12: LLVM-IR of Listing 10 accessed to retrieve a location, a RE effect is attached to the statement causing that access.

B. Type function τ

To support memory allocation, the type function τ maps a type identifier to the number of bytes required to store its values. It is used for all user-defined types, be they typedef, struct, union or enum. The effects on τ , read type (RT) and write type (WT), correspond to apply and update operations. When a new user-defined type is declared, τ is updated with a new pair (identifier, size). This is modeled by a WT effect on τ . When a new variable is declared with a user-defined type, the type function τ is applied to the type identifier, i.e., a RT effect occurs.

C. Representation

The traditional read and write effects on the store function, a.k.a. memory, are thus extended in a natural way to two other semantic functions, the environment and the type functions. The common domain of these two new functions is the identifier set, for variables and userdefined types. The traditional memory effects are more difficult to implement because they map locations and not identifiers to values. However, a subset of the location domain is mapped one-to-one to identifiers. Thus, the three different kind of effects can be considered as related to maps from locations to some ranges, which unify their implementation.

D. Implementations

The new effects can be implemented in two different ways, with different impacts on the classical transformations based on the Data Dependence Graph.

The first possibility is to consider separately the effects on stores, environments and types, and to generate usedef chains and dependence graphs for each of them, and possibly fusing them when it is necessary.

The second possibility is to label the effects and then use a unique Effects Dependence Graph to represent the arcs due to each kind of functions. Passes based purely on the Data Dependence Graph have to filter out arcs not related to the store function.

1) Merging different dependence graphs:

The first approach creates a specific dependence graph for each kind of effects, a Data Dependence Graph, an Environment Dependence Graph and a Type Dependence Graph. To obtain the global Effects Dependence Graph required as input by passes such as loop distribution, these three graphs could be fused via a new pass.

As an example, PIPS manages resources for effects on variable values and could manage two new resources for effects on environment and for effects on types. With three effect resources, it is now possible to generate three different dependence graphs, one for each of our effect resources: a Data Dependence Graph, an Environment Dependence Graph and a Type Dependence Graph. The union of the three different dependence graphs of the example in Listing 6, the total Effects Dependence Graph, is presented in Figure 2. The traditional data dependences (W, R) are represented with full arcs, when environment dependences (WE, RE) are in dashed arcs and type dependences (WT, RT) in dotted arcs. void example () { int i ; int a [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF] , b [START_REF] Irigoin | Semantical interprocedural parallelization: an overview of the PIPS project[END_REF]; for ( i =0; i <10; i ++) a [ i ] = i ; for ( i =0; i <10; i ++) { typedef int mytype ; mytype x ; x = i ; b [ i ] = x ; } return ; } Listing 13: After loop distribution of Listing 6 using its Effects Dependence Graph With these new dependence graphs, the loop distribution algorithm produces the expected Listing 13. The loops can then be properly parallelized. Since we have a dependence graph for each kind of effects, we can independently select which dependence graph we need to compute or use. Still, at the implementation level, these independent dependence graphs also imply to launch three different analyses and to fuse their results with a fourth pass to obtain the Effects Dependence Graph for loop distribution.

2) A unique dependence graph: The second approach consists in extending the current use-def chains and data dependence graph with the different kinds of effects. On this Effects Dependence Graph, some labeling is used to distinguish between the different kinds of effects: data values, memory locations and types.

Since the change is applied at the lowest level of the data structure definition, the existing passes dealing with reads and writes are left totally unchanged. The Effects Dependence Graph for Listing 6 is identical to the result of the first approach (Figure 2). This implementation leads to the same output of loop distribution and loop parallelization as the three graph approach (see Listing 13). Besides, only one dependence graph is generated; so we do not need to manage three different ones, plus their union.

However, since the Data Dependence Graph is replaced by an unique Effects Dependence Graph, the source-tosource transformations that now use the Effects Dependence Graph must take into account new constraints. Sometimes, the Effects Dependence Graph implies too many constraints which can be detrimental for some source-to-source transformations. These issues are studied in the next section.

VI. Transformations and Analyses

The introduction of the Effects Dependence Graph allows source-to-source compilers to better support the C99 specification. However, not all classical code transformations and analyses benefit from this new data structure. In this section, we discuss the impact of substituting the Data Dependence Graph by the Effects Dependence Graph in source-to-source compilers.

A. Effects Dependence Graph Compatibility

Some transformations require the new environment effects and the corresponding dependencies. In fact, in some passes, we cannot move or remove the declaration statements.

The first example is the Allen & Kennedy [START_REF] Allen | Automatic Translation of FOR-TRAN Programs to Vector Form[END_REF] algorithm on for loop parallelization and distribution that we used in Subsection II-C. These algorithms were designed for the Fortran language initially, without taking declarations into account since they are grouped before the first executable statement. When proposing solutions to extend them for the C language, Allen & Kennedy [START_REF] Kennedy | Optimizing Compilers for Modern Architectures: A Dependence-based Approach[END_REF] only focused on pointer issues and not on declaration ones.

Another typical algorithm that requires our Effects Dependence Graph is Dead Code Elimination [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]. Without our Effects Dependence Graph, the traditional dead code elimination pass either does not take declarations into count, i.e., never eliminates a type or variable declaration statement, or always eliminates them since no dependence arcs link them to useful statements. So, if applied to the high-level internal representation of a source-to-source compiler and not to a three-address code one, the dead code elimination pass either performs half of its job, or generates illegal code when the classical use-def chains is the underlying graph.

B. Filtering the Effects Dependence Graph

When the legality of a pass is linked to the values reaching a statement, the new arcs, which embody address or type information, are not relevant. For instance, a forward substitution pass uses the use-def chains, also known as reaching definitions, to determine if a variable value is computed at one place or not. Additional arcs due to the environment are not relevant and should not be taken into account.

When applying Forward Substitution [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF] to the loop body of Listing 13, the Read after Write Environment dependence arc between the statements mytype x; and b[i] = x; prevents the compiler from substituting x by i. Filtering out the Environment and Type Declaration effects or arcs is, in this pass, necessary to retrieve its expected behavior.

C. Adapting the Effects Dependence Graph

Some transformations do not use scheduling information, but their standard implementations may not be compatible with type declarations or dependent types.

For instance, the pass that moves declaration statements at the beginning of a function in PIPS (flatten code) does not use data dependence arcs. When dependent types or simply variable-length arrays are used in typedef or variable declaration statements, scheduling constraints exist and must be taken into account. A new algorithm is required for this pass, and the legality of the existing pass can be temporarily enforced by not dealing with codes containing dependent types.

In the same way, loop unrolling, full or partial, does not modify the order of statements and does not take any scheduling constraint into consideration. However, its current implementation in PIPS is based on alpha-renaming and declaration hoisting to avoid multiple scopes within the unrolled loop or the resulting basic block. This is not compatible with dependent types, and non-dependent types are uselessly renamed like ordinary variables.

Polyhedral scheduling as performed in Pluto [START_REF] Acharya | Pluto+: Near-complete modeling of affine transformations for parallelism and locality[END_REF] or PPCG [START_REF] Verdoolaege | Polyhedral parallel code generation for cuda[END_REF] should be compatible with Effects Dependence Graph. However, the code generation phase based on a multidimensional affine schedule, Cloog [START_REF] Bastoul | Code generation in the polyhedral model is easier than you think[END_REF], is unlikely to generate valid C99 code as input statements can be repeated without paying attention to scoping issues. For instance, an affine schedule corresponding to a loop peeling requires a copy of the loop body as preamble or postlude.

VII. Related Work

We did not find any directly related work deal either with restricted input, e.g. polyhedral compilers and static control parts (SCoPs [START_REF] Benabderrahmane | The Polyhedral Model is More Widely Applicable Than You Think[END_REF]), or are using robust parsers and low-level intermediate representations [19][22].

Pluto [START_REF] Acharya | Pluto+: Near-complete modeling of affine transformations for parallelism and locality[END_REF] and PPCG [START_REF] Verdoolaege | Polyhedral parallel code generation for cuda[END_REF], for instance, only work on restricted parts of the input code defined by pragma directives. In these parts of the code, Pluto cannot deal with declarations. However, PPCG is able to deal with basic variable declarations in loop nests by flattening them outside the loops, though it does not handle VLA depending on a loop variable or typedefs. Other tools using multidimensional affine schedules such as XFOR tools [START_REF] Fassi | XFOR: filling the gap between automatic loop optimization and peak performance[END_REF] cannot handle variable and type declarations either. As multidimensional schedules are usually linked to unreadable codes, this is not too much of an issue for such source-to-source compilers, or for high-level IR.

The popular and robust parser Clang with its lowlevel intermediate representation LLVM-IR [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF] also has problem to generate a simple readable representation of variable length arrays, like Listing 4 and Listing 5 illustrate it. It is partially due to its three-address code representation.

The source-to-source compiler from and to LLVM-IR can be used, but not to regenerate a C source code, since Version 3.1 of LLVM removed this option. Even in version 3.0, the regenerated C source code is quite different from the original input source code due to the low level representation that was passed by.

Other source-to-source research compilers such as Oscar [START_REF] Obata | Hierarchical Parallelism Control for Multigrain Parallel Processing[END_REF] and Cetus [START_REF] Lee | Cetus -An Extensible Compiler Infrastructure for Source-to-Source Transformation[END_REF] simply do not support the C99 standard.

Among work that is indirectly related, the memory allocation issue can be dealt with in different ways by optimizers operating on low-level representations. The stack allocation of local variables could be performed first without reusing stack space so as not to create spurious conflicts preventing parallelization and statement scheduling, and a second pass could reallocate variables in a more compact way once the schedule is known. A usual approach performs variable and possibly array privatization to remove related dependencies, but this may involve a new memory allocation pass. A third approach involves a live-range analysis to filter out dependencies created by stack reuse when scheduling and to preserve the front-end stack allocation.

VIII. Conclusion

C99 is a challenge for source-to-source compilers that intend to respect the different scopes of the input code and generate a better and more readable output code.

We show that some traditional algorithms fail when applied to a high-level intermediate representation, because the use-def chains and the data dependence graph do not carry enough scheduling constraints. We have explored three different ways to solve this problem. We showed that adding effects and arcs for transformations and using the current type mapping and environment function solution best respect the original source code and existing passes. We also showed that the new kinds of read and write effects fit easily in the traditional use-def chains and data dependence graph structures. Passes that need the new constraints are working right away when the data dependence graph is replaced by the effects dependence graph. Some passes are hindered by these new constraints and must filter them out, which is very easy to implement. Finally, some other passes are invalid for C99 declarations, but are not fixed by using the Effects Dependence Graph because they do not use scheduling constraints that have to be met. This extension has been used for several years in our PIPS source-to-source framework and has remained compatible with its new developments such as offloading compilers for GPUs [START_REF] Amini | Static compilation analysis for host-accelerator communication optimization[END_REF] and coprocessors [START_REF] Guelton | Building source-to-source compilers for heterogenous targets[END_REF].

The newer C11 standard [START_REF]ISO/IEC 9899:2011 -Programming Languages -C[END_REF], released in 2011 by the ISO/IEC as a revision of C99, is more conservative in terms of disruptive features. Some mandatory C99 features even have become optional in C11. Indeed, due to implementation difficulties in compilers, Variable-Length Array support is no longer required by the C11 standard. These difficulties could dwell in traditional compilers separating declarations from computation statements although Variable-Length Array mixes them. Without VLA, declarations can more easily be moved around without modifying the code semantic. Nevertheless, the solution introduced and discussed in this article is still valid and useful for C11 codes, as well as codes written in previous versions of C.

Some transformations, such as code flattening, do not take into account the scheduling constraints and additional research should be carried out to tackle declarations. Code replication, as in loop unrolling, also requires special attention to preserve scopes and/or flatten them. Additional work is needed.

The high-level intermediate representation described here for source-to-source compilers could also have an impact on the architecture of production compilers. Two IR could be used to offer the best level of information to two different sets of passes and to avoid recomputing missing information in CFG such as loops, multidimensional arrays and local variables.

Listing 4 :Listing 5 :

 45 VLA Example 2 -LLVM-IR version (obtained with clang -O0 -S -emit-llvm) /* ... */ # if __GNUC__ < 4 /* Old GCC 's , or compilers not GCC */ # define _ _ b u i l t i n _ s t a c k _ s a v e () 0 /* not implemented */ # define _ _ b u i l t i n _ s t a c k _ r e s t o r e ( X ) /* noop */ # endif void foo ( unsigned int llvm_cbe_n ) { unsigned int llvm _c b e_ tm p_ _ 1 ; unsigned char * l lv m_ cb e _t mp __ 2 ; unsigned int llvm _c b e_ tm p_ _ 3 ; unsigned char * l lv m_ cb e _t mp __ 4 ; unsigned int * ll vm _ cb e_ tm p __ 5 ; unsigned char * l lv m_ cb e _t mp _ _6 ; *(& llvm_cbe_tmp_ _ 1 ) = llvm_cbe_n ; l lvm_cbe_tmp__3 = *(& l lv m_ cb e _t mp __ 1 ); l lvm_cbe_tmp__4 = 0; *(( void **)& llvm_c be _t m p_ _4 ) = _ _ b u i l t i n _ s t a c k _ s a v e (); *(& llvm_cbe_tmp_ _ 2 ) = l lv m_ c be _t mp _ _4 ; l lvm_cbe_tmp__5 = ( unsigned int *) alloca ( sizeof ( unsigned int ) * ((( unsigned long long )( unsigned int ) llvm_cbe_t mp __ 3 ))); l lvm_cbe_tmp__6 = *(& l lv m _c be _t m p_ _2 ); /* ... */ _ _ b u i l t i n _ s t a c k _ r e s t o r e ( ll v m_ cb e_ t mp __ 6 ); return ; } VLA Example 2 -LLVM-IR to C conversion (obtained with llc -march=c (version 3.0))

Figure 1 :

 1 Figure 1: Data Dependence Graph for Listing 6

Figure 2 :

 2 Figure 2: Effects Dependence Graph for Listing 6

  : the Environment function ρ takes an Identifier and yields some corresponding Memory Locations; and the Memory State or Store function σ gives the Value stored in a Memory Location. With the above, a Statement S can be seen as transforming a Store and/or an Environment, in case of additional declarations, into another. We call memory effects of a Statement S the set of Memory Locations whose Values have been used or modified during the execution of S. Effects E are formally defined as a function taking a Statement and returning a mapping between a pre-existing Memory State and a set of Memory Locations.

  Declarations cannot in general be grouped at the same place, regardless of precedence constraints.• User-defined types such as struct, union, enum

	void example () {	void example () {
	int i ;	int i ;
	int a [10] , b [10];	int a [10] , b [10];
	typedef int mytype ;	typedef int mytype ;
	mytype x ;	mytype x ;
	for ( i =0; i <10; i ++) {	for ( i =0; i <10; i ++)
	a [ i ] = i ;	a [ i ] = i ;
	x = i ;	for ( i =0; i <10; i ++) {
	b [ i ] = x ;	x = i ;
	}	b [ i ] = x ;
	return ;	}
	}	return ;
	Listing 8: After applying	}
	flatten code to Listing 6	Listing 9: After loop distribution of Listing 8
	in C99.

• Dependent types especially variable-length arrays (VLA), are a new way to declare dynamic variables

  table. When a new entry in the symbol table is made, i.e. a declaration statement, a WE effect is attached to this statement. When the symbol table is

	void example () {	define void @example () #0 {
	int i , j , x , y ;		%i = alloca i32 , align 4
	for ( i =1; i <10; i ++) {		; [ alloca others variables ...]
	int a [ i ];		%1 = alloca i8 *
	int b [ i ];	; for ( i =1; i <10; i ++) {
	for ( j =0; j < i ; j ++) {		store i32 1 , i32 * %i , align 4
	a [ j ] = j + i ;		br label %2
	b [ j ] = j * i ;	; < label >:2
	x += a [ j ];		%3 = load i32 * %i , align 4
	y += b [ j ];		%4 = icmp slt i32 %3 , 10
	}		br i1 %4 , label %5 , label %50
	}	; < label >:5
	}	; save the stack
	Listing 10: Two VLA declared inside a loop		%8 = call i8 * @llvm . stacksave () store i8 * %8 , i8 ** %1
		; int a [ i ];
			%6 = load i32 * %i , align 4
	void example () {		%7 = zext i32 %6 to i64
	int i , j , x , y ;		%9 = alloca i32 , i64 %7 , align 16
	for ( i =1; i <10; i ++) {	; int b [ i ];
	int b [ i ];		%10 = load i32 * %i , align 4
	for ( j =0; j < i ; j ++)		%11 = zext i32 %10 to i64
	b [ j ] = j * i ;		%12 = alloca i32 , i64 %11 , align 16
	for ( j =0; j < i ; j ++)	; for ( j =0; j < i ; j ++) {
	y += b [ j ];		store i32 0 , i32 * %j , align 4
	}		br label %13
	for ( i =1; i <10; i ++) {	; < label >:13
	int a [ i ];	; [ computation ...]
	for ( j =0; j < i ; j ++)	; }
	a [ j ] = j + i ;	; restore the stack
	for ( j =0; j < i ; j ++)		%46 = load i8 ** %1
	x += a [ j ];		call void @llvm . stackrestore ( i8 * %46 )
	}	; }
	}	; < label >:50
	Listing 11: After loop distribution of Listing 10	}	ret void

Generated variables are really new variables because they have different scopes.

Acknowledgment

We are grateful to Mehdi Amini who implemented the Effects Dependence Graph technique in PIPS during his PhD work. We also thank Corinne Ancourt, Albert Cohen and Pierre Jouvelot for their careful reading of preliminary versions of this paper and their many suggestions.


Towards a naturalization of social sciences

A case study on semantic social networks analysis

Emile GAYOSO (LATTS, UPEM) Contemporary sociology and anthropology have been deeply influenced by works whose main challenge was to overhaul the distinction between nature and culture.

These include the emblematic research lead by Bruno Latour or Philippe Descola, the first in the field of the sociology of science and technology [START_REF] Latour | Nous n'avons jamais été modernes -Essai d'anthropologie symétrique[END_REF], the second in what he calls himself an « anthropology of nature » [START_REF] Descola | Par-delà nature et culture[END_REF]. Both authors agree to move the border that social scientists previously placed between naturals beings and cultural beings to a dotted line which separates humans from nonhumans, these latter constantly weaving complex links to the first ones and forming "hybrid networks".

In their introduction to the book Naturalism versus constructivism (de Fornel & al., 2007), de Fornel and Lemieux seek to overcome the sterile opposition between "constructivism" and "naturalism" and call for a "non-reductionist naturalization of social sciences". The authors identify two possible routes for such a conversion of social sciences. The first one would be a praxeology concerned with institutions not as abstract social constructs but in action. The second one with the approach proposed by Descola, Latour and Callon and is called a "metaphysicalist comparatism", which would allow to "never lose sight of that te naturalistconstructivist metaphysics is not the only possible method to refer to the existing ".

In this paper, we propose to consider, in light of these theoretical distinctions, the path followed by a stream of research emerging in social sciences the semantic social networks analysis. This field of research has emerged from the convergence of methods from science of complex systems and sociology. In particular, french researchers from the former Centre de recherche en Epistémologie Appliquée (CREA) in the Polytechnique School have developped both a conceptual framework and methodological tools (an online platform allowing socio-semantics corpus analysis) in order to give an empirical basis to the concept of « epistemic communities ». First confined to the analysis of scientific communities [START_REF] Roth | Coevolution in epistemic networks[END_REF][START_REF] Cointet | Dynamiques sociales et sémantiques dans les communautés de savoirs[END_REF], this model has been gradually extended to other data, particularly those produced by the Internet users [START_REF] Dario | Viable Web Communities: Two Case Studies[END_REF]Cardon & alii, 2014).

The greatest ambition of this stream is clearly expressed in one of the first PhD thesis is this domain about "co-evolution in epistemic networks" : "Agents producing and exchanging knowledge are forming as a whole a socio-semantic complex system.

Studying such knowledge communities offers theoretical challenges, with the perspective of naturalizing further social sciences, as well as practical challenges, with potential applications enabling agents to know the dynamics of the system they are participating in. » [START_REF] Roth | Coevolution in epistemic networks[END_REF].

It seems to us that these approaches show a very thorough formalization of the actornetwork theory since it is based on the joint analysis of "individuals" and "concepts", id est humans and non-humans, the latter being objectified, made actors with their representation as nodes in socio-semantic networks. In addition, the researchers of this current, first trained in mathematics, physics and complex systems, are claiming a "naturalization of the social sciences" project calls an epistemological questioning and debate among practitioners of sociology. Thus, relying both on a corpus of documents representative of the development of this line of research, and on a study of the diffusion in european social sciences institutions of the ideas, tools and researchers supporting the semantic social network analysis, we propose to highlight the methodological and epistemological concerns of the expansion of this research field for social sciences1 .

In comparison with the use of other new quantitative methods in sociology like multi-agents models, which have already provoked reactions in the social complex systems analysis community(Venturini & alii,

2015).


Philipp Hertz
email: phertz@ethz.ch

Alexander Sproedt
email: asproedt@ethz.ch

Service supply chain planning for industrial servicesdesign and application of a decision support tool

Keywords: Service supply chain, field service, network planning, decision support, case study, after-sales

Industrial services such as classical MRO-services and also advanced offerings, e.g. performance based contracting, are gaining importance in the machine and equipment industry. From a niche the business units responsible for service have grown to major contributors to the success of the company. Meanwhile operations have grown historically and service manager struggle to professionalize their service operations to improve efficiency. In this contribution we provide an overview of 3 cases of companies trying to gain competitiveness by using a simulation-based decision support system for field service supply networks.

Introduction

In the last years many companies have shifted away from the traditional business of offering manufactured goods only to create more customer value by selling industrial product-service systems based on a the trend called "servitization" [START_REF] Baines | The servitization of manufacturing: A review of literature and reflection on future challenges[END_REF]. The reasons for that are manifold. Financially services contribute to a high ratio of the profit in most companies as the service business still provides the opportunities for high margins for reactive repairs or critical spare parts [START_REF] Alexander | The secret life of factory service centers[END_REF]. Additionally services allow to maintain a customer relationship during the life cycle of the sold product and provide increased customer value which benefits customer loyalty and the potential to react on the feedback of the customer for future product developments [START_REF] Legnani | A framework for the configuration of after-sales service processes[END_REF]. Therefore industrial field services have gained importance in the business of western manufacturing companies for years and became a critical factor for the profitability and competiveness in many cases. These services include basic contracts for pround reactive maintenance activities as well as advances offerings such as technical consulting or retrofitting [START_REF] Gaiardelli | Performance measurement of the after-sales service network--Evidence from the automotive industry[END_REF].

Field service supply networks (FSSNs), as a special kind of service delivery systems, incorporate the technical support in form of service technicians in and off the field and a supply network for the delivery of spare parts. Both parts of the field service network have to work cooperatively to fulfill SLAs at lowest cost. Thereby service mangers face among other problems uncertain and lumpy demand, heterogenic technical and customer requirements with different performance targets, a highly scattered installed base with a variety of technologies and generations of asset from different centuries [START_REF] Dennis | Service management: Building profits after the sales[END_REF]. This requires a highly skilled and flexible workforce that can provide service in a timely manner over a certain region. But many companies still struggle with historical structures, lack of transparency and rising costs while customer demand more complex services, e.g. availability or performance based contracting, for reasonable prices.

Though the importance of the service business for manufacturing companies is beyond dispute, and many researcher and practitioners have stressed the "urgency for rigorous study to guide service managers in improving the design, competitiveness, efficiency and effectiveness of service delivery" decision makers today are still missing decision support tools [START_REF] Metters | Service Management-Academic Issues and Scholarly Reflections from Operations Management Researchers*[END_REF]. Most methods used to investigate or improve service operations to professionalize service operations in field service networks are outdated and overly simplistic [START_REF] Watson | A Simulation Metamodel for Response-Time Planning*[END_REF]. Therefore we will investigate the area of FSSNs planning and decision support in the following.

2

Literature review

Field service network planning

Decision support systems are "interactive computer-based systems that help people use computer communications, data, documents, knowledge, and models to solve problems and make decisions" [START_REF] Power | Decision support systems[END_REF]. Their purpose is to support decision-making without before any kind of changes is conducted. This is of upmost importance for the service business, as changes in the field service network are costly while their effects on the performance of the systems, e.g. in terms of responsiveness or costs, can hardly be anticipated. In the following we want to detail the different decisions to be made in FSSN design and planning shortly, before we will analysis contributions from literature and practices in industry.

Similarly to Advanced Planning in Supply Chain Management, field service planning includes different varies planning tasks that need to be conducted to design the "people and parts" network over different time horizons [START_REF] Hertz | Industrial field service network planning: Existing methods in supply chain planning and modeling and their applicability for field services[END_REF]. On a strategic and long-term horizon this includes districting of the installed base into decoupled territories which that are covered by a common a set of resources for a certain service [START_REF] Watson | A Simulation Metamodel for Response-Time Planning*[END_REF][START_REF] Colen | Product service systems: exploring operational practices[END_REF], the definition of skill sets for technicians and the right target mix in the workforce [START_REF] Chakravarthy | Optimal Workforce Mix in Service Systems with Two Types of Customers[END_REF][START_REF] Colen | Cross-training policies in field services[END_REF], as well as the selection of locations for facilities [START_REF] Frederick | Aggregate planning models for field service delivery[END_REF]. Mid-term process design, including the definition of dispatching rules for the assignment of tickets to technicians [START_REF] Banerjee | Simulation-based evaluation of dispatching policies in service systems[END_REF][START_REF] Hill | An Experimental Comparison of Dispatching Rules for Field Service Support*[END_REF], and capacity, e.g. manpower and inventory, planning for each location becomes relevant [START_REF] Watson | A Simulation Metamodel for Response-Time Planning*[END_REF]. All these planning tasks are highly interrelated and therefore hard to optimize individually. Furthermore, small changes in such a complex system might lead to a totally different behavior of the entire system [START_REF] Joseph | Using Simulation To Evaluate Resource Utilization Strategies[END_REF][START_REF] Hilla | An Approximate Model for Field Service Territory Planning[END_REF]. Therefore also highlevel decision support should rely on the analysis of the realistic behavior of the complex system as a whole.

Decision support for field service network planning

State of the art software packages mostly offer planning support on an operational level by providing optimization algorithms or visual presentations of the work load based on real time data to enhance the information that is available for dispatchers. On a strategic or tactical level these software packages offer only limited support [START_REF] Rapaccini | A simulation-based DSS for field service delivery optimization[END_REF].

In literature a variety of contribution of different authors can be found that have developed mathematical programming or queuing models to support single or multiple planning tasks of FSSN design [START_REF] Frederick | Aggregate planning models for field service delivery[END_REF][START_REF] Hilla | An Approximate Model for Field Service Territory Planning[END_REF][START_REF] Tang | An approximation manpower planning model for after-sales field service support[END_REF][START_REF] Abernathy | A Three-Stage Manpower Planning and Scheduling Model -A Service-Sector Example[END_REF][START_REF] Dinh | Manpower Capacity Planning Model Using a Queuing Approach for Ocè Nederland BV After-Sales Field Service Support[END_REF]. Based on shortcomings of these approaches such as the limited the problem's complexity [START_REF] Watson | A Simulation Metamodel for Response-Time Planning*[END_REF][START_REF] Joseph | Using Simulation To Evaluate Resource Utilization Strategies[END_REF] or the use of deterministic model parameters in such a uncertain environment which make most contributions only moderately applicable, simulation has been chosen as underlying technique to provide heuristic "("What-If") support" by applying proper design of experiment [START_REF] Aggarwal | Simulation as a DSS modelling technique[END_REF][START_REF] Mjema | An analysis of personnel capacity requirement in the maintenance department by using a simulation method[END_REF]. The most relevant contributions based on the use of simulation to support decision making in this context can be clustered in different parts. On a tactical level support staffing, process design, or more specifically dispatching policies, are investigated based on response time and utilization indicators by Hill [START_REF] Hill | An Experimental Comparison of Dispatching Rules for Field Service Support*[END_REF], Watson et al. [START_REF] Watson | A Simulation Metamodel for Response-Time Planning*[END_REF], Dear [START_REF] Joseph | Using Simulation To Evaluate Resource Utilization Strategies[END_REF], Visser [START_REF] Visser | A simulation technique for optimising maintenance teams for a service company[END_REF] and Duffuaa and Raouf [START_REF] Duffuaa | A simulation model for determining maintenance staffing in an industrial environment[END_REF]. Another important class of contributions focuses on the optimal qualification and dispatching strategies in manpower planning for different scenarios [START_REF] Colen | Cross training policies in a maintenance field service organization[END_REF][START_REF] Agnihothri | Cross-training Decisions in Field Services with Three Job Types and Server-Job Mismatch[END_REF][START_REF] Agnihothri | Workforce Cross-Training Decisions in Field Service Systems with Two Job Types[END_REF]. Focus here lies on the degree of cross training and pooling effects within the workforce. Only a few contributions integrate several aspects of field service network design as for example Rapaccini et al. [START_REF] Rapaccini | A simulation-based DSS for field service delivery optimization[END_REF]. Though all contributions provide important insides into the challenges of operations management for field services, they lack important characteristics to be applicable for modeling and analyzing a FSSN holistically. An overview of the evaluation of the most important contributions is given in table 1. The introduction and literature review have revealed a gap in academia and practice alike in regard to appropriate methods to assist service managers in designing and planning their FSSN. Based on the decision prior made to use discrete event simulation as a technique to support decision making, the following research questions have been formulated in regard to the development of a DSS:

Table 1. Relevant contributions in FSSN simulation

Author Focus

1. How can decision making for designing an industrial FSSN in different industries be supported adequately by a DSS based on discrete event simulation? a. What are the different entities that have to be considered in such a model and how do they interact? b. Which performance indicators are needed to support decision making for the different planning problems? 2. Which insights can be drawn from the application of such a DSS?

The project AsPlanned provided the starting point for this research. The aim of the project was to develop a decision support tool based on discrete-event simulation. The software should support decision-making in field service network planning for different planning tasks, e.g. the districting of field service networks or location and capacity planning for the technical field support and the spare parts supply chain. Efforts for modeling and using the software should be reduced by explicitly adapting it to the needs of FSSN planning while the generalizability and therefore wide applicability should be assured based on the use of reference models for the processes and resources inside a FSSN. Therefore five different companies offering field services were included in the project to assist the software design as depicted in table 2.

Table 2. Companies participating in the project

Industry Industrial conglomerate

Infrastructure/ Construction

Machine tool manufacturing

Machine tool manufacturing

Medical equipment

The main methodology for the development of the simulation framework embedded in the DSS was based on the guidelines provided by Bertrand (2002). The life cycle of a simulation study approach by Pidd [29] was used while guidelines proposed by Law and McComas [START_REF] Law | Simulation Modeling and Analysis[END_REF] were considered as well. Different stakeholders, as for example service managers and field technicians, were already involved in the design phase of the DSS to support internal validity of the simulation framework and the usability of the software.

Decision support system for field service supply networks

The DSS is intended to support decision-making by the use of a discrete-event simulation framework to model FSSN. The process of service delivery can be designed based on predefined activities and includes normally at least the generation of random or planned service demand from machines in the field, the allocation these service tickets to technicians who then transfer to the assets, perform the required service and leave for home or the next asset. The input for the simulation model can be inputted via an adapted version of the Activiti process mapper, which represents a visual process mapping interface that includes drag-and-drop functionality and a data input interface including different tables and drop down cells that can be filled manually or imported from MS Excel. The simulation engine running in the background is based on the DesmoJ [START_REF] Liu | Scheduling and Coordination of Distributed Design Projects[END_REF]. Next to the modules for data input, the DSS support the geographical visualization of assets, service technicians, and facilities based on Open-StreetMap and allows for performance analysis of the simulation runs in a comprehensive KPI module. Figure 1 shows the most important modules of the DSS.

Fig. 1. General user interface of the AsPlanned Software

The simulation models are configured automatically based on the input of the user. The service delivery process is obtained from the Activiti process drawing while the data input data, e.g. for assets and technicians, are needed to create the different entities interacting in the FSSN. The main entities of the simulation framework are employees, assets, spare parts and service tickets. Only a few parameters are mandatory to construct a basic simulation model while a lot of detail can be added by including optional parameters in the models. Each predefined and enumerable parameter of an entity may also define the dimension for the calculation of operational parameters in the service delivery process (e.g. mean of processing time based on product and service type). Employees can be of different types, e.g. field technicians (FTs) or offfield staff (technical or non-technical). Various parameters include the skill, home location, shift, break and capabilities to perform the different activities. Assets consist of different items, which might represent modules of a machine, e.g. drive or control unit, and represent technical equipment as part of the installed base. Item may generate service tickets of different types based on the user input. Tickets represent service requests of a certain type for a specific item of an asset. Daily and weekly demand patterns can be inputted for each service type to allow for a realistic workload during the week while the time between the generations of two tickets can be modeled by various probability distributions. In addition to immaterial services, service parts (e.g. spares and tools) can also be modeled including parameters such as availability and replenishment time. Activities are parts of the process and can be of 10 unique types that all have different parameters, e.g. the travel speed for transfer activities or the activity time for on-site service execution. During the activity "dispatching" tickets are assigned to FTs and placed in their job list. After finishing a job the employee conducts the activity "job planning" which refers to the selection of the next ticket for execution in the field. Various assignment algorithms for different service and shift types can be selected for both of these activities. Tickets in the field can be interrupted by breaks, the nonavailability of parts, escalations in regard to capabilities or interruptions by high priority jobs. Transfer times are calculated based on the geographical distance that is obtained automatically by converting addresses in GPS coordinates via Google Maps.

5

Improving operations in the field service supply network

The DSS has been used for evaluating different scenarios for all five companies being part of the project. In general the investigations can be clustered as local, with networks stretching over an area of less than 100 km2 up to the size of one country, and global for networks operating world or continent-wide. Performance was evaluated based on the response times and the total hours spent in the different activities.

In the following we will highlight three different investigations, two on a local (2 years simulation time) and one on global level (10 years simulation time). In a high density local network company 2 wanted to investigate the change of districting and qualification strategy by moving from a generalist's qualification profile with many decoupled districts to a specialist profile where up to 6 districts were accumulated on a regional layer. FTs were now dispatched based on their skill, distance to the customer and work load instead having a fixed assignment to their assets. While on-site execution times and therefore total hours spent on-site could be reduced by more than 6% due to better skill-job matches, travel time and response time were increasing by 14%, respectively 13%. On a global level the result of a generalization of the workforce and therefore better geographical dispatching was investigated as well and in a reduction of average response times by 23% while transfer times were 33% shorter. Another local network investigation was focused on the reduction of the number of technicians being able to conduct field work (with 32% of total work time spent in the field on average) by 10% and therefore increasing the time spent in the field for specialized FTs by 12.5%. This resulted in the simulation in an increase of the response time for critical interventions with high priority by more than 22% and an increase in transfer times of 3%.

Limitations & Outlook

The last paragraph has shown that the simulation-based DSS provides a huge potential to obtain meaningful quantitative results for difficult questions regarding the operations of FSSNs. Without a question results have to be investigated and understood well enough. During the projects the models have been improved in the level of detail in multiple cycles until results were obtained that could be understood in every detail.

During the application of the tool as well as during the investigation of historical data for the data input interesting results were obtained, that improved the transparency of the service operations and capabilities of decision makers to improve operations. Next to all benefits there are still limitations. Though the software reduces the time and cost effort for modeling significantly by building upon a generic framework, investigations with the DSS still mean a lot of work due to the data that was often not available in the required quality. Additionally the software is still at a prototype stage and has its limitations in respect to models sizes and simulation durations depending on the hardware used.