Georges Habchi
email: habchi@esia.univ-savoie.fr

Claire Berchet
email: berchet@esia.univ-savoie.fr

SOME CONCEPTS FOR INDUSTRIAL CONTROL PROCESS MODELLING

After an introduction concerning today Firm evolution and the state of the art of industrial control and making decision, this paper first presents a classification of decision depending on production span, reactivity, application field and number of actors. Then, it introduces the methods (a priori, reactive, a posteriori) and the dimensions (hierarchy, space, time) of control. And last, it proposes some concepts for generic modelling of its process using "control centre", "local" and "global" structures.

INTRODUCTION

In Companies, it is important to examine the methods of anticipating and resolving problems, deciding and controlling physical, informational and decisional flows.

To study an integrated industrial control process, we must distinguish between the information acquisition and evaluation, the making-decision process, the act of deciding and the implementation of actions. Some authors [START_REF] Ecosip | Cohérence, pertinence et évaluation[END_REF] [9] [START_REF] Lemaître | La décision[END_REF] proposed models to formalise the making-decision process. But, this process changes with Companies evolution and management according to new concepts of Just-In-Time, Total Productive Management, Total Quality Management, continuous improvement, etc. Then, the process of control also must be adapted to this change and the industrial flows organised and synchronised with time. The control process must take into account external factors of environment and internal factors of organisation and technology. In the classical Taylor's model the action is based on a clear definition of roles and highly simplified tasks. Individual thinking and decision are minimised. The interpretation of problems and the decision about actions concern an actor endowed with a control capacity on the social system. A local interpretation and a local decision can not be practised. The process of decision based on the model of Simon [START_REF] Le | Les systèmes de décisions dans les organisations?[END_REF] is simple, linear and without interactions (problem analysis, elaboration of solutions, choice). This model supposes that the problem is perfectly defined, a complete information exists, all actors have the ability to manage this information and the consequence of alternatives may be known. Unfortunately, this model is utopian because the ability of actors is limited and leads to substitute satisfaction against maximisation. In present day Companies, skills and autonomy of actors increase giving them more responsibility. An action will result from a local interpretation and actors will be further requested to interpret their work. We pass from a centralised model to an integrated control model able to react to the internal and external evolution of systems. The works of Burns and Stalker [START_REF] Ecosip | Gestion Industrielle et Mesure Economique[END_REF] underline the fact that the performance of a structure depends on its capacity to anticipate the variation of its environment. In the next sections of this paper mainly we analyse the industrial control and present some concepts and formalisms for its process modelling.

INDUSTRIAL CONTROL

It is classic to decompose the Firm system into physical, informational and decisional sub-systems. The object of the decisional sub-system is to control the evolution of the physical sub-system via the informational sub-system considered as the nervous one [START_REF] Le | La théorie du Système Général[END_REF]. Prior to present the approach developed in this paper, we give next an analysis on decision classification and control methods.

Classification of Decision in Industrial Control

The literature situates the first important developments on decision theory during the Second World War, when some researches endeavoured to elaborate methods called by "operational research", to rationalise military and economic choices. According to this literature [START_REF] Barabel | Un style de décision à la française[END_REF] [3] [START_REF] Giard | Gestion de la Production[END_REF] [10] [11] [15] [16], we present the following typology of decision:  According to the production span, decision could be strategic, tactical or operational.  According to the reactivity, decision is event driving or periodic.  Decision depends on the application field and is economic, technological or human.  Decision depends on the number of actors and is individual or collective.

Approaches of Industrial Control

Whatever the organisation of Companies, the industrial control could be based on one or more of the following three different approaches:  The «a priori control» is a theoretical upstream approach based on objectives, models and tools of planning, scheduling, simulation... It poses fundamental problems if models are founded on assumptions noncoherent with the actual system.

 The «anticipated reactive control» is a preventive event driven approach applied in actual time to prevent risks and problems. It needs the use of tools as process performance indicators, control charts, preventive maintenance... to correct permanently controlled process trend or deviation.  The «a posteriori control» is a downstream corrective approach applied to correct residual risks and problems. It is more adapted to periodic control and could be used by the help of result performance indicators, corrective maintenance…

Dimensions of Industrial Control Process

The term of «Industry control» introduces voluntarily a comparison with some complex, rapid and heavy vehicles such as aircraft, missiles or ships. Controlling a vehicle corresponds to choosing an objective and defining the best trajectory according to it. Once the vehicle is launched, one must permanently correct its deviation against this trajectory. Then, eventually it must be envisaged to modify during functioning, the trajectory or even the objective, whether the information about the environment and about the behaviour of the vehicle shows that the original plan can not be maintained [START_REF] Avenier | Pilotage de l'entreprise et environnement complexe, une aide à la conception d'un pilotage plus effectif[END_REF]. Then, the control is a dynamic process built on the basis of several actions decided by different actors, at different times and points of the system. This implies that a system to be controlled it must have an organised structure and in movement. Consequently, the control process depends on the dimensions of hierarchy, depth and time:  The «hierarchical dimension» concerns decisions relevant to the hierarchical structure of the system. At a given time and according to this dimension, actors situated at different levels examine decisions. The decision and control level is a function depending on the objective and the complexity of problem. The coordination principle constitutes the basis of decision coherence between successive levels of the hierarchical structure [START_REF] Gallois | Intégration de la productique dans l'entreprise[END_REF] [START_REF] Giard | Du global au local: structure et coordination[END_REF].  The «depth or spatial dimension» concerns decisions relevant to the lateral structure of the vertical levels. At a given time and according to this dimension, actors situated at the same level examine decisions. The results of a decision act directly on lateral actors and horizontal propagation of the decision. The co-operation principle constitutes the basis of decision coherence between successive actors of the lateral structure.  The «temporal dimension» concerns decisions relevant to the behavioural dynamic evolution of the state of the system. At a given point of the system and at a given time a decision is different from a decision at an another time. An applied decision becomes irreversible with time. According to this dimension, decisions are dependent and some triggering events, some actions are susceptible to definitively call into question the strategic objectives of an organisation.

CONCEPTS FOR INDUSTRIAL CONTROL PROCESS MODELLING

In literature, the control process is limited to the lowest level of the industrial system and called "Production Activity Control" or "Shop Floor Control" [START_REF] Melnyk | Production Activity Control[END_REF]. On the other hand, decision is linked to the highest levels, it is a matter of strategic or tactic decisions for managers and a question of shop floor control for production actors. It is important to note that we are not faced to two-tier concepts. Decision is a part of the control process, which must be expanded to the whole corporate system. Very often, the system is analysed according to decisional levels, and a global analysis of physical, decisional and informational flows is not clear enough. The systemic approach is not adapted for an analysis considering the time factor. Then, we think that it is judicious to model the control according to a process approach, in which we consider the major role of time factor, hierarchy, space and internal and external risks.

To design and model the control process, we propose the following three concepts: global, local and control centre concepts. The global concept (fig. 1) situates the control process in its environment and proposes a structure based on its dimensions, the local concept (fig. 2) organises control process around its methods whereas the control centre represents the brain of control process. The complementarity between these concepts creates an integrated vision to build the whole control process.

Hierarchical dimension

Spatial dimension

Temporal dimension

Production flow Decisional flow "t" "t-1" "t+1"

Operational level

Co-ordination

Co-operation

Control centre

Functional levels

Evolution of the state of the system Environment Level i

Level i+1

Decisional flow

Fig. 1 -Global structure of industrial control process

The "a priori" approach is projected and defined according to structural information, orders, forecasts, management rules, routes and objectives.

The "a posteriori" approach is corrective, periodic and defined to correct periodic deviation of operational process and residual failures.

Controlled Process

The "anticipated reactive" approach is preventive, event driven, and defined to prevent permanently operational process deviation and risks, the knowledge of physical resources and customers is vital for its implementation.

Fig. 2 -Local structure of the industrial control process

The control centre is composed of the following components: actors (a), referents (R), objectives (O), rules (), actions (A), measures (m), resources (r).

We use the following notations to formalise the industrial control process:

