Keisuke Kuroyanagi

André Seznec
email: seznec@irisa.fr

Service Value Aware Memory Scheduler by Estimating Request Weight and Using per-Thread Traffic Lights *

The memory controller has become one of the performance enabler of a computer system. Its impact is even higher on multicores than it was on uniprocessor systems.

In this paper, we propose the sErvice Value Aware memory scheduler (EVA) to enhance memory usage. EVA builds on two concepts, the request weight and the per-thread traffic light. For a read request on memory, the request weight is an evaluation of the work allowed by the request. Per-thread traffic lights are used to track whether or not in a given situation it is worth to service requests from a thread, e.g. if a given thread is blocked by refreshing on a rank then it is not worth to serve requests from the same thread on another rank.

The EVA scheduler bases its scheduling decision on a service value which is heuristically computed using the request weight and per-thread traffic lights. Our EVA scheduler implementation relies on several hardware mechanisms, a request weight estimator, per-thread traffic estimators and a next row predictor.

Using these components, our EVA scheduler estimates scores to issue scheduling decisions.

EVA is shown to perform efficiently and fairly compared with previous proposed memory schedulers. For the memory scheduling competition, we submit EVA to Delay and PFP tracks and EVA-E (EVA with optimisations for EDP) to EDP track. Total delay is 2975 ×10 7 , EDP value is 19.79 and PFP value is 2842 ×10 7 .

INTRODUCTION

The performance impact of scheduling requests on main memory has been increasing over the last few years especially with the advent of multicores and multithreaded processors. Smart memory controllers scheduling policies have now become of major importance.

Several memory scheduling policies have been recently proposed.

Some of these methods propose prediction strategy [START_REF] Stankovic | Dram controller with a complete predictor[END_REF][START_REF] Xu | Prediction in dynamic sdram controller policies[END_REF]. They predict whether an opened row should be closed or not, which row should be speculatively activated and so on. These methods mainly focused on improving the row hit rate in order to minimize accesses latency and maximize throughput. However, requests issued from multiple threads disturb the predictability of the tracked phenomena and induce a very complex request behavior. To effectively handle multiple cores and threads, some recent methods are thread aware [START_REF] Kim | Atlas: A scalable and high-performance scheduling algorithm for multiple memory controllers[END_REF][START_REF] Kim | Thread cluster memory scheduling: Exploiting differences in memory access behavior[END_REF]. These methods try to maximize memory throughput while not impairing fairness or vice-versa.

Our proposition, the sErvice Value Aware memory scheduler (EVA), takes scheduling decisions based on an evaluation of the potential performance benefit or cost of servicing the requests. It computes this service value, based on two concepts, the request weight and the per-thread traffic light. For a read request on memory, the request weight is an evaluation of the quantity of work before the next read request. Per-thread traffic lights are used to track whether or not in a given situation it is worth to service requests from a thread, e.g. if some request is blocked for a given thread then it is not worth to serve requests from the same thread even when possible. Additionally, EVA uses per-thread next row prediction for speculative activation and some other advanced techniques. Our experiments indicate that EVA performs efficiently and fairly compared with previous proposed memory schedulers.

The remainder of the paper is organized as follows. First, we present a design overview of our EVA memory scheduler in Section 2, including the request weight estimator, the per-traffic lights and the next row address predictor. Section 3 describes the EVA memory scheduler algorithm. Section 4 introduces the variations of the scheduler targeting the different tracks of the memory scheduling competition. Section 5 presents evaluation results. Finally, Section 6 concludes this paper.

DESIGN

Overview

Figure 1 illustrates the general principle of the EVA memory scheduler. EVA uses a request weight estimator, per-thread traffic lights and a next row predictor. These components are described below. Information provided by these components are used by the scheduler to decide which command should be issued next.

Request weight estimation

General principle

For deciding that a request should be issued or not, we rely on the new concept, called request weight.

For a request R, we define its request weight as the quantify of useful work from the relevant thread that can be executed after servicing R and without servicing any subsequent request from the same thread. The example in Figure 2 illustrates our general intuition: six read requests R11-R14 for Thread 1, and R21-R22 for Thread 2 R12, R13, R14 arrived 5 cycles after the prior request while R21 arrived between R11 and R12, and R22 arrived 1000 cycles after R21. In this situation, R21 should be given priority even if R11-R14 are row hit requests because it allows to trigger more useful work than servicing R12.

Unfortunately the request weight cannot be precisely known, even at runtime. Therefore it has to be estimated. In our proposal, we differentiate two situations 1) If at run-time, when the next memory read request from the same thread after request R arrives after servicing R then we use the number of cycles after this servicing as the request weight for R. 2) Otherwise, i.e. R is still waiting for execution, the weight is calculated as the number of instructions separating R from the following memory read request (this number is available from the instruction sequence number in ROB).

Some previous proposals like ATLAS [START_REF] Kim | Atlas: A scalable and high-performance scheduling algorithm for multiple memory controllers[END_REF] or Thread Cluster Memory Scheduling [START_REF] Kim | Thread cluster memory scheduling: Exploiting differences in memory access behavior[END_REF] change the thread priority depending on the behaviour of each thread. However, EVA tracks the behaviour of each individual request and changes thread priority more quickly. Our weight estimation is independent from the behavior of the other threads and it can be computed easily provided that instruction sequence numbers and thread numbers are forwarded up to the memory scheduler.

Request weight estimator

To utilize request weight estimation for scheduling, this Figure 3: Updating method of per-thread traffic lights.

estimation must be predicted in most cases, i.e. when the subsequent request has not been already sent by the processor. Estimated request weights are provided by the request weight estimator that is directly derived from the ITTAGE [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF] predictor, a state-of-the-art indirect branch predictor.

