Ludwig Dumetz

Jonathan Gaudreault

André Thomas

Nadia Lehoux

Philippe Marier

Hind El-Haouzi

ATP vs CTP policies in co-production context: the winner is not always the expected one

Keywords: Order promising, simulation, divergent process, co-production

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

For traditional manufacturing industries (e.g. assembly), the impact of orderpromising policies (ATP, CTP, etc.) is well known and documented (e.g. [START_REF] Slotnick | Order acceptance and scheduling: A taxonomy and review[END_REF] [START_REF] Slotnick | Order acceptance and scheduling: A taxonomy and review[END_REF]. The literature typically shows the trade-off between accepting orders and losing sales ( [START_REF] Altendorfer | Influence of order acceptance policies on optimal capacity investment with stochastic customer required lead times[END_REF] [START_REF] Altendorfer | Influence of order acceptance policies on optimal capacity investment with stochastic customer required lead times[END_REF]. In contrast, for industries with divergent processes (i.e. several products from the same raw material) and coproduction, the assessment of these policies regarding market conditions seems to have attracted less attention. In these industries, producing a specific product leads to the production of other co-products and by-products, which generates inventories for products that can be difficult to sell or that may have less value. This is the case of the sawmilling industry where standard commodity products as well as products designed for specific customers are produced from the same raw material and at the same time. Customer orders are handled by most North-American lumber sawmills by applying a make-to-stock production strategy. Certain others accept/refuse orders according to available-to-promise (ATP) quantities while a few use more advanced approaches like capable-to-promise (CTP) or mixed approaches combining both ATP and CTP.

In this paper, a simulation framework from [START_REF] Dumetz | A Simulation Framework for the Evaluation of Production Planning and Order Management Strategies in the Sawmilling Industry[END_REF] Dumetz et al. (2015) is used to compare these different policies for the sawmilling industry context based on various market conditions. This paper is different from the previous work by going further via more advanced order management strategies tested depending on various market conditions. It also assesses the impact of key parameters on the number of accepted orders. Results show that these advanced order acceptance policies like CTP (capable-to-promise) allow us to accept more orders in certain types of markets and, in contrast to classical manufacturing industries, ATP (available-to-promise) performs better for a huge demand than other policies.

The remainder of the paper is organised as follows. Section 2 presents preliminary concepts regarding mathematical models in lumber industry, as well as a description of the simulation framework used. Section 3 presents how the framework was used to compare and analyse the lumber industry performance when adopting different order promising policies based on various market conditions. Finally, Section 4 concludes the paper.

Preliminary concepts

Lumber production is a three-phase manufacturing process ([4] Gaudreault et al. 2010) that first involves a unit responsible for sawing logs into green rough lumber according to a certain cutting pattern. At this stage, the lumber produced varies in terms of quality (grade), lengths, and dimensions. The lumber must then be dried using a kiln unit so as to reduce its moisture content. The final step is conducted by the finishing unit to obtain the desired surface and thickness. The lumber manufacturing system is thus defined as a divergent process with co-production.

During the last few years, lumber production planning has been better supported by the development of many optimisation models. At the detailed operational level, [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] Gaudreault et al. (2010) proposed three MIP models that can be used to plan/schedule sawing, drying, and wood finishing operations. The objective function allows maximising production value and/or minimising order lateness. A basic coordination mechanism (heuristic) is provided to synchronise these plans. Improved coordination mechanisms are proposed in [START_REF] Gaudreault | Distributed search for supply chain coordination[END_REF] Gaudreault, Frayret, and Pesant (2009) as well as in [START_REF] Gaudreault | Supply chain coordination using an adaptive distributed search strategy[END_REF] [START_REF] Gaudreault | Supply chain coordination using an adaptive distributed search strategy[END_REF]. A stochastic version of the sawing operations planning was developed by [START_REF] Kazemi | A stochastic programming approach for sawmill production planning[END_REF] Kazemi-Zanjani, Ait-Kadi, and Nourelfath (2013). An improved version of the drying model was also proposed in [START_REF] Gaudreault | Combined planning and scheduling in a divergent production system with co-production : A case study in the lumber industry[END_REF] [START_REF] Gaudreault | Combined planning and scheduling in a divergent production system with co-production : A case study in the lumber industry[END_REF].

The previous production planning models try to minimise costs, maximise revenues or minimise customer orders lateness. At the detailed operational planning stage, it is difficult to find good solutions for these problems when faced with both divergent process and co-production. Indeed, even if there is one order for one specific product, the production process will produce several other products and byproducts at the same time for which there will not necessarily be a demand. Not only will the production planning be affected, but it will also impact the order promising process.

An order-promising policy defines the rules for accepting or rejecting the orders depending on product availability and the capacity of the company. The best-known policies are available-to-promise (ATP) and capable-to-promise (CTP). [9] APICS, (2012) defines ATP as "the uncommitted portion of a company's inventory and planned production at a designated location" while CTP as "the process of committing orders against available capacity as well as inventory".

In his thesis, [START_REF] Islam | Order promising and production planning methods for sawmills[END_REF] Islam, (2013) combines order promising and production planning via an MIP model. His object is to maximise the total revenues over a planning horizon of 52 weeks via promising orders and making a production schedule to fulfil orders. [START_REF] Pibernik | Inventory reservation and real-time order promising in a make-to-stock system[END_REF] Pibernik and Yadav (2009) made use of a combination of both ATP and CTP to optimise the target level without permitting back orders in a make-to-stock system. [START_REF] Kilic | Order acceptance in food processing systems with random raw material requirements[END_REF] Kilic et al. (2010) proposed a two-bound method for orders acceptance/rejection in the food industry, based on the resource level. [START_REF] Azevedo | Advances in Profit-Driven Order Promising for Make-To-Stock Environments -A Case Study With a Canadian Softwood Lumber Manufacturer[END_REF] Azevedo, D'Amours, and Rönnqvist (2012) proposed an order-promising model in a make-tostock environment for the Canadian softwood lumber industry. They proposed a three-step method that segments market based on customers' price sensitiveness. They maximised the profit while allowing back orders. Finally, [START_REF] Dumetz | A Simulation Framework for the Evaluation of Production Planning and Order Management Strategies in the Sawmilling Industry[END_REF] Dumetz et al.

(2015) created a simulation framework to evaluate production planning and order management strategies for the sawmilling industry. Using the framework, the authors were successful in showing the importance of the length of the planning horizon for different order-promising policies like ATP as well as how a company's performance is affected by demand intensity by utilising such order-promising policies. However, CTP was not taken into account in their experiments.

Even though the mathematical models developed in the literature led to interesting results, it remains difficult for a company to evaluate the efficiency of which orderpromising policy would be the most efficient one for its market contexts. This issue may therefore be dealt with by simulation through testing different scenarios in a dynamic environment and illustrating how diverse order-acceptance policies may impact a company's performance. Furthermore, the conclusions highlighted by the authors concerning the order-promising policy performance in classical manufacturing systems might not necessarily reflect the reality for a divergent/coproduction process. As a result, the research we propose here aims to use simulation so as to compare order-acceptance policies for a sawmilling production system based on different market conditions.

ATP vs CTP according to production and market conditions

In this section, we describe how the simulation framework developed by [START_REF] Dumetz | A Simulation Framework for the Evaluation of Production Planning and Order Management Strategies in the Sawmilling Industry[END_REF] was used to determine which policy should be adopted by a company facing a divergent production system according to specific market characteristics. The framework includes the generation, the acceptance/rejection, and the shipment of orders. It also includes an ERP system for inventory management, production, ATP and CTP calculation, etc. The simulation model was developed using Simio, while the ERP modules were developed using the C# programming language. During the simulation, the system generates orders. Each order can either be accepted or rejected according to certain parameters that define the policy used (ATP, CTP, or other). If the order is accepted, it waits until the delivery date and the availability of material. The order is then shipped. No order lateness is tolerated.

Three order management policies were compared, namely Stock, ATP, and CTP, since they are the ones most used by the sawmilling industry. Two different market contexts were also considered: one composed of commodity products only and another one composed of a combination of both commodity products and customised products. The demand intensity varies for each market. Demand intensity is a parameter expressing the total number of orders received as a percentage of the maximal production capacity, and is used to define the order arrival rate. The simulation horizon covered two years, each day was divided into two production shifts (periods) of 7 hours. This production was planned each week for a planning horizon of four weeks. The same optimisation model as in [START_REF] Dumetz | A Simulation Framework for the Evaluation of Production Planning and Order Management Strategies in the Sawmilling Industry[END_REF] was used to generate the production plan. The demand lead, that is the time between the date we receive the order until the due date, is fixed to a triangular law (1,2,3). Some assumptions were also made when developing the experimentation: there is no stochastic event like failure in production; and raw material is infinite. A warm-up period of one year was set to reach a steady state situation. A total of 240 scenarios were simulated with a significant number of replications to have a desired confidence interval (95%). The volume of sales and the average inventory were the two key elements used to measure the performance of the company according to the order management policy selected.

Market with only commodity products

First, we compare how the different order-management policies selected perform in a 100% commodity-product market. Figure 1 gives the volume of sales (number of orders) according to the demand intensity for the order acceptance policies chosen (Stock, ATP, and CTP). As can be seen, CTP accepts more orders than ATP when the demand is low. It seems to be more profitable to reschedule the production according to customers' needs while avoiding missing opportunities. This is the same result we would get in classical manufacturing systems with no divergent/co-production processes. However, the particularities of the lumber industry come into play when demand intensity reaches 125%. From that point, ATP outperforms CTP. This is explained by the following reason. When demand intensity reaches 125%, demand is significant and all the production planned according to forecasts can be sold. With a CTP policy, the production processes are modified to best suit the most recent orders. However, by changing the manufacturing process used, the co-products produced change too, and nothing guarantees that in the short term, there will be a demand for these new coproducts. On the other hand, the ATP policy maintains the same production plan that was established based on forecast and that volume is easily sold when demand is high. Therefore, what is an advantage when demand is low becomes a disadvantage when demand is high. This situation is a good example of the specific impact and difficulties associated to processes embedding co-production.

In order to show how the ATP/CTP trigger point is affected by forecast accuracy, Figure 2 provides results similar to Figure 1, but for a situation with inaccurate forecasts. In the previous experiments, planning was carried out using a forecast supposing that 80% of the most popular produced products would form 100 % of demand. In this new experiment, we suppose that 20% of the less popular products will form 100% of the demand. The trigger point is therefore shifted to the right in comparison to Figure 1 because ATP needs greater demand so that more low-demand products can be used to fulfil the demand.

Market with both commodity and customised products

In the previous subsection, we compared different policies (ATP, CTP, Stock) in a market composed of 100% commodity products. Forest products are standardised in North America by the NLGA1 organisation, which allows the products to be considered as a commodity. However, the forest industry has to confront the increasing demand for customised product2 . In the next experiments, when comparing the impact of different order-acceptance policies, both commodity and customised products are considered. To do so, some additional parameters were defined and a new order-acceptance policy included (a mixed approach called MIX that uses ATP for commodity product orders and CTP for customised products).

Figure 3 shows the results for a market composed of 70% commodity products and 30% customised products. CTP can again accept more orders than ATP as it can accept orders for customised products. However, when demand intensity is high enough, ATP is still able to use the entire capacity for commodity products only. ATP becomes better than CTP for very high demand (around 190% demand intensity) for the same reason explained previously.

Figure 3 also introduces the MIX policy, which, we recall, uses the ATP to satisfy demand for commodity products. It only generates a new schedule when there is demand for customised products. When demand is very low, ATP is outperformed by MIX (for the same reason ATP is outperformed by CTP). When demand intensity reaches 100%, MIX performs better than CTP because it benefits from the effect of good forecasts, i.e. MIX uses ATP for commodity products and then keeps the same production plan that was established using forecast. When demand is high, that volume is easily sold. At a very high demand intensity level, the three policies are almost equal.

Impact on inventory

The previous analyses focused on the volume of sales to measure the performance of different order-promising policies according to demand intensity. However, when selecting the most efficient policy to put into practice the average inventory over the year must be considered. The new experiment takes this element account for a market composed of 90% commodity products and 10% customised products with an accurate forecast.

As shown in Figure 4, for any policy, the average inventory decreases with an increase of the demand intensity. Nonetheless, greater demand intensity involves a larger difference between ATP/CTP and Stock policies. We observed previously that for a very high demand intensity, the number of accepted orders by ATP or CTP was equal. In contrast, the average inventory for CTP is smaller than for ATP because CTP can trigger a new plan each time an order is received, resulting in less time spent in stock. Finally, the AcceptAll policy appearing in blue in Figure 4 consists of accepting all orders whatever the consequences, which explains the low inventory level. However, since no company would accept orders they could not fill, this policy is utopic. It is used for comparison purposes only.

In this research, the simulation framework developed by [START_REF] Dumetz | A Simulation Framework for the Evaluation of Production Planning and Order Management Strategies in the Sawmilling Industry[END_REF] [START_REF] Dumetz | A Simulation Framework for the Evaluation of Production Planning and Order Management Strategies in the Sawmilling Industry[END_REF] was used to compare different order-promising policies for a divergent production system with co-production. By testing different scenarios, we were able to measure the impact of well-known policies on the performance of a company in the sawmilling sector. This allowed us to illustrate that the best policy to use in a divergent production system often differs from the one that would have been optimal in a classical manufacturing (e.g. assembly) context. As an example, we showed that although CTP allows having a better income for certain types of market (i.e. where demand is very low), ATP performs better in some other cases. Moreover, we showed that using a mixed policy when market is composed of commodity products and customised products is a beneficial option.

  of sales (MBFM) Demand intensity (% of the maximal production capacity) Volume of sales ATP Volume of sales CTP Volume of sales Stock

Figure 1 :

 1 Figure 1: Volume of sales according to the demand intensity (Commodity product = 100%; accurate forecast)

  % of the maximal production capacity) Volume of sales ATP Volume of sales CTP Volume of sales Stock

Figure 2 :

 2 Figure 2: Volume of sales according to the demand intensity (Commodity product = 100%; inaccurate forecast)

Figure 3 :

 3 Figure 3: Volume of sales according to the demand intensity (Commodity product = 70%; accurate forecast)

Figure 4 :

 4 Figure 4: Average inventory over the year according to the demand intensity and the associated volume of sales (Commodity product = 90%; accurate forecast)

NLGA: National Lumber Grades Authority.

In Europe, customised products represent the main part of the market.


Ludwig Dumetz
email: ludwig.dumetz@cirrelt.ca

Jonathan Gaudreault
email: jonathan.gaudreault@forac.ulaval.ca

André Thomas
email: andre.thomas@univ-lorraine.fr

Hind Bril El-Haouzi
email: hind.el-haouzi@univ-lorraine.fr

Nadia Lehoux
email: nadia.lehoux@cirrelt.ca

Philippe Marier
email: philippe.marier@ulaval.ca

Planning and Coordination for Decentralised Business Units in a Lumber Production Company

Keywords: Coordination mechanisms, simulation, planning, divergent process, co-production. 

Mathematical models are frequently used in various industries to help decision makers to plan their activities. Many researchers develop planning models for a specific business unit. As an example, the forestproducts industry has access to specialised mathematical models for each production centre of thesawmill (sawing, drying, finishing units) which calls for decentralised planning. In the literature, these models are most of the time evaluated/tested separately, or connected using heuristics and testedin a "static" context ("one shot"demand datasets are provided).In this paper, we want to simulate theuse of these tools by companies for a long period of time (new orders are arriving dynamically, planning need to be updated periodically, etc.).Different coordination mechanisms are compared. We show what the performance of the company would be in terms of accepted orders and average inventory using various coordination mechanisms and order acceptance policies such as available-to-promise (ATP) and capableto-promise (CTP). Our main finding is that previously published coordination mechanisms for decentralised planning leads to bad CTP implementations which open very interesting research avenues.

INTRODUCTION

The wood transformation process consists of three main activities: the sawing, drying and finishing operations. At the sawing operation, logs are sawn according to different plans. The basket of products obtained is composed of green wooden board with different lengths, thicknesses and qualities. These wooden boards are then dried in kilns depending on their physical characteristics. Finally, those boards are planed to get the right thickness and stored until delivery to the customer. This transformation process must take into account the customer demand and the supply of raw material. It is known as a divergent process with coproduction. In addition, the combinatorial effect between each activity, as well as the variability in the supply (quality, diameter, length ...) makes it extremely difficult to manage a sawmill. To help decision makers, there are various mathematical models to optimise those three activities.

Many researchers develop planning models for a specific business unit. As an example, the forestproducts industry has access to specialised mathematical models for each production centre of the sawmill (sawing, drying, finishing units) which calls for decentralised planning.

In previous work, Dumetz et al. (2016) evaluated and compared the impact of different order acceptance policies for different market contexts.

In this paper, the focus is on the coordination between each activity of the wood transformation process. A simulation approach is proposed to evaluate and compare various coordination mechanisms between the three activities of the sawmill (sawing, drying and finishing operations), depending on the market context of the company and its own production parameters. The entire wood transformation process is taken into account and each activity has its optimisation model. We show that it is very difficult to obtain good performance in a decentralised environment facing a divergent process with co-production because of the combinatorial character of the entire process, even if each activity plans their production using an optimisation model. Thus coordination mechanisms need to be used to maintain a good performance of the company in terms of accepted orders and average inventory. This article is organized as follows: Section 2 presents a literature review of the various concepts discussed. Section 3 introduces the simulation model carried by Dumetz et al. (2016) and used to perform the experiments. Changes have been added and are explained. Planning models at the sawing, drying and finishing operations are also explained in this section. Section 4 presents the coordination mechanisms used in all the scenarios. Section 5 shows the results and analyses. Finally, Section 6 concludes the paper and indicates future work to be carried out.

LITERATURE REVIEW

For sawing operation, [START_REF] Maturana | Scheduling production for a sawmill: A comparison of a mathematical model versus a heuristic[END_REF] mention several authors who have worked on the best way to cut wood and thus select the best plan that creates the best volume, the best value or/and the best yield: Occeña&Schmoldt, (1996); [START_REF] Todoroki | Combined primary and secondary log breakdown optimisation[END_REF]; [START_REF] Winn | Alog: A spreadsheet-based program for generating artificial logs[END_REF]. But few worked on how to plan the sawing operation to meet demand. As an example, [START_REF] Todoroki | Dynamic control of timber production at a sawmill with log sawing optimization[END_REF] proposed a system that takes into account the optimisation at the sawing operation and the demand for sawn products. The product price is also highlighted by undergoing variability over time. It is shown that the problems of over-production/under-production were reduced. [START_REF] Maturana | Scheduling production for a sawmill: A comparison of a mathematical model versus a heuristic[END_REF] compared two methods (a mathematical model and a heuristic already used) to select the best cutting patterns over a period of 6 weeks in a sawmill. The demand is considered. The supply is fixed and there is no stochastic event in the machine's yield or the demand.More recently, Alvarez and Vera (2014) proposed a robust optimisation method to plan the production of a sawmill at the sawing operation. They highlight the fact that there is some variability in the yield coefficients of the cutting pattern and they showed that the methodology they used is less prone to variability of inputs. No uncertainty is considered for the supply. At the drying operation, [START_REF] Marier | Kiln Drying Operation Scheduling with Dynamic Composition of Loading Patterns[END_REF] proposed a MIP/constraint hybrid planning model that dynamically generates load patterns during the planning. This model is used in industry. [START_REF] Marier | Implementing a MIP model to plane and schedule wood finishing operation in a sawmill: lessons learned[END_REF] adapted a model developed by [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] to plan the finishing operations in a sawmill. This MIP model is used by a company and allows them to minimise order lateness. As for a lot of industries, the sum of local optima is not equal to the global optimum.It is necessary to somehow take into account the transformation process in its entirety. To the best of our knowledge, only [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] proposed, for the wood industry, an approach considering the possibility of taking into account the entire operational transformation process. In this paper we want to simulate the wood planning process as a whole to assess and compare different control strategies. The aim is to provide tools to mills for the planning, the design and the deployment of control systems. A control strategy is defined, inter alia, a control architecture (that represents the structure and the organisation of the decision levels), optimisation models used in the planning of each activity, the size of the planning horizon, the order acceptance policies used, the coordination mechanisms used to coordinate each operation.

For many years, mathematical models used for production planning help decisionmaking in different industries (see the review of Díaz -Madroñero, Mula&Piedro ( 2014)). At each stage of the production process, an optimisation is performed to maximise different values such as efficiency, produced value, or minimise other such delays. However, although these models are very useful to optimise each business in the process, some indicators or goals may be in conflict with each other. The need for consistency and overall objective is therefore necessary for industries. The overall objective can correspond to an objective of cost or quality (e.g. customer satisfaction). However, having an overall objective involves the use of coordination mechanisms [START_REF] Strader | Simulation of order fulfillment in divergent assembly supply chains[END_REF]). [START_REF] Rose | Towards a common repository for collaborative knowledge in product design activity[END_REF] define coordination as "a set of rules and procedures ensuring the operation of a group." Moreover, the Grai method gives methodology that can be applied to our case: coordination allows each decision unit to work with information, treating his problems in a decentralised manner taking into account the overall objectives. Each unit will have its own model, reduced to its area of intervention. Many authors are interested in coordination problems in industry [START_REF] Bhatnagar | Models for multi-plant coordination[END_REF]. [START_REF] Muhl | Global optimization in a vehicle manufacturer factory[END_REF] showed the importance of coordination in a transformation process composed by different jobs (so several local optimisers), and based on a global optimisation method for an assembly line in the automotive industry. The assembly line is composed of three units: the body assembly, painting and the final assembly. Each unit is optimised and there are various performance indicators to evaluate the unit's performance. The approach is to vary the parameters of each local optimiser modelled as a chromosome. In order to qualify and quantify the variation in these genes, the authors have developed a simulator of the productive system and a weighted indicator system. This study is interesting: it shows the interest in taking into account the local optimisers in a more overall optimisation approach. It also shows the interest of the use of simulation to measure the overall performance of the company. But in our case, the combinatorial effect between the sawmill operations, drying operation and finishing operation, as well as the divergent process with coproduction in the forest industry make it very difficult to generate a single plan for all these activities. More recently [START_REF] Arshinder | A review on supply chain coordination: coordination mechanisms, managing uncertainty and research directions[END_REF] showed an overview of what coordination could be in a supply chain. One can find various coordination mechanisms such as contracts, information technology, information sharing or joint decisionmaking. In the forest industry and especially regarding the wood transformation process, [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] studied the problems of coordination and offer three models for each activity (sawing, drying and finishing operations) connected by coordination mechanisms. To the best of our knowledge, this is the only study taking into account the whole process of wood transformation. The combinatorial effects are then highlighted and various coordination mechanisms are studied: upstream planning (See [START_REF] Bhatnagar | Models for multi-plant coordination[END_REF]) when planning each activity is done one after the other (starting with the one closest to the client), Two-phase planning (there is a demand propagation phase where plans are made according to an infinite supply and a real plan of the propagation phase for each activity) and finally bottleneckfirst schedule (which consists in a two-phase planning starting from the neck). Infinite supply means that the production planning takes into account an infinite raw material supply: at the finishing operations the plan is made by considering infinite dried products and at the drying operation the plan is made by considering infinite cut wood boards. Those coordination mechanisms will be better explained in Section 4. For each activity of the wood transformation process, a mathematical model generates a production plan. The authors showed that over a period of sixty days, the mechanism "bottleneck-first planning" has better results (in terms of on-time delivered orders). While this study is very interesting, we want to go further by simulating a rolling horizon and varying control strategies (various market contexts, several order acceptance policies...). We will use the simulation that is necessary because of the stochastic nature of many variables as highlighted by [START_REF] Chang | Supply chain modeling using simulation[END_REF]) and the will to measure the company's performance in different configurations.