-Control centre ) ; ; ; ; ; ; ( , , , , , , , , j i j i j i j i j i j i j i j i r m A O R a C C   (1)
Where i = hierarchical level, j = number of control centre at the same level -Objective of a control centre ) ( ,

, j i j i R O O  (2)
-Co-operation relation (at the same level i)

) ; ; ( 1 , 1 , , ,    j i j i j i cop cop C C R R j i, C (3)
-Co-ordination relation (between levels i-1, i and i+1) )

; ; ( , 1 , 1 , , j i j i j i cor cor C C R R    j i, C (4)
R R O m A A   (5)

CONCLUSION

This study shows how the process of industrial control is deeply linked to the change and mutation of systems. The design of industrial control process must be founded on significant analysis of this system, its evolution and its environment. The modelling of control process becomes more complex with the consideration of environment, time, risk factors and new management approaches. Then, we must have necessary experience and skills about the considered field and about situations needing frequent decisions. In order to consider industrial preoccupation, our research takes into account the numerous interconnections between actors and flows according to the dimensions we have fixed: hierarchical, temporal, and spatial. Considering time is a necessary condition for dynamic modelling and design of control process. With time advance the effects of an action could change. According to the proposed concepts, we focus our research on risk factors (breakdowns, scraps, lateness, uncertainty...) needing corrective or preventive decisions, whatever the level of the structure: operational, tactic or strategic. The existing researches on decision and the consideration of irreversibility allow us to consider the increasing complexity of the organisation on the proposed concepts. Modelling the system by a non-linear model calls into question traditional linear models. However, the proposed concepts must be refined and a generic model integrating the decision making process will be proposed to model the concept of control centre. Aggregation of results and decomposition of decisions and structural information must be considered to formalise both co-operation and co-ordination relations.


Qian Li
email: qian.l@stu.xjtu.edu.cn

Weiguo Wu
email: wgwu@mail.xjtu.edu.cn

Long Xu

Jianhang Huang

Mingxia Feng

A Statistics Based Prediction Method for Rendering Application

Keywords: Rendering, prediction, statistics, classification, render farm

As an interesting commercial application, rendering plays an important role in the field of animation and movie production. Generally, render farm is used to rendering mass images concurrently according to the independence among frames. How to scheduling and manage various rendering jobs efficiently is a significant issue for render farm. Therefore, the prediction of rendering time for frames is relevant for scheduling, which offers the reference and basis for scheduling method. In this paper a statistics based prediction method is addressed. Initially, appropriate parameters which affect the rendering time are extracted and analyzed according to parsing blend formatted files which offers a general description for synthetic scene. Then, the sample data are gathered by open source software Blender and J48 classification algorithm is used for predicting rendering time. The experimental results show that the proposed method improve the prediction accuracy about 60% and 75.74% for training set and test set, which provides reasonable basis for scheduling jobs efficiently and saving rendering cost.

Introduction

High performance computing (HPC) provides a chance for scientists to use large scale computing resources to settle problems in intensive computation application [START_REF] Mochocki | Signature-based workload estimation for mobile 3d graphics[END_REF]. Gradually, researchers concentrate on how to manage what application could be applied on HPC platforms to maximize the performance. As an intensive computation and massive data access application, rendering with the feature of independence among frames is suitable for parallel processing in HPC environment. Rendering is the process of creating an image from a model by means of computer programs [START_REF] Monte | Estimation of volume rendering efficiency with gpu in a parallel distributed environment[END_REF][START_REF] Baharon | Secure rendering process in cloud computing[END_REF], which is used widely on many field, for example, animation design, development of games, simulation [START_REF] Chapman | A framework for rendering high resolution synthetic aperture radar images on heterogeneous architectures[END_REF], etc.

With the rapid development of animation industry, rendering is widely used in movie production and directly determines the visual effect of animation works. For an animation production, rendering a photo-realistic image with high resolution of 4K to 6K can be exceptionally costly, often taking days, or even weeks. Generally, render farm, which is a cluster of interconnected computers used for rendering images in parallel [START_REF] Chong | Grid-based computer animation rendering[END_REF], is used by companies to rendering mass images concurrently, which has been proven to be quite effective way to cutting down hours of render time into minutes.

When using the render farm, users just submit their rendering jobs which includes the requirement of number of rendering resources, types of rendering software, budget and deadline etc. through web portal or client. The render farm with a pool of finite rendering resources receives the rendering jobs, chooses appropriate resources according to the demands of rendering users and scheduling rendering jobs according to some policies. Generally speaking, the research spot is focus on optimizing and design of scheduling policy [START_REF] Khan | Improving the performance of hierarchical scheduling for rendering[END_REF][START_REF] Yu | Dynamic scheduling and realtime rendering for large-scale 3d scenes[END_REF][START_REF] Tamm | Hybrid rendering with scheduling under uncertainty. Visualization and Computer Graphics[END_REF]. But many issues are based the on the premise of obtaining the application running time in advance or have not a-priori knowledge on execution time prediction [START_REF] Schnitzer | Concepts for execution time prediction of 3d gpu rendering[END_REF], which will negatively impacts the efficiency of scheduling policy, especially for the static policy from the view of system. And from the view of users, without prediction, users have no idea how long they will be waiting for finish rendering jobs, users cannot obtain better experience on rendering service and choose an economical way to employ rendering resources. Therefore, how to predict running time of applications and improve prediction accuracy is significant topic for render farm.

In this paper, we propose a statistics based prediction method to provide a guidance for scheduling policy in render farm. The proposed method extracts and analyzes firstly the appropriate parameters which affect the rendering time by the way of parsing blend formatted files. Then, the sample data are gathered by open source software Blender and we use J48 classification algorithm to train and predict rendering time. And the test result indicate that our method improves the prediction accuracy about 60% and 75.74% for training set and test set respectively.

The rest of this paper is organized as follows: related works are introduced in section 2. In Section 3, we describe the system design and proposed method. Section 4 presents the experimental results. And conclusion and future works are provided in Section 5.

Related Works

Rendering is one of the most important research topics in computer graphics, and it is closely related to the other technologies. Rendering plays an important role in the field of animation and movie production. The execution time prediction for rendering is necessary for scheduling and user's Qos. Obviously for this schedule to be effective and experience to be better, a good prediction of the execution time for rendering is required.

Many researchers have explored the use of various time models to predict execution time. According to auto-regressive model a time series based prediction method [START_REF] Wu | A time series based solution for the difference rate sampling between haptic rendering and visual display[END_REF] is also proposed. For physically-based medical simulation, a multirate output-estimation method using the ARMAX model [START_REF] Lee | Real-time haptic rendering using multi-rate output-estimation with armax model[END_REF] is presented to improve the computational speed and accuracy. By rigid model, Liu [START_REF] Liu | Proxy position prediction based continuous local patch for smooth haptic rendering[END_REF] pro-poses a proxy position prediction method using the geometric patch. The patch is calculated from the real-time contact region prediction method. Hou and Sourina [START_REF] Hou | A prediction method using interpolation for smooth six-dof haptic rendering in multirate simulation[END_REF] present a new prediction method based on auto-regressive model for smooth haptic rendering [START_REF] Cheng-Jun | Contact elements prediction based haptic rendering method for collaborative virtual assembly system[END_REF] to overcome the low update rate of the physical simulation with complex or deformable models. Schnitzer et al. [START_REF] Schnitzer | Concepts for execution time prediction of 3d gpu rendering[END_REF] predict the individual execution time of graphics commands using models for the main three commands relevant for rendering, namely, FLUSH, CLEAR, and DRAW.

And then, prediction ideology is also be used for various types of render. For remote image-based rendering (IBR) [START_REF] Leung | Compression with mosaic prediction for image-based rendering applications[END_REF] in mobile virtual environments, Lazeml et al. [START_REF] Lazem | Prediction-based prefetching for remote rendering streaming in mobile virtual environments[END_REF] propose a prefetching scheme that predicts the client potential path based on the movement history using a linear prediction model. The server then sends one predicted image with every position update for the client, which reduces the server load and improves the system scalability. In Depth imagebased rendering (DIBR), a combined hole-filling approach [START_REF] Yu | Combined hole-filling with spatial and temporal prediction[END_REF] with spatial and temporal prediction is presented.

Considering the workload in the process of rendering, Wimmer and Wonka [START_REF] Wimmer | Rendering time estimation for real-time rendering[END_REF] present an estimation approach based on sampling rendering times, and an improved mathematical heuristics based on a cost function. They propose two hardware extensions, i.e. a time-stamping function and a conditional branch mechanism, which make rendering time estimations more robust. Meantime, the proposed estimation method for rendering time can also be used to calculate efficient placement of impostors in complex scenes. Doulamis et al. [START_REF] Doulamis | A combined fuzzy-neural network model for non-linear prediction of 3-d rendering workload in grid computing[END_REF] address the method of 3D rendering workload prediction based on a combined fuzzy classification and neural network model. Litke et al. [START_REF] Litke | Computational workload prediction for grid oriented industrial applications: the case of 3d-image rendering[END_REF] predict computational workload of jobs assigned for execution 3D image rendering on commercially exploited Grid. And Doulamis et al. [START_REF] Doulamis | Adjusted fair scheduling and non-linear workload prediction for qos guarantees in grid computing[END_REF] propose an efficient non-linear task workload prediction mechanism with a non-linear model incorporated with a fair scheduling algorithm for task allocation and resource management in Grid computing. The history-based motion prediction method [START_REF] Xiaohong | A history-based motion prediction method for mouse-based navigation in 3d digital city[END_REF] aims at high file hits and predicts the future motion according to the historical ones, which produces better results when interpolation is added. Son et al. [START_REF] Son | Prediction-based dynamic load balancing using agent migration for multi-agent system[END_REF] propose a new approach for predicting and identifying the load condition of agents to solve load balancing problem. However, these methods only works for static model but ignore the influence of the parameters used in render files.

3 Proposed strategy environment. Also it describes the rendering algorithm as well as respective parameters used for performing the rendering. To identify the parameters that impact the rendering process and the algorithm used, the scene files are parsed. In this way, a set of candidate parameters is constructed, which is responsible for selecting the most significant parameters among all candidates, i.e., a feature vector of appropriate attributes is constructed to predict the rendering time.

The predictor predicts the time of a rendering process by taking into consideration the feature vector. The J48 classification algorithm is used for training and predicting rendering time. And then, scheduler will scheduling rendering jobs according to exploiting information provided by the previous prediction result. In the paper, we mainly focus the process of prediction.

Parsing of parameters

A BLEND file usually contains many parameters which describe the rendering attributes, and some parameters may have less impact on rendering time. We use Blender's API for Python scripting to parse parameters and the scene image is shown in Figure 2. And Table 1 shows the initial parsing result.

We use the method of control variable to select the parameters and change the corresponding value of parameter to get rid of the parameters with less impact on the rendering time. The rendering time is an average value obtained by 20 times rendering. As shown in Table 1, the change of parameters value has less impact on the rendering time. Except that, the vertex, edge and face of object is fixed in a scene and the impact of these factors is included in that of no. of Mesh. And then three parameters are also rejected. Therefore, at the processing of prediction we don't consider these parameters. Then, we will introduce the parameters which mainly impact on the rendering time.

-Shadow [START_REF] Doulamis | Non-linear prediction of rendering workload for grid infrastructure[END_REF], Blender provides two types of shadow, Ray-Tracing Shadow and Buffer Shadow. Table 2 shows the relationship between rendering time and

-Pixel value, which is the product of resolution ratio, the more pixels the more elaborate image, and the rendering time is longer. In the paper, we use 17 types of resolution ratio.

-Tile size, the more tile size, the longer rendering time. Usually, the tile size is approximate number of resolution ratio.

-Number of object, the object has many attributes and in the paper we just consider the influence of number of object. The more objects the longer rendering time.

-Anti-aliasing, there are 4 types of Anti-aliasing sample values, 5, 8, 11, 16.

And the value 0 means that the anti-aliasing is not used. The impact is shown in Table 3.

-Raytrace method, there include 6 types, AUTO, OCTREE, BLIBVH, VBVH, SIMD SVBVH and SIMD QBVH. The impact with different types is shown in Table 4.

Strategy description

In this section, we will introduce the prediction strategy according to the parameters parsed in above section. We use Weka as tool and J48 classification algorithm [START_REF] Yadav | Solar energy potential assessment of western himalayan indian state of himachal pradesh using j48 algorithm of weka in ann based prediction model[END_REF]. The J48 has the following advantages.

-Easy understand for rules. Each branch of the decision tree in J48 corresponds to a classification rule, and the total rules set is easy to understand.

-The fast running. The time complexity of J48 algorithm is O(n 3 ), n is sample size.

-The higher accuracy.

Experimental Results

At the beginning, we need dispose the original data. The inactive data is to be rejected. And then, the rendering time set need to be discretized, which is helpful to classification and prediction. We sort the rendering time set with descending order, and each 5 second as a subsection. The disposed data is input into Weka and Figure 3 shows the visualization result. The rendering time is automatically discretized into 20 classes. The low accuracy rate is due to the less change range for each parameter. The useful data in each classification is less and unrepresentative. Therefore, we can suitably reduce the accuracy of the classification for rendering time and use 10 second as a subsection and discretize rendering time set again. And the accuracy rate of training set and test set is 60% and 75.74% respectively. The prediction result is shown in Figure 6. The comparison result shows that the J48 classification algorithm can obtain the accurate prediction result for rendering time according to the main parameters parsed from scene files.

Conclusion and Future Work

In this paper, we present a statistics based prediction method for rendering application. The scene files with BLEND format are parsed to extract and analyze the parameters which affect the rendering time. And we use Blender to gather the sample data and J48 classification algorithm to predict rendering time. The experimental results show that the proposed method improve the prediction accuracy about 60% and 75.74% for training set and test set respectively, which provides reasonable guide for scheduling jobs efficiently and saving rendering cost.

3. 1 Fig. 1 .

 11 Fig. 1. Workflow of prediction

Fig. 2 .

 2 Fig. 2. The scene image for prediction

N 2 )-

 2 Light s = 1 5 * N P oint s + 1 5 * N Sun s + 1 10 * N Spot s + 1 10 * N Hemi s +Aera s (Ambient light, there are two types, raytrace and approximate. The approximate is rarely used and we use raytrace as the main factor. The raytrace usually includes three types, CONSTANT QMC, ADAPTIVE QMC, CONSTANT JITTERED. We use formula (3) to indicate the influence on rendering time. And the coefficient is empirical value. Ambientlight = 5 * CON ST AN T QM C +3.5 * ADAP T IV E QM C +1.4 * CON ST AN T JIT T ERED

Fig. 3 .

 3 Fig. 3. The visualization result of discretized data

Fig. 4 .

 4 Fig. 4. The classification matrix of training set

Fig. 5 .

 5 Fig. 5. The classification matrix of test set

Fig. 6 .

 6 Fig. 6. The comparison of rendering time and prediction result.

Table 1 .

 1 The Light type, there are five types of light, point light, sun light, spot, hemi light and area light. Hemi light has no sampling value so it is rejected. We use formula (1) to indicate the influence of light types on rendering time. And the coefficient is empirical value.

	Absorption intensity of ambient light	[1-10]	[50.3848-55.6572]
	Types of diffuse reflection	5 types	[50.1567-55.6572]
	Types of highlight	5 types	[50.1688-55.6572]
	Types of anti-aliasing filter	7 types	[55.6572-58.8323]
	Light s = 1 7 * P oint s + 1 7 * Sun s + 1 7 * Spot s + Aera s	(1)

parameters with less impact on rendering time Parameter Variation range Rendering time intensity of illuminant [1.01-11] [55.0401-59.9534] No. of camera [1-10] [55.0572-55.6572] Absorption types of ambient light [MULTIPLY,ADD] [50.3848-55.6572]

types of Buffer Shadow. When an image is rendered, the rendering time with different types of Buffer Shadow is different.

-

Table 2 .

 2 The rendering time with different types of shadows Number of light, which is an important factor on rendering time. In a scene, there includes various types of light corresponding to different number of light. We use formula[START_REF] Baharon | Secure rendering process in cloud computing[END_REF] to indicate the influence on rendering time. And the coefficient is empirical value.

	Types	Rendering time
	REGULAR	49.7928
	IRREGULAR	50.6198
	HALFWAY	52.3219
	DEEP	50.3958
	-

Table 3 .

 3 The rendering time with different types of Anti-aliasing sample values

	Value Rendering time
	0	14.5008
	5	55.6572
	8	85.4189
	11	116.9777
	16	171.1598

Table 4 .

 4 The rendering time with different types of Anti-aliasing sample values

	Type	Rendering time
	AUTO	55.6572
	OCTREE	162.5122
	BLIBVH	138.0688
	VBVH	78.2354
	SIMD SVBVH	56.6742
	SIMD QBVH	59.0663

Acknowledgments. This work is supported by Natural Science Foundation of China (61202041, 91330117), National High-Tech R&D (863) Program of China (2012AA01A306, 2014AA01A302) and the Key Technologies Program for Social Development of Shaanxi Province (2016SF-428). Computational resources have been made available on Xi'an High Performance Computing Center.


Lan Liu
email: liulan@buaa.edu.cn

Zhongzhi Luan

Haozhan Wang
email: wanghaozhan@buaa.edu.cn

Depei Qian
email: depeiq@buaa.edu.cn

IBB: Improved K-resource Aware Backfill Balanced Scheduling for HTCondor

HTCondor, a batch system characterized by its matchmaking mechanism, schedules job in FCFS way, so its performance is not ideal as expected. Backfilling is a technique to address the above problem. Most backfilling algorithms are based on CPU information and have large room for improvements with considering other resource information. The K-resource aware scheduling algorithm Backfill Balanced (BB) selects backfill job which can best balance the usage of all resources and achieve better performance compared with the classical backfilling algorithm. However, BB does not realize that small jobs' impacts on resource utilization are negligible and they mainly contribute to reduce the average response time. Here we propose the IBB algorithm, which utilizes the characteristics of small jobs to guide a better job selection. We implemented IBB on HTCondor to improve its performance. Experiments results show that IBB can provide up to 60% performance gains in most performance metrics compared with BB.

Introduction

HTCondor, a high-throughput distributed system, can produce high job throughput and reliable system performance by using a flexible mechanism ClassAd [START_REF] Wright | Cheap cycles from the desktop to the dedicated cluster: combining opportunistic and dedicated scheduling with Condor[END_REF]. However, its dedicated scheduler performs in FCFS which may result in lots of resource fragmentations when the current job is too large. It provides another way called "Best-fit" to skip the current blocked job. However, the blocked job may suffer from starvation when the subsequent jobs are quite small.

An effective way to handle the above problem is backfilling which schedules lowpriority small jobs after the current blocked one into execution to utilize the resource fragmentations. There are two typical backfilling methods: Conservative backfilling and EASY backfilling [START_REF] Mu'alem | Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[END_REF]. William Leinberger et al. proposed the K-resource aware scheduling algorithm Backfill Balanced (BB) which can use the additional resource information to select backfill jobs more intelligently than typical backfilling methods [START_REF] Leinberger | Job Scheduling in the presence of Multiple Resource Requirements[END_REF]. However, BB does not realize that the influence differences on system resource utilization and global system resource status diagram exerted by large jobs and small ones. What's more, it can only select one job to backfill in one traversal.

Our contribution is to provide a variant of backfilling algorithm termed Improved Backfill Balanced (IBB) based on BB. IBB can make use of the additional resource information and the characteristic of small jobs to make more intelligent decisions on the selection of backfilling jobs. And we implemented IBB on HTCondor which can further improve its job throughput.

This paper is organized as follows: Section 2 describes the related work of past research in parallel job scheduling. Section 3 presents the core thought and application of IBB. Experiments and evaluations are given in Section 4. The conclusion and future work are provided in Section 5.

Related Work

As mentioned in Section 1, the system resource utilization and job throughput of HTCondor are not ideal enough. How to utilize the resource fragmentations effectively in parallel job scheduling is one of its most difficult problems.

Backfilling is well known in parallel job scheduling to increase system resource utilization and job throughput. Conservative backfilling can select a small job to backfill from the back of the queue as long as it does not delay the start time of all the jobs in front of it. EASY takes a more aggressive way and selects a job to backfill if it will not delay the start time of the first job in the queue [START_REF] Mu'alem | Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[END_REF]. It is obvious that Conservative backfilling is not as flexible as EASY since it is under the limitation that all front queued jobs cannot be delayed for execution.

Aside from methods mentioned above, a number of variants based on backfilling have been put forward recent years, including Slack-Based backfilling, Relaxed backfilling, etc [START_REF] Talby | Supporting priorities and improving utilization of the IBM SP scheduler using slack-based backfilling[END_REF] [5] [6] [START_REF] Jackson | Core algorithms of the Maui scheduler[END_REF]. Those variants were shown to have lower average slowdown than EASY. However, they may result in worse wait time and higher time complexity. Most important of all, none of them takes any additional job resource requirements and system resource information into consideration, which can easily lead to unbalanced resource utilization and finally harm system performance.

William Leinberger et al. put forward Backfill Balanced (BB) which provides Kresource aware job selection heuristics. BB uses the additional job resource requirements and current system resource status information to guide job selection for backfilling. It can make efficient use of all the available system resource information and experiments show that its performance gains in average response time can up to 50% over classical backfilling scheduling methods.

3

Improved Backfill Balance Scheduling

Thought of IBB

The classical backfilling algorithms can improve system resource utilization and job throughput by selecting small jobs to execute on resource fragmentations. However, none of them takes any other available resource information into consideration except CPU. The performance degrades since there may be lots of other resource being wasted. BB can achieve better system performance than classical backfilling methods by providing K-resource aware job selection heuristics. BB selects job based on the overall ability to balance the system resource utilization, its general notion is that if all the resource usages are kept balanced, then more jobs will likely fit into the system, creating a larger backfill candidate pool. BB's evaluation mechanism showed in [START_REF] Wright | Cheap cycles from the desktop to the dedicated cluster: combining opportunistic and dedicated scheduling with Condor[END_REF] includes two parts: a balance measure and a fullness modifier. The balance measure showed on the left part of ( 1) is used to score each backfill job candidate which aims at achieving the best resource utilization balance. The fullness modifier showed on the right is applied to relax the balance criteria as the system gets full by allowing a larger job which achieves a worse balance to be selected over a smaller one which achieves a better balance when the larger one can nearly full the machine. The job with the lowest score indicates a best balance it can up to by the time. The goal of BB is to improve the average response time of the system by improving the response time of small jobs which can best balance the usage of all system resource [START_REF] Leinberger | Job Scheduling in the presence of Multiple Resource Requirements[END_REF].

max i (S i + R i j ) ∑ (S i + R i j ) K i=1 K ⁄ * {1.0 - ∑ (S i + R i j ) K i=1 K } ( 1
)
The notations are explained in Table 1:

Table 1. Notation explanation Notation Explanation K The number of resource types i S
The current utilization of resource i in the system S j i

R

The requirement for resource i by job j

The BB algorithm can significantly improve system performance compared with the classical backfilling algorithms. However, transient imbalance of resource utilization can be neglected, since it is often caused by the execution of a small number of large jobs and will come out of the circumstance once the large jobs terminate. Long-duration imbalance of resource utilization is often caused by successive execution of many large jobs, and it can only be relieved by the execution of large jobs which are complementary in resource requirements as small jobs characterized by short execution time and tiny resource needs can usually do little improvement for the ease of imbalanced resource utilization situation.

As described above, we found that BB doesn't realize the fact that the small jobs' influence on system resource utilization is negligible for their resource requirement is tiny and the execution time is very short relative to large jobs. Another flaw in BB is that in one traversal of the job queue, it can only select one job to backfill, which lowers the efficiency of backfilling and thus affects the average job response time and job throughput.

Here we put forward the Improved Backfill Balanced (IBB) algorithm based on BB. The same with BB, it is K-resource aware as it takes all available resource information into consideration for backfill job selection. Our standpoint is trying to backfill more small jobs as far as possible by taking all available resource information and the characteristics of small jobs into consideration, which, in return, can achieve considerable performance gains over BB. The difference of IBB from BB mainly lies in the points listed below:

 If the job meets the basic backfilling requirements and will not worsen the resource imbalance in the system, it can be selected.  In one traversal of the job queue, backfill all the jobs meet the above requirement. The evaluation mechanism in IBB is shown in [START_REF] Mu'alem | Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling[END_REF], if the evaluation result is true, then we select the job for backfilling, skip it if not:

max i (S i + R i j ) ∑ (S i + R i j ) K i=1 K ⁄ ≤ max i (S i ) ∑ S i K i=1 K ⁄ ( 2
)
The reason for performance improvement which IBB gains over BB lies in the fact that we realized the influence difference on system resource utilization and global system resource status diagram exerted by large jobs and small ones, and try to backfill more small jobs as far as possible to reduce the average response time and improve job throughput more significantly. The algorithm is given in Algorithm 1.

Algorithm 1. Improved Backfill

Apply Backfilling to HTCondor

HTCondor's simple and novel matchmaking algorithm which can produce high system reliability and high job throughput makes it become more and more attractive. However, to ensure simplicity and reliability, its scheduling strategy for parallel jobs just basically follows the FCFS principle and limits the improvement of system performance. Actually backfilling has little impact on system reliability and simplicity since it only needs to traverse the job queue to select jobs for backfilling when the first job in the queue got blocked, with no other complex algorithm and communications needed.

To further improve HTCondor's system performance, we implement IBB on it, the performance gains over the original FCFS and Best-fit scheduling methods are substantial as expected.

Experiments and Evaluations

This subsection describes the experiments conducted to evaluate the IBB. As the scale of real environment is limited, we first make performance comparison by simulating to prove the feasibility and effectiveness of IBB on large scale computing systems. As there is little information about jobs' requirements for disk, network, etc, we only consider CPU and memory here. Then we implemented IBB on HTCondor to improve its job throughput, job response time and system resource utilization, which also proves the effectiveness of IBB in modern RJMS.

Simulation Experiments

We make performance comparison by simulating to prove the feasibility and effectiveness of IBB on large scale computing systems. As the simulator [START_REF] Cappello | CONTRIBUTIONS FOR RESOURCE AND JOB MANAGEMENT IN HIGH PERFORMANCE COMPUTING[END_REF] does not provide job throughput and system resource utilization information, we list them as future work and here just provide results for average wait time, average response time and average slowdown. We simulated on the following two kinds of workloads.  Workload composed of the same job type which we call as Pure Workload.  Workload composed of mixed type of jobs. We refer it as Mixed Workload. By simulating on the above two kinds of workloads, we can prove that our algorithm works well in both scenarios, which, to some extent, can generalize all kinds of workloads in real environments.

Pure Workload. This workload is provided by the Los Alamos National Lab (LANL) called LANL-CM5. It contains detailed information about job's actual CPU and memory usage, as well as the arrival time and execution time. We simulated the experiments in a 1024-node cluster with 1GB memory per node.

Fig. 1 depicts the performance results for pure workload. The relative load means the experimental system load relative to the workload's original experiment load. The results indicate that IBB is far better than BB. For the average wait time and average response time, the performance gains can up to 65%. The average slowdown has relative lower gains since it mainly depends on the execution of large jobs. The results show that IBB can work well in environment with a single workload type.

Mixed Workload. To verify that IBB can also work well with mixed types of jobs, we selected two traces to synthetic a mixed workload. The first trace is LANL-CM5 introduced above. The second one called MetaCentrum is memory-intensive and contains several months' worth of accounting records. We processed the synthetic workload in the same way as LANL-CM5. Fig. 2 depicts the average wait time, average response time and average slowdown for Mixed Workload. The system load changes in the same way as experiment conducted on Pure Workload. The performance gains for the three metrics can up to 60%. Experiment results show that IBB can be applied to mixed job types well and even produces better performance gains than it does on Pure Workload.

Experiments Conducted on HTCondor

Experiment was also conducted on HTCondor to evaluate the performance gains of IBB over its default FCFS and Best-fit scheduling algorithm in real environment.

Experiment results prove that IBB can significantly improve HTCondor's performance. The experiment was conducted on a four-node cluster. The job queue was composed of 54 MPI jobs from the NAS Parallel Benchmark and the time interval between each job is one second. we can see that the job parallelism degree scheduled by IBB is much higher than FCFS with quite a number of small jobs being packed to execute on the resource fragmentations while almost no large jobs suffering from starvation. Although the Best-fit scheduling method can get almost the same performance as IBB in job parallelism degree, it can easily make large jobs suffer from starvation, which means it cannot guarantee fairness well. Fig. 3(c) shows that each job's slowdown is almost the same for IBB, which means the wait time of each job endured is negligible compared with its execution time. However, the slowdown is uneven distributed with FCFS scheduling algorithm which indicates worse average job response time.

Discussion

To summarize, the experiment conducted on HTCondor are somewhat inconclusive and depend on the job queue. As the scale of our HTCondor pool is limited and the job queue we designed may not strictly conform to the real scenario, the performance gains of IBB in real environment is much better than it got by simulation. To some extent, the experiments conducted on simulator can reflect the true performance of IBB. The success of IBB indicates that taking the characteristic of small jobs and overall system resource information into consideration is reasonable and can select small jobs to backfill in a more efficient way.

Conclusion and Future Work

In this paper, we improved the K-resource aware backfilling algorithm by utilizing the characteristics of small jobs and all available resource information, and proposed a new model to select jobs for backfilling more effectively. Meanwhile, we implement backfilling algorithm on HTCondor, which can significantly improve its performance. The success of IBB shows that small jobs' influence on system resource status diagram is negligible and its contribution to reduce average response time is attractive. IBB can perform a better job packing of the small jobs while maintaining sufficient progress of the large jobs. While our algorithm performs better than almost all existing backfilling algorithms, it still has some drawbacks. For example, it has to do scheduling based on the job resource requirements information and estimated execution time given by users which may be inaccurate and affect system performance. Future work will focus on putting forward a way to provide appropriate estimation of job resource requirements and execution time to further improve system resource utilization and job throughput.

Fig. 3 Fig. 2 .Fig. 1 .

 321 Fig. 2. Average wait time, response time, slowdown under different load with mixed workload

Fig. 3 .

 3 Fig. 3. Job wait time, response time, slowdown on HTCondor

Acknowledgments. This research is supported by the National Key R&D Program (Grant No. 2016YFB0201403) and the National Natural Science Foundation of China (Grant No. 61361126011, 61133004, 61502019). And here we would like to thank the HTCondor team and the father of HTCondor Miron Livny for providing us help in understanding and using HTCondor.


On the precision in polyhedral partition representation and the fragility of PWA control

Rajesh Koduri 1 Sorin Olaru 1 and Pedro Rodriguez-Ayerbe 1

Abstract-Explicit model predictive control (EMPC) solves a multi-parametric Quadratic Programming (mp-QP) problem for a class of discrete-time linear system with linear inequality constraints. The solution of the EMPC problem in general is a piecewise affine control function defined over non-overlapping convex polyhedral regions composing a polyhedral partition of the feasible region. In this work, we consider the problem of perturbations on the representation of the vertices of the polyhedral partition.Such perturbations may affect some of the structural characteristics of the PWA controller such as "non-overlapping within the regions" or "the closed-loop invariance". We first show how a perturbation affects the polyhedral regions and evoke the overlapping within the modified polyhedral regions. The major contribution of this work is to analyze to what extend the non-overlapping and the invariance characteristics of the PWA controller can be preserved when the perturbation takes place on the vertex representation. We determine a set called sensitivity margin to characterize for admissible perturbation preserving the non-overlapping and the invariance property of the controller. Finally, we show how to perturb multiple vertices sequentially and reconfigure the entire polyhedral partition.

I. INTRODUCTION

Explicit control laws can be efficiently implemented on hardware circuits for systems with fast dynamics and relatively small dimension of system states [1]- [START_REF] Grancharova | Explicit Nonlinear Model Predictive Control Theory and Applications[END_REF]. Recently, such control laws have gained popularity for a wide range of realtime control applications [START_REF] Johansen | Hardware Synthesis of Explicit Model Predictive Controllers[END_REF]- [START_REF] Takács | Embedded explicit model predictive vibration control[END_REF]. However, the adoption of such control laws are pertained to the numbers of state space partitions and the piecewise affine control laws associated with those partitions. In order to exploit the computational advantages of the explicit controller, a truncation or quantization operation must be performed on the coefficients of the representation of the state space partitions and on their associated PWA controls [START_REF] Suardi | Robust explicit MPC design under finite precision arithmetic[END_REF]. The implications of the quantized state-partitions and the quantized PWA gains and offsets extend to affect control input accuracy, whose computations are based on point location functions, and the properties of the PWA controller. The quantized state partitions might also adversely affect the non-overlapping (uniqueness) and nonemptiness (feasibility) characteristics of the PWA controller. The authors of [START_REF] Olaru | Explicit robustness margins for discrete-time linear systems with PWA control[END_REF] and [START_REF] Nguyen | Explicit robustness and fragility margins for linear discrete systems with piecewise affine control law[END_REF] proposed a geometrical approach to determine robustness/fragility margins with respect to the invariance characteristics of the PWA controller. However *The work leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Unions Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no 607957 (TEMPO). 1 The Authors are with L2S, CentraleSupelec-CNRS-UPS, Paris Saclay University, 91192, Gif-Sur-Yvette, France. rajesh.koduri; pedro.rodriguez-ayerbe; sorin.olaru@centralesupelec.fr their approach does not extend to the quantized representation of the state space partitions. In a recent study [START_REF] Knyazev | Explicit model predictive control accuracy analysis[END_REF], the accuracy of the explicit control input for the quantized representation of the regions and the quantized representation of the PWA control laws are analyzed in general to prove the scale of quantization required in order to obtain a certain degree of control accuracy. However, the paper builds the control input analysis on the assumption that the modified state space regions are non-overlapping and thus does not address one of the essential characteristics of the representation of the state partitions: the non-overlapping and completeness of the polyhedral partition of the feasible domain.

This paper is a continuation of earlier work [START_REF] Koduri | Sensitivity of Piecewise Control Laws with Respect to Perturbation of the State-Space Partition[END_REF] where a vertex sensitivity region is derived that guarantees the nonoverlapping characteristics of the PWA controller in the event of perturbation on the vertex representation of the partition. In this work we extend the above results to analyze to what extend the non-overlapping and the invariance characteristics of the PWA controller can be preserved when a perturbation on the vertex representation of the partition takes place. First, we approximate the outer representation of the feasible set for admissible perturbation on the frontier vertices, which are considered to be sensitive all by ensuring the feasible set to preserve the non-overlapping and the invariance property of the controller. Second, starting from the new feasible domain, we analyze the polyhedral partitions by considering each of the vertices of the partition which are not placed on the frontiers of the feasible domain. We determine a set called sensitivity margin for the closed-loop invariance. This set characterizes for admissible perturbation on the vertex representation to preserve the non-overlapping and the invariance characteristics of the PWA controller. Third, we compute the perturbed polyhedral partitions for all the inner vertices of the feasible set sequentially completing the transformation of the original polyhedral regions to a new polyhedral regions for all the vertices in the feasible set.

II. BASIC NOTATIONS

This section addresses some basic notations and definitions. The sets R, Z, N and N + denote set of real numbers, set of integers, set of non-negative integers and set of positive integers respectively. A vector is noted

x ∈ R n , x = [ x 1 , • • • , x n ] T and a matrix S ∈ R n×m , S = [s ij ].
An identity matrix is represented by I n , where the subscript n denotes the dimension of that matrix.

A polyhedron is the (convex) intersection of a finite number of open or closed half-spaces and a polytope is a bounded and closed polyhedron. For a N ∈ N + , I N denotes the set of integers,

I N := { i ∈ N + | i ≤ N }.
For a given set P, int(P) denotes the interior of P and Conv denotes the convex hull. The set of vertices of a polytope P ⊂ R n is denoted V(P). Given a matrix S, V(S) denotes the set of points described by the colums of S.

III. SYSTEM DESCRIPTION Consider a linear discrete-time system given by,

x k+1 = Ax k + Bu k (1)
here, x k ∈ R n and u k ∈ R m denote the state vector and input variables respectively at time k.

The constraints on the system's states and input variables are represented by polytopic sets,

X = {x : H x x ≤ h x , H x ∈ R nx×n , h x ∈ R nx } (2a) U = {u : H u u ≤ h u , H u ∈ R mu×m , h u ∈ R mu } (2b)
The constrained control law is considered to be designed upon a classical MPC framework for (1)-( 2) with a quadratic cost function and standard stability guarantees based on the terminal costs and terminal constraints [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF]. Subsequently the receding horizon constrained problem is transformed into a multi-parametric Quadratic Programming (mp-QP) problem [START_REF] Alessio | A survey on explicit model predictive control[END_REF] to obtain a so-called explicit MPC (EMPC) formulation for the feedback control law.

The solution of EMPC problem is a finite set of affine functions defined over the polyhedral partition of the set R, where

P N (R)= [R 1 , R 2 • • • R N ] also called polyhedral partitions of the set R. The polyhedral regions R i are non- overlapping such that int(R i ) ∩ int(R j ) = ∅, for i = j.
The non-overlapping property ensures the unique solution for the point location of a given state x k ∈ R i , ∀i ∈ I N . Two neighboring polyhedral R i and R j share common facets. It is worth to be recalled that the feasible set R represents a bounded polyhedron in itself.

Definition 1: A mapping from R n to R m described by:

f pwa (x) = F i x + g i , ∀x ∈ R i , i ∈ I N (3)
is called a piecewise affine function over

∪ i∈I N R i .
The EMPC feedback law is given in terms of the piecewise affine function defined over the polyhedral partition P N (R) of the set R ⊂ R n and it can be written as:

u pwa (x k ) = F i x k + g i , ∀x k ∈ R i . (4)
Definition 2: The closed and bounded set R ⊂ X is called positively invariant with respect to the system (1) in closed loop with the control law

u pwa (x k ) in (4) if ∀x(0) ∈ R, it follows x k ∈ R, ∀k ∈ Z [1;∞] .
By construction of the standard MPC the positive invariance is considered to be guaranteed for the explicit MPC law.

IV. MOTIVATION AND PROBLEM FORMULATION

For real-time implementation of explicit controller, the online implementation of the PWA control law is composed of three stages, (i) Storage of the polyhedral regions R i , the PWA control gains F i and affine components g i .

(ii) Implementation of a point location mechanism with respect to the parameter x and the polyhedral partitions R = ∪ N i=1 R i . (iii) On-line evaluation of the PWA control law u pwa (x) = F i x + g i based on the elements resulting from the first two stages and the state measurements. In practice this evaluation procedure can fail due to several reasons. Some of those are i) the precision of R i representation ii) due to point location mismatch iii) PWA control accuracy inflicted by the precision of representation of the control gain F i and offset g i .

