X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/dmems12.git/blobdiff_plain/378804e7fc26018b70fc8beafbb03b16a0e536f2..77fc759e3cccd43e2d9f6ee355069a0e80e5221f:/dmems12.tex diff --git a/dmems12.tex b/dmems12.tex index 806e509..d8d592d 100644 --- a/dmems12.tex +++ b/dmems12.tex @@ -1,7 +1,9 @@ -\documentclass[12pt]{article} + +\documentclass[10pt, conference, compsocconf]{IEEEtran} %\usepackage{latex8} %\usepackage{times} -\usepackage[latin1]{inputenc} +\usepackage[utf8]{inputenc} +%\usepackage[cyr]{aeguill} %\usepackage{pstricks,pst-node,pst-text,pst-3d} %\usepackage{babel} \usepackage{amsmath} @@ -16,34 +18,45 @@ \usepackage{fullpage} \usepackage{fancybox} +\usepackage[ruled,lined,linesnumbered]{algorithm2e} + %%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. \newcommand{\noun}[1]{\textsc{#1}} \newcommand{\tab}{\ \ \ } -%%%%%%%%%%%%%%%%%%%%%%%%%%%% my bib path. + + +\begin{document} + + +%% \author{\IEEEauthorblockN{Authors Name/s per 1st Affiliation (Author)} +%% \IEEEauthorblockA{line 1 (of Affiliation): dept. name of organization\\ +%% line 2: name of organization, acronyms acceptable\\ +%% line 3: City, Country\\ +%% line 4: Email: name@xyz.com} +%% \and +%% \IEEEauthorblockN{Authors Name/s per 2nd Affiliation (Author)} +%% \IEEEauthorblockA{line 1 (of Affiliation): dept. name of organization\\ +%% line 2: name of organization, acronyms acceptable\\ +%% line 3: City, Country\\ +%% line 4: Email: name@xyz.com} +%% } + \title{Using FPGAs for high speed and real time cantilever deflection estimation} +\author{\IEEEauthorblockN{Raphaël Couturier\IEEEauthorrefmark{1}, Stéphane Domas\IEEEauthorrefmark{1}, Gwenhaël Goavec-Merou\IEEEauthorrefmark{2} and Michel Lenczner\IEEEauthorrefmark{2}} +\IEEEauthorblockA{\IEEEauthorrefmark{1}FEMTO-ST, DISC, University of Franche-Comte, Belfort, France\\ +\{raphael.couturier,stephane.domas\}@univ-fcomte.fr} +\IEEEauthorblockA{\IEEEauthorrefmark{2}FEMTO-ST, Time-Frequency, University of Franche-Comte, Besançon, France\\ +\{michel.lenczner@utbm.fr,gwenhael.goavec@trabucayre.com} +} + + -\author{ Raphaël COUTURIER\\ -Laboratoire d'Informatique -de l'Universit\'e de Franche-Comt\'e, \\ -BP 527, \\ -90016~Belfort CEDEX, France\\ - \and Stéphane Domas\\ -Laboratoire d'Informatique -de l'Universit\'e de Franche-Comt\'e, \\ -BP 527, \\ -90016~Belfort CEDEX, France\\ - \and Gwenhaël Goavec\\ -?? -?? \\ -??, \\ -??\\} -\begin{document} \maketitle @@ -58,34 +71,100 @@ BP 527, \\ \section{Introduction} -%% blabla + +Cantilevers are used inside atomic force microscope (AFM) which provides high +resolution images of surfaces. Several technics have been used to measure the +displacement of cantilevers in litterature. For example, it is possible to +determine accurately the deflection with different mechanisms. +In~\cite{CantiPiezzo01}, authors used piezoresistor integrated into the +cantilever. Nevertheless this approach suffers from the complexity of the +microfabrication process needed to implement the sensor in the cantilever. +In~\cite{CantiCapacitive03}, authors have presented an cantilever mechanism +based on capacitive sensing. This kind of technic also involves to instrument +the cantiliver which result in a complex fabrication process. + +In this paper our attention is focused on a method based on interferometry to +measure cantilevers' displacements. In this method cantilevers are illuminated +by an optic source. The interferometry produces fringes on each cantilevers +which enables to compute the cantilever displacement. In order to analyze the +fringes a high speed camera is used. Images need to be processed quickly and +then a estimation method is required to determine the displacement of each +cantilever. In~\cite{AFMCSEM11}, the authors have used an algorithm based on +spline to estimate the cantilevers' positions. + + The overall process gives +accurate results but all the computation are performed on a standard computer +using labview. Consequently, the main drawback of this implementation is that +the computer is a bootleneck in the overall process. In this paper we propose to +use a method based on least square and to implement all the computation on a +FGPA. + +The remainder of the paper is organized as follows. Section~\ref{sec:measure} +describes more precisely the measurement process. Our solution based on the +least square method and the implementation on FPGA is presented in +Section~\ref{sec:solus}. Experimentations are described in +Section~\ref{sec:results}. Finally a conclusion and some perspectives are +presented. + + + %% quelques ref commentées sur les calculs basés sur l'interférométrie -\section{Measurement architecture} -\label{sec:measure-archi} +\section{Measurement principles} +\label{sec:measure} + + + + + + + +\subsection{Architecture} +\label{sec:archi} %% description de l'architecture générale de l'acquisition d'images %% avec au milieu une unité de traitement dont on ne précise pas ce %% qu'elle est. -%% image tirée des expériences. - -\section{Design goals} -\label{sec:goals} +In order to develop simple, cost effective and user-friendly cantilever arrays, +authors of ~\cite{AFMCSEM11} have developped a system based of +interferometry. In opposition to other optical based systems, using a laser beam +deflection scheme and sentitive to the angular displacement of the cantilever, +interferometry is sensitive to the optical path difference induced by the +vertical displacement of the cantilever. + +The system build by authors of~\cite{AFMCSEM11} has been developped based on a +Linnick interferomter~\cite{Sinclair:05}. It is illustrated in +Figure~\ref{fig:AFM}. A laser diode is first split (by the splitter) into a +reference beam and a sample beam that reachs the cantilever array. In order to +be able to move the cantilever array, it is mounted on a translation and +rotational hexapod stage with five degrees of freedom. The optical system is +also fixed to the stage. Thus, the cantilever array is centered in the optical +system which can be adjusted accurately. The beam illuminates the array by a +microscope objective and the light reflects on the cantilevers. Likewise the +reference beam reflects on a movable mirror. A CMOS camera chip records the +reference and sample beams which are recombined in the beam splitter and the +interferogram. At the beginning of each experiment, the movable mirror is +fitted manually in order to align the interferometric fringes approximately +parallel to the cantilevers. When cantilevers move due to the surface, the +bending of cantilevers produce movements in the fringes that can be detected +with the CMOS camera. Finally the fringes need to be +analyzed. In~\cite{AFMCSEM11}, the authors used a LabView program to compute the +cantilevers' movements from the fringes. + +\begin{figure} +\begin{center} +\includegraphics[width=\columnwidth]{AFM} +\end{center} +\caption{schema of the AFM} +\label{fig:AFM} +\end{figure} -%% objectifs en terme de rapidité et de précision, avec en vue l'ajout -%% du contrôle => l'unité de traitement qui s'impose est un FPGA => -%% algo adapté au FPGA. -%% peut etre que cette section peut être déplacée en intro ... à voir. - -\section{Proposed solution} -\label{sec:solus} +%% image tirée des expériences. \subsection{Cantilever deflection estimation} +\label{sec:deflest} -%% => faire de l'interpolation de signal sinusoidal -%% descriptif rapide des deux méthodes : splines et moindres carrés As shown on image \ref{img:img-xp}, each cantilever is covered by interferometric fringes. The fringes will distort when cantilevers are deflected. Estimating the deflection is done by computing this @@ -113,19 +192,72 @@ where $x$ is the position of a pixel in its associated segment. The global method consists in two main sequences. The first one aims to determin the frequency $f$ of each profile with an algorithm based -on spline interpolation (see below). It also computes the coefficient -used for unwrapping the phase. The second one is the acquisition loop, -while which images are taken at regular time steps. For each image, -the phase $\theta$ of all profiles is computed to obtain, after -unwrapping, the deflection of cantilevers. - -This phase computation is obviously the bottle-neck of the whole -process. For example, if we consider the camera actually in use, an -exposition time of 2.5ms for $1024\times 1204$ pixels seems the -minimum that can be reached. For a $10\times 10$ cantilever array, if -we neglect the time to extract pixels, it implies that computing the -deflection of a single cantilever should take less than 25$µ$s, which is -quite small. +on spline interpolation (see section \ref{algo-spline}). It also +computes the coefficient used for unwrapping the phase. The second one +is the acquisition loop, while which images are taken at regular time +steps. For each image, the phase $\theta$ of all profiles is computed +to obtain, after unwrapping, the deflection of cantilevers. + +\subsection{Design goals} +\label{sec:goals} + +If we put aside some hardware issues like the speed of the link +between the camera and the computation unit, the time to deserialize +pixels and to store them in memory, ... the phase computation is +obviously the bottle-neck of the whole process. For example, if we +consider the camera actually in use, an exposition time of 2.5ms for +$1024\times 1204$ pixels seems the minimum that can be reached. For a +$10\times 10$ cantilever array, if we neglect the time to extract +pixels, it implies that computing the deflection of a single +cantilever should take less than 25$\mu$s, thus 12.5$\mu$s by phase.\\ + +In fact, this timing is a very hard constraint. Let consider a very +small programm that initializes twenty million of doubles in memory +and then does 1000000 cumulated sums on 20 contiguous values +(experimental profiles have about this size). On an intel Core 2 Duo +E6650 at 2.33GHz, this program reaches an average of 155Mflops. It +implies that the phase computation algorithm should not take more than +$240\times 12.5 = 1937$ floating operations. For integers, it gives +$3000$ operations. + +%% to be continued ... + +%% � faire : timing de l'algo spline en C avec atan et tout le bordel. + + + + +\section{Proposed solution} +\label{sec:solus} + + +\subsection{FPGA constraints} + +A field-programmable gate array (FPGA) is an integrated circuit designed to be +configured by the customer. A hardware description language (HDL) is used to +configure a FPGA. FGPAs are composed of programmable logic components, called +logic blocks. These blocks can be configured to perform simple (AND, XOR, ...) +or complex combinational functions. Logic blocks are interconnected by +reconfigurable links. Modern FPGAs contains memory elements and multipliers +which enables to simplify the design and increase the speed. As the most complex +operation operation on FGPAs is the multiplier, design of FGPAs should not used +complex operations. For example, a divider is not an available operation and it +should be programmed using simple components. + +FGPAs programming is very different from classic processors programming. When +logic block are programmed and linked to performed an operation, they cannot be +reused anymore. FPGA are cadenced slowly than classic processors but they can +performed pipelined as well as pipelined operations. A pipeline provides a way +manipulate data quickly since at each clock top to handle a new data. However, +using a pipeline consomes more logics and components since they are not +reusable, nevertheless it is probably the most efficient technique on FPGA. +Parallel operations can be used in order to manipulate several data +simultaneously. When it is possible, using a pipeline is a good solution to +manipulate new data at each clock top and using parallelism to handle +simultaneously several data streams. + +%% contraintes imposées par le FPGA : algo pipeline/parallele, pas d'op math complexe, ... + \subsection{Considered algorithms} @@ -137,7 +269,7 @@ classical least square method but suppose that frequency is already known. \subsubsection{Spline algorithm} - +\label{sec:algo-spline} Let consider a profile $P$, that is a segment of $M$ pixels with an intensity in gray levels. Let call $I(x)$ the intensity of profile in $x \in [0,M[$. @@ -228,20 +360,77 @@ computed. \end{itemize} -\subsubsection{Comparison} - -\subsection{FPGA constraints} +Finally, the whole summarizes in an algorithm (called LSQ in the following) in two parts, one before and one during the acquisition loop : +\begin{algorithm}[h] +\caption{LSQ algorithm - before acquisition loop.} +\label{alg:lsq-before} + + $M \leftarrow $ number of pixels of the profile\\ + I[] $\leftarrow $ intensities of pixels\\ + $f \leftarrow $ frequency of the profile\\ + $s4i \leftarrow \sum_{i=0}^{M-1} sin(4\pi f.i)$\\ + $c4i \leftarrow \sum_{i=0}^{M-1} cos(4\pi f.i)$\\ + $nb_s \leftarrow $ number of discretization steps of $[-\pi,\pi]$\\ + + \For{$i=0$ to $nb_s $}{ + $\theta \leftarrow -\pi + 2\pi\times \frac{i}{nb_s}$\\ + lut\_sin[$i$] $\leftarrow sin \theta$\\ + lut\_cos[$i$] $\leftarrow cos \theta$\\ + lut\_A[$i$] $\leftarrow cos 2 \theta \times s4i + sin 2 \theta \times c4i$\\ + lut\_sinfi[$i$] $\leftarrow sin (2\pi f.i)$\\ + lut\_cosfi[$i$] $\leftarrow cos (2\pi f.i)$\\ + } +\end{algorithm} + +\begin{algorithm}[h] +\caption{LSQ algorithm - during acquisition loop.} +\label{alg:lsq-during} + + $\bar{x} \leftarrow \frac{M-1}{2}$\\ + $\bar{y} \leftarrow 0$, $x_{var} \leftarrow 0$, $xy_{covar} \leftarrow 0$\\ + \For{$i=0$ to $M-1$}{ + $\bar{y} \leftarrow \bar{y} + $ I[$i$]\\ + $x_{var} \leftarrow x_{var} + (i-\bar{x})^2$\\ + } + $\bar{y} \leftarrow \frac{\bar{y}}{M}$\\ + \For{$i=0$ to $M-1$}{ + $xy_{covar} \leftarrow xy_{covar} + (i-\bar{x}) \times (I[i]-\bar{y})$\\ + } + $slope \leftarrow \frac{xy_{covar}}{x_{var}}$\\ + $start \leftarrow y_{moy} - slope\times \bar{x}$\\ + \For{$i=0$ to $M-1$}{ + $I[i] \leftarrow I[i] - start - slope\times i$\tcc*[f]{slope removal}\\ + } + + $I_{max} \leftarrow max_i(I[i])$, $I_{min} \leftarrow min_i(I[i])$\\ + $amp \leftarrow \frac{I_{max}-I_{min}}{2}$\\ + + $Is \leftarrow 0$, $Ic \leftarrow 0$\\ + \For{$i=0$ to $M-1$}{ + $Is \leftarrow Is + I[i]\times $ lut\_sinfi[$i$]\\ + $Ic \leftarrow Ic + I[i]\times $ lut\_cosfi[$i$]\\ + } + + $\theta \leftarrow -\pi$\\ + $val_1 \leftarrow 2\times \left[ Is.\cos(\theta) + Ic.\sin(\theta) \right] - amp\times \left[ c4i.\sin(2\theta) + s4i.\cos(2\theta) \right]$\\ + \For{$i=1-n_s$ to $n_s$}{ + $\theta \leftarrow \frac{i.\pi}{n_s}$\\ + $val_2 \leftarrow 2\times \left[ Is.\cos(\theta) + Ic.\sin(\theta) \right] - amp\times \left[ c4i.\sin(2\theta) + s4i.\cos(2\theta) \right]$\\ + + \lIf{$val_1 < 0$ et $val_2 >= 0$}{ + $\theta_s \leftarrow \theta - \left[ \frac{val_2}{val_2-val_1}\times \frac{\pi}{n_s} \right]$\\ + } + $val_1 \leftarrow val_2$\\ + } + +\end{algorithm} -%% contraintes imposées par le FPGA : algo pipeline/parallele, pas d'op math complexe, ... - -\subsection{Least square algorithm} -%% description précise -%% avantage sur FPGA +\subsubsection{Comparison} -\subsection{VDHL design paradigms} +\subsection{VHDL design paradigms} -\subsection{VDHL implementation} +\subsection{VHDL implementation} \section{Experimental results} \label{sec:results}