Agustín Emmanuel Stahl

Gabriel Yabo

Olivier Richard

Bruno Bzeznik

Bogdan Robu
email: bogdan.robu@gipsa-lab.grenoble-inp.fr

Eric Rutten

Agustín Gabriel Yabo

Towards a control-theory approach for minimizing unused grid resources

Keywords: High performance computing, resource management, self-adaptive systems, autonomic computing, control theory

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

A. Need for autonomic administration in HPC

HPC systems are facing more and more variability in their behavior, related to e.g. performance and power consumption, and the fact that they are less predictable requires more runtime management. Some examples in HPC can be:

• uncertainties concerning actual runtime performances (e.g. execution times) compared to evaluations which were used for off-line scheduling. • variations in data access times due to e.g. more and more elaborate cache mechanisms. • variations related to the values in the data e.g. number of iterations or depth of computation depending on variables' precision. Coping with such phenomena must be done at run time, based upon measurements performed during the execution. This can be done in response to monitored information in the systems, by analysis of this data and utilization of the results in order to activate appropriate system-level or applicationlevel feedback mechanisms (e.g. informing schedulers, downclocking CPUs).

One such problem is found in the context of CiGri, a simple, lightweight, scalable and fault tolerant grid system which exploits the unused resources of a set of computing clusters. Computing power left over by the execution of a main HPC application scheduling is used to execute smaller jobs, which are injected as much as the global system allows.

B. Control theory for Autonomic HPC

Such feedback mechanisms rely on extensive monitoring and analysis, and involve decisions and their execution. These feedback loops, in the domain of Computer Science, are the object of Autonomic Computing [START_REF] Kephart | The vision of autonomic computing[END_REF], which emerged mainly from distributed and Cloud systems at IBM.

One approach in designing feedback loops is naturally Control Theory, which is extremely widespread in all domains of engineering, but only quite recently and scarcely applied to regulation in computing systems [START_REF] Hellerstein | Feedback Control of Computing Systems[END_REF], [START_REF] Litoiu | What Can Control Theory Teach Us About Assurances in Self-Adaptive Software Systems?[END_REF]. It can bring to systems designers methodologies to conceive and implement feedback loops with well-mastered and guaranteed behavior in order to obtain automated management with goals of optimization of resources or avoidance of crashes and overloads.

Different control designs have been proposed in the past, aiming to solve different classes of control problems and involving different classes of dynamical models. Classical control addresses quantitative dynamics, using continuous models based on differential equations. Discrete Event Systems concern systems where the dynamics involves a set of discrete, logical states (possibly finite), and events causing transitions: they are commonly modelled using Petri nets or finite state automata. Probabilistic aspects can be addressed with e.g., Markov Decision Processes. The control problems encountered in complex computing systems can be of various kinds, and represent a new application domain for Control Theory, for which research is still identifying and evaluating modelling approaches.

C. Contributions

This paper presents first results addressing automated resource management using Control Theory. More precisely, it attacks the regulation of the injection of jobs into a grid system, in such a way that it maximizes its utilization, by leaving only a minimum of resources unsused, while at the same time avoiding to overshoot the bounds leading to a system overload, and hence avoiding the firing of costly safety mechanisms.

Our method proceeds with the following phases: 1) analysis of the system and identification of its dynamics and the overload problems to be tackled. 2) design of a feedback controller, with P (Proportional) and PI (Proportional+Intregral) regulation, through a maximum number of jobs to be sent to the cluster, in response to the current number of jobs processed. The control objective is to maximize cluster utilization while avoiding overload. 3) implementation and experimental results, in an emulated environment, comparing the new control scheme with the previously used, more ad hoc solution. In the remainder of this paper, background is given in Section II on Autonomic Computing and its control, and on the overall Architecture of the system to be controlled, and its current, ad-hoc regulation mechanism. Analysis and modeling of the system, leading to the design of a first proportional controller, and then a PI controller, is described in Section III. Then Section IV shows experimental validation of our approach. Finally, Section V concludes and draws perspectives.

II. BACKGROUND A. Autonomic Computing and its control