PLANNING AND SIMULATION MODELS

We want to simulate the entire wood planning process in a decentralised manner and thus use various coordination mechanisms to ensure communication between the sawing, the drying and the finishing operation. Three different planning models will be used for each business unit.Simio will be used to simulate scenarios.

In previous works, Dumetz et al. (2016) evaluated different order acceptance policies for industries facing a divergent process with co-production. The simulation model is shown below in Figure 1. Coupled with a production planning module of a "custombuilt ERP" responsible for the creation of a production planning, orders are generated, accepted or refused depending on order acceptance policies (ATP: available-to-promise, CTP: Capable-to-promise ...) then sent. This production planning module used a mathematical model from [START_REF] Marier | Implementing a MIP model to plane and schedule wood finishing operation in a sawmill: lessons learned[END_REF] to generate the production planning. The production process was centralised: model used raw material as an input and created a production planning over a given horizon. The outputs were the final products. It has been shown that for a company facing a divergent context with co-production -compared to a traditional manufacturing system such as assembly for example -the use of certain policies over others was more appropriate, according to the type of market and the specific parameters of the company. In this paper, we propose to decentralise the process, as is the case in reality, using various mathematical models for each activity. So we want to run all three units together and study the coordination mechanisms that link those three units to meet the customer needs. Three order acceptance policies are highlighted and tested: Stock (we accept the order if it is in stock), ATP (we accept the order if the inventories taking into account the production to the delivery due date are sufficient) and CTP (we modify the plan to include the new order without compromising previous commitments). The simulation horizon is two years; each day is divided into two seven-hour production shifts. The planning horizon is four weeks and the replanning frequency is one week. The demand lead time, which is the time between the reception date of the order and the delivery due date is fixed by a triangular distribution (1,2,3). Moreover, there is no stochastic event during production, the raw material is infinite and no delay is tolerated. A warmup period of a year was set to reach the steady state. More than 300 scenarios are tested with a sufficient number of replications for a significant confidence interval (95%). Number of accepted orders, average finished goods inventory, average sawn and planed products inventories have been used as performance indicators to measure the company's performance. The same optimisation model used in Dumetz et al. (2016) for the centralised model was used to generate the production plan at the finishing operation. A model was developed for the sawing operation and is based on the finishing operation model. It provides a period-byperiod production plan taking into account the raw material supply, the capacity, and the cutting patterns. The drying model comes from [START_REF] Marier | Kiln Drying Operation Scheduling with Dynamic Composition of Loading Patterns[END_REF]. This is an MIP/constraint hybrid planning model that dynamically generates load patterns during the planning.

