6ème commit

[dmems12.git] / dmems12.tex

diff --git a/dmems12.tex b/dmems12.tex
index f559661e358c7e6f2041166b10f9a7a69daf7081..3fd1ca1636cf186c473dce04b75c496ee6f81b0d 100644 (file)
--- a/dmems12.tex
+++ b/dmems12.tex
@@ -71,20 +71,27 @@
 
 \section{Introduction}
 
 
 \section{Introduction}
 

-Cantilevers  are  used  inside  atomic  force  microscope  which  provides  high
+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
 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        optic
-interferometer~\cite{CantiOptic89},     pizeoresistor~\cite{CantiPiezzo01}    or
-capacitive  sensing~\cite{CantiCapacitive03}.  In  this paper  our  attention is
-focused   on  a  method   based  on   interferometry  to   measure  cantilevers'
-displacements.   In  this  method   cantilevers  are  illiminated  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} {\bf verifier ref}, the authors have used an algorithm based
-on spline  to estimate  the cantilevers' positions.   The overall  process gives
+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
 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


@@ -105,12 +112,54 @@ presented.
 \section{Measurement principles}
 \label{sec:measure}
 
 \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.
 
 \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.
 

+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}
+
+

 %% image tirée des expériences.
 
 \subsection{Cantilever deflection estimation}
 %% image tirée des expériences.
 
 \subsection{Cantilever deflection estimation}


@@ -147,19 +196,30 @@ 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
 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.
+to obtain, after unwrapping, the deflection of
+cantilevers. Originally, this computation was also done with an
+algorithm based on spline. This article proposes a new version based
+on a least square method.

 
 \subsection{Design goals}
 \label{sec:goals}
 
 
 \subsection{Design goals}
 \label{sec:goals}
 

+The main goal is to implement a computing unit to estimate the
+deflection of about $10\times10$ cantilevers, faster than the stream of
+images coming from the camera. The accuracy of results must be close
+to the maximum precision ever obtained experimentally on the
+architecture, i.e. 0.3nm. Finally, the latency between an image
+entering in the unit and the deflections must be as small as possible
+(NB : future works plan to add some control on the cantilevers).\\
+

 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
 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
+$1024\times 1204$ pixels seems the minimum that can be reached. For
+100 cantilevers, 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
 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


