\documentclass[a4paper,conference]{IEEEtran/IEEEtran}
\usepackage{graphicx,color,hyperref}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{url}
\usepackage[normalem]{ulem}
\graphicspath{{/home/jmfriedt/gpr/170324_avalanche/}{/home/jmfriedt/gpr/1705_homemade/}}
% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}
\textheight=26cm
\setlength{\footskip}{30pt}
\pagenumbering{gobble}
\begin{document}
\title{Filter optimization for real time digital processing of radiofrequency signals: application
to oscillator metrology}

\author{\IEEEauthorblockN{A. Hugeat\IEEEauthorrefmark{1}\IEEEauthorrefmark{2}, J. Bernard\IEEEauthorrefmark{2},
G. Goavec-M\'erou\IEEEauthorrefmark{1},
P.-Y. Bourgeois\IEEEauthorrefmark{1}, J.-M. Friedt\IEEEauthorrefmark{1}}
\IEEEauthorblockA{\IEEEauthorrefmark{1}FEMTO-ST, Time \& Frequency department, Besan\c con, France }
\IEEEauthorblockA{\IEEEauthorrefmark{2}FEMTO-ST, Computer Science department DISC, Besan\c con, France \\
Email: \{pyb2,jmfriedt\}@femto-st.fr}
}
\maketitle
\thispagestyle{plain}
\pagestyle{plain}
\newtheorem{definition}{Definition}

\begin{abstract}
Software Defined Radio (SDR) provides stability, flexibility and reconfigurability to
radiofrequency signal processing. Applied to oscillator characterization in the context
of ultrastable clocks, stringent filtering requirements are defined by spurious signal or
noise rejection needs. Since real time radiofrequency processing must be performed in a
Field Programmable Array to meet timing constraints, we investigate optimization strategies
to design filters meeting rejection characteristics while limiting the hardware resources
required and keeping timing constraints within the targeted measurement bandwidths.
\end{abstract}

\begin{IEEEkeywords}
Software Defined Radio, Mixed-Integer Linear Programming, Finite Impulse Response filter
\end{IEEEkeywords}

\section{Digital signal processing of ultrastable clock signals}

Analog oscillator phase noise characteristics are classically performed by downconverting
the radiofrequency signal using a saturated mixer to bring the radiofrequency signal to baseband,
followed by a Fourier analysis of the beat signal to analyze phase fluctuations close to carrier. In
a fully digital approach, the radiofrequency signal is digitized and numerically downconverted by
multiplying the samples with a local numerically controlled oscillator (Fig. \ref{schema}) \cite{rsi}.

\begin{figure}[h!tb]
\begin{center}
\includegraphics[width=.8\linewidth]{images/schema}
\end{center}
\caption{Fully digital oscillator phase noise characterization: the Device Under Test
(DUT) signal is sampled by the radiofrequency grade Analog to Digital Converter (ADC) and
downconverted by mixing with a Numerically Controlled Oscillator (NCO). Unwanted signals
and noise aliases are rejected by a Low Pass Filter (LPF) implemented as a cascade of Finite
Impulse Response (FIR) filters. The signal is then decimated before a Fourier analysis displays
the spectral characteristics of the phase fluctuations.}
\label{schema}
\end{figure}

As with the analog mixer,
the non-linear behavior of the downconverter introduces noise or spurious signal aliasing as
well as the generation of the frequency sum signal in addition to the frequency difference.
These unwanted spectral characteristics must be rejected before decimating the data stream
for the phase noise spectral characterization. The characteristics introduced between the downconverter
and the decimation processing blocks are core characteristics of an oscillator characterization
system, and must reject out-of-band signals below the targeted phase noise -- typically in the
sub -170~dBc/Hz for ultrastable oscillator we aim at characterizing. The filter blocks will
use most resources of the Field Programmable Gate Array (FPGA) used to process the radiofrequency
datastream: optimizing the performance of the filter while reducing the needed resources is
hence tackled in a systematic approach using optimization techniques. Most significantly, we
tackle the issue by attempting to cascade multiple Finite Impulse Response (FIR) filters with
tunable number of coefficients and tunable number of bits representing the coefficients and the
data being processed.

\section{Finite impulse response filter}

We select FIR filter for their unconditional stability and ease of design. A FIR filter is defined
by a set of weights $b_k$ applied to the inputs $x_k$ through a convolution to generate the outputs $y_k$
$$y_n=\sum_{k=0}^N b_k x_{n-k}$$

As opposed to an implementation on a general purpose processor in which word size is defined by the
processor architecture, implementing such a filter on an FPGA offer more degrees of freedom since
not only the coefficient values and number of taps must be defined, but also the number of bits defining
the coefficients and the sample size.

The coefficients are classically expressed as floating point values. However, this binary
number representation is not efficient for fast arithmetic computation by an FPGA. Instead,
we select to quantify these floating point values into integer values. This quantization
will result in some precision loss. 

%As illustrated in Fig. \ref{float_vs_int}, we see that we aren't
%need too coefficients or too sample size. If we have lot of coefficients but a small sample size,
%the first and last are equal to zero. But if we have too sample size for few coefficients that not improve the quality.