The scenarios that are tested allow us to show the performance of the company in terms of accepted orders and average inventory for various order acceptance policies, different coordination mechanisms taking into account the context market and the parameters of the company. Coordination mechanisms are explained the next section.

COORDINATION MECHANISMS

Each scenario highlights different coordination mechanisms that are described in this section. We wanted to be able to accurately represent the production process of a North American sawmill at the operational level. Figure 2 below shows the first basic coordination mechanism.

Figure 2: Classical push system Here, the flow is 100% pushed: the raw material supply enables the production of sawn products (1), which will be dried (2) and planed (3). Customer needs are ignored and each unit operates independently maximising its production. Only commitments are counted to avoid order delays. This simple coordination mechanism is tested for Stock and ATP policies. For ATP policy, a frozen period ensures compliance commitments. Naturally it was more efficient to adopt a policy based on the ATP rather than stock. Using ATP policy, the company can accept 5% more orders than Stock policy depending on the demand intensity. Moreover, the average inventory using ATP policy is 80% less than Stock policy depending of the demand intensity. In addition, the durationof the frozen horizon to ensure that no order will be late is essential. This means coordination ensures the balance between the three activities.

Two-Phase Planning (Figure 3) This mechanism resulting from [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] allows taking into account the demand at the finishing operation, the needs of dried products for the drying operation and the needs of sawn products for the sawing operation.