Table 2 shows the configuration of this estimator. 12-bit entry values are used as request weight, the maximum value (M AX V ALU E) means equal to or greater than that value. We use ten logical tables T0-9. Among them, T1,2, T3-5, T6,7, T8,9 are severally sharing one physical table, that is to say, there are five physical prediction tables in this estimator. As history , we use 1 bit from the program counter and 1 bit from the DRAM row number and manage them as per thread PC and row histories. Note that we use relative short histories to accesses T0-5, the main objective being to increase the associativity of the estimator. On the other hand, longer histories are used to access T7-9 to track request patterns that change their behavior depending on the execution history. There is a much larger number of hard-to-predict behaviors than for branch prediction. Therefore, we employ blacklist filtering method [START_REF] Yasuo | Revisiting Local History to Improve the Fused Two-Level Branch Predictor[END_REF] to track such requests and to avoid useless updating. This filtering consists of 64-entry 16-way set associative table.

The weight estimator provides the predicted request weight as soon as the memory request arrives.

The estimated value is overwritten by small weight if its confidence is low to keep away from falsely predicting large weights. This value is stored in the read request queue. After the next request arrives, first, the actual request weight is calculated as mentioned above. Then, the request weight estimator is updated with the calculated weight. Predicting precise weight is difficult and useless; therefore, we consider the estimation as correct when actual value * 0.5 -1 < estimated value < actual value * 1.5 + 1 and we update prediction table with (estimated value + actual value) ÷ 2.

Per-thread traffic lights

On a multicore, requests from the different threads interfere. In particular, a request is unlikely to allow substantial progress on the execution of a thread if a prior request from a thread is blocked by a rank refreshing or the channel servicing write memory requests.

To track such situations, we introduce the per-thread traffic light. A per-thread traffic light is a one-bit flag that indicates whether requests from the thread are worth servicing or not.

This status is updated at the beginning of every DRAM cycle as shown in Figure 3. First, for all threads, EVA checks if there are read requests that are related to a refreshing rank and raise a refreshing flag for such threads. Then, EVA checks if there are read requests that are related to write draining channel and raise a write drain flag for such threads. Finally, the ORed value of all per-thread flags is used as the per-thread traffic lights. A raised flag, which indicates the light is red, means that processing read requests from the thread is useless. EVA changes scheduling priority based on per-thread traffic lights to maximize execution performance. Details of scheduling strategy are described in Section 3.

Next row prediction

For speculative activation, EVA implements a next row prediction method that predicts the channel, the rank, the bank and the row of next read request. In our proposal, EVA uses a per-thread next row prediction method based on ITTAGE. Using an ITTAGE derived next row predictor can be effective, essentially because a row features a large number of memory blocks.

For accessing the tables of the next row predictor, we privilege row history on PC history because the behavior of target address is tend to be related to memory address stream rather than to instruction address stream. Predicted rows with high confidence are used for speculative activation. It should be noted that memory controller often have to handle requests from multiple threads at the same time; this makes it difficult to decide which row should be opened. To deal with this issue, we use information of request weight and traffic lights to choose which row should be activated. Details of speculative activation method are described in Section 3.4.

Bus utilization tracking

Request weight sometimes cannot be well estimated because of initial misses, unpredictability behavior or capability limitation of the estimator. In such situations, performance and fairness can be greatly impaired.

To manage these issues, EVA tracks bus utilization for each thread and uses it as a global index of priority. We use the following heuristic similar to the bandwidth allocation method proposed by J.Turner [START_REF] Turner | New directions in communications (or which way to the information age?)[END_REF]. Bus utilization is measured by employing per-thread tickets.

Every N U M CORES ×T DAT A T RAN S ×6 cycles, each thread get one ticket and when read request is issued, the thread pays one ticket. EVA decides request priority also depending on how many tickets the thread has.

Information used for scheduling

EVA maintains some information for each thread, each channel, each rank and each bank.

For each thread, we maintain a read request counter, a thread weight, an oldest request pointer, a latest request pointer, a traffic light, ticket numbers, information for request weight estimator and information for next row predictor. The thread weight is the sum of weights of the waiting requests from the thread.

For each channel, we maintain a per thread read request counter, a 2-bit counter that indicates write drain state, and a last refreshed rank.

For each rank, we maintain a read request counter, a write request counter, a per thread read request counter, a rank weight, a activation history and a last refresh cycle register. Rank weight is sum of the request weights that are related to the rank. The activation history consists of four counters that record the cycle value when activation commands are issued to track how many activations are issued in tF AW . The last refresh cycle register records the cycle value that last refresh command was issued.

For banks, we maintain a 2-bit preactivated flags and a read request counter.

Managing the information

issuing activation command

The oldest entry of activation history for the rank is replaced with current cycle value.

issuing refresh command Last refresh cycle of target rank is replaced with current cycle value.

SCHEDULING METHOD

We assume that the memory scheduler enforces the refreshing on deadlines if needed as well as it enforces the respect of the semantics, i.e. if a read request addresses a block to be written then the write is performed before the read. Apart these cases, EVA estimates if DRAM commands is worth to be launched. Then to select the issued command, EVA uses the priority order illustrated in Table 3 Priority requests are decided as shown in Algorithm 1. Below, we describe our algorithms to estimate whether commands are worth to be launched or not.

Algorithm 1 Deciding priority read requests.

if thread value ≥ M AX V ALU E then priority ← true end if if tickets ≥ M AX N U M T ICKET S -8 then priority ← true end if

Write requests

On every cycle, EVA checks whether each channel should switch to the write drain mode through Algorithm 2. Three water marks(HI W M , M D W M , LO W M ) and three write drain levels (DRAIN ST RON G, DRAIN W EAK, N OT DRAIN ) are considered. DRAIN W EAK is a write drain mode that can be interrupted by any refreshing or priority request. When there are no rows referred by more than three requests, EVA exits DRAIN W EAK mode.

Once EVA gets into the write drain mode, it follows the simple way to process write requests until it leaves from the write drain mode. First, EVA tries to serve the row hit requests. Then, EVA opens the row that is demanded by the largest number of write requests. The EVA scheduler tries to issue refresh commands in advance at intervals of T REF I ÷ 2 cycles. However, refreshes should not be given always priority. In some cases, the scheduler had better wait for requests even though the rank has nothing to do. First, we try to distribute the refresh over the whole refreshing interval. Second, write draining has priority over refresh. Third, if the number of writes to the rank is high then refresh is delayed in order to allow future write draining and finally if there is a high priority thread, refresh should also be delayed.