% JMF je ne comprends pas la derniere phrase ci-dessus ni la figure ci dessous
%\begin{figure}[h!tb]
%\includegraphics[width=\linewidth]{images/float-vs-integer.pdf}
%\caption{Impact of the quantization resolution of the coefficients}
%\label{float_vs_int}
%\end{figure}

The tradeoff between quantization resolution and number of coefficients when considering
integer operations is not trivial. As an illustration of the issue related to the
relation between number of fiter taps and quantization, Fig. \ref{float_vs_int} exhibits
a 128-coefficient FIR bandpass filter designed using floating point numbers (blue). Upon
quantization on 6~bit integers, 60 of the 128~coefficients in the beginning and end of the
taps become null, making the large number of coefficients irrelevant and allowing to save
processing resource by shrinking the filter length. This tradeoff aimed at minimizing resources
to reach a given rejection level, or maximizing out of band rejection for a given computational
resource, will drive the investigation on cascading filters designed with varying tap resolution
and tap length, as will be shown in the next section.

\begin{figure}[h!tb]
\includegraphics[width=\linewidth]{images/demo_filtre}
\caption{Impact of the quantization resolution of the coefficients: the quantization is
set to 6~bits, setting the 30~first and 30~last coefficients out of the initial 128~band-pass
filter coefficients to 0.}
\label{float_vs_int}
\end{figure}

\section{Filter optimization}

A basic approach for implementing the FIR filter is to compute the transfer function of
a monolithic filter: this single filter defines all coefficients with the same resolution
(number of bits) and processes data represented with their own resolution. Meeting the
filter shape requires a large number of coefficients, limited by resources of the FPGA since
this filter must process data stream at the radiofrequency sampling rate after the mixer.

An optimization problem \cite{leung2004handbook} aims at improving one or many
performance criteria within a constrained resource environment. Amongst the tools
developed to meet this aim, Mixed-Integer Linear Programming (MILP) provides the framework to
provide a formal definition of the stated problem and search for an optimal use of available
resources \cite{yu2007design, kodek1980design}.

The degrees of freedom when addressing the problem of replacing the single monolithic
FIR with a cascade of optimized filters are the number of coefficients $N_i$ of each filter $i$,
the number of bits $c_i$ representing the coefficients and the number of bits $d_i$ representing
the data fed to the filter. Because each FIR in the chain is fed the output of the previous stage,
the optimization of the complete processing chain within a constrained resource environment is not
trivial. The resource occupation of a FIR filter is considered as $c_i+d_i+\log_2(N_i)$ which is
the number of bits needed in a worst case condition to represent the output of the FIR.

\begin{figure}[h!tb]
\includegraphics[width=\linewidth]{images/noise-rejection.pdf}
\caption{Rejection as a function of number of coefficients and number of bits}
\label{noise-rejection}
\end{figure}

The objective function maximizes the noise rejection while keeping resource occupation below
a user-defined threshold. The MILP solver is allowed to choose the number of successive
filters, within an upper bound. The last problem is to model the noise rejection. Since filter
noise rejection capability is not modeled with linear equation, a look-up-table is generated
for multiple filter configurations in which the $c_i$, $d_i$ and $N_i$ parameters are varied: for each
one of these conditions, the low-pass filter rejection defined as the mean power between
half the Nyquist frequency and the Nyquist frequency is stored as computed by the frequency response
of the digital filter (Fig. \ref{noise-rejection}).

Linear program formalism for solving the problem is well documented: an objective function is
defined which is linearly dependent on the parameters to be optimized. Constraints are expressed
as linear equation and solved using one of the available solvers, in our case GLPK\cite{glpk}.

The MILP solver provides a solution to the problem by selecting a series of small FIR with
increasing number of bits representing data and coefficients as well as an increasing number
of coefficients, instead of a single monolithic filter. Fig. \ref{compare-fir} exhibits the
performance comparison between one solution and a monolithic FIR when selecting a cutoff
frequency of half the Nyquist frequency: a series of 5 FIR and a series of 10 FIR with the
same space usage are provided as selected by the MILP solver. The FIR cascade provides improved
rejection than the monolithic FIR at the expense of a lower cutoff frequency which remains to
be tuned or compensated for.

\begin{figure}[h!tb]
% \includegraphics[width=\linewidth]{images/compare-fir.pdf}
\includegraphics[width=\linewidth]{images/fir-mono-vs-fir-series-200dB.pdf}
\caption{Comparison of the rejection capability between a series of FIR and a monolithic FIR
with a cutoff frequency set at half the Nyquist frequency.}
\label{compare-fir}
\end{figure}

The resource occupation when synthesizing such FIR on a Xilinx FPGA is summarized as Tab. \ref{t1}.