Figure 3: Two-phase Planning A first phase plans each activity (1 and 2) considering infinite supply. Then real planning is done for the sawing operation (3), the drying operation (4) and the finishing operation (5) considering finite supply.

Bottleneck-first Planning (Figure 4) This mechanism is also from [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] and allows taking into account the demand for drying, which is the bottleneck of the process. The demand for planed products s directly passed to the drying operation. A first phase plans the drying operation considering infinite supply (1). Then a real planning phase is made for the sawing operation (2), the drying operation (3) and the finishing operation (4) considering a finite supply. This mechanism has been tested by [START_REF] Gaudreault | Distributed operations planning in the lumber supply chain: models and coordination[END_REF] and has shown better performance over previous mechanisms. However, we want to test this mechanism in a rolling period taking into account the market context of the company.

Those two last types of mechanism are used with the CTP, where we try to include each new order without compromising previous commitments.

EXPERIMENTS

As a base case, we considered results obtained when using a centralised planning algorithm. Planning sawing, drying and finishing operations at the same time using a single model is impossible in practice, but here we are able to do it in a research context using toy datasets. Indeed, in previous work, CTP were used in a centralised manner (Dumetz et al. (2016)). The performance of this type of order acceptance policy in a centralised context was clearly superior to other order acceptance policies depending on the market context and the demand intensity. Figure 5 below shows the results and the performances of both ATP and CTP policies for the same market context. It shows the number of accepted orders according to the demand intensity. We recall that the demand intensity is the number of orders the company received in one year. It is a percentage of the maximal production capacity. CTP accepts more orders than ATP when the demand is low because only CTP can reschedule the production according to customer needs. However, when demand intensity reaches 125%, ATP outperforms CTP because demand is significant and all the production planned can be sold. With a CTP policy, the production processes are modified to suit the recent orders. However, by changing the manufacturing process used, the co-products produced change too, and it could be hard to sell them.

Drying

Finishing operation sawing But what would the performances of the company be using a decentralised planning under a CTP approach? First, let's recall that CTP supposes we are able to tentatively re-plan production in reaction to a new order (with the constraint that we still need to satisfy past engagements). Although it is easy in a centralised context, our first simulation results quickly illustrated that the coordination mechanism described in previous section (two-phase planning and bottleneck first), when implemented "as is"cannot provide that. The business units were never (rarely) able to generate a new plan satisfying new orders without putting past orders late. Indeed, given the combinatorial nature of the problem, accepting an order by modifying the plan of sawing, drying and finishing operations without compromising past commitments became impossible.The production change causes changes in production for the next unit and so on: at each cutting pattern change, each recipe change at the drying or finishing operations, and the company performance varied considerably. The performance of a decentralised CTP is therefore below the centralised CTP performance of our previous experiments.

Following these preliminary results, we set up a decoupling point before the finishing operations. Using CTP, this allows making a new finishing operation plan to try to include the new order without compromising the previous commitments. We need enough replications to obtain a significant confidence interval (95%), we need to run around 300 simulations, each replication starts 1:30 hours of computation time.These new scenarios are currently running and the results will be soon analysed

CONCLUSION

In this research, the simulation framework developed by Dumetz et al. (2016) was used to simulate the wood planning process at the operational level in a decentralised manner. We took into account the market context and the production parameters of the company. Scenarios are still being simulated and if the paper is accepted we will show them in a revised version. But we can show that it is very difficult to obtain good performance in a decentralised environment facing a divergent process with co-production. Even if each activity uses an optimisation model to plan its production. This is due, among other things, to the combinatorial nature of the problem, as well as mathematical models; although they are extremely useful when planning a single unit or in a centralised manner. In a future work, a tactical level will be integrated and horizontal coordination mechanisms will be highlighted. The framework will be used to perform a more complex study by integrating stochastic events in the demand and the production.

Figure 1 :

 1 Figure 1: Conceptual representation of the framework

Figure 4 :

 4 Figure 4: Bottleneck-first Planning

Figure 5 :

 5 Figure 5: Number of accepted orders according to the demand intensity (ATP and CTP order acceptance policies) [Adapted from Dumetz et al. (2016)]

ACKNOWLEDGMENTS

We would like to thank the research consortium FORAC and its partners, as well as the financial support from CRSNG.


Albert Cohen

Valentin Perrelle

Dumitru Potop-Butucaru

Marc Pouzet

Elie Soubiran

Zhen Zhang

Hard Real Time and Mixed Time Criticality on Off-The-Shelf Embedded Multi-Cores

Keywords: Mixed criticalities, Multi-core, Embedded realtime system, Synchronous Language, Time-triggered execution

The paper describes a pragmatic solution to the parallel execution of hard real-time tasks on off-the-shelf embedded multiprocessors. We propose a simple timing isolation protocol allowing computational tasks to communicate with hard real-time ones. Excellent parallel resource utilization can be achieved while preserving timing compositionality. An extension to a synchronous language enables the correct-by-construction compilation to efficient parallel code. We do not explicitly address certification issues at this stage, yet our approach is designed to enable full system certification at the highest safety standards, such as SIL 4 in IEC 61508 or DAL A in DO-178B.

I. INTRODUCTION

This paper presents the design of a synchronous language enabling hard real-time applications to run on off-the-shelf multi-core platforms. 1 The language and methodology ensure the isolation of time-critical tasks from the non-time-critical ones under the following three hypotheses:

1) most of the computational load takes place in non-timecritical tasks; 2) it is possible to program the reaction to the absence of timely data, when non-time-critical tasks are delayed; 3) the target multiprocessor provides means to strictly prioritize memory accesses of one or more processors executing time-critical tasks, or to fully isolate such accesses into a scratch-pad memory; and the target also supports asymmetric multiprocessing (e.g., bare-metal execution on one core and Linux on another). We illustrate our approach and validate it on a train signaling use case provided by Alstom Transport. It is representative of the complexity in terms of vital/non-vital code interweaving, operational performance and availability constraints. The system function is called "Passenger Exchange" (PE). This function takes control of the train when safely docked at a station; it organizes the exchange of passengers (train and station doors opening/closing) while protecting them from any untimely train movement or non-aligned doors opening, and finally gives the departure authorization when all safety conditions are met. The functional specification is made of more than 300 requirements (natural language and SysML), and the system function is composed of about twenty subfunctions.