1) Autonomic administration: Autonomic Computing (AC) [START_REF] Kephart | The vision of autonomic computing[END_REF] aims at making computing systems able of selfmanagement, w.r.t. self-configuration (deployment), selfoptimization (resource management), self-healing (fault tolerance) and self-protection (security). The management of system administration is automated so as to replace, as much as possible, human intervention, for motivations of facing complexity or fast response. AC has been proposed in distributed systems and particularly in the area of Cloud computing. Recently, the perspectives of self-adaptive systems and autonomic management have also been considered in HPC. AC relies on a structure of feedback loop, where a controller, separate from the system to be managed, runs in parallel to it: the well known MAPE-K loop [START_REF] Rutten | Feedback Control as MAPE-K loop in Autonomic Computing[END_REF] involves components to Monitor (through probes and sensors), Analyze (extracting relevant information from data, and take decisions), Plan (transform decisions into adaptation actions) and Execute (perform adaptation actions). All this is done using Knowledge on the system (reified representation, data-base).

2) Control-based approaches: The classical MAPE-K AC loop can be considered in the perspective of Control Theory [START_REF] Rutten | Feedback Control as MAPE-K loop in Autonomic Computing[END_REF], and its feedback loop represented in Figure 1. In this domain, a deep and long history of research and practice has been developed, applied to most domains of engineering, but only quite recently to management issues in computing systems [START_REF] Hellerstein | Feedback Control of Computing Systems[END_REF], [START_REF] Litoiu | What Can Control Theory Teach Us About Assurances in Self-Adaptive Software Systems?[END_REF], [START_REF] Berekmeri | Feedback autonomic provisioning for guaranteeing performance in mapreduce systems[END_REF], [START_REF] Abdelzaher | Introduction to control theory and its application to computing systems[END_REF]. In short, the design of control functions is based on approximated models (a perfect model is not necessary, nor is it always feasible) of the dynamics of the process to be controlled (Target System in Figure 1), in order to derive controllers with guaranteed concerning convergence, avoidance of oscillations, mastering of overshoot effects, etc. This process implies the identification of certain variables of interest in the infrastructure:

• The output, which is a measurable indicator of the state of the system. • The reference, the objective value to which we want to drive the output. • The input, the action through which the output can be modified or regulated to match the reference value. • The error, the difference between the reference value and the system's output, as a measure of deviation. • The disturbance, an external agent that affects the system's dynamics in an unpredictable way.

Through the knowledge of a system's dynamical model, control theory approaches can deliver management strategies that define how to adjust system's inputs to get the desired outputs, i.e. to control the state of the system. Traditional control solutions include Proportional-Integral-Derivative (PID) controllers [START_REF] Levine | The Control Handbook, Second Edition[END_REF]: the value of the commands to be executed is given by an equation with three terms: P proportional to the error, I involving an integration over time of its past values (i.e., a memory-like effect), D based on its current "speed" or rate of change, which takes into account possible future trends. More advanced approaches incorporate the use of optimal control theory, where management strategies are derived from the formulation of objective functions (so-called cost functions) that describe the goals of the administration loop as a mathematical expression. This scope enables multi-objective control schemes when dealing with infrastructures composed of several inputs and outputs, but requires a fine-tuning of the objective function, and a fairly accurate knowledge of the dynamical model of the system. HPC scheduling is a problem that has already been addressed by means of Control Theory in the past for specific objectives. It has been applied for achieving predictable scheduling by ensuring each job in a workflow to meet its deadline, and additionally regulating incoming jobs through admission control [START_REF] Park | Predictable high-performance computing using feedback control and admission control[END_REF], but the proposed solution assumes each job's progress can be measured by the algorithm, which is not always true in HPC environments. More recent works use model predictive control (MPC) to increase cluster utilization while minimizing slack in periodic workflows [START_REF] Ghazzawi | A control theoretic approach for workflow management[END_REF], [START_REF]Mpc vs. pid controllers in multi-cpu multi-objective real-time scheduling systems[END_REF], but they assume to count on a priori knowledge of the job's duration (that should be provided by the user), leading to a control scheme that is not robust to deviations from the analyzed workflows. In any case, the HPC scene has still plenty of room for innovation in terms of autonomy.