Algorithm 2 Checking write drain mode

HI W M ← W Q CAP ACIT Y -5 M ID W M ← HI W M -8 LO W M ← M ID W M -8 if write drain = N OT
Algorithm 3 illustrates the precise algorithm implemented in our proposal.

Algorithm 4 Scoring read requests

score ← 0 if traf f ic light = GREEN then score ← 4 end if if is f rom max value thread() then score ← score + 4 end if if is oldest in thread() then score ← score + 1 end if if thread.read count = 1 then score ← score + 2 end if

Read requests

EVA tries to serve read request on every cycle unless the channel is in the write drain mode or a refresh command is issued.

First, EVA computes a score for each issuable request as illustrated in Algorithm 4. Each item in the algorithm favors some particularity of the request: the thread with GREEN traffic light, the thread with the maximum sum of request weights, oldest request in the thread and only one remaining request from the thread.

Based on this score, EVA looks for the candidate column read, activate and precharge command that has the highest score among the same type commands.

Among the candidate commands, EVA issues the one with the highest score. When several candidates have same score, activate commands take precedence over precharge commands. If there are no more requests for the accessed row then EVA issues an auto precharge command at the same time as dispatching a column read command.

Speculative activation

Algorithm 5 determines which row EVA will be activated speculatively among the next predicted rows with high confidence.

First, the thread status is checked in order to determine if the traffic light is green and if there are not more than two pending requests, because it would take a long time to serve the next request if the traffic light is red or if many requests are pending. Then, the rank status is checked to determine if there are not any requests for the rank and if the rank is not preactivated.

In addition, EVA tests the constraint on parameter tFAW. At most four activation commands can be issued in a tFAW interval. Therefore as speculative activation has very low priority, EVA only launches speculative activation if at most two activation commands are already inflight in that interval. Then for each candidate, EVA computes a score based on the last request value of the thread and the thread read request counter, then EVA chooses the address that has the lowest score, which is the most likely to be used first. The selected row is speculatively activated if the value of P REACT CT R, which is signed 6-bit saturated counter, is higher than the threshold. This counter shows global confidence of speculative activation. P REACT CT R is incremented if the selected row is used; otherwise, three is subtracted from this counter value. The EVA scheduler described in the previous sections is submitted to both the performance track and fairness track. By construction, the EVA scheduler tries to favor the requests with high quantity of work through the use of the request weight estimator, while the use of bus utilisation tracking enables some fairness in the access to the DRAM.

For the energy-delay product track, we present a slightly modified version of EVA, that targets the energy-product metric that will be used to rank the proposals at the competition.

Energy-Delay Product track

DRAM power consumption is a limited part of the power dissipated by the system. Therefore our experiments showed that instead of trying to manage power in the DRAM, focusing on minimizing the execution time of the slowest thread was the best strategy to minimize the energy-delay product metric.

We use an extra counter for each thread to monitor the execution progress by adding all the request weights. EVA use this value to compute read request scores and deduces request weights. We call this scheduler EVA-E (EVA with "optimizations" for Energy-delay product track).

Storage Budget

Table 4 illustrates the storage budget for the submitted EVA memory scheduler. For this count, we assume a maximum of 16 threads and a maximum read queue length of 255 entries.

The total storage budget size for EVA is 541,474 bits and EVA-E additionally uses per thread 64-bit counters; thus, the total budget size of EVA-E is 542,498 bits. Both of them are less than 557,056 bits (68KB).

RESULTS

We have evaluated the EVA memory scheduler with the distributed framework [START_REF] Chatterjee | USIMM: the Utah SImulated Memory Module[END_REF]. In this section, EVA refers to the memory scheduler for Delay and Performance-Fairness Product track and EVA-E refers to the memory scheduler for Energy-Delay Product track. Table 5: Comparison of key metrics on baseline and proposed schedulers. c1 and c2 represent commercial transaction-processing workloads, MT-canneal is a 4-threaded version of canneal, and the rest are single-threaded PARSEC programs. "Close" represents an opportunistic close-page policy that precharges inactive banks during idle cycles. metric. These are respectively 10.2%, 17.3% and 17.1 % lower than the scores of FCFS scheduler and 6.2%, 9.7% and 8.8 % lower than the scores of close-page policy scheduler.

CONCLUSION

We have proposed a new structure of DRAM memory scheduler, the sErvice Value Aware memory scheduler EVA. EVA relies on two concepts, the request weight, i.e. the quantity of work that a request enables, and per-thread traffic lights which evaluate whether a thread is blocked by a pending request. EVA predicts request weights and also relies on advanced speculative row selection.

The scheduling decision on EVA is based on a fixed priority to select among the launchable commands. The launchable commands are determined through 3 relatively simple algorithms involving no loops: a hardware implementation of these algorithms should be very effective.

Our experiments shows that our EVA proposal outperform the FCFS scheduler and the close-page policy scheduler on the three metrics proposed for the Championship.

Figure 1 : 7 Figure 2 :

 172 Figure 1: Overview of EVA memory scheduler.

Table 1 :

 1 Configuration of request weight estimator.

		T0 T1 T2 T3 T4 T5 T6 T7 T8 T9
	#entries 2 12	2 11			2 11		2 10		2 10
	tag bits	10	11			13		15		17
	pc hist	0	0	1	2	3	5	9 16 32 64
	row hist	0	0	1	2	3	5	8	8	8	8