The PWA control accuracy and the fragility issues of the F i and g i has been extensively discussed in [START_REF] Olaru | Explicit robustness margins for discrete-time linear systems with PWA control[END_REF]- [START_REF] Knyazev | Explicit model predictive control accuracy analysis[END_REF]. The resulting solution obtained from the EMPC problem is a set of PWA functions defined over the polyhedral partition P N (R) and their analysis in the point iii) above can be handled in the respective framework. However, the issues related with the representation and the closely related point location problems (items (i and ii) above) remain largely uncovered and will represent the main goal of the present study. Before entering into the details of the main results, let us motivate the chosen approach by considering a polyhedral region R i ⊂ R ∈ R n , i ∈ I N , and its half-space representation is given by,

R i = {x | h i,r b x ≤ b i,r b , ∀i ∈ I N , r b = 1, • • • , r i } (5)
here, r i denotes the number of closed half-spaces of the region R i . In order to analyze the sensitivity of the polyhedral partition representation and its implication on the PWA control, a perturbation in the representation of the half-space {h i,r b ≤ b i,r b }, for some r b ∈ I ri of the region R i will be considered,

ĥi,r b = h i,r b + ∆h i,r b and bi,r b = b i,r b + ∆b i,r b (6)
which leads to a new polyhedral set:

Ri = {x | ĥi,r b x ≤ bi,r b }. (7)
The perturbation of the half-space inequalities of the region R i will concomitantly affect all the neighbor regions R j sharing the respective frontier within their half-space representation. As several regions are affected, the analysis of the effects on the partition will encounter structural problems. 1) Overlapping of the polyhedral partitions, violating the PWA characterization:

int( Ri ) ∩ int( Rj ) = ∅, ∀i = j. 2) R \ ∪ N
i=1 Ri = ∅ posing an well-possessedness issue in the characterization of the polyhedral partition. The first type of problem arise from the asymmetric consideration of the perturbation in between neighboring regions while the second can take place even if the perturbation is treated similarly among the neighboring regions. Moreover, both phenomena lead to invalidation of the PWA control law defined over the partitions. Particularly the second phenomenon leaves the point location function seemingly untraceable and this case is shown in Figure 1. The drawbacks demonstrated by the perturbation on the half-space representation are the consequence that the perturbations are not considered jointly for different half-spaces. This is due to the fact that the closed half-spaces of the regions R i are described uniquely and addressing perturbation on such representation is not possible locally. These drawbacks force us to rely on the duality of the polyhedron and lead us to the following problem formulation. Eq (6) can be given with equivalent vertex representation in the virtue of Motzkin duality:

R i = Conv{v i,1 , • • • , v i,ri }, ∀i ∈ I N (8)
here r i is the number of vertices of R i . Now, consider a perturbation with respect to the vertex representation v i,j , j ∈ I ri of the region R i , vi,j = v i,j + ∆v i,j , i ∈ I N , j ∈ I ri [START_REF] Nguyen | Explicit robustness and fragility margins for linear discrete systems with piecewise affine control law[END_REF] this will lead to a new polyhedral set:

Ri = Conv{v i,1 + ∆v i,1 , • • • , v i,ri + ∆v i,ri }. (10)
In order to illustrate the representation in this framework and present the obvious advantages of considering perturbation on the vertex representation a similar partition to the one presented in Figure 1 is depicted in the Figure 2. This time it is obvious that the completeness of the partition is not lost. In general terms, the case R \ ∪ N i=1 Ri = ∅ is avoided from the consequences of the in the polyhedral partition. To resume, the main objective is to start from the existence of the system in the form (1) stabilized by a PWA control law, and discuss the impact of perturbations on the vertex representation of the polyhedral region by proposing:

• An analysis of the admissible perturbations with respect to the non-overlapping and invariance characteristics of the PWA controller.

V. TREATMENT OF ONE VERTEX CONSIDERED INDEPENDENTLY