B. Overall Architecture of the system 1) A lightweight grid: CiGri: CiGri 1 is a simple, lightweight, scalable and fault tolerant grid system which exploits the unused resources of a set of computing clusters, a concept used in similar solutions such as OurGrid [START_REF] Cirne | Labs of the world, unite!!![END_REF] and Condor [START_REF] Butt | A self-organizing flock of condors[END_REF]. This grid is based on two software tools. The CiGri server software is based on a database and offers a user interface for launching grid computations (scripts and web tools). It interacts with the computing clusters through the Ressource Job Management System OAR [START_REF] Capit | A batch scheduler with high level components[END_REF], a batch scheduler software. This lightweight grid system is a simplified version of the general grid concept [START_REF] Foster | The Grid 2: Blueprint for a new computing infrastructure[END_REF], in particular a certain homogeneity of services and administration procedures are adopted. Also, this grid system is well adapted to address bag-of-tasks workload which is composed of lots of independent and identical tasks. The nature of this specific kind of workload arises from the need of running large-scale scientific computations with different input parameters, by means of grid computing infrastructures. An example of this implementation is MCFOST [START_REF] Pinte | Monte carlo radiative transfer in protoplanetary disks[END_REF], a 3D radiative transfer code based on Monte-Carlo method, which can usually amount to 30000 tasks with average computation times of 45 minutes per job. Typically, parametric workloads of this kind show small variability in their execution time. According to our analysis of historical data from CiGri database, distribution of computation times exhibits coefficients of variability [START_REF] Bendel | Comparison of skewness coefficient, coefficient of variation, and gini coefficient as inequality measures within populations[END_REF] that ranges from 10% to 30%, indicating negligible dispersion. Sample histograms of computation times for different campaigns are shown in Figure 2.

Jobs in CiGri bag-of-tasks are essentially treated as lowpriority tasks intended to be run on cluster's idle resources. This means that, if during their execution, the resource is requested by a local cluster user, the best-effort job is killed by the local batch scheduler and later resubmitted according to specific fault-treatment mechanisms [START_REF] Georgiou | Evaluations of the lightweight grid cigri upon the grid5000 platform[END_REF]. Additionally, the notion of best-effort means there is no QoS objective to meet, and so the problem falls outside the classical scheduling theory. As a consequence, there are aspects -such as the queued time of a job-that are excluded from the analysis. To sum up, the challenge of CiGri is to guarantee the complete execution of this scientific computations in despite of resources' volatility, in the most efficient way. This clearly implies maximizing the amount of idle resources used by best-effort jobs, without overloading any component of the infrastructure. Figure 3 presents the overall architecture of the CiGri lightweight grid with the OAR batch scheduler and the Irods storage system [START_REF] Rajasekar | irods primer: integrated rule-oriented data system[END_REF]. There are two options for job submission:

• job submission by a user, directly through OAR.

• submission of a jobs campaign through CiGri: with numerous small jobs, managed in a best-effort manner. The downloading and uploading of input data and results of the jobs is handled by iRODS, a distributed storage management system.

2) Computing infrastructure: CiGri production environment is currently deployed onto CIMENT, part of the Gricad unit 2 and one of the most powerful HPC tier-2 centers in France, located at Grenoble. It is a joint center from the Community Université Grenoble Alpes and more than 30 research laboratories from CEA, INRIA and CNRS; composed of over 6500 cores that add up to 135 TFlop/s and 28 TB of memory distributed over 12 clusters. Its resources are managed by OAR 3 , a modular batch scheduler for HPC clusters that supports integration with CiGri through a dedicated waiting queue for best-effort jobs introduced in each cluster. Even though the center is composed of heterogeneous resources, they are grouped by similar specifications (i.e. processing power) to achieve certain uniformity throughout clusters, so that resource homogeneity can be assumed.

The Gricad unit provides HPC resources to academic research communities from a wide range of disciplines: Biology and Health, Chemistry, Environment and Climate, Numerical Physics, Earth and Planetary Sciences, and Distributed Computing [START_REF] Biscarat | Synergy between the ciment tier-2 hpc centre and the hep community at lpsc in grenoble (france)[END_REF]. As an example, the center has been extensively used in the ATLAS particle detector experiment [START_REF] Aad | The atlas experiment at the cern large hadron collider[END_REF], one of the seven experiments performed at the LHC (Large Hadron Collider) particle accelerator, and one of the two involved in the discovery of the Higgs boson.

3) Administration problems considered: The current, ad hoc, solution to manage job submission is based on a tap mechanism implemented in the Runner component of CiGri. It maps jobs from the bag-of-tasks on the available resources of the cluster with the following criteria, The algorithm cyclically submits rate number of jobs to the cluster, which increases at every iteration. Note that, in each cycle, the algorithm waits for the completion of all submitted jobs, but taking into account several failsafe mechanisms intended to protect the infrastructure. As an example, the loop timeouts when job's walltime is exceeded. Other more complex scenarios are also considered by the algorithm, which might involve cluster blacklisting depending on the severity of the problem, requiring administrator intervention to regularize the situation.