@@ -168,24 +228,105 @@ 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
 (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.
-
-
+$155\times 12.5 = 1937$ floating operations. For integers, it gives
+$3000$ operations. Obviously, some cache effects and optimizations on
+huge amount of computations can drastically increase these
+performances : peak efficiency is about 2.5Gflops for the considered
+CPU. But this is not the case for phase computation that used only few
+tenth of values.\\
+
+In order to evaluate the original algorithm, we translated it in C
+language. Profiles are read from a 1Mo file, as if it was an image
+stored in a device file representing the camera. The file contains 100
+profiles of 21 pixels, equally scattered in the file. We obtained an
+average of 10.5$\mu$s by profile (including I/O accesses). It is under
+are requirements but close to the limit. In case of an occasional load
+of the system, it could be largely overtaken. A solution would be to
+use a real-time operating system but another one to search for a more
+efficient algorithm.
+
+But the main drawback is the latency of such a solution : since each
+profile must be treated one after another, the deflection of 100
+cantilevers takes about $200\times 10.5 = 2.1$ms, which is inadequate
+for an efficient control. An obvious solution is to parallelize the
+computations, for example on a GPU. Nevertheless, the cost to transfer
+profile in GPU memory and to take back results would be prohibitive
+compared to computation time. It is certainly more efficient to
+pipeline the computation. For example, supposing that 200 profiles of
+20 pixels can be pushed sequentially in the pipelined unit cadenced at
+a 100MHz (i.e. a pixel enters in the unit each 10ns), all profiles
+would be treated in $200\times 20\times 10.10^{-9} =$ 40$\mu$s plus
+the latency of the pipeline. This is about 500 times faster than
+actual results.\\
+
+For these reasons, an FPGA as the computation unit is the best choice
+to achieve the required performance. Nevertheless, passing from
+a C code to a pipelined version in VHDL is not obvious at all. As
+explained in the next section, it can even be impossible because of
+some hardware constraints specific to FPGAs.

 
 
 \section{Proposed solution}
 \label{sec:solus}
 
 
 
 \section{Proposed solution}
 \label{sec:solus}
 

-
-\subsection{FPGA constraints}
-
-%% contraintes imposées par le FPGA : algo pipeline/parallele, pas d'op math complexe, ...
-
+Project Oscar aims to provide an hardware and software architecture to
+estimate and control the deflection of cantilevers. The hardware part
+consists in a high-speed camera, linked on an embedded board hosting
+FPGAs. By the way, the camera output stream can be pushed directly
+into the FPGA. The software part is mostly the VHDL code that
+deserializes the camera stream, extracts profile and computes the
+deflection. Before focusing on our work to implement the phase
+computation, we give some general informations about FPGAs and the
+board we use.
+
+\subsection{FPGAs}
+
+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 more slowly than classic  processors but they can
+performed pipelined as  well as parallel 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.
+
+\subsection{The board}
+
+The board we use is designed by the Armadeus compagny, under the name
+SP Vision. It consists in a development board hosting a i.MX27 ARM
+processor (from Freescale). The board includes all classical
+connectors : USB, Ethernet, ... A Flash memory contains a Linux kernel
+that can be launched after booting the board via u-Boot.
+
+The processor is directly connected to a Spartan3A FPGA (from Xilinx)
+via its special interface called WEIM. The Spartan3A is itself
+connected to a Spartan6 FPGA. Thus, it is possible to develop programs
+that communicate between i.MX and Spartan6, using Spartan3 as a
+tunnel. By default, the WEIM interface provides a clock signal at
+100MHz that is connected to dedicated FPGA pins.
+
+The Spartan6 is an LX100 version. It has 15822 slices, equivalent to
+101261 logic cells. There are 268 internal block RAM of 18Kbits, and
+180 dedicated multiply-adders (named DSP48), which is largely enough
+for our project.
+
+Some I/O pins of Spartan6 are connected to two $2\times 17$ headers
+that can be used as user wants. For the project, they will be
+connected to the interface card of the camera.

 
 \subsection{Considered algorithms}
 
 
 \subsection{Considered algorithms}
 


@@ -466,18 +607,54 @@ to numbers of pixels $M$. For LSQ, it also depends on $nb_s$ and for
 SPL on $N = k\times M$, i.e. the number of interpolated points. 
 
 We assume that $M=20$, $nb_s=1024$, $k=4$, all possible parts are
 SPL on $N = k\times M$, i.e. the number of interpolated points. 
 
 We assume that $M=20$, $nb_s=1024$, $k=4$, all possible parts are

-already in lookup tables and only arithmetic operations (+, -, *, /)
-are taken account. Translating the two algorithms in C code, we obtain
-about 400 operations for LSQ and 1340 (plus the unknown for $atan$)
-for SPL. Even if the result is largely in favor of LSQ, we can notice
-that executing the C code (compiled with \tt{-O3}) of SPL on an
-2.33GHz Core 2 Duo only takes 6.5µs in average, which is under our
-desing goals. The final decision is thus driven by the third criterion.\\
+already in lookup tables and a limited set of operations (+, -, *, /,
+<, >) is taken account. Translating the two algorithms in C code, we
+obtain about 430 operations for LSQ and 1550 (plus few tenth for
+$atan$) for SPL. This result is largely in favor of LSQ. Nevertheless,
+considering the total number of operations is not really pertinent for
+an FPGA implementation : it mainly depends on the type of operations
+and their
+ordering. The final decision is thus driven by the third criterion.\\

 
 The Spartan 6 used in our architecture has hard constraint : it has no
 
 The Spartan 6 used in our architecture has hard constraint : it has no

-floating point units. Thus, all computations have to be done with
-integers. 
-
+built-in floating point units. Obviously, it is possible to use some
+existing "black-boxes" for double precision operations. But they have
+a quite long latency. It is much simpler to exclusively use integers,
+with a quantization of all double precision values. Obviously, this
+quantization should not decrease too much the precision of
+results. Furthermore, it should not lead to a design with a huge
+latency because of operations that could not complete during a single
+or few clock cycles. Divisions are in this case and, moreover, they
+need an varying number of clock cycles to complete. Even
+multiplications can be a problem : DSP48 take inputs of 18 bits
+maximum. For larger multiplications, several DSP must be combined,
+increasing the latency.
+
+Nevertheless, the hardest constraint does not come from the FPGA
+characteristics but from the algorithms. Their VHDL implentation will
+be efficient only if they can be fully (or near) pipelined. By the
+way, the choice is quickly done : only a small part of SPL can be.
+Indeed, the computation of spline coefficients implies to solve a
+tridiagonal system $A.m = b$. Values in $A$ and $b$ can be computed
+from incoming pixels intensity but after, the back-solve starts with
+the lastest values, which breaks the pipeline. Moreover, SPL relies on
+interpolating far more points than profile size. Thus, the end
+of SPL works on a larger amount of data than the beginning, which
+also breaks the pipeline.
+
+LSQ has not this problem : all parts except the dichotomial search
+work on the same amount of data, i.e. the profile size. Furthermore,
+LSQ needs less operations than SPL, implying a smaller output
+latency. Consequently, it is the best candidate for phase
+computation. Nevertheless, obtaining a fully pipelined version
+supposes that operations of different parts complete in a single clock
+cycle. It is the case for simulations but it completely fails when
+mapping and routing the design on the Spartan6. By the way,
+extra-latency is generated and there must be idle times between two
+profiles entering into the pipeline.
+
+Before obtaining the least bitstream, the crucial question is : how to
+translate the C code the LSQ into VHDL ?

 
 
 \subsection{VHDL design paradigms}
 
 
 \subsection{VHDL design paradigms}