The PE application is partitioned into tasks, some of them being safety-critical and hard real-time, and some of them being mission-critical but non-vital. These tasks expose input and output signals and may result from the compilation of a synchronous block-diagram language. Unlike most related work on mixed criticality [START_REF] Burns | Mixed criticality systems-a review[END_REF], dependences and communication among tasks of different criticality are allowed. There is a simple reason why we can afford such a breach of criticality partitions: our approach composes tasks of different timecriticalities, without relaxing any other validation requirement. In other words, all tasks may still be certified at the highest (relevant) level of safety, but we acknowledge that only a subset of the tasks needs to be time-predictable and validated against real-time constraints. Let us discuss this hypothesis on the PE application. The computation of the doors that are safe to open (e.g., because they are not aligned) is safety-critical, as well as the task preventing train departure if safety conditions are not met (e.g. the doors are open or opening). Less vital tasks are in charge of operating doors with respect to the mission and to a time table; these are still mission-critical since the quality of service depends on the rare occurrence of timeouts. In this example we identify two occurrences of mission-critical to safety-critical communication. First, in order to ensure that door commands (mission-critical) do not lead to an accident, they must be checked against the enabled set of doors (safetycritical). Second, the departure authorization (safety-critical) must be computed regarding door commands to ensure that no opening commands will be executed after the authorization has been given. Such communication patterns are quite common in the case study.

In this paper, we will be using a modified version of the PE application. These modifications decouple computational aspects of the original safety-critical components. These computational tasks are amenable to parallelization and aggressive optimization, while satisfying a relaxed set of soft real time constraints. As a result, a safety critical component is split into a non-time-critical and a time-critical task, both of them being certified at the highest levels of safety. On the other hand, several less critical components with no connection to safety critical tasks have been coalesced for didactic reasons.

In the following, we focus on the validation of the hard real time requirements of the time-critical components of the system. The difficulty being that interferences on shared buses and caches of conventional multicores make it impossible in general to establish a practically useful worst-case execution time of a given task [START_REF] Pyka | A real-time capable coherent data cache for multicores[END_REF]. Our goal is to design a software stack and composition methodology enabling hard real-time control code to be isolated from timing interference, while exploiting parallelism among non-time-critical tasks, and still allowing for communications between the two. To solve this apparently paradoxical and infeasible set of constraints, our language provides an automatic inference mechanism for "late" communications between time-criticality levels. Time compositionality may be implemented through mode changes, and introduced incrementally into existing design and validation flows.

II. STATE OF THE ART

Thread-level parallelism has become unavoidable in any area where performance matters. While specific designs are emerging that combine predictability and performancee.g. [START_REF] Pyka | A real-time capable coherent data cache for multicores[END_REF]-off-the-shelf multiprocessors designed for massmarket areas are not well suited to timing analysis. Indeed, it is necessary to establish strict bounds on the worst case execution time (WCET) to address the time-predicability requirements of safety-critical systems [START_REF] Wilhelm | Embedded systems: many cores -many problems[END_REF]. If contention of shared resources can not be avoided, the complexity and imprecision of these techniques worsens dramatically. A survey of these researches can be found in a recent paper [START_REF] Fernandez | Contention in Multicore Hardware Shared Resources: Understanding of the State of the Art[END_REF]. Our approach is not to improve timing analyses themselves, but to make those more effective by controlling how the system is designed, from specification to code generation. We also hope to reduce the reliance on timing analysis on large parts of its code: ideally, most of the software components would not need a fully safe worst-case execution time characterization, even though the full system remains globally time-predictable and provably safe.

We are interested in mass-market commercial off-the-shelf (COTS) platforms, but we believe our approach will also be applied to more predictable classes of multiprocessors, such as the Kalray MPPA [START_REF] Kalray | Kalray MPPA R -256 integrated manycore processor[END_REF], [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF], increasing resource efficiency. Such extensions are left for future work. Numerous hardware components impact WCET analysis on multiprocessors [START_REF] Dasari | Identifying the sources of unpredictability in cots-based multicore systems[END_REF], such as shared caches and shared busses, etc. The main solutions attempt to reduce the general problem to a composition of sequential WCET analyses, enforcing a strict isolation at all levels of the memory hierarchy. For example, softwarecache partitioning has been realized for ARM Cortex A9 [START_REF] Ward | Making shared caches more predictable on multicore platforms[END_REF], and other approaches using scratch-pad and multi-ported memories are also possible. Our proposal builds on these ideas to implement spatial and temporal partitioning.

Our proposal was also inspired by the Logical Execution Time (LET) paradigm [START_REF] Kirsch | Advances in Real-Time Systems, chapter The Logical Execution Time Paradigm[END_REF] where the correctness of the system relies on observable input and output times independently of the actual execution time of the system's components. We extend LET with communications across time-criticality partitions, introducing a new protocol for tightly controlling timing isolation. We also leverage the multiple levels of timecriticality in real-world safety-critical applications to relax the timing isolation of parts of the system, improving overall efficiency and reducing certification costs without jeopardizing the safety of the full system. This approach has also been applied to Automotive control applications, but without enforcing hard timing isolation and compositionality [START_REF] Claraz | Introducing multi-core at automotive engine systems[END_REF].

Finally, when compared with the state of the art in mixedcriticality real-time scheduling, our paper proposes a totally different approach. Isolation between low-criticality and highcriticality components is ensured not only temporally, but also functionally, by means of language design and code generation. This approach is fully complementary to the mixedcriticality task models proposed in the real-time scheduling community. As such, it could be a contribution towards aligning academic work on mixed-criticality systems with the notion of mixed criticality introduced in industry standards [START_REF] Esper | How realistic is the mixed-criticality real-time system model?[END_REF].

III. A MIXED-TIME-CRITICAL SYNCHRONOUS LANGUAGE

We designed a simple mixed-time-critical extension of an existing synchronous dataflow language: HEPTAGON [START_REF] Gérard | A Modular Memory Optimization for Synchronous Data-Flow Languages. Application to Arrays in a Lustre Compiler[END_REF]. 2It is a research language and compiler with a LUSTRElike syntax, analogous to the textual language of SCADE SUITE. 3 HEPTAGON features state of the art constructs such as finite state machines and functional arrays with in-place operations. Its compiler implements a clock calculus upon which the generation of efficient embedded code is built, 4 and a number of optimizations to reduce control flow and memory management overhead.

The original PE application has been completely implemented in HEPTAGON, with only low-level I/O and system calls implemented in C. This choice allowed to faithfully implement the original specification, facilitating the application of formal methods or manual certification procedures. Although using mainly a natural language, the specification describes the functions to be implemented in an equational way which suits easily a dataflow language. HEPTAGON has been used to describe the tasks themselves as well as the target-specific code which describes how tasks communicate. We were also able to compile and test the different components early, then proceed with their integration and static scheduling, preserving timing isolation in a compositional way. In later development and validation stages, the tasks have been identified and mapped to specific processors, scheduled and executed in separation, with no functional changes to the program and reusing its high-level communication code. The detailed presentation and discussion of the parallelization and distribution features is out of the scope of the paper (some of the principles can be found in Gérard et al. [START_REF] Cohen | Programming parallelism with futures in lustre[END_REF] and Delaval et al. [START_REF] Delaval | A type system for the automatic distribution of higher-order synchronous dataflow programs[END_REF]). Instead, we outline the proposed extensions to HEPTAGON, and in particular how to programmatically control what happens when a task misses its deadline. For this purpose, we extend our language with the notion of "tasks" and "punctuality".

A task is defined as a dataflow node which is the smallest partition of the synchronous program after static scheduling and code generation. Tasks may then be amenable to dynamic or time-triggered scheduling. A task is a reactive program, a property inherited from HEPTAGON nodes: it activates repeatedly in response to a signal, its inputs need to be present before it activates (dataflow semantics) and the task's outputs are present after it terminates its reaction. After the beginning of the task and before its end, the task does not communicate with any other task. It is the programmer's duty to choose which dataflow nodes in the node instantiation tree will be tasks and thus to define the granularity at which the application is deployed on the target platform.

If ever a task were to be instantiated inside another task, the compiler would simply ignore this information and continue as if the task was a simple node. This does not guarantee time and space isolation across the "embedded" and "embedding" task, but we found it sufficient to ensure time and space isolation across top-level tasks in the system.