Table 2 :

 2 Configuration of next row predictor.

		T0 T1 T2 T3 T4 T5 T6 T7
	#entries 2 10	2 10			2 10		2 10
	tag bits	10	11			13		15
	pc hist	0	0	1	2	3	5	8	8
	row hist	0	0	1	2	3	5 16 32

  This information are updated after the DRAM commands or receiving a new request as follows: receiving read request Read request counters are updated. Thread weight and rank weight are updated by adding estimated request weight. If a prior request is still queueing, these values are adjusted with computed actual request weight. Oldest and latest pointers are updated with channel and queue entry number of the new read request when needed.

	receiving write request
	Write request counters are updated.
	issuing column read command
	Read request counters are updated. Thread weight
	and rank weight are updated by subtracting the
	request weight of issuing request. Oldest pointer for
	the thread is updated with the second oldest request.
	Tickets counter of the related thread is decremented.
	issuing column write command
	Write request counters are updated.

Table 3 :

 3 Priority order of DRAM commands.

		command	condition
	1	refresh	!DRAIN ST RON G
	2	priority column read
	3	column write	DRAIN ST RON G
	4	priority activation and precharge
	5	column read
	6	column write
	7	command for write requests	!N OT DRAIN
	8	activation and precharge for read
	9	activation and precharge for write
	10 precharge unrefferd row
	11 speculative activation

  Refresh num ← num issued ref reshes rest ← next ref resh completion deadline -CY CLE V AL if num * 2 < rest ÷ T REF I then ref resh = f alse else if write drain = DRAIN ST RON G then ref resh = f alse else if rank.write count > HI W M/N U M RAN KS then

	3.2 Refreshing
	Algorithm 3 ref resh = f alse
	else if rank.read count = 0 then
	ref resh = true
	else if rank has high prio thread() then
	ref resh = f alse
	else
	ref resh = true
	end if
	DRAIN then
	if write queue length > M ID W M then
	write drain ← DRAIN ST RON G
	else if write queue length > LO W M then
	if interuppted by valuable read() then
	write drain ← N OT DRAIN
	else if max reqs row ≤ 2 then
	write drain ← N OT DRAIN
	else
	write drain ← DRAIN W EAK
	end if
	else
	write drain ← N OT DRAIN
	end if
	end if
	if write queue length > HI W M then
	write drain ← DRAIN ST RON G
	end if

  Algorithm 5 Detecting what row should be activated speculatively candidates ← ∅ for all t ∈ threads do (channel, rank, bank, row) ← t.pred next t.traf f ic light = GREEN &&t.read count ≤ 2 then if rank.read count = 0&&!bank.pre activated then if num act in tACT (channel, rank) < 3 then

	candidates ← t
	end if
	end if
	end if
	end for
	preact ← arg max	t.oldest.value + t.read count × 100
	t∈candidates
	if P REACT CT R ≥ 28 then
	activate(preact.addr)
	end if
	4. EVA	FOR	THE	MEMORY
	SCHEDULING CHAMPIONSHIP

Table 4 :

 4 Storage budgets for all the components

	Component	Configuration	Budget
	Request	276,480-bit prediction tables
	weight	57,344-bit blacklist filter
	estimator	64-bit, 8-bit hist × 16-thread
		8-bit and 4-bit counters	334,988
	Next	168,960-bit prediction tables
	row	32-bit, 8-bit hist × 16-thread
	predictor	8-bit and 4-bit counters	169,612
	Write row	(2+1+3+17)-bit tag, 8-bit cntr
	count table	× 128-entry × 4-ch	15,872
	Thread	8-bit read counter
	info table	13-bit weight counter
		(2+8)-bit pointer × 2
		1-bit traffic light
		7-bit tickets counter
		67-bit for request value est.
		59-bit for next row pred.
		160 × 16-thread	2560
	Channel	2-bit write drain state
	info table	1-bit last refresh rank
		8-bit read count × 16-thread
		131 × 4-ch	524
	Rank	8-bit read counter
	info table	8-bit read counter × 16-thread
		8-bit write counter
		13-bit rank weight counter
		64×4-bit act history
		64-bit last refresh cycle
		477 × 4-ch × 2-rank	3,816
	Bank	8-bit read counter
	info table	17-bit preactivated row
		2-bit preactivate flags
		27 × 4-ch × 2-rank × 8-bank	1,728
	Others	128-bit for RNG (Xorshift [8])	128
		6-bit P REACT CT R	6
		12-bit request weight in RQ ×	12,240
		255-entry × 4-ch
	Total		541,474

Table 5

 5 illustrate our simulation results. For the total delay metric, EVA achieves 2975 ×10 7 . For the PFP metric, EVA achieves 2842 ×10 7 . EVA-E achieves 19.79 for the EDP

	Workload	Config Sum of exec times (10 M cyc)		Max slowdown			EDP (J.s)
			FCFS Close	EVA	FCFS	Close	EVA	FCFS Close EVA-E
	MT-canneal	1 chan	418	404	363	NA	NA	NA	4.23	3.98	3.57
	MT-canneal	4 chan	179	167	165	NA	NA	NA	1.78	1.56	1.55
	bl-bl-fr-fr	1 chan	149	147	138	1.20	1.18	1.12	0.50	0.48	0.42
	bl-bl-fr-fr	4 chan	80	76	76	1.11	1.05	1.06	0.36	0.32	0.32
	c1-c1	1 chan	83	83	78	1.12	1.11	1.07	0.41	0.40	0.37
	c1-c1	4 chan	51	46	48	1.05	0.95	1.00	0.44	0.36	0.40
	c1-c1-c2-c2	1 chan	242	236	213	1.48	1.46	1.35	1.52	1.44	1.25
	c1-c1-c2-c2	4 chan	127	118	119	1.18	1.10	1.12	1.00	0.85	0.89
	c2	1 chan	44	43	43	NA	NA	NA	0.38	0.37	0.37
	c2	4 chan	30	27	28	NA	NA	NA	0.50	0.39	0.44
	fa-fa-fe-fe	1 chan	228	224	202	1.52	1.48	1.39	1.19	1.14	0.97
	fa-fa-fe-fe	4 chan	106	99	98	1.22	1.15	1.13	0.64	0.56	0.56
	fl-fl-sw-sw-c2-c2-fe-fe	4 chan	295	279	262	1.40	1.31	1.24	2.14	1.88	1.68
	fl-fl-sw-sw-c2-c2-fe-fe-4 chan	651	620	569	1.90	1.80	1.65	5.31	4.76	4.05
	-bl-bl-fr-fr-c1-c1-st-st
	fl-sw-c2-c2	1 chan	249	244	221	1.48	1.43	1.30	1.52	1.44	1.23
	fl-sw-c2-c2	4 chan	130	121	123	1.13	1.06	1.07	0.99	0.83	0.88
	st-st-st-st	1 chan	162	159	147	1.28	1.25	1.18	0.58	0.56	0.49
	st-st-st-st	4 chan	86	81	81	1.14	1.08	1.09	0.39	0.35	0.35
	Overall		3312	3173	2975	1.30	1.24	1.20	23.88	21.70	19.79
						PFP: 3438 PFP: 3149 PFP: 2842