A. Vertex Perturbation with respect to non-overlapping characterization In the following, the definition of the vertex sensitivity for a single vertex is provided under the assumption that all the other vertices are fixed and not subject to perturbations.

(R) ∈ R n with R i = Conv{v i,1 , • • • , v i,ri }, i ∈ I N
given by vertex representation. Assume v ∈ R n be a vertex within P N (R) and denote Θ v as the set of indexes of polyhedral regions having v as a vertex:

Θ v = {j ∈ I N | v ∈ V(R j )} (11)
The set

Ψ v ⊂ R ⊂ R n is describing the vertex sensitivity for v if ∀(v + ∆v) ∈ Ψ v the collection of sets Rj = Conv{V(R j ) \ {v}, v + ∆v}, ∀j ∈ Θ v , Rj = R j , ∀j ∈ I N \ Θ v (12)
represents a polyhedral partition:

PN (R) = { R1 , • • • , RN }.
Theorem 1: Consider the subset of regions R j , j ∈ Θ v of P N (R) such that v ∈ V(R j ), ∀j ∈ Θ v , then the perturbed vertex sensitivity for v is represented by a polyhedral set.

Proof: For interested readers, please refer proof 1 in [START_REF] Koduri | Sensitivity of Piecewise Control Laws with Respect to Perturbation of the State-Space Partition[END_REF] .

B. Vertex Perturbation with respect to invariance characterization

In this section, we discuss the invariance characterization of the PWA controller as an additional "dynamics-related" property, to be considered on top of the non-overlapping property of the PWA control. We will preserve the assumption that only one vertex is perturbed at the time. This last point will be relaxed in section VI.

From Theorem 1, it is understood that the vertex sensitivity is analyzed for the admissible perturbation related to the nonoverlapping characteristics for any single vertex that belongs to the polyhedral regions R i . In order to incorporate the analysis for vertex sensitivity and the invariance property of the PWA control law, we will have to deal with the vertices that are sensitive to perturbation. The vertices that represent extreme points of the set R are particularly sensitive to perturbation taking into account that they characterize the controlled-invariant properties per se. This can result in the invalidation of the invariant set with respect to the nominal system and the constraints given in equation ( 1) and (2). Now, we define the set of vertices on the frontier of R as:

V = {v ∈ R : ∃i such that v ∈ V(R i ) and v / ∈ int(R)} (13) Consider the set R = ∪ N i=1 R i , with R i = Conv{v i,1 , v i,2 , • • • , v i,ri }. Let, V = {v 1 , v 2 , • • • , v r }
be the vertices, such that v j ∈ V, ∀j ∈ I r , lies on the frontier of the set R. The approximation of set R assuring the nonoverlapping and invariance characteristics is characterized by and positioning the frontier vertices sequentially. We start by defining the closed-loop mapping for any point in the set R preserving the invariance characteristics of the PWA controller:

f pwa (x) = Ax + Bu pwa (x) ∈ R (14)
From ( 14), we can represent the image of the set R preserving the invariance with,

F = Conv{f pwa (v j ), ∀j ∈ I r } (15)
In the reference [START_REF] Scibilia | On feasible sets for MPC and their approximation[END_REF], it has been shown that any sets of approximation of R denoted by R α ⊆ R and R α ⊇ F, the invariance holds with respect to the approximated set R α for the existing PWA controller,

R α = conv{v α j = v j + ∆v j , v α i = v i : ∃j ∈ I r , ∀i ∈ I r \ j such that v α j ∈ (Ψ vj ∩ R) and v α j / ∈ int(F)} .
(16) The validity of this construction will be demonstrated based on the idea in [START_REF] Scibilia | On feasible sets for MPC and their approximation[END_REF] and also considering the non-overlapping issues emerging from vertex perturbation. Figure 3 illustrates the set R with its image F and the vertex sensitivity sets for the corresponding vertices v j depicted with blue dots. In the following, we discuss about the possible scenarios where it leads to invalidation of invariance of the approximate set and overlapping issues.

Stage 1: From Figure 3, it can be noted that some boundary vertices of the image set F lies on the frontier of the set R and perturbing those vertices will result in violating the relation R α ⊇ F, here R α denotes the approximated set for the perturbed vertex. These vertices have no admissible perturbation in the first stage of the procedure. There after, we perturb any vertices that satisfies the relation R α ⊇ F.

Stage 2: Take two vertices [v 1 , v 2 ] ∈ V , the vertex sensitivity of the set Ψ v1 for the vertex v 1 is computed assuming that the vertex v 2 is fixed and vice versa. Perturbing the vertex v 1 inside its vertex sensitivity set may invalidate the vertex sensitivity set computed for the vertex v 2 . There after, we fix the position for the vertex after perturbation satisfying Stage 1 and recompute the set R with its partition Ri , here the perturbed set is assumed to be R α . We proceed to deriving the image set for the new R α and recompute the vertex sensitivity sets for all the untreated vertices.

Thus, we complete the proof that R ← R α represents the approximation of the set R whose vertices are perturbed and positioned in a way that the set R α assures the nonoverlapping and the invariance property of the controller. Fig. 3: Representation of the set R and its image F are represented by contour in dashed lines and the contour in full lines respectively. The colored polytopes apart from white and gray ones represent the vertex sensitivity for the vertices depicted in blue dots Remark 1: Analyzing the PWA characteristics with respect to the vertex sensitivity for the boundary vertices are considered vital for many purposes. It could help the on-line PWA controller to tackle considerable perturbation on the system states. The most resourceful purpose is to perform "quantizer" operation on the state-space partition given by vertex representation. Such a process can effectively bring down the memory cost concerning the hardware requirements.

In the following we assume R ≡ R α and we introduce a matrix V ∈ R n×p to store all the vertices of all the polyhedral regions R i , ∀i ∈ I N excluding the vertices on the boundary of the polyhedron R,

V = [v 1 , v2 , • • • , vp ]. (17)
2) Treatment of one inner vertex for non-overlapping and invariance: Definition 4: Consider the polyhedral partition

P N (R) ⊂ R n with R i = Conv{v i,1 , • • • , v i,ri }, i ∈ I N , V = [v 1 , • • • , vp ]
and R is assumed to be invariant with respect to the closed-loop dynamics (1)-(4). For any v ∈ V( V ) ∈ R n , denote Λ v as the subset of indexes of regions that satisfies