Note: the HEPTAGON language allows the programmer to declare "external" nodes and tasks which can be resolved at link time. This allows specific nodes to be written in plain C.

A task is called unpunctual if it is not time-critical. In this case, the task can miss its deadline. It may be left to run to completion, ignoring its outputs, or it may be killed or preempted by the system. When it happens, the outputs of the task are not present. To reflect this possibility, we say that the outputs of the task are also unpunctual. We extend the type system of HEPTAGON by assigning a punctuality to each variable and each task. Our language requires that the punctuality of the output variables is always the same as the punctuality of the task. These unpunctual values can be transmitted to other nodes. However, to exploit these values, the programmer must distinguish two cases: either the value has been computed on time or the unpunctual computation timed out and it is not available. The operator ontime takes an unpunctual variable argument and returns a boolean which evaluates to true when the variable can be read. In other words, the expression ontime v is the clock of the unpunctual variable v. This means that the merge operator-combining multiple flows with mutually exclusive clocks in HEPTAGON-can be used to build a punctual value by combining the actual value when present and a "default" value otherwise.

In many cases, the "default" value to be used in place of the actual value when a task missed its deadline is a static constant. This happens when there is a value which is always safe. For instance in our case, it is always safe that the component sends no commands or to considers that there is no door correspondence. The programmer can then give a default value to the unpunctual variable which will be used when the actual value is not available. When an unpunctual variable is set to its default value, its clock is the one of the node. (Or the one explicitly declared if it is different.) Sometimes, specifying a default value is not powerful enough. For instance, in Model Predictive Control (MPC), a more suitable reaction may be to repeat the command issued in the last cycle but following a suboptimal, faster prediction [START_REF] Wang | Fast model predictive control using online optimization[END_REF], [START_REF] Borrelli | Predictive control for linear and hybrid systems[END_REF].

IV. MIXED-TIME-CRITICAL FLOW AND PLATFORM

We review the tool flow and run-time support for the compilation and execution of synchronous programs with multiple levels of time criticality.

A. Compilation

The extensions to HEPTAGON require three main changes. 1) The task keyword is a synonym of node. It is supported as an annotation in the intermediate representation, which can then be read by the back-end to generate a scheduling table [START_REF] Cohen | Mixed-criticality in railway systems: A case study on signalling application[END_REF] or communication code.

2) The type system is extended with a punctuality property.

3) A transformation pass abstracts the punctuality information such that the resulting program have the same semantics but is lowered to conventional synchronous code without the mixed-time-criticality constructions. Further down, the usual compilation flow can be applied. We add a "punctuality" attribute to the type of expressions and variables. The type system verifies that variables assigned from an unpunctual task application are also unpunctual and that unpunctual variables may only be passed as argument when the corresponding parameter is also unpunctual. The new construct ontime is always typed as boolean.

The additional transformation pass uses clocks to represent the punctuality. Each unpunctual variable is split into two variables: one is a boolean signal representing whether the value has been computed on time or not, the other is the actual value which is only defined on the former clock. The ontime v expression for any variable v is translated to either true if the variable v is punctual or to the clock of v otherwise.

A task with an unpunctual parameter is split the same way. HEPTAGON allows one parameter to be the clock of another and thus supports this construction.

When a default value is provided for an unpunctual variable, the real value is selected when present, and the default one otherwise; it corresponds to the merge construct in HEPTAGON.

The clock variable for each unpunctual variable needs an input from the system telling whether the task generating the encapsulated value has completed on time or not. We introduce for each task call a fresh abstract function which provides this information. It is the responsibility of the back-end to stub these functions appropriately.

It is worth noting that by relaxing the type system to be a bit more lenient on unpunctual arguments we could have allowed interesting constructions, at the cost of additional compilation efforts: since unpunctual tasks are not time-critical, it should be possible to execute them one after another, waiting for the previous task to terminate normally without killing it when 1. Simplified implementation of a safety-critical function which ensures that there are no command for a train or platform door which is not aligned with a corresponding platform or train door, respectively. The door_map array provides a valid description of which pairs of doors are aligned, and the door_commands is the array of commands computed for each door. The latter is unpunctual as it results from a best-effort computation in a mission-critical task; when commands are not computed in time, it is always safe for the passenger that the doors receive no commands. a deadline is missed. At worst, the unpunctual task missing its deadline could be preempted to ensure it does not use resources (CPU, memory, etc.) which belong to any timecritical task. Thus depending on the criticality of a task, the behavior to follow when a data is not computed on time would not be the same. If the task is time-critical, we use the constructions introduced in this paper to program the temporary transition to a degraded mode. If the task is not time-critical then it can wait until its data are computed. This solution may accumulate delay if multiple tasks miss their deadline or the delay of a task can be compensated by another. For this purpose, we could have allowed unpunctual arguments to be passed to unpunctual tasks without declaring them as unpunctual, but this would involve heavier changes in the type system.

B. Distribution and parallel code generation

At this stage of our research, the code generation procedure is only partially implemented and thus semi-automatic.

Like in LUSTRE, a HEPTAGON program can be seen as a dataflow graph where vertices are operators or instances of other nodes. A program is defined by its root node. All nodes instanciated from a parent task node can be statically scheduled by the HEPTAGON compiler into a single step function. Calls to the node's internal operators and child nodes may even be inlined if desirable. 5 After the program has been compiled, we obtain a dataflow graph whose vertices are tasks and whose edges are communications between these tasks.

In our case study, most dataflow operators are copies of outputs of one task to the input of another, or field selection where a subset of the data is being copied. Other operators, such as arithmetic ones, are also encapsulated into tasks. The punctuality of an encapsulating task is completely determined by the type system which imposes that the operands and the result of an operators must have the same punctuality.

In summary, the first transformation pass produces a dataflow graph where, after inlining and encapsulation, all 5 Recursion is forbidden.

vertices are tasks and where edges are communications. These tasks must then be allocated and scheduled. Although the HEPTAGON compiler has its own scheduler, it is intended for pure sequential scheduling and for a totally different optimisation goal. Thus, our approach relies on the existence of external tools to allocate and schedule tasks. These tools must take into account the cost of communications as well as the individual execution cost of tasks. For instance, we have implemented a back-end for the LOPHT [START_REF] Carle | From dataflow specification to multiprocessor partitioned time-triggered real-time implementation[END_REF] scheduler: this back-end allow us to feed the scheduler with the list of tasks, data dependencies, clocks and constraints. LOPHT then produces a scheduling table for all these tasks. [START_REF] Cohen | Mixed-criticality in railway systems: A case study on signalling application[END_REF].

Basically, the allocator gives a color to each vertex in the dataflow graph while the scheduler gives a topological order to those vertices. In our framework, allocation just splits punctual and unpunctual tasks. For each computation resource-i.e. for each color in the dataflow graph-one may generate sequential code. This code calls each task in the order given by the scheduler. When the input of a task is produced by another task on the same computation resource, a simple data copy takes place. When the two tasks are allocated in different computation resources, the generated code uses the communication protocol described in the next section.

C. Partitioning and time-triggered communication protocol

Systems with mixed time-criticalities require a strong assurance on the worst case execution time (WCET) of most safety critical tasks. However this is almost impossible to achieve without temporal and spatial partitioning, due to the shared resources of conventional multi-cores [START_REF] Pyka | A real-time capable coherent data cache for multicores[END_REF]. Concretely, concurrent accesses on shared resources, such as a shared L2 cache or a shared scratch-pad memory bank, result in contentions, which prohibit timing analysis at the system level. Building on partitioning techniques, we propose a time-triggered communication protocol to realize contentionavoidance and timing isolation.

A strict spatial partitioning requires independent physical memory and computing units. This is for two reasons: first, to keep the register and memory context of safety-critical tasks away from malware or bugs; second, to avoid concurrent accesses on shared resources, including instruction caches. Such spatial partitioning can be achieved on off-the-shelf hardware platforms, such as the Zynq 7K [START_REF]Xilinx. Zynq-7000 all programmable SoC[END_REF]. It integrates an ARM MPcore (Dual Cortex-A9) and a FPGA permitting asymmetric multiprocessing (AMP) configurations. Each ARM core can run its own software stack, set up separately in the shared DDR or on chip memory (OCM). Precise timers and bus arbitration policies can also be controlled. Moreover, building on the embedded FPGA, a variety of memory and computing units can be implemented, e.g., for communication buffers, and for controlling external I/O. Therefore the time-critical and non-time-critical tasks can be fully isolated on the physical platform. This does come with a significant cost however, as communications and DDR accesses from the time-critical level must be temporally isolated from any other activity. Such temporal isolation may dramatically reduce the effective parallelism available in the program. In particular, to the best of our knowledge, it is not possible to execute two timepredictable tasks in parallel on such a platform.