* This work was partially supported by the European Research Council Advanced Grant DAL No 267175 and the Study Program at Overseas Universities, the Graduate school of Information Science and Technology from the University of Tokyo.


Emilie Roche
email: emilie.roche@u-bordeaux1.fr

Olivier Sename
email: olivier.sename@gipsa-lab.fr

Daniel Simon
email: daniel.simon@inria.fr

An LFR approach to varying sampling control of LPV systems: application to AUVs

This paper deals with the varying sampling control of Linear Parameter Varying (LPV) systems, where varying sampling can be used to accommodate limited computation or sensory resources. A discrete-time Linear Fractional Representation of a LPV system is used to design a gain-scheduled controller, where both varying or uncertain parameters of the plant and the sampling rate are gathered in a unique varying parameters structure. The method is successfully applied for the case of the altitude control of an Autonomous Underwater Vehicle (AUV).

I. INTRODUCTION

In the context of network-controlled systems the idea of using varying control intervals naturally arises when the available computing power devoted to feedback control is limited, e.g. in embedded systems. It can be easily shown, e.g. [START_REF] Simon | Robust control/scheduling codesign: application to robot control[END_REF], that decreasing the control frequency directly decreases the amount of computing needed for control. In that case a feedback scheduler is assumed to compute on-line new control intervals according to the CPU load and system's state. Another case is when sensing cannot be done at any time. For example, underwater vehicles mainly sense their environment using acoustic sensors. Due to the slow propagation of the acoustic signals, measurements are subject to delays increasing with the distance to the target. Also, to avoid cross-talking between acoustic sensors working in a narrow area these sensors must be scheduled, so that some of the sensors used in the control laws are triggered only at instants determined by an external manager [START_REF] Opderbecke | Description of the scientific mission scenario(s) to be investigated for the marine application[END_REF]. In all these cases the control intervals are not equidistant, nevertheless they can be accurately measured by the local clock of the controller when the control computation is started.

Different control approaches have been considered to design varying sampling discrete-time controller. In [START_REF] Sala | Computer control under time-varying sampling period: An LMI gridding approach[END_REF] a gridding approach is used to design a discrete-time controller and observer with variable sampling. In [START_REF] Cuenca | A predictorobserver for a networked control system with time-varying delays and non-uniform sampling[END_REF] stability analysis of a controlled system under non uniform sampling is realized with a predictor/observer structure. Furthermore the authors have proposed in [START_REF] Robert | An H ∞ LPV design for sampling varying controllers: experimentation with a t inverted pendulum[END_REF], [START_REF] Roche | A hierarchical varying sampling H ∞ control for an AUV[END_REF] a LPV method for polytopic systems, under the assumption that the system representation is affine w.r.t the sampling period.

On the other hand Linear Parameter Varying representations are also increasingly used to deal with robust control of nonlinear systems. In particular this allows to represent some non-linearities as varying parameters (assuming some knowledge of internal measurements), and also to schedule a controller according to some performance criteria, e.g [START_REF] Shirazi | An LPV design approach for voltage control of an electrostatic MEMS actuator[END_REF], [START_REF] Wei | Gain scheduled H ∞ control for air path systems of diesel engines using LPV techniques[END_REF].

The contribution stands here in the combination, for the first time, of these two ideas by synthesizing a discrete-time controller with a variable sampling rate for LPV systems.

The key point then relies on the connection of the sampling parameter with the system's parameters. Indeed, when the number of varying parameters of the system increases, the inherent conservatism of the previously studied polytopic approach may lead to poor performances of the controlled system, or to unsolved problems due to numerical issues.

Another approach is proposed here to design sampling varying gain-scheduled controller for LPV systems, based on the Linear Fractional Representation (LFR). This method has already been studied in [START_REF] Roche | LPV / H ∞ varying sampling control for autonomous underwater vehicles[END_REF] concerning the synthesis of discrete-time gain-scheduled controller, depending only on the sampling period. This paper extends this previous work and deals with the design of a gain scheduled LFR controller w.r.t the sampling interval and w.r.t system's parameters, given a discrete-time Linear Fractional Representation (LFR) of the LPV varying sampling model.

The approach is then applied to an Autonomous Underwater Vehicle (AUV) for which for the operating constraints and plant's non-linearities fits well the LPV methodology.

In the next section, the LFR approach is presented, and an approach to get a discrete-time LPV model scheduled by both the plant's varying parameters and the varying sampling rate is described. In section III, two LPV models under LFR are developed, considering a hierarchical control structure (altitude and pitch angle control) for an Autonomous Underwater Vehicle (AUV). Finally in section IV, the two controllers of the hierarchical structure are designed using the LFR methodology with variable sampling period, and applied for the altitude control of the AUV.

II. LFR APPROACH

The LFR formulation is widely used in robust analysis to study the influence of the plant's uncertain parameters on the stability and performances of a closed-loop system. It can also be used to build a parameter dependent model of a dynamical system, depending on a known set of parameters.

In particular, this approach can be used to keep some system's non linearities in a LFR model, and then linear control tools can be used to compute a controller scheduled by the parameters (as in [START_REF] Gauthier | An H ∞ linear parameter-varying (LPV) controller for a diesel engine common rail injection system[END_REF]). In this section, the LFR formulation is presented and applied to the case of discrete-time sampling varying modeling and control of LPV systems.