(Ψ v ∩ R j ) = ∅: Λ v = {j ∈ I N | v ∈ (Ψ v ∩ R j ) = ∅} (18)
The set

Υ v ⊆ Ψ v ⊂ R is representing the invariance- vertex sensitivity for a given vertex v if ∀(v + ∆v) ∈ Υ v ,
the following properties hold for the newly constructed polyhedral partition P N ( R):

1) R is a polytope. 2) R is invariant with respect to the closed loop dynamics. 3) R = ∪ N i=1 Ri . 4) int( Ri ) ∩ int( Rj ) = ∅, ∀i, j ∈ I N , i = j. Theorem 2: Let the subset of regions {R j : j ∈ Λ v } ⊂ P N (R) satisfy (Ψ v ∩ R j ) = ∅ and
R be invariant with respect to the closed-loop dynamics (1)-( 4). Then the invariance-vertex sensitivity for v is represented by a polyhedral set:

Υ v = Ψ v ∩ {v | Av + B(F j v + g j ) ∈ R, ∀j ∈ Λ v } (19)
Proof: Starting from the PWA state-feedback control assuring the invariance characteristics of the set R,

Av + B(F i v + g i ) ∈ R, ∀i ∈ I N , (20)
and the vertex sensitivity described by the set Ψ v . Now, locate the subset of regions of P N (R) assuring the non-overlapping behavior for the vertex v and index it using a set Λ v . Using (20) and the description of Λ v , we are able to compute the sets denoted by S v j containing all the points for the PWA controllers, given by the indexes in the set Λ v , such that the invariance property is preserved. By simply intersecting the set S v j and Ψ v sequentially we obtain the invariance-vertex sensitivity set:

Υ v = j∈Λ v (S v j ∩ Ψ v ) (21)
VI. TREATMENT OF MULTIPLE VERTEX PERTURBATION In this section, we propose to perturb multiple vertices inside the polyhedral partition P N (R). So far, we have discussed the perturbation of a single vertex assuring the nonoverlapping characteristics of the set R and the invariance property of the PWA closed-loop dynamics hold, under the assumption that all the other vertices are fixed.

We propose an algorithm to consider perturbing the position of all the inner vertices sequentially given in Algorithm 1. The steps involved in transforming the set R to R with respect to relocating the position of the vertices to the perturbed ones are described in the following.

• The first loop involvs the computation of vertex sensitivity, sensitivity margin and Chebyshev radius of the sensitivity margin set for all the inner vertices yet to be perturbed. • Secondly, the the vertex, also called as candidate, that has the least fragility is selected. This is done by identifying the vertex that has the smallest Chebyshev radius associated to its invariance-vertex sensitivity. • The next step is to consider a quantization function as f (v) = v + ∆v, here ∆v is a random vector satisfying ∆v ∞ ≤ 10 -, ∈ N + . • The regions that contain the perturbed (quantized) vertex are updated. • The reconstruction of the set R is performed by removing the candidate vertex from the matrix V and restarting the same procedure for the remaining vertices.

VII. EXAMPLE Consider the discrete-time linear system,

x k+1 = Ax k + Bu k , (22)
v qn = quantif y(v R(1) ) 11: if v qn / ∈ Υ vR(1) break end if 12:
for t = 1 to length(Θ vR (1) ) do 13:

Rj = Conv{V(R j ) \ {v R(1) }, v qn } ∀j ∈ Θ vR(1)
14:

end for 15:

V (R(1), :) = [ ] 16:

R = R

17: end for 18: return R Solving the EMPC problem using MPT 3.0 toolbox [14] yields 13 affine controllers and its associated state space partitions. First, we approximated the set R by perturbing the vertices on the boundary of the set. A quantization function f (v j ) = v j + ∆v j , ∀j ∈ I r with a random variable ∆v j ∞ ≤ 10 -2 is considered for perturbing the frontier vertices. A smaller quantizer function is chosen concerning the volume of the operating domain.

In the next step, we assume that the vertices on the boundary are fixed and we proceed to perturb the inner vertices in the set R sequentially as described in Algorithm 1. In the set R there are 8 inner vertices and we choose to manually displace them for this analysis for illustrative purpose. Figure 4 shows the functioning of the algorithm for each iteration. In the subplots from Figure 4, the polyhedral regions Ri are presented with the vertex sensitivity and invariance-vertex sensitivity sets depicted in red and green color respectively, for the vertex that has the smallest Chebyshev radius. The symbols dot and × in the subplots are the vertex candidate and the new position where the candidate needs to be pushed. The positions of the vertex candidate for each iteration and their new position are presented in the TABLE I. The regions that need to go under transformation for each iteration are also given in the table along with the Chebyshev radius for the candidate vertex. The numerical values of the vertices v are originally double precision representation but in the table we restricted the values till four decimal places due to space constraint. Starting from Figure 4 (a), for the first vertex candidate, we perturb the vertex to the position [-4.0, 1.6] T there by affecting three regions with indexes 8, 12, 13. The next subplot shows the new polyhedral regions after pertur-bation. After the 8th iteration, the subplot 4 (i) represents the final set R that is the output of the algorithm 1. In Figure 4, it is obvious from the subplots that no overlapping took place although a very aggressive perturbation has been tested for illustration. This validates one part of our work. In order to conclude on the closed loop behavior, we simulated the state trajectories for the PWA controller for the outer vertices as initial states and present the results in Figure 5. VIII. CONCLUSION In this work the analysis on the perturbation of the vertex representation has been presented for a PWA control function. The sensitivity set that preserve the closed-loop invariance in the event of perturbation has been computed. It was shown that a perturbed polyhedral partition can be constructed by treating sequentially each vertex with a higher priority on those with a small sensitivity margin.

γ v Chebyshev radius v + ∆v Θ vR(1)

  (a) 2-D Polyhedral with four regions R = ∪ 4 i=1 Ri before perturbation of the half-space representation. (b) Illustration of regions R1, R2, R3 and R4 after perturbation. Such a reconfiguration produces holes in the feasible domain that will undermine the wellpossessedness characteristics.

Fig. 1 :

 1 Fig. 1: 2-D polyhedral representation before and after perturbation on the half-space representation

  Ri) ∩ int( Rj) = ∅, ∀i, j ∈I4, i = j.(c) After perturbation with the particular configuration leading to: int( Ri) ∩int( Rj) = ∅, ∀i, j ∈I4, i = j.

Fig. 2 : 3 :

 23 Fig. 2: 2-D polyhedral representation before and after perturbation of the vertex representation

1 )

 1 Perturbations of extreme points of the feasible domain R: In the following, we aim to analyze the perturbation of vertices that represent extreme point of the set R and reconstruct the polyhedral partition R = {R 1 , • • • , R N }.

Algorithm 1 2 : 3 : 4 : 5 : 6 :%

 123456 on the states are 5 ≤ [1 0 ]x k ≤ -5 and input constraint5 ≤ u k ≤ -5. The weighing matrices Q = 1 0 0 1 , R = 1and prediction horizon of length 2 are considered in the finite time optimal control problem. Algorithm for computing the perturbed set RInput: R = ∪ N i=1 R i , i ∈ I N , V ∈ int(R). Output: R Initialization : R = R LOOP Process 1: for γ = 1 to p do Rad = [ ] for b 1 = 1 to p -γ -1 do Compute the vertex sensitivity set Ψ vb 1 Compute the sensitivity margin Υ vb 1 Rad(b 1 ) = Υ vb 1 .Chebyshev.radius() Set the quantified value for vR(1) 10:

Fig. 4 :

 4 Fig. 4: In the subplots, the polyhedral regions Ri are presented with the vertex sensitivity and invariant-vertex sensitivity sets depicted in red and green color respectively. The dot and the × in the subplots are the vertex candidate and their new positions

Fig. 5 :

 5 Fig. 5: The states trajectories for the polyhedral partition, outcome of the algorithm 1 as show in Fig 4 (i), for the vertices that lie on the boundary of the polytope.

TABLE I :

 I This table represents the vertex candidates for each iteration and their new position along with their Chebyshev radius. The last column shows the indexes of the subset of regions that are impacted by the perturbation of the vertex