Under the explained behavior, jobs are submitted onto a cluster only when its waiting queue is fully empty. In practice, this behavior yields situations where the cluster is being underused (or not used at all) in spite of the existence of remaining jobs in the CiGri bag-of-tasks. This occurs when, between cycles of the algorithm, there is no queued jobs.

Other side problems that can occur are:

• Cluster overload, when too many jobs are submitted, and can not be served by the cluster resources: a stress factor is defined, between 0 and 1, and sent back to CiGri, so that it avoids sending jobs to a cluster for which it is beyond 0,8. • Irods overload, when too many requests are submitted.

• Particular storage resource overload, concerning access to an individual storage server. As a result, the way CiGri handles jobs submission to the waiting queue turns out to be a major factor in the overall performance. Maximizing the exploitation of idle resources, then, requires an improved strategy in this regard.

III. ANALYSIS AND MODELING

As said before, in this paper we focus on the problem of minimizing the unused resources of a grid while avoiding overloading. To do this, we followed this methodology, 1) informal analysis of the system in order to extract the feedback loop: identify sensors and actuators (which are the inputs and outputs of the process) and formulate the control objective. 2) open loop testing to approximate an analytic model, by measures in the absence of regulation, in order to acquire some parameters of the system behavior. 3) design of the control law at the heart of the Autonomic Manager: in this case simple P and PI regulators.

A. The considered administration loop

Figure 4 sketches the process detailed in Section II-B3, highlighting elements involved in our administration loop:

• The Cluster is the main component: we want to control the "pressure" it undergoes (risk of overload). • The Resource Job Management System (RJMS) is done by OAR which plans execution of jobs on the cluster. • The "Runner" module : submits CiGri jobs as presented in Section II-B3. Moreover, Figure 4 shows in green the feedback loop we intend to construct. Our intention is to regulate around a fixed number of jobs in the queue waiting to be executed. At runtime, we cyclically measure the number of jobs in the queue and compare this value with a reference value of number of jobs in the queue. Based on this difference, our administration loop (the controller) will automatically decide how much to open the tap in order to send more or less CiGri jobs through the Runner to the Cluster. This type of control will allow us to maximize the number of resources utilized by the cluster without overloading it.

We consider that users can also send jobs to the Cluster directly through OAR, which represents an unknown and nonmeasurable disturbance to our system. These jobs have a nonnegligible impact on the cluster charge, therefore on its job treatment speed, and finally on the number of jobs left in the queue.

Figure 5 presents the feedback loop from a Control Theory perspective. We can notice on this figure the actuator (the tap), the sensor which measures the number of jobs in the queue, as well as the external perturbations which act on the system: the users jobs sent directly through OAR.

Since the sensor measuring the number of jobs in the queue was not present on our system, we had to construct it. In order to do this, we placed in the core of the Runner module the instructions detailed in Code 1. Line 1 gets the number of jobs on a cluster, and Line 3 gets the jobs in the queue and therefore counts their number. Since the administration loop is incorporated into the main cycle of the Runner, it will also run periodically and with the same frequency. Although this cycle time might vary during the execution depending on the amount of workload the Runner is under, it is lower bounded to 15 seconds. In practice, there are no significant deviations from this bound, so we assume it to be constant.

Another key factor in the behavior of the loop is the selection of the reference value for the waiting queue, in which there is a clear trade-off. A lower number of jobs in the waiting queue might lead to cases with free resources in the OAR cluster, but no available jobs to run, which translates into under-usage of idle resources. This effect can be even worse in the presence of disturbances: user jobs not managed by CiGri, when finished, release a big number of resources that can be potentially used by best-effort jobs, so having a considerable amount of waiting jobs ready to be launched is a good way to deal with this uncertainties. However, an excessively large number of queued jobs can certainly overload the OAR scheduler. For this reasons, the selection of this value is not straightforward: to our understanding, it should be dynamically adjusted to meet the administration loop's objectives in an optimal way. For this first approach, we manually adjusted the reference to 40 waiting jobs, as this value delivered reasonable results throughout our experiments.

B. Open loop testing for model identification

In order to have an idea about the behavior of the system, we started with some open loop tests, that is to say the system is left free to evolve while only monitoring its behavior. We test the behavior of the system once when resource number is fixed (jobs are varying) and once when the initial number of jobs is fixed (number of available resource is varying).

For the experiments, we used workflows composed of dummy jobs with distribution of execution times similar to those analyzed in the previous section (Figure 2) to ensure a representative scenario. In particular, the mean execution time for this experiment was 30 seconds.

The evolution of the queue when the initial number of jobs is fixed (200 jobs) and when the number of resources varies is given in Figure 6. As expected, the number of available resources has an impact on the evolution of the number of jobs in the queue: the larger the number of resources, the steeper is the slope of the queue drain. After testing the queue behavior when the number of resources is fixed and with varying initial number of jobs in the queue, we obtained a relation between the slope of the draining queue and the number of available resources, as depicted in Figure 7. Moreover, we can notice a linear evolution of the slope towards resource number.

C. A Proportional controller

As a controller in Figure 5, we use a proportional one written: tap = K p * error, where K p is the gain of the controller. In this case, the error between the number of jobs set as reference and the actual number of jobs is multiplied by a fixed gain, then sent to the tap. The choice of this gain is not straightforward as a small value will imply a slow filling of the cluster, while a large value could lead to oscillations of the queue size, which at the end can worsen the performance of the system. In our case, for a fixed number of resources (see Figure 6), we approximate the system behavior as a second order differential equation expressed through its Laplace transformation (a well documented method in control theory [START_REF] Levine | The Control Handbook, Second Edition[END_REF]) as,

H(p) = 1 - K p (1 + T 1 p)(1 + T 2 p) ,
with T 1 = 125 and T 2 = 235. The values of T 1 and T 2 are computed using the Identification Toolbox in Matlab or the well known Cadwell technique [START_REF] Levine | The Control Handbook, Second Edition[END_REF]. Based on the simulations on the identified (approximated) we choose a Proportional controller which is not very aggressive to the system and does not produce overshoot and instability. Using Matlab, we find a suitable value of K p = 0.713. Another gain can be used and the regulation will still work but the system might experience other side problems: lower values can lead to very slow response to disturbances, meaning that the algorithm may take more time to control the queue length in the presence of local user's jobs. By contrast, if the gain is very large, the system can became unstable, an undesired property of dynamical systems that causes the queue length to grow unbounded instead of remaining steady as desired.

D. A PI controller

In a second stage, we designed a PI controller by extending the obtained P controller from previous section to accomplish integral action. In other words, the new control law as a function of time becomes,

tap(t) = K p error(t) + K i ∫ t 0 error(τ )dτ.
This expression describes the general form of a PI controller in continuous time, but the implementation of such controller requires a time-discrete control law, which can be done by approximating the integral of the error as a cumulative sum of the previous values of this error function,

tap(t) = K p error(t) + K i t ∑ k=0 error(k)∆t k ,
where ∆t k corresponds to the cycle time of the main loop in the Runner module at time k. This expression shows the main effect of PI controllers: a control action that depends not only of error values computed at present time, but also of error values computed in the past. In practice, it is not necessary to store the value of the error function at each cycle as long as the cumulative error is kept, The proportional gain K p is tuned as in the P controller. The contribution from the integral term depends on the cumulative error computed at each time instant, but also on the amount of time the error persisted. This effect should be taken into consideration when tuning K i parameter to avoid overshooting in the time response of the controller. In the control theory framework, overshoot is the effect in which the controlled variable exceeds its target, a common issue that occurs when cumulating "too much" in the integral term (errcum for this case). A frequent workaround to this problem is to implement an anti-windup scheme [START_REF] Azar | Design and modeling of anti wind up pid controllers[END_REF]. For this particular case, we imposed lower and upper thresholds on errcum (of 20 and -20 respectively) to limit the effect of the integral action term. Another key characteristic of the integral action is that it accomplishes null steady-state error, in contrast with plain P controllers. This basically means that the amount of jobs in the queue will asymptotically tend to the desired value (and so the difference between this two variables will be equal to zero). In this Section we validate our approach on the real system. The behavior of the system without control is depicted in Figure 8, the P controller is considered in Figure 9 and the PI one can be seen in Figure 10. The behavior of the system through the experiments is characterized by the waiting queue (upper graph in Figures) and the running jobs (lower graph in Figures). The experiment consisted of a 400 jobs campaign running on a 12 resources cluster. We performed this experiment 10 times per scheme and computed the average performance, depicted in Table I. As in the open loop analysis, we used the same dummy jobs with mean execution time of 30 seconds and small variance, based on real workflows previously processed by CiGri. As we can see, the use of a controller diminishes considerably the completion time of the campaign. This leads to an average improvement in cluster utilization of 5% with the simplest control algorithm, and of 8% in the case of the PI controller. The usage upgrade is reflected in a significant reduction of the total time: approximately 10% faster completion time was achieved for the same campaign. The cluster usage in an interval [t 0 , t f ] was computed using the following expression,

IV. EXPERIMENTAL VALIDATION

U sage[%] = 1 T t f ∑ k=t0 r(k)∆t r max , (1)
where r(k) is the number of resources used by best-effort jobs at time k and r max the total amount of resources in the cluster (constant, in this case). The total time of the experiment is computed as T = t f -t 0 . Moreover, for further evaluating the performance of the solution, we tested the robustness of our control algorithm. In order words, we analyzed the controller performance when dealing with unknown external factors. Specifically, we stressed the system with external disturbances by submitting higher priority jobs to the cluster, in order to dynamically vary the amount of available resources. The results of the controlled system for this scenario are shown in Figures 11 and12. The periods when the cluster is unutilized are also diminished, even though the system is not able to measure the amount of available resources. The latter varies randomly by occupying resources in a range of 0-12 equiprobably, making the expectancy of resource availability equal to 6 (half of the total resources), so the completion time of the campaign is expected to be twice as much as that of non-disturbed experiments. However, the usage can be still analyzed as in 1 by computing r max in terms of the time-varying function r available (k),

r max = 1 T t f ∑ k=t0 r available (k)∆t.
Needless to say, computing the cluster usage is equivalent to compute the ratio of the area below the used resources curve to the area below the available resources curve. From the experiments, we observed an average cluster usage of 79% in the presence of disturbances using the P I controller.

It is noteworthy that the behavior of the system may vary when dealing with workflows other than those used for experimentation. However, as one of the advantages of control theory approaches, the controller will certainly ensure the waiting queue to converge to the reference value in any scenario, in despite of this variations.

V. CONCLUSION AND PERSPECTIVES

1) Results: we presented preliminary results addressing autonomic administration in HPC systems, more particularly automated resource management using techniques from Control Theory. We focused on a controller that maximizes cluster utilization while avoiding overload. For this, we performed a control-oriented analysis of the system involving the identification of its dynamics, taking into account the overload problems to be tackled. Further on, we proposed two feedback controllers based on P (Proportional) and PI (Propor-tional+Integral) regulation; we implemented the approach and validated it through experimental results. Comparing with the previously used, more ad hoc solution, the new controller proved to be more efficient in terms of usage of idle resources. The main contribution of this work is a proof of concept. We showed, for a particular case study, the benefits of rethinking computing infrastructures as dynamical systems, to allow the use of the control theory toolset in order to solve specific problems and improve performance measures of computing systems. In past works [START_REF] Ghazzawi | A control theoretic approach for workflow management[END_REF], [START_REF]Mpc vs. pid controllers in multi-cpu multi-objective real-time scheduling systems[END_REF], the identification process was performed taking into account several input and output variables of the infrastructure, which leads to more comprehensive models intended to be used for multi-objective control. However, the obtained linear models lack the ability to reflect several non-linear behaviors and variable constraints of the real system, since its accuracy is limited to a specific region of operation. Thus, the performance improvements are constrained to this region, and the controller fails to ensure the desired performance and stability objectives for all possible situations. Our solution do not seek to replace the scheduler but to complement it, which simplifies the whole approach, simultaneously ensuring robustness to variations in the analyzed scenarios.

2) Perspectives: We have ongoing work on considering other problems of overload concerning the storage architecture. On the control side, we plan to consider more elaborate techniques which made their proof when applied to other computing systems, e.g. adaptive [START_REF] Cerf | Adaptive feedforward and feedback control for cloud services[END_REF], discrete [START_REF] Berthier | Logico-numerical control for software components[END_REF], or stochastic. Another promising research direction is to adopt an integral point of view of the infrastructure. In practice, the running module manages each cluster submissions separately. A centralized administration loop could provide an improved strategy towards a unified framework for autonomic grid management.

Fig. 1 .

 1 Fig.1. Block diagram for a simplistic control loop[START_REF] Abdelzaher | Introduction to control theory and its application to computing systems[END_REF].

FrequencyFig. 2 .Fig. 3 .

 23 Fig. 2. Campaign histograms for different types of workloads handled by CiGri.

Algorithm II. 1 :

 1 JOB SUBMISSION( ) main rate ← 3 increase f actor ← 1.5 whilejobslef tinthebag -of -tasks do        launchrateamountof jobs whilejobsrunning > 0 and not(timeout) do sleep rate ← min(rate * increase f actor, 100)

Fig. 4 .

 4 Fig. 4. Feedback loop for the CiGri cluster

Fig. 5 .

 5 Fig. 5. Diagram of the model-based feedback control loop.

1

  cluster_jobs = cluster.get_jobs() 2 temps = Time.now 3 jobs = cluster_jobs.select{ |j| j["state"] == "Waiting" } 4 file = File.open("/home/user1/Nb_jobs.txt", "a+") 5 file << "#{jobs.length};#{temps.to_f}\n" 6 file.close Listing 1. Sensor measuring the number of jobs in the queue

Fig. 6 .

 6 Fig. 6. Number of jobs in the queue for varying resource numbers and fixed job campaign of 200 jobs. Campaign start time among experiments is synchronized to the same time instant t = 80s for better comparison of the responses.

Fig. 7 .

 7 Fig. 7. Slope evolution towards available resources

  err = job_reference -queue_load # Compute current error errcum = errcum + err # Compute cumulative error tap = kp * err + ki * errcum * dt # Compute control action Listing 2. Pseudo-code for the PI implementation

Fig. 8 .

 8 Fig. 8. Open loop behavior (i.e. original algorithm).

Fig. 9 .Fig. 10 .

 910 Fig. 9. Closed loop behavior with the P controller.

Fig. 11 .

 11 Fig. 11. Test in presence of perturbations in the amount of available resources (40 jobs reference) for a 200 jobs campaign.

Fig. 12 .

 12 Fig. 12. Test in presence of perturbations in the amount of available resources (40 jobs reference) for a 400 jobs campaign.

https://gricad.univ-grenoble-alpes.fr/

http://oar.imag.fr/


Michael Wessely
email: michael.wessely@inria.fr

Nadiya Morenko
email: n.morenko@xmlab.org

Juergen Steimle
email: jsteimle@cs.uni-saarland.de

Michael Schmitz
email: m.schmitz@xmlab.org

Interactive Tangrami: Rapid Prototyping with modular paper-folded electronics

Keywords: personal fabrication, modular fabrication, building blocks, tangibles, design tool, sensing technologies, printed electronics

Prototyping interactive objects with personal fabrication tools like 3D printers requires the maker to create subsequent design artifacts from scratch which produces unnecessary waste and does not allow to reuse functional components. We present Interactive Tangrami, paper-folded and reusable building blocks (Tangramis) that can contain various sensor input and visual output capabilities. We propose a digital design toolkit that lets the user plan the shape and functionality of a design piece. The software manages the communication to the physical artifact and streams the interaction data via the Open Sound protocol (OSC) to an application prototyping system (e.g. MaxMSP). The building blocks are fabricated digitally with a rapid and inexpensive ink-jet printing method. Our systems allows to prototype physical user interfaces within minutes and without knowledge of the underlying technologies. We demo its usefulness with two application examples.

INTRODUCTION

Fabricating tangible user interfaces has been made rapid with personal fabrication tools like 3D printers, which can create interactive objects in just a few hours [START_REF] Schmitz | Capricate: A Fabrication Pipeline to Design and 3D Print Capacitive Touch Sensors for Interactive Objects[END_REF]. However, these objects are created most often out of one piece which poses a challenge in the design process. If just specific parts of a design have to be changed, it is hard for the maker to perform local changes and reuse individual segments of an object without re-creating the full object from scratch. This is particularly problematic in light of frequent design iterations, which are common in typical design processes. Requiring the maker to produce several intermediate prototypes is lengthy and results in unnecessary waste and time overflow.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). Prior work has proposed approaches for lowering the fidelty of intermediate prototypes [START_REF] Mueller | WirePrint: 3D Printed Previews for Fast Prototyping[END_REF] or creating light-weight paper prototypes [START_REF] Olberding | Foldio: Digital Fabrication of Interactive and Shape-Changing Objects With Foldable Printed Electronics[END_REF]. While this has improved the process, it still requires each object to be built from scratch. Other work lets the user segment or replace certain geometric parts of model, but do not support interactive I/O components [START_REF] Mueller | faBrickation: Fast 3D Printing of Functional Objects by Integrating Construction Kit Building Blocks[END_REF][START_REF] Thijs | Grafter: Remixing 3D-Printed Machines[END_REF] We present Interactive Tangrami, functional paper-folded building blocks (Tangramis) that enable makers to prototype functional Tangible User Interfaces (TUIs) rapidly and at low cost. Each building block can be reused for other projects or can be replaced during prototyping. The Tangramis are fabricated with a rapid ink-jet printing method and can be visually customized by the user.

UIST '18 Adjunct

In the following we will present the fabrication of interactive Tangramis and a digital design toolkit that lets the maker plan and fabricate the interactive object. We show the usefulness of this system with two demonstrations.

FABRICATION OF INTERACTIVE TANGRAMIS

We will present the paper folding technique for tangramis and proceed to propose functional circuit patterns that can be embedded inside tangramis to add interactivity.

Tangrami

Tangrami folding is an established art practice and is based on simple construction blocks with pouches and plugs that can be attached into each to connect them. A description of the folding technique can be found at [START_REF] Taubner | Tangrami pour plieurs avances: Plier et assembler du papier[END_REF].

Embedding Interaction

We propose a set of circuit patterns for tangramis that can embed various input sensing and visual output methods. Currently, our system supports touch sensing, embedding of electrical components (e.g. LEDs) and actuated tangramis. An overview can be seen in figure 1.

For printing the conductive patterns we use an Epson ET-2550 ink-jet printer and Mitsubishi's conductive silver ink (NBSIJ). The actuated tangrami gets taped with a shape-memory polymer (polyethelene) that expands when heated above 90 ○ C. While the underlying paper keeps its shape under higher temperatures, the tape bends the tangrami while expanding by up to 90 ○ . We covered the heating structure of the tangrami with Workzone PE Tape and removed one layer of paper on the back side for less resistance while bending.

Demo Reception

UIST'18 Adjunct, October 14-17, 2018, Berlin, Germany

Connecting Tangramis

Connections are formed by plugging a tangrami into another one. We found that a tangrami can be rotated up to 45 ○ before a shortcut appears. We designed the silver traces to be large especially at the folds in order to increase their robustness and better connection between two tangramis.

We recommend for permanent installations of a tangrami object to use conductive tape between two segments. Gluing tangramis together once the artist is finished with her object is a common practice among professionals.

DESIGN TOOLKIT

We found through several design iterations with artists that placing and routing the functional components makes the fabrication of an interactive object difficult. Also, programming a mobile micro-controller and sending the interaction data to a computer required a trained expert. Thus, we developed a design toolkit that supports artists in creating an object with interactive tangramis and prototyping interactivity.

Figure 2 shows the design tool-kit. The artist can select from a library of functional tangramis and place them on the working area. Pin icons from a controller and a tangrami can be connected by drawing wires (green). The tool can connect and configure an Arduino Uno controller and stream the received interaction data via OSC protocol to the system. When the artist finished the planing phase, the toolkit generates all circuit patterns of the implemented tangramis and exports them as a pdf file for printing.

APPLICATION EXAMPLES

In the following we illustrate two application examples that show the usefulness of tangrami interfaces.

Demo 1 -Interactive Dress

We build a dress out of tangramis that contains a set of LEDs at the collar and a set of touch tangramis that can sense several body postures. Different body postures invoke an audio-visual response from the dress which helps the wearer in non-verbal communication. The piece has been exhibited at the Hager Award at the Academy of Fine Arts, Saarbrücken and the Saarland museum in Berlin, Germany.

Demo 2 -Paper Pet

We implemented a versatile paper pet out of 4 functional tangramis. The two head tangramis are customized with an individual texture. The cow head can sense being cuddled with internal touch sensors and responds with a moo-sound. The cow tangramis can be removed and replaced with a lion head that contains red LEDs as eyes. The LEDs can be turned on to leave ambient notifications in a room.

CONCLUSION

We presented Interactive Tangrami, modular paper-folded construction blocks that contain various input sensing and visual output capabilities. We proposed a design toolkit that supports artists in creating functional TUIs and demonstrate its usefulness with two application examples.

Figure 1 .

 1 Figure 1. Ink-jet printable circuit patterns for Tangrami. 2-Pole wires transport signals through the object to capacitive touch tangramis, tangramis that can contain electrical components and tangramis that can be actuated with shape-memory polymer. Each side of a tangrami can be electrically isolated or connected.

Figure 2 .

 2 Figure 2. Digital Interface for planing a tangrami UI. The tool generates the circuit patterns and manages communication with the controller (Serial) and Application prototyping environments (e.g. MaxMSP) via OSC.

Figure 3 .

 3 Figure 3. We implemented a tangrami dress (a) and a paper pet (b) with a replaceable head (c).

ACKNOWLEDGMENTS

We thank Theophanis Tsandilas for the valuable help. This work was supported by the European Research Council (ERC) grant 321135 CREATIV and European Union's Horizon 2020 research and innovation program (grant agreement No 714797, StG Interactive Skin). Demo Reception UIST'18 Adjunct, October 14-17, 2018, Berlin, Germany