A. LFR model depending on system parameters

The approach comes from the robust control theory and consists in separating the LTI part P (not depending on the set of parameters) from the varying part ∆ (parameters or uncertainties), as shown on figure 1. The matrix ∆ represents the influence of the set of parameters ρ(.) on the plant. ρ(.) is a varying parameter vector that takes values in the parameter space P ρ such that:

z ∆ w ∆ z w P ∆(ρ) u y
P ρ := ρ(.) := ρ 1 (.) . . . ρ n (.) T ∈ R N ρ i (.) ∈ ρ i ρ i ∀i = 1, . . . , N
where N is the number of varying parameters. P ρ is a convex set.

Here the vector of parameters ρ(.) represents plant's parameters to be kept in the model, for example some non-linearities as in [START_REF] Biannic | Nonlinear simplified LFT modelling of an aircraft on ground[END_REF]. Note that the dependence of the system matrices w.r.t the parameters is not bounded to be affine, e.g. it can be rational.

For a LPV system depending on a vector of parameters ρ(.) an equivalent Linear Fractional Representation can be found as presented in Figure 1, with P a continuous-time LTI plant (P(s)) and ∆ a block diagonal matrix composed from the uncertain parameters.

The LFR representation is written as :

    ẋ z ∆ z y     =     A B C D         x w ∆ w u     (1)
where the continuous uncertain system's matrices as :

A (continuous plant state) B = [B ∆ B 1 B 2 ] C =   C ∆ C 1 C 2   D =   D ∆∆ D ∆1 D ∆2 D 1∆ D 11 D 12 D 2∆ D 21 D 22   (2)
From this model, a gain scheduled controller can be computed, depending on the same set of parameters ∆ (or on a subset of ∆) as presented in [START_REF] Apkarian | A convex characterisation of gain-scheduled H ∞ controllers[END_REF]. Here the LFR approach proposed in [START_REF] Roche | LPV / H ∞ varying sampling control for autonomous underwater vehicles[END_REF] will be extended to set-up a LFR model that accounts for system and sampling parameters. The steps below describe the proposed methodology.

B. Parametrized discretization

The interest of the previous LFR formulation is that the varying part is separated from the system dynamics. Then the LFR model in figure 1 can be discretized, assuming that the uncertain input/outputs (w ∆ and z ∆ ) are sampled and hold at the sampling frequency. Then, in that context, the methodology proposed in [START_REF] Roche | LPV / H ∞ varying sampling control for autonomous underwater vehicles[END_REF] can be extended to get a sampling dependent LFR discrete-time model of an LPV system.

From the LFR model ( 1), where non-linearities are considered as varying parameters, a new LFR is computed by adding the sampling interval to the existing set of varying parameters.

The exact discretization w.r.t. a sampling interval h of the LTI system (A,B,C,D) is given in equation ( 3)

G : x k+1 = A d (h)x k + B d (h)[w ∆ w u] T [z ∆ z y] T = Cx k + D[w ∆ w u] T (3)
with:

A d (h) = e Ah B d (h) = Z h 0 e Aτ dτB (4)
The usual numerical method uses the matrix exponential :

A d (h) B d (h) 0 I = exp A B 0 0 h (5)
The sampling interval is assumed to be in [h min , h max ] with h min > 0, it is evaluated around its nominal value h 0 as:

h = h 0 + δ with h min -h 0 ≤ δ ≤ h max -h 0 (6)
As explained in [START_REF] Robert | An H ∞ LPV design for sampling varying controllers: experimentation with a t inverted pendulum[END_REF] equation [START_REF] Robert | An H ∞ LPV design for sampling varying controllers: experimentation with a t inverted pendulum[END_REF] in this case becomes:

A d (h) B d (h) 0 I = A d (h 0 ) B d (h 0 ) 0 I A d (δ) B d (δ) 0 I (7) with matrices A h 0 = A d (h 0 ), A δ = A d (δ), B h 0 = B d (h 0 ) and B δ = B d (δ)
in equation 7 are defined following equation [START_REF] Robert | An H ∞ LPV design for sampling varying controllers: experimentation with a t inverted pendulum[END_REF].

Matrices A d (h) and B d (h) depend both on the constant part h 0 and on the varying part δ of the sampling interval :

A d (h) = A h 0 A δ (8) B d (h) = B h 0 + A h 0 B δ (9)
Only the matrices A δ and B δ depend on the varying part of the sampling interval δ which appears in the varying part of the LFR model. An approximate form of equation ( 4) can be obtained by a Taylor series expansion at order l (with a very good approximation for small values of δ, as shown in [START_REF] Robert | An H ∞ LPV design for sampling varying controllers: experimentation with a t inverted pendulum[END_REF]).

A δ = I + l ∑ i=1 A i i! δ i + o(δ l+1 ) (10)
B δ = l ∑ i=1 A i-1 B i! δ i + o(δ l+1 ) (11)
The Taylor series expansion associated with the uncertain model leads to an LFR representation depending on the variation of the sampling interval (δ) and the plant's uncertain parameters (∆) (see [START_REF] Roche | LPV / H ∞ varying sampling control for autonomous underwater vehicles[END_REF] for the details) as:

z Θ =   z δ z ∆   z w y u   w δ w ∆   = w Θ P d δI 2ln 0 0 ∆ Fig. 2.
LFR system depending on system parameters and sampling period variation

P d :                        x k+1 = Ax k + B     w δ w ∆ w u     k     z δ z ∆ z y     k = C x k + D     w δ w ∆ w u     k (12)
with

Θ = δI 2×l×n 0 0 ∆ (13)
A = A h 0 B = B 1 B 2 B h 0 (14) C = C δ C D =   D 0 0 0 D D 2u 0 0 D   (15)
B 1 = (A h 0 A 0 n . . . 0 n (l-1) times ) B 2 = (A h 0 0 n . . . 0 n (l-1) times ) (16)
) T D =        0 n A 2 . . . 0 n . . . . . . . . . . . . . . . . . . . . . A l 0 n . . . . . . 0 n        D 2u =    B . . . B    ( 17
)
where l is the order of the Taylor series expansion order in δ and n is the number of states of the continuous plant.

C. LFR controller

Following [START_REF] Apkarian | A convex characterisation of gain-scheduled H ∞ controllers[END_REF] an H ∞ gain scheduled LFR controller can be computed from this discrete-time LFR model. This controller depends on the same set of varying parameters Θ (or on a subset of this one). The controller will be computed using tools derived from the bounded Real Lemma. Some performance specification are therefore fixed using weighting functions for loop shaping and H ∞ design. The dependence between the discrete-time LTI plant P d , the controller K, the parameter block (including the system and sampling parameters) and the weighting functions W i and W o is depicted in Figure 3. Finally, the LFR controller is computed using the methodology presented in [START_REF] Apkarian | A convex characterisation of gain-scheduled H ∞ controllers[END_REF]. Note that the controller synthesis relies on the resolution of LMIs (as for the Polytopic case, see [START_REF] Roche | A hierarchical varying sampling H ∞ control for an AUV[END_REF]). But conversely with the polytopic case, for the LFR case the number of LMIs to be solved do not depend on the number of parameters, only the sizes of the matrices in the LMIs are increasing with the size of the Θ matrix. It is worth noting that to get the solution of the control problems the YALMIP parser [START_REF] Lofberg | YALMIP : A toolbox for modeling and optimization in MATLAB[END_REF] and SeDuMi solver [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] have been used.

III. A LPV DISCRETE-TIME MODEL OF THE AUV WITH SAMPLING DEPENDENCE

The LFR formulation developed in the previous section is applied to the altitude control of an Autonomous Underwater Vehicle (AUV) using the hierarchical structure already used in [START_REF] Roche | A hierarchical varying sampling H ∞ control for an AUV[END_REF], depicted in Figure 4. Two cascaded loops are used for altitude control, (K z (δ) and K θ (δ, ρ)) based on two LPV models (G d z (δ) and G d θ (δ, ρ)) detailed in the sequel. The description of the full vehicle's dynamics uses a 12 dimensional state vector: 6 for the positions x, y, z (linear positions) and φ, θ and ψ (roll, pitch an yaw angles) expressed in a fixed frame and 6 for the velocities (derivatives of the positions), u, v, w, p, q, r expressed in the body frame.

K u K θ (δ, ρ) K z (δ)

A. LPV model for the pitch angle

To control motions around the pitch axis, a model reduction is considered keeping only the 2 state variables of interest, the pitch angle θ and the corresponding velocity q. The non-linear state equations corresponding to these states are : θ =cos(φ)qsin(φ)r

M 55 q = -pr(I x -I z ) -m[Z g (qw -rv)] -(Z q m -Z f µV )gsin(θ) -(X q m -X f µV )gcos(θ)cos(φ) + M wq w|q| + M qq q|q| + Γ θ ( 18
)
where M 55 is a diagonal element of the mass matrix (including water-added mass), m is the mass of the vehicle, V the volume of the hull and µ the density of the fluid. I x , I z , Z g , Z q , Z f , X q , X f , M wq are inertial and hydrodynamics scalar coefficients. Γ θ is the torque induced by the lift and drag actions on the control surfaces.

An LFR representation of this model is obtained using a tangential linearization around a variable equilibrium point : all position and speeds are taken equal to zero except the longitudinal speed (u eq ) and the pitch angle (θ eq kept as a variable equilibrium point). The equations of the linearized model are :

G θ :      θ = q M 55 q = [-(Z g m -Z f µV )gcos(θ eq ) + (X g m -X f µV )gsin(θ eq )] θ + Γ θ (19)
with θ = θθ eq . The LFR formulation is used here to keep θ as a varying parameters into the model formulation. Indeed, in previous works, the limits of a simple linearization around a fixed equilibrium point appeared : when the pitch angle significantly deviates from 0 (the value chosen for linearization), the linearized model becomes too different from the actual one (due to the hydro-static return torque needing high actuators solicitations to keep the equilibrium around θ eq ), leading to poor control performances.

An LFR model of the vehicle described in the form of figure 1 is derived from equations (19). The ∆ block contains the varying part of the model, which depends on the linearization point (θ eq ). The LFR form is defined by :

G θ :          θ q = A θ q + B ∆ B 1 w ∆ u z ∆ z = C ∆ I 2 x k + 0 0 0 0 w ∆ u (20)
with

A = 0 1 0 0 , B ∆ = 0 0 -(Z q m -Z f µV )g (X q m -X f µV )g B 1 = 0 0 B β 1 B β 2 , C ∆ = 1 0 1 0 (21)
where the gains B β 1 and B β 2 depend on the geometry of the control surfaces and are both proportional to u 2 eq (assumed constant), and the control vector is u = (β 1 β 2 ) T .

z ∆ = θ θ ; w ∆ = ∆z ∆ ; ∆ = ρ 1 0 0 ρ 2 (22)
with:

ρ 1 = cos(θ eq ) ρ 2 = sin(θ eq ) ( 23
)
This model is then discretized, and the sampling interval, considered as a varying parameter in the model, is added to the ∆ parameter block (as in section II-B).

Finally, choosing a Taylor series expansion of order l = 1, a discrete-time LFR is obtained (as in equations ( 12) to ( 17)), with the parameter block Θ as:

Θ =   δ × I 4 0 0 0 ρ 1 0 0 0 ρ 2   (24)
B. LPV model for the altitude Using the geometric relation between the altitude variations and the pitch angle, it appears that the the pitch angle, combined with the forward velocity, is in some sense the "actuator" to be used to generate altitude variations with low drag. Note that the cutoff frequency for the pitch controller is chosen faster than the one for the altitude controller to decouple the two loops, as done classically for cascade loops. Therefore the altitude controller computes the pitch angle setpoint needed to follow the desired path.

The projection of the body velocities in the fixed frame leads to a simple model : ż = u eq sin θ A first order development of the sinus function is valid for the moderate pitch angles which are feasible by the AUV, which provides the linear model and transfer function :

ż ≃ u eq θ G z (p) = z θ = u eq p (25)
Therefore, the inner loop composed by the non linear model and the pitch angle controller G θ can be approximated by an integrator, leading to a low-order controller for which the discretization step is very simple. The model given in (25) can be discretized by :

z k+1 = z k + u eq .h.θ k (26)
The sampling interval is still assumed to belong to [h min , h max ], so that the altitude discrete-time model is :

G d z (δ) : z k+1 = z k + (h 0 + δ).u eq .θ k (27)
Therefore, assuming a constant forward velocity u eq , the altitude model is scheduled by the sampling interval only.

IV. CONTROL DESIGN To control the altitude of the AUV at a constant forward velocity, three controllers are designed to implement the structure of Figure 4. An H ∞ controller with a constant sampling period of 0.1s is used to regulate the forward speed u around u eq , its classical design is not detailed here.

Two controllers are synthesized in discrete time to control the altitude z. The altitude controller K z (δ) (computed from the model G d z (δ)) gives a desired pitch angle θ re f , which is used by the pitch angle controller K θ (δ, ρ) (model G d θ (δ, ρ)) to compute the actions β 1 and β2 applied to the AUV.

A. H ∞ loop shaping

The two controllers involved in the altitude control loop are designed using the LFR methodology developed in II-C, based on H ∞ control design : some weighting functions are used to specify the performances of the closed loop system.

1) K θ (δ, ρ): The pitch angle controller is designed using the structure of Remark: The weighting function on the tracking error is defined directly in discrete-time as a constant (LTI) first order filter. This correspond to an equivalent continuous time filter that depends on the period, allowing the adaptation of the performances with respect to the current sampling rate, as explained in [START_REF] Robert | An H ∞ LPV design for sampling varying controllers: experimentation with a t inverted pendulum[END_REF].

The controller K θ (δ, ρ) is then computed as in [START_REF] Apkarian | A convex characterisation of gain-scheduled H ∞ controllers[END_REF] and its Bode diagram plotted in Figure 6 shows the adaptation of the controller gain w.r.t. the parameter vector. The pitch angle controller is scheduled by the "physical" parameters ρ 1 = cos(θ) and ρ 2 = sin(θ) and also the sampling interval h. The bounds on these parameters are chosen as follow: θ ∈ [-30; 30] so ρ 1 ∈ [0.86; 1] and ρ 2 ∈ [-0.5; 0.5] and the sampling interval h ∈ [0.005; 0.03]s.

2) K z (δ): The altitude controller is designed using a similar control configuration (see figure 7).

with weighting functions defined as follows:

W z e = z M ′ Sz e + w ′ S ze z + w ′ S ze ε ′ S ze , W z u = 5 ( 29
)
The controller is synthesized and its Bode diagram is presented in figure 8, for 10 frozen value of the parameter δ. The altitude controller is scheduled only by the sampling interval,varying inside the interval [0.05; 0.3]s.

B. Simulation results

The full (12 state variables) non-linear model (detailed in [START_REF] Roche | LPV / H ∞ varying sampling control for autonomous underwater vehicles[END_REF]) is used for the simulations, combined with the global control structure of Figure 4. The mission consists in bottom following at a constant altitude with a constant forward velocity (constant speed is needed for most payload, e.g., for map making using a sonar). An independent discrete-time H ∞ controller regulates the cruising speed u around 1m/s during all the simulation.

For testing purpose the control interval h is given as a sinusoidal wave (Figure 11 stability is preserved for a large range of sampling intervals, and the tracking of the altitude and pitch angle references is achieved with a very good precision and time of response.

Compared with the same case study in [START_REF] Roche | LPV / H ∞ varying sampling control for autonomous underwater vehicles[END_REF], where only the sampling rate was considered as a varying parameter, considering here both the sampling interval and the plant's non-linearities (cos(θ eq ) and sin(θ eq )) in the LPV model allows to improve the close loop performances, in particular through a more effective use of the actuators range. In the same case study, it was also observed that when using discrete-time H ∞ controllers designed for a constant sampling period, the control systems becomes unstable as soon as the sampling rate significantly deviates from the nominal value.

V. CONCLUSION

In this paper, the problem of varying sampling control of an LPV system is addressed. An LFR methodology provides a unified framework to handle both the plant's non-linearities and the varying sampling rate in the same structure. The approach is applied on the example of the altitude control of a non-linear AUV.

Considering the sampling interval as a varying parameter of the LTI system makes the methodology well suited for the problem, since expressing the LPV system under a LFR makes quite simple the discretization step. The loop-shaping weighting templates are also made sampling dependent to handle the closed-loop performance variations w.r.t. the actual sampling rate, and to preserve the stability margins. Furthermore the model is well suited for control synthesis through currently available LMI solvers.

However it is expected that these results, in particular their conservatism, might be improved considering improvements in LPV/LFR design, such as using new multipliers for Linear Fractional Transformations as in [START_REF] Scherer | LPV control and full block multipliers[END_REF], or by using parameterdependent Lyapunov functions as in [START_REF] Wu | Gain-scheduling control of LFT systems using parameter-dependent Lyapunov functions[END_REF].

Fig. 1 .

 1 Fig. 1. System under LFR form

C

  δ = (I n . . . I n l times 0 n . . . 0 n l times

Fig. 3 .

 3 Fig. 3. LFR control structure

Fig. 4 .

 4 Fig. 4. Global control structure

Figure 5 .Fig. 5 .

 55 Fig. 5. Pitch control structure W θ u are defined in discrete-time as follows:

6 .Fig. 7 .

 67 Fig. 7. Altitude control structure

Fig. 8 .Fig. 9 .Fig. 10 .

 8910 Fig. 8. Bode diagram of the altitude controller K z (δ)

  Fig. 11. left: Control signals ; right: Sampling interval (top) Speed (bottom)