Our time-triggered communication protocol aims at realizing sufficient temporal partitioning without destroying the potential for parallel execution. This protocol controls not only shared communication buffers by building access time frame and deadline in order to avoid contentions. But it can also tolerate timeout events in order to avoid delaying the timecritical functions by non-time-critical ones. And it achieves this inspite of the presence of communications between the two levels.

In this protocol, each task is split into phases falling in one of six classes:

• time-critical computing (TCCP),

• time-critical copy to buffer (TCTB),

• time-critical copy from buffer (TCFB),

• non-time-critical computing (NTCCP),

• non-time-critical copy to buffer (NTCTB), and • non-time-critical copy from buffer (NTCFB).

To set the execution deadlines, we rely on a supplied WCET for each of these phases. Fig. 2 shows a sample chronogram of the time-triggered protocol. In this simple example, there are two parallel execution chains, one for safety-time critical tasks, another for mission critical ones, they are executed in parallel on different CPUs.

Phase I: On the time-critical level, at the end of the date T 0 that is the deadline of previous function, the TCTB function is executed to copy the data to buffer. Its WCET W 0 is used to define its deadline T 1 (T 1 = T 0 + W 0).

On the non-time-critical level, T 1 is the deadline for the previous functions. It should be noted that this deadline is not a hard one: late events are tolerated.

Phase II: The NTCFB function of the non-time-critical level transfers the data from the buffer at date T 1. Then the NTCCP function deals with the data and generates the output results. Finally the NTCTB function transfers the data to the buffer. The sum of WCETs Y 0 + Y 1 + Y 2 of NTCFB, NTCCP and NTCTB is used to define the date of T 2. The temporal gap between T 1 and T 2 can be filled by other TCCP functions according to the task scheduling strategy. The WCET value W 1 should be less than T 2 -T 1.

Phase III: The TCFB function copies the data from the buffer when the data is ready, if no timeout takes place. Otherwise the late event is handled appropriately by the second TCCP task. The maximal WCET value of LCFB and of the backup function defines the deadline date T 3.

In fact, if missing a deadline on an unpunctual communication is harmless, a default value may be enough to react to the timeout event. Otherwise, a more evolved backup function is needed, and its WCET needs to be accounted for at design time, to set up the timeout accordingly. On the other hand, if a timeout should be considered as a fault, the approach is not applicable and the task should not be considered as non-timecritical; fail-safe or degraded mode transitions, or fault-tolerant approaches might be considered.

It should be noted that, not only a communication from non-time-critical to time-critical, but also time-unpredictable communications between two time-critical tasks or two parallel time-critical execution chains (operating in parallel on two different CPUs) may be unpunctual. This feature makes the protocol suitable for network-on-chip (NoC) systems, such as the Kalray MPPA manycore processor [START_REF] Kalray | Kalray MPPA R -256 integrated manycore processor[END_REF]. On such a chip, time-critical tasks can executed in parallel in the different clusters, while implementing unpunctual communication between clusters to reduce overhead and certification cost.

V. VALIDATION

As mentioned above, the PE application is coded according to its original functional specification. This specification, written in SysML, details functional and behavioral aspects, risk levels (vital or non-vital), the component architecture, communications and interfaces. We split the vital functions into time critical and non-time critical ones according to their timing requirements, but any atomic behavior is not broken down.

Although the PE application is a reasonably simple use case, it has more than 300 functional and behavioral requirements already: it is a representative industrial SIL (Safety Integrity Level) application. Many other application areas combine the needs for computational components in the loop of safetycritical control. From engine control to monitoring, control engineers need computational tasks in order to improve trajectories, leading to resource optimization, emission reductions, longer maintenance cycles, etc. Model-predictive control (MPC) is one of the best representatives of such computational control applications. 6 Its applicability to real-time systems has so far been limited by its time impredictability [START_REF] Zeilinger | On real-time robust model predictive control[END_REF], making it a prime candidate for mixed-time-critical execution.

Fig. 3 presents a simplified dataflow graph of the PE application. The following safety requirements must be met by time-critical tasks: 2) if the train is not immobilized, doors cannot be opened;

3) doors must be closed to allow the train to depart. The non-time-critical part sets three other requirements:

1) open/close commands are issued according to the mission; 2) inform passengers of an imminent opening/closing; 3) send warnings to the traffic supervision when the passenger exchange cannot be completed. These last three requirements are handled by two non-timecritical functions. The first one computes a mapping from train doors to platform doors and vice versa, such that matching doors are physically aligned. The second one uses this mapping to compute commands to be sent to the doors according to the current mission.

To meet the safety requirements, these commands must be checked. If a command breaks one of the requirements, it is canceled: it is always safe, according to these requirements to send no commands. This check relies on three timecritical functions. First, the physical position of the platform doors is retrieved. Then, the door mapping computed by the corresponding mission-critical function is checked using these physical positions and the current train position. Finally, the commands are checked against this mapping and information about the train docking state. The last requirement is ensured by a fourth function which issues a departure authorization when no commands have been sent for the last few seconds.

The application also has a non-critical logging function which records the commands history.

We show in Listing 1 the HEPTAGON source code, declaring two unpunctual variables, door map and door commands. The generated C code is presented in Listing 2. Two functions are generated, for the time-critical code and one for the nontime-critical code, respectively. The communication functions send and receive have the same parameters: an identifier for the channel buffer, the address and the size of the payload, and the time-criticality of the sender or receiver. The result of the receive function is a boolean which indicates whether the communication has been done on time or a timeout has occurred. This boolean can only be false when communicating from a non-time-critcical task to a time-critical one. The communication mechanism is illustrated on a custom system configuration and platform in the next subsection.

A. Hardware/software implementation

We selected an off-the-shelf hardware platform, the Zynq 7K SoC ZedBoard [START_REF] Zedboard | [END_REF] as our experimental target. It provides a pair of ARM cores and a FPGA. This flexible platform is very popular in mixed critical execution environments and in hardware-software codesign. In this paper, we leverage the ARM cores for their flexibility and performance on typical software stacks, and rely on the FPGA only for configuring the local memory and bus interfaces, and for implementing communication buffers.

As mentioned in Section IV-C, our first goal is to realize a strict spatial partitioning on the Zynq 7K. This is achieved through asymmetric multi-processing (AMP). The Zynq 7K permits at least two kinds of AMP configurations [START_REF]Xilinx. Xilinx Zynq multi-os support (AMP & hypervisor)[END_REF], between two ARM cores and between ARM and FPGA based soft-cores. We selected the ARM core-only AMP configuration to suit our performance-driven implementation strategy:

• ARM core 1 executes the time-critical tasks in a baremetal environment. The software stack is allocated on bool * departure_authorization) { int platform, door_map [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF], safe_door_map [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]; command door_commands [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]; bool ontime1, ontime2; get_platform(train_position, &platform); send(0, &platform, sizeof(int), TC); ontime1 = receive(1, door_map, sizeof(int) * 8, TC); check_door_map(ontime1, door_map, safe_door_map); ontime2 = receive(2, door_commands, sizeof(command) * 8, TC); check_commands(ontime2, door_commands, safe_door_map, safe_door_commands); check_departure_conditions(safe_door_commands, departure_authorization); } void passenger_exchange_ntc() { int platform, door_map [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]; command door_commands [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]; receive(0, &platform, sizeof(int), NTC); compute_door_map(platform, door_map); send(1, door_map, sizeof(int) * 8, NTC); compute_commands(door_map, door_commands); send(2, door_commands, sizeof(command) * 8, NTC); } the on chip memory (OCM) of 256KB (code and data).

• ARM core 0 executes the non-time-critical and noncritical tasks in a Linux environment: Petalinux [START_REF]Xilinx. PetaLinux tools[END_REF]. The software stack is allocated on the DDR (512MB). • The communication buffers are implemented on the FPGA. Figure 4 details the hardware IPs used in the Vivado tool chain [START_REF]Xilinx. Vivado design suite[END_REF] for our system configuration.

a) Processing system7 0: is the IP used to configure a couple of ARM codes. We use almost all default configuration values. It should be noticed that, CPU0 uses both L1 and L2 caches, but CPU1 uses only the L1 cache, in order to avoid concurrent access on the shared L2. The communication buffers on the FPGA are not cached.