\begin{table}[h!tb]
\caption{Resource occupation on a Xilinx Zynq-7000 series FPGA when synthesizing the FIR cascade
identified as optimal by the MILP solver within a finite resource criterion. The last line refers
to available resources on a Zynq-7010 as found on the Redpitaya board. The rejection is the mean
value from 0.6 to 1 Nyquist frequency.}
\begin{center}
\begin{tabular}{|c|cccc|}\hline
FIR & BlockRAM & LookUpTables & DSP & rejection (dB)\\\hline\hline
1 (monolithic) & 1 & 4064 & 40 & -72 \\
5 & 5 & 12332 & 0 & -217 \\
10 & 10 & 12717 & 0 & -251 \\\hline\hline
Zynq 7010 & 60 & 17600 & 80 &  \\\hline
\end{tabular}
\end{center}
%\vspace{-0.7cm}
\label{t1}
\end{table}

\section{Filter coefficient selection}

The coefficients of a single monolithic filter are computed as the impulse response
of the filter transfer function, and practically approximated by a multitude of methods
including least square optimization (Matlab's {\tt firls} function), Hamming or Kaiser windowing
(Matlab's {\tt fir1} function). Cascading filters opens a new optimization opportunity by
selecting various coefficient sets depending on the number of coefficients. Fig. \ref{2}
illustrates that for a number of coefficients ranging from 8 to 47, {\tt fir1} provides a better
rejection than {\tt firls}: since the linear solver increases the number of coefficients along
the processing chain, the type of selected filter also changes depending on the number of coefficients
and evolves along the processing chain.

\begin{figure}[h!tb]
\includegraphics[width=\linewidth]{images/fir1-vs-firls}
\caption{Evolution of the rejection capability of least-square optimized filters and Hamming
FIR filters as a function of the number of coefficients, for floating point numbers and 8-bit
encoded integers.}
\label{2}
\end{figure}

\section{Conclusion}

We address the optimization problem of designing a low-pass filter chain in a Field Programmable Gate
Array for improved noise rejection within constrained resource occupation, as needed for
real time processing of radiofrequency signal when characterizing spectral phase noise
characteristics of stable oscillators. The flexibility of the digital approach makes the result
best suited for closing the loop and using the measurement output in a feedback loop for
controlling clocks, e.g. in a quartz-stabilized high performance clock whose long term behavior
is controlled by non-piezoelectric resonator (sapphire resonator, microwave or optical
atomic transition).

\section*{Acknowledgement}

This work is supported by the ANR Programme d'Investissement d'Avenir in
progress at the Time and Frequency Departments of the FEMTO-ST Institute
(Oscillator IMP, First-TF and Refimeve+), and by R\'egion de Franche-Comt\'e.
The authors would like to thank E. Rubiola, F. Vernotte, G. Cabodevila for support and
fruitful discussions.



	\subsubsection{Contraintes}
	\label{def-contraintes}
	Maintenant que nous avons d\'efini ce qu'\'etait une chaine de traitement, nous allons voir
	quelles sont les contraintes li\'ees à celles-ci.
	
	Le temps d'ex\'ecution des t\^aches se compte en front montant d'horloge souvent appel\'e 
	coup d'horloge. On a donc une unit\'e de temps discr\'etis\'ee car un coup d'horloge est indivisible.
	les dates sont donc cadenc\'ees par l'horloge du FPGA. 
	
	Chaque t\^ache doit pouvoir traiter chaque donn\'ee qui arrive, ce qui impose une contrainte 
	forte de d\'ebit d'entr\'ee. En effet, dans le cadre du traitement du signal, il est primordial
	d'avoir toutes les donn\'ees de manière cons\'ecutive. Si la moindre donn\'ee est perdue, le r\'esultat
	obtenu n'est plus valide. Cette contrainte se traduit la plupart du temps par de m\'ecanisme de 
	FIFO qui bufferise les donn\'ees entrantes (dans le cas où la t\^ache n\'ecessite en tableau de donn\'ees,
	par exemple). Ou cela peut aussi se mettre en place par un m\'ecanisme de pipeline ou de parall\'elisme
	à l'int\'erieur du bloc. Mais cela relève de l'impl\'ementation bas niveau du bloc.
	
	Le temps d'ex\'ecution d'une t\^ache correspond à la latence d'un bloc. Il s'agit donc  du
	temps que passe une donn\'ee brute dans le bloc avant de ressortir trait\'ee. Dans notre contexte
	la latence n'est pas importante. En effet, puisqu'on a un flux de donn\'ees continu, après un court laps
	de temps toutes les t\^aches ont d\'epass\'e leur temps de latence et elles produisent les donn\'ees 
	r\'egulièrement.
	
	Il y a tout de même une exception à cela, c'est lors d'un traitement parallèle. Dans l'exemple de la 
	figure \ref{exemple-chaine-traitement}, on voit un bloc qui divise le flux en deux branches. Dans le 
	cas où on resynchronise le flux, il est imp\'eratif que la somme des latences des deux branches soit la
	même. Cela peut donc imposer la pr\'esence de blocs qui ajoutent de la latence sans faire de traitements utiles.
	
	En revanche, une t\^ache se caract\'erise par un d\'ebit de sortie et celui-ci doit rester fixe.
	Cela s'explique par la contrainte du d\'ebit d'entr\'ee du bloc de traitement suivant. Si un bloc a un d\'ebit de sortie 
	fluctuant, il est \'evident que la contrainte d'entr\'ee ne sera pas possible à formaliser.
	
	Une autre contrainte li\'ee de manière plus globale est la consommation de ressources. Comme nous l'avons
	dit dans la section \ref{def-fpga}, le FPGA dispose d'un nombre de portes logiques limit\'e.
	Il faut donc que la chaine de traitement ne d\'epasse pas le nombre de ressources dont dispose la puce
	FPGA.
	
	La consommation de ressources est influenc\'ee par les blocs de traitement. En effet, pour pouvoir 
	tenir les d\'ebits d'entr\'ee \'elev\'ees, cela consomme \'enorm\'ement de ressources. Plus le d\'ebit est rapide, plus 
	la consommation de ressources sera grande.
	
	\subsection{Travaux traitant du sujet}
	Nous avons commenc\'e notre recherche en lisant des articles traitant de l'optimisation dans un FPGA.
	Dans sa thèse, S. Mirzaei \cite{these-dsp-fpga} donne surtout des bonnes pratiques pour d\'evelopper 
	des composants FPGA bas niveau. Ce n'est pas exactement ce que nous cherchions.
	
	Dans les r\'ef\'erences \cite{zhuo2007scalable, olariu1993computing, pan1999improved}, les auteurs 
	proposent tous des optimisations hardware uniquement. Cependant ces articles sont focalis\'es sur des optimisations mat\'erielles
	or notre objectif est de trouver une formalisation math\'ematique d'un FPGA. 
	
	Une autre approche est propos\'ee par S. Kasbah et al. dans leur article \cite{kasbah2008multigrid}.
	En effet, ils utilisent une approche HLS de leur problème. Ils ont utilis\'e un synth\'etiseur optimis\'e et
	un langage d\'eriv\'e du C++ pour d\'ecrire leur algorithme. Bien qu'ils obtiennent de bons r\'esultats, 
	leur m\'ethode n'est pas exploitable dans notre cas, car ils n'ont pas les mêmes contraintes de d\'ebit et 
	de temps r\'eel que nous.
	
	Une dernière approche que nous avons \'etudi\'ee est l'utilisation de \emph{skeletons}. D. Crookes et A. Benkrid
	ont beaucoup parl\'e de cette m\'ethode dans leur articles \cite{crookes1998environment, crookes2000design, benkrid2002towards}.
	L'id\'ee essentielle est qu'ils r\'ealisent des composants très optimis\'es et param\'etrables. Ainsi lorsqu'ils 
	veulent faire un d\'eveloppement, ils utilisent les blocs d\'ejà faits. 

	Ces blocs repr\'esentent une \'etape de calcul (une d\'ecimation, un filtrage, une modulation, une 
	d\'emodulation etc...). En prenant le cas du FIR, on rend param\'etrables les valeurs des coefficients
	utilis\'es pour le produit de convolutions ainsi que leur nombre. Le facteur de d\'ecimation est 
	lui aussi param\'etrable.
	
	On gagne ainsi beaucoup de temps de d\'eveloppement car on r\'eutilise des composants d\'ejà \'eprouv\'es et optimis\'es.
	De plus, au fil des projets, on constitue une bibliothèque de composants nous 
	permettant de faire une chaine complète très simplement.
	
	K. Benkrid, S. Belkacemi et A. Benkrid dans leur article\cite{hide} caract\'erisent
	ces blocs en Prolog pour faire un langage descriptif permettant d'assembler les blocs de manière
	optimale. En partant de cette description, ils arrivent à g\'en\'erer directement le code VHDL.
	
	G. Goavec-Merou, dans sa thèse\cite{gwen-cogen}, pr\'esente un outil, CoGen, bas\'e sur l'approche en skeletons. Son id\'ee
	est de caract\'eriser des blocs \'ecrits en VHDL, en donnant diff\'erents caract\'eristiques :
	\begin{itemize}
		\item la latence du bloc repr\'esente, en coups d'horloge, le temps entre l'entr\'ee de la donn\'ee 
		et le temps où la même donn\'ee ressort du bloc.
		\item l'acceptance repr\'esente le nombre de donn\'ees par coup d'horloge que le bloc est capable 
		de traiter.
		\item la sortance repr\'esente le nombre de donn\'ees qui sortent par coup d'horloge.
	\end{itemize}
	
	Gr\^ace à cela, le logiciel est capable de donner une impl\'ementation optimale d'un problème qu'on lui
	soumet. Le problème ne se d\'efinit pas uniquement par un r\'esultat attendu mais aussi par des 
	contraintes de d\'ebit et/ou de pr\'ecision.
	
	Dans une second temps, nous nous sommes aussi int\'eress\'es à des articles d'ordonnancement. 
	Nous avons notamment lu des documents parlant des cas des micro-usines. 
	
	Les micro-usines ressemblent un peu à des FPGA dans le sens où on connait à l'avance les 
	t\^aches à effectuer et leurs caract\'eristiques. Nous allons donc nous inspirer 
	de leur modèle pour essayer de construire le notre.
	
	Dans sa thèse A. Dobrila \cite{these-alex} traite d'un problème de tol\'erance aux pannes 
	dans le contextes des mirco-usines. Mais les FPGA ne sont pas concern\'es dans la mesure 
	où si le composant tombe en panne, tout le traitement est paralys\'e. Cette thèse nous a n\'eanmoins
	permis d'avoir un exemple de formalisation de problème.
	
	Pour finir nous avons lu la thèse de M. Coqblin \cite{these-mathias} qui elle aussi traite du sujet
	des micro-usines. Le travail de M. Coqblin porte surtout sur une chaine de traitement 
	reconfigurable, il tient compte dans ses travaux du surcoût engendr\'e par la reconfiguration d'une machine.
	Cela n'est pas tout à fait exploitable dans notre contexte puisqu'une 
	puce FPGA d\'es qu'elle est programm\'ee n'a pas la possibilit\'e de reconfigurer une partie de sa chaine de 
	traitement. Là encore, nous avions un exemple de formalisation d'un problème.
	
	Pour conclure, nous avons vu deux approches li\'ees à deux domaines diff\'erents. La première est le
	point de vue \'electronique qui se focalise principalement sur des optimisations mat\'erielles ou algorithmiques.
	La seconde est le point de vue informatique : les modèles sont très g\'en\'eriques et ne sont pas 
	adapt\'es au cas des FPGA. La suite de ce rapport se concentrera donc sur la recherche d'un compromis
	entre ces deux points de vue.
	
	\section{Contexte d'ordonnancement}
	Dans cette partie, nous donnerons des d\'efinitions de termes rattach\'es au domaine de l'ordonnancement 
	et nous verrons que le sujet trait\'e se rapproche beaucoup d'un problème d'ordonnancement. De ce fait
	nous pourrons aller plus loin que les travaux vus pr\'ec\'edemment et nous tenterons des approches d'ordonnancement 
	et d'optimisation.
	
	\subsection{D\'efinition du vocabulaire}
	Avant tout, il faut d\'efinir ce qu'est un problème d'optimisation. Il y a deux d\'efinitions 
	importantes à donner. La première est propos\'ee par Legrand et Robert dans leur livre \cite{def1-ordo} :
	\begin{definition}
		\label{def-ordo1}
		Un ordonnancement d'un système de t\^aches $G\ =\ (V,\ E,\ w)$ est une fonction $\sigma$ : 
		$V \rightarrow \mathbb{N}$ telle que $\sigma(u) + w(u) \leq \sigma(v)$ pour toute arête $(u,\ v) \in E$.
	\end{definition}
	
	Dit plus simplement, l'ensemble $V$ repr\'esente les t\^aches à ex\'ecuter, l'ensemble $E$ repr\'esente les d\'ependances 
	des t\^aches et $w$ les temps d'ex\'ecution de la t\^ache. La fonction $\sigma$ donne donc l'heure de d\'ebut de 
	chacune des t\^aches. La d\'efinition dit que si une t\^ache $v$ d\'epend d'une t\^ache $u$ alors 
	la date de d\'ebut de $v$ sera plus grande ou \'egale au d\'ebut de l'ex\'ecution de la t\^ache $u$ plus son 
	temps d'ex\'ecution.
	
	Une autre d\'efinition importante qui est propos\'ee par Leung et al. \cite{def2-ordo} est :
	\begin{definition}
		\label{def-ordo2}
		L'ordonnancement traite de l'allocation de ressources rares à des activit\'es avec
		l'objectif d'optimiser un ou plusieurs critères de performance.
	\end{definition}
	
	Cette d\'efinition est plus g\'en\'erique mais elle nous int\'eresse d'avantage que la d\'efinition \ref{def-ordo1}.
	En effet, la partie qui nous int\'eresse dans cette première d\'efinition est le respect de la pr\'ec\'edance des t\^aches.
	Dans les faits les dates de d\'ebut ne nous int\'eressent pas r\'eellement.
	
	En revanche la d\'efinition \ref{def-ordo2} sera au c\oe{}ur du projet. Pour se convaincre de cela,
	il nous faut d'abord d\'efinir quel est le type de problème d'ordonnancement qu'on traite et quelles 
	sont les m\'ethodes qu'on peut appliquer.
	
	Les problèmes d'ordonnancement peuvent être class\'es en diff\'erentes cat\'egories :
	\begin{itemize}
		\item T\^aches ind\'ependantes : dans cette cat\'egorie de problèmes, les t\^aches sont complètement ind\'ependantes 
		les unes des autres. Dans notre cas, ce n'est pas le plus adapt\'e.
		\item Graphe de t\^aches : la d\'efinition \ref{def-ordo1} d\'ecrit cette cat\'egorie. La plupart du temps,
		les t\^aches sont repr\'esent\'ees par une DAG. Cette cat\'egorie est très proche de notre cas puisque nous devons \'egalement ex\'ecuter 
		des t\^aches qui ont un certain nombre de d\'ependances. On pourra même dire que dans certain cas, 
		on a des anti-arbres, c'est à dire que nous avons une multitude de t\^aches d'entr\'ees qui convergent vers une 
		t\^ache de fin. 
		\item Workflow : cette cat\'egorie est une sous cat\'egorie des graphes de t\^aches dans le sens où
		il s'agit d'un graphe de t\^aches r\'ep\'et\'e de nombreuses de fois. C'est exactement ce type de problème
		que nous traitons ici.
	\end{itemize}
	
	Bien entendu, cette liste n'est pas exhaustive et il existe de nombreuses autres classifications et sous-classifications
	de ces problèmes. Nous n'avons parl\'e ici que des cat\'egories les plus communes.
	
	Un autre point à d\'efinir, est le critère d'optimisation. Il y a là encore un grand nombre de 
	critères possibles. Nous allons donc parler des principaux :
	\begin{itemize}
		\item Temps de compl\'etion total (ou Makespan en anglais) : ce critère est l'un des critères d'optimisation
		les plus courant. Il s'agit donc de minimiser la date de fin de la dernière t\^ache de l'ensemble des 
		t\^aches à ex\'ecuter. L'enjeu de cette optimisation est donc de trouver l'ordonnancement optimal permettant
		la fin d'ex\'ecution au plus tôt.
		\item Somme des temps d'ex\'ecution (Flowtime en anglais) : il s'agit de faire la somme des temps d'ex\'ecution de toutes les t\^aches
		et d'optimiser ce r\'esultat.
		\item Le d\'ebit : ce critère quant à lui, vise à augmenter au maximum le d\'ebit de traitement des donn\'ees.
	\end{itemize}
	
	En plus de cela, on peut avoir besoin de plusieurs critères d'optimisation. Il s'agit dans ce cas d'une optimisation
	multi-critères. Bien entendu, cela complexifie d'autant plus le problème car la solution la plus optimale pour un
	des critères peut être très mauvaise pour un autre critère. De ce cas, il s'agira de trouver une solution qui permet
	de faire le meilleur compromis entre tous les critères.
		
	
	\subsection{Formalisation du problème}
	\label{formalisation}
	Maintenant que nous avons donn\'e le vocabulaire li\'e à l'ordonnancement, nous allons pouvoir essayer caract\'eriser 
	formellement notre problème. En effet, nous allons reprendre les contraintes \'enonc\'ees dans la sections \ref{def-contraintes}
	et nous essayerons de les formaliser le plus finement possible.
	
	Comme nous l'avons dit, une t\^ache est un bloc de traitement. Chaque t\^ache $i$ dispose d'un ensemble de paramètres
	que nous nommerons $\mathcal{P}_{i}$. Cet ensemble $\mathcal{P}_i$ est propre à chaque t\^ache et il variera d'une
	t\^ache à l'autre. Nous reviendrons plus tard sur les paramètres qui peuvent composer cet ensemble.
	
	Outre cet ensemble $\mathcal{P}_i$, chaque t\^ache dispose de paramètres communs :
	\begin{itemize}
		\item Dur\'ee de la t\^ache : Comme nous l'avons dit auparavant, dans le cadre d'un FPGA le temps est compt\'e en nombre de coup d'horloge.
		En outre, les blocs sont toujours sollicit\'es, certains même sont capables de lire et de renvoyer une r\'esultat à chaque coups d'horloge.
		Donc la dur\'ee d'une t\^ache ne peut être le laps de temps entre l'entr\'ee d'une donn\'ee et la sortie d'une autre. Nous d\'efinirons la 
		dur\'ee comme le temps de traitement d'une donn\'ee, c'est à dire la diff\'erence de temps entre la date de sortie d'une donn\'ee 
		et de sa date d'entr\'ee. Nous nommerons cette dur\'ee $\delta_i$. % Je devrais la nomm\'ee w comme dans la def2
		\item La pr\'ecision : La pr\'ecision d'une donn\'ee est le nombre de bits significatifs qu'elle compte. En effet, au fil des traitements 
		les pr\'ecisions peuvent varier. On nomme donc la pr\'ecision d'entr\'ee d'une t\^ache $i$ comme $\pi_i^-$ et la pr\'ecision en sortie $\pi_i^+$.
		\item La fr\'equence du flux en entr\'ee (ou sortie) : Cette fr\'equence repr\'esente la fr\'equence des donn\'ees qui arrivent (resp. sortent). 
		Selon les t\^aches, les fr\'equences varieront. En effet, certains blocs ralentissent le flux c'est pourquoi on distingue la fr\'equence du
		flux en entr\'ee et la fr\'equence en sortie. Nous nommerons donc la fr\'equence du flux en entr\'ee $f_i^-$ et la fr\'equence en sortie $f_i^+$.
		\item La quantit\'e de donn\'ees en entr\'ee (ou en sortie) : Il s'agit de la quantit\'e de donn\'ees que le bloc s'attend à traiter (resp.
		est capable de produire). Les t\^aches peuvent avoir à traiter des gros volumes de donn\'ees et n'en ressortir qu'une partie. Cette
		fois encore, il nous faut donc diff\'erencier l'entr\'ee et la sortie. Nous nommerons donc la quantit\'e de donn\'ees entrantes $q_i^-$ 
		et la quantit\'e de donn\'ees sortantes $q_i^+$ pour une t\^ache $i$.
		\item Le d\'ebit d'entr\'ee (ou de sortie) : Ce paramètre correspond au d\'ebit de donn\'ees que la t\^ache est capable de traiter ou qu'elle 
		fournit en sortie. Il s'agit simplement de l'expression des deux pr\'ec\'edents paramètres. Nous d\'efinirons donc la d\'ebit entrant de la 
		t\^ache $i$ comme $d_i^-\ =\ q_i^-\ *\ f_i^-$ et le d\'ebit sortant comme $d_i^+\ =\ q_i^+\ *\ f_i^+$.
		\item La taille de la t\^ache : La taille dans les FPGA \'etant limit\'ee, ce paramètre exprime donc la place qu'occupe la t\^ache au sein du bloc.
		Nous nommerons $\mathcal{A}_i$ cette taille.
		\item Les pr\'ed\'ecesseurs et successeurs d'une t\^ache : cela nous permet de connaître les t\^aches requises pour pouvoir traiter 
		la t\^ache $i$ ainsi que les t\^aches qui en d\'ependent. Ces ensemble sont not\'es $\Gamma _i ^-$ et $ \Gamma _i ^+$ \\
		%TODO Est-ce vraiment un paramètre ?
	\end{itemize}
	
	Ces diff\'erents paramètres communs sont fortement li\'es aux \'el\'ements de $\mathcal{P}_i$. Voici quelques exemples de relations 
	que nous avons identifi\'ees : 
	\begin{itemize}
		\item $ \delta _i ^+ \ = \ \mathcal{F}_{\delta}(\pi_i^-,\ \pi_i^+,\ d_i^-,\ d_i^+,\ \mathcal{P}_i) $ donne le temps d'ex\'ecution
		de la t\^ache en fonction de la pr\'ecision voulue, du d\'ebit et des paramètres internes.
		\item $ \pi _i ^+ \ = \ \mathcal{F}_{p}(\pi_i^-,\ \mathcal{P}_i) $, la fonction $F_p$ donne la pr\'ecision en sortie selon la pr\'ecision de d\'epart
		et les paramètres internes de la t\^ache.
		\item $d_i^+\ =\ \mathcal{F}_d(d_i^-, \mathcal{P}_i)$, la fonction $F_d$ donne le d\'ebit sortant de la t\^ache en fonction du d\'ebit
		sortant et des variables internes de la t\^ache.
		\item $A_i^+\ =\ \mathcal{F}_A(\pi_i^-,\ \pi_i^+,\ d_i^-,\ d_i^+, \mathcal{P}_i)$
	\end{itemize}		
	Pour le moment, nous ne sommes pas capables de donner une d\'efinition g\'en\'erale de ces fonctions. Mais en revanche, 
	sur quelques exemples simples (cf. \ref{def-contraintes}), nous parvenons à donner une \'evaluation de ces fonctions. 
	
	Maintenant que nous avons donn\'e toutes les notations utiles, nous allons \'enoncer des contraintes relatives à notre problème. Soit
	un DGA $G(V,\ E)$, on a pour toutes arêtes $(i, j)\ \in\ E$ les in\'equations suivantes :
	
	\paragraph{Contrainte de pr\'ecision :}
	Cette in\'equation traduit la contrainte de pr\'ecision d'une t\^ache à l'autre : 
	\begin{align*}
		\pi _i ^+ \geq \pi _j ^-
	\end{align*}
	
	\paragraph{Contrainte de d\'ebit :}
	Cette in\'equation traduit la contrainte de d\'ebit d'une t\^ache à l'autre : 
	\begin{align*}
		d _i ^+ = q _j ^- * (f_i + (1 / s_j) ) & \text{ où } s_j \text{ est une valeur positive de temporisation de la t\^ache}
	\end{align*}
	
	\paragraph{Contrainte de synchronisation :}
	Il s'agit de la contrainte qui impose que si à un moment du traitement, le DAG se s\'epare en plusieurs branches parallèles 
	et qu'elles se rejoignent plus tard, la somme des latences sur chacune des branches soit la même.
	Plus formellement, s'il existe plusieurs chemins disjoints, partant de la t\^ache $s$ et allant à la t\^ache de $f$ alors :
	\begin{align*}
		\forall \text{ chemin } \mathcal{C}1(s, .., f), 
			\forall \text{ chemin } \mathcal{C}2(s, .., f) 
				\text{ tel que } \mathcal{C}1 \neq \mathcal{C}2 
		\Rightarrow 
			\sum _{i} ^{i \in \mathcal{C}1} \delta_i = \sum _{i} ^{i \in \mathcal{C}2} \delta_i
	\end{align*}
	
	\paragraph{Contrainte de place :}
	Cette in\'equation traduit la contrainte de place dans le FPGA. La taille max de la puce FPGA est nomm\'e $\mathcal{A}_{FPGA}$ : 
	\begin{align*}
		\sum ^{\text{t\^ache } i} \mathcal{A}_i \leq \mathcal{A}_{FPGA}
	\end{align*}
	
	\subsection{Exemples de mod\'elisation}
	\label{exemples-modeles}
	Nous allons maintenant prendre quelques blocs de traitement simples afin d'illustrer au mieux notre modèle. 
	Pour tous nos exemple, nous prendrons un d\'ebit en entr\'ee de 200 Mo/s avec une pr\'ecision de 16 bit.
	
	Prenons tout d'abord l'exemple d'un bloc de d\'ecimation. Le but de ce bloc est de ralentir le flux en ne gardant
	que certaines donn\'ees à intervalle r\'egulier. Cet intervalle est appel\'e le facteur de d\'ecimation, on le notera $N$.
	
	Donc d'après notre mod\'elisation :
	\begin{itemize}
		\item $N \in \mathcal{P}_i$
		%TODO N ou 1 ?
		\item $\delta _i = N\ c.h.$ (coup d'horloge)
		\item $\pi _i ^+ = \pi _i ^- = 16 bits$
		\item $f _i ^+ = f _i ^-$
		\item $q _i ^+ = q _i ^- / N$
		\item $d _i ^+ = q _i ^- / N / f _i ^-$
		\item $\Gamma _i ^+ = \Gamma _i ^- = 1$\\
		%TODO Je ne sais pas trouver la taille...
	\end{itemize}
	
	Un autre exemple int\'eressant que l'on peut donner, c'est le cas des spliters. Il s'agit la aussi d'un bloc très 
	simple qui permet de dupliquer un flux. On peut donc donner un nombre de sorties à cr\'eer, on note ce paramètre 
	%TODO pas très inspir\'e...
	$X$. Voici ce que donne notre mod\'elisation :
	\begin{itemize}
		\item $X \in \mathcal{P}_i$
		\item $\delta _i = 1\ c.h.$
		\item $\pi _i ^+ = \pi _i ^- = 16 bits$
		\item $f _i ^+ = f _i ^-$
		\item $q _i ^+ = q _i ^-$
		\item $d _i ^+ = d _i ^-$
		\item $\Gamma _i ^- = 1$
		\item $\Gamma _i ^+ = X$\\
	\end{itemize}
	
	L'exemple suivant traite du cas du shifter. Il s'agit d'un bloc qui a pour but de diminuer le nombre de bits des
	donn\'ees afin d'acc\'el\'erer les traitement sur les blocs suivants. On peut donc donner le nombre de bits à shifter, 
	on note ce paramètre $S$. Voici ce que donne notre mod\'elisation :
	\begin{itemize}
		\item $S \in \mathcal{P}_i$
		\item $\delta _i = 1\ c.h.$
		\item $\pi _i ^+ = \pi _i ^- - S$
		\item $f _i ^+ = f _i ^-$
		\item $q _i ^+ = q _i ^-$
		\item $d _i ^+ = d _i ^-$
		\item $\Gamma _i ^+ = \Gamma _i ^- = 1$\\
	\end{itemize}
	
	Nous allons traiter un dernier exemple un peu plus complexe, le cas d'un filtre d\'ecimateur (ou FIR). Ce bloc 
	est compos\'e de beaucoup de paramètres internes. On peut d\'efinir un nombre d'\'etages $E$, qui repr\'esente le nombre
	d'it\'erations à faire avant d'arrêter le traitement. Afin d'effectuer son filtrage, on doit donner au bloc un ensemble 
	de coefficients $C$ et par cons\'equent ces coefficients ont leur propre pr\'ecision $\pi _C$. Pour finir, le dernier
	paramètre à donner est le facteur de d\'ecimation $N$. Si on applique notre mod\'elisation, on peut obtenir cela :
	\begin{itemize}
		\item $E \in \mathcal{P}_i$
		\item $C \in \mathcal{P}_i$
		\item $\pi _C \in \mathcal{P}_i$
		\item $N \in \mathcal{P}_i$
		\item $\delta _i = E * |C| * q_i^-\ c.h.$ %Trop simpliste
		\item $\pi _i ^+ = \pi _i ^- * \pi _C$
		\item $f _i ^+ = f _i ^-$
		\item $q _i ^+ = q _i ^- / N$
		\item $d _i ^+ = q _i ^- / N / f _i ^-$
		\item $\Gamma _i ^+ = \Gamma _i ^- = 1$\\
	\end{itemize}
	
	Ces exemples ne sont que des modèles provisoires; pour s'assurer de leur performance, il faudra les 
	confronter à des simulations.
	
	
Bien que les articles sur les skeletons, \cite{gwen-cogen}, \cite{skeleton} et \cite{hide}, nous aient donn\'e des indices sur une possible 
	mod\'elisation, ils \'etaient encore trop focalis\'es sur l'optimisation spatiale des blocs. Nous nous sommes donc inspir\'es de ces travaux
	pour proposer notre modèle, en faisant abstraction des optimisations bas niveau.
	
\bibliographystyle{IEEEtran}
\bibliography{references,biblio}
\end{document}