b) Proc sys reset 0: is the IP used to reset FPGA components controlling by the Processing System. c) Axi mem intercon: is the interconnection IP used to connect the AXI master components with the AXI slave ones. This is a 1 → 3 crossbar as there are one master (processing element) and three slave components: memory block, ZedBoard LEDs and switch GPIO. The latter two interfaces are used during PE application timeout injection and functional test.

d) MEM: is a block memory wrapper containing two IPs, one for the AXI BRAM controller and the other one for a block memory generator. In our implementation, we realize a 32KB memory buffer.

The resource utilization metrics are presented in the table below. Only a small fraction of the FPGA is used.

On the ARM Core1, tasks are time triggered relying on a snoop control unit (SCU) 32 bits local timer. We experimented with two ways to configure the timer: a fixed frequency static value and a dynamic value derived from to executing task's WCET. Both of them were tested successfully.

As the ZedBoard Zynq 7K SoC can operate at 666 MHz, we can set up a static timer reaching a relatively high frequency such as 100 KHz, 500 KHz or even 1 MHz, to accomodate multiperiodic schedules and a wide diversity of task WCET. A "jiffies" counter is used to hold the number of time ticks that have occurred since a task was initiated. At the end of the task, a comparison between the expected WCET and the measured jiffies allows to determine if the deadline was reached. 7 If it did, the next task executes and the jiffies counter is reset to zero. Otherwise, a loop spins until the expected deadline. When using a dynamic timer, it is defined according to the WCET of the operating task, with a "deadline" variable set to detect to the WCET. The rest proceeds identically as with a static counter. The dynamic scheme requires slightly more code generation effort but it saves CPU resources, saving the need to handle intermediate interrupts. For example in the PE application, the task's largest WCET is 120× the shortest WCET, which means at least 120 timer interrupts can be saved using a dynamic timer.

On the ARM Core0, we did not yet realize time-triggered execution on Linux, but enter a spin loop instead to check if the data is ready. To avoid interferences on the communication buffer due to round robin arbitration, we have to time-isolate the non-time-critical side of the communication as well, which doubles the WCET of the corresponding communication function. This overhead is very lightweight as the communication function has a low cost compared with other components.

The chronogram of the execution is illustrated in Fig. 6; 8 the digits correspond to the following tasks: (1) Get Platform, 7 We do not attempt to deal with missed deadlines on time-critical tasks, which should be handled as critical faults at another level (e.g., a degraded mode of operation). 8 The lengths are not on (timing) scale.

(2) Compute Door Map, (3) Check Door Map, (4) Compute Commands, (5) Check Commands, ( 6) Check Departure Conditions, (7) Logging Utility.

As we just presented, the time-critical communication function A runs in parallel with the spin loop, effectively wasting parallel computing resources for a short time period. On the other hand, for most of the execution, functions (3) and ( 4) run in parallel, showing the benefit of our mixed time-critical design. More complex applications and scalable platforms would make even more effective use of the approach. Listing 3 details the language C structure dedicated to unpunctual communications. This structure contains five fields, ready signals that a communication packet is ready, timeout informs about missing packets when reaching a timeout, cycle count stores the packet's logical instance cycle (a.k.a. period), payload wraps the packet data and size represents the size of the payload. We use the "C" and "D" communications of Figure 6 to explain this C implementation.

As shown in the Figure 7, we declare a sender variable C (type of communication t) on the non-time-critical side, and a receiver variable D (type of communication t) on the timecritical side.

e) The ready fields: of C and D point to a 32 bits physical address allocated on the FPGA Mem Buffer-0x40000000. The sender variable C produces the ready signal, it enables ready once the packet payload has been copied to the buffer, i.e., when the packet is ready for the receiver. The "ontime" operator is implemented by checking the ready field at the receiver side when the deadline date is reached. If ready is not enabled, a timeout occurs. The receiver should execute a backup function.

f) The timeout fields: of C and D point to the following 32 bits physical address-0x40000004. The receiver variable D produces the timeout signal, it enables timeout when the deadline date T3 is reached and packet payload is not yet ready. That is to say, when the packet timeout occurs. The sender variable C is the consumer; when it seens an enabled timeout, it aborts the current packet transmission.

g) The cycle count fields: of C and D point to the next 32 bits physical address-0x40000008. The sender variable C is the producer, the cycle count of the non-time-critical task is sent to the receiver. If it is different from the receivers', a fullcycle delay accumulation occured. That means the sender and the receiver have lost their synchronous association, which is a more severe situation, but still one that the protocol aims to tolerate. It may happen it the non-time-critical task is seriously delayed due to a chaotic accumulation of interferences. In such a case, the simplest approach would be to skip the upcoming instances of the non-time-critical task(s) until the synchrony of the cycle counts can be restored. Optimized methods to handle such severe and accumulated delays are outside the scope of this paper, but the reader interested in advanced strategies may refer to [START_REF] Erickson | Recovering from overload in multicore mixed-criticality systems[END_REF].

h) The payload fields: of C and D point to the following 32 bits physical address-0x4000000C. To preserve timing isolation, the packet's contents is first copied from the sender to the buffer, then from the buffer to the receiver.

The memory overhead of our time-triggered communication protocol are is limited to the additional communication variables (cycle count, timeout and ready). On the PE application, only 6 such variables are needed to implement the (two) crosstime-criticality communications.

B. Early experiments

Our first experimental validation was to test the mixed-timecritical version of PE application with its original functional self-test, which takes the form of a set of scenario simulations. This test was passed successfully, which proved that the timetriggered protocol does not change the PE function.

Next, we replayed the functional test with an additional timeout injection hazard. We did not change the test scenarios, but inserted controllable delays in the functions (2) Compute Door Map and (4) Compute Commands. Practically, these delays took the form of simple device I/O on the Zync platform, checking if the corresponding ZedBoard switch is on. if yes, a random number of loop iterations were executed in order to simulate a non-predictable delay. If this induces a timeout, the backup function or default values are used, as implemented in the mixed-time-critical synchronous program. The trace of the PE application proved the absence of timing violations or incorrect commands on the time-critical tasks.

As noticed earlier, when a huge delay affects the function (2) or (4), delay accumulation may occur and the cycle count fields of the sender and receiver may differ. Our current implementation simply aborts the PE application by an exception for now, as an illustration of the self-diagnosis potential of the communication protocol. Of course, a complete implementation should skip some upcoming tasks and resynchronize accordingly instead.

VI. CONCLUSION

We presented an application where mixed criticality resides at the application level, or even at function level, rather than the system level. Moreover, all functions remain safety critical, and the different criticalities we consider are focused on timing predictability and requirements instead. Different time predictability requirements allowed us to expose parallelism and optimize resource utilization, compared to a much more conservative timing isolation of all components. We demonstrate the feasibility of hard real-time and parallel execution of safety-critical tasks on a conventional embedded multicore platform. A timing isolation protocol allows best-effort, functionally validated tasks to communicate with hard real-time ones, while (1) preserving timing compositionality, and (2) satisfying all hard real-time constraints in the complete application. To program and certify such applications, we proposed an extension to a synchronous language enabling correct-byconstruction code generation and parallel execution on a multiprocessor platform. Based on this experience, we advocate for a multidimensional approach to mixed criticality where timing constraints are managed separately from other system validation aspects. We also advocate for a holistic approach, where the design flow of complex control applications takes into account different levels of timing predictability: our proposal is one step towards the construction of such a flow. We encourage control engineers to detail the different admissible modes, limiting the extent of hard real-time components, and defining the hard real-time reactions to the late availability of non-time-critical data.

Figure 2 .

 2 Figure 2. Chronogram of ideal time-triggered communication protocol.

Figure 3 .

 3 Figure 3. PE application modeling graph.

Figure 4 .

 4 Figure 4. Hardware IPs (Vivado tool chain) used in our implementation.

Figure 5 .

 5 Figure 5. Mainly resource utilization ratio.

Figure 6 .

 6 Figure 6. Execution chronogram of PE application.

Figure 7 .

 7 Figure 7. Implementation of the "C" and "D" communication of Figure 6.

This work is supported by the Technological Research Institute (IRT) SystemX, partially funded by the French public program "Investissement d'Avenir". It is also partially funded by the EMC2 ECSEL and ITEA ASSUME projects.

See http://heptagon.gforge.inria.fr for documentation, source code and applications.

http://www.esterel-technologies.com/products/scade-suite.

Clocks can be seen as a type system for sequences of boolean conditions controlling the presence or the absence of values in stream variables, or the stepping of synchronous, stateful nodes in a process network.

http://www.mpc.berkeley.edu/mpc-course-material