-\documentclass[10pt, conference, compsocconf]{IEEEtran}
+\documentclass[10pt, peerreview, compsocconf]{IEEEtran}
%\usepackage{latex8}
%\usepackage{times}
\usepackage[utf8]{inputenc}
\newcommand{\tab}{\ \ \ }
-
\begin{document}
-\maketitle
+%\maketitle
\thispagestyle{empty}
-{\it keywords}: FPGA, cantilever, interferometry.
+
\end{abstract}
+\begin{IEEEkeywords}
+FPGA, cantilever, interferometry.
+\end{IEEEkeywords}
+
+
+\IEEEpeerreviewmaketitle
+
\section{Introduction}
Cantilevers are used inside atomic force microscope (AFM) which provides high
following. Furthermore, a reference profile is taken on the base of
the cantilever array.
-The pixels intensity $I$ (in gray level) of each profile is modelized by :
+The pixels intensity $I$ (in gray level) of each profile is modelized by:
\begin{equation}
\label{equ:profile}
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).\\
+(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
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
-$155\times 12.5 = 1937$ floating operations. For integers, it gives
-$3000$ operations. Obviously, some cache effects and optimizations on
+E6650 at 2.33GHz, this program reaches an average of 155Mflops.
+
+%%Itimplies that the phase computation algorithm should not take more than
+%%$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
+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
+language. As said further, for 20 pixels, it does about 1550
+operations, thus an estimated execution time of $1550/155
+=$10$\mu$s. For a more realistic evaluation, we constructed a file of
+1Mo containing 200 profiles of 20 pixels, equally scattered. This file
+is equivalent to an image stored in a device file representing the
+camera. 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
\section{Proposed solution}
\label{sec:solus}
-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.
+Project Oscar aims to provide a 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 information 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.
+A field-programmable gate array (FPGA) is an integrated circuit
+designed to be configured by the customer. FGPAs are composed of
+programmable logic components, called configurable logic blocks
+(CLB). These blocks mainly contains look-up tables (LUT), flip/flops
+(F/F) and latches, organized in one or more slices connected
+together. Each CLB can be configured to perform simple (AND, XOR, ...)
+or complex combinational functions. They are interconnected by
+reconfigurable links. Modern FPGAs contain memory elements and
+multipliers which enable to simplify the design and to increase the
+performance. Nevertheless, all other complex operations, like
+division, trigonometric functions, $\ldots$ are not available and must
+be done by configuring a set of CLBs. Since this configuration is not
+obvious at all, it can be done via a framework, like ISE. Such a
+software can synthetize a design written in a hardware description
+language (HDL), map it onto CLBs, place/route them for a specific
+FPGA, and finally produce a bitstream that is used to configre the
+FPGA. Thus, from the developper point of view, the main difficulty is
+to translate an algorithm in HDL code, taking account FPGA resources
+and constraints like clock signals and I/O values that drive the FPGA.
+
+Indeed, HDL programming is very different from classic languages like
+C. A program can be seen as a state-machine, manipulating signals that
+evolve from state to state. By the way, HDL instructions can execute
+concurrently. Basic logic operations are used to agregate signals to
+produce new states and assign it to another signal. States are mainly
+expressed as arrays of bits. Fortunaltely, libraries propose some
+higher levels representations like signed integers, and arithmetic
+operations.
+
+Furthermore, even if FPGAs are cadenced more slowly than classic
+processors, they can perform pipeline as well as parallel
+operations. A pipeline consists in cutting a process in sequence of
+small tasks, taking the same execution time. It accepts a new data at
+each clock top, thus, after a known latency, it also provides a result
+at each clock top. However, using a pipeline consumes more logics
+since the components of a task are not reusable by another
+one. Nevertheless it is probably the most efficient technique on
+FPGA. Because of its architecture, it is also very easy to process
+several data concurrently. When it is possible, the best performance
+is reached using parallelism to handle simultaneously several
+pipelines in order to handle multiple 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
+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)
intensity in gray levels. Let call $I(x)$ the intensity of profile in $x
\in [0,M[$.
-At first, only $M$ values of $I$ are known, for $x = 0, 1,
-\ldots,M-1$. A normalisation allows to scale known intensities into
-$[-1,1]$. We compute splines that fit at best these normalised
-intensities. Splines are used to interpolate $N = k\times M$ points
-(typically $k=4$ is sufficient), within $[0,M[$. Let call $x^s$ the
-coordinates of these $N$ points and $I^s$ their intensities.
+At first, only $M$ values of $I$ are known, for $x = 0, 1, \ldots,M-1$. A
+normalisation allows to scale known intensities into $[-1,1]$. We compute
+splines that fit at best these normalised intensities. Splines (SPL in the
+following) are used to interpolate $N = k\times M$ points (typically $k=4$ is
+sufficient), within $[0,M[$. Let call $x^s$ the coordinates of these $N$ points
+ and $I^s$ their intensities.
In order to have the frequency, the mean line $a.x+b$ (see equation \ref{equ:profile}) of $I^s$ is
computed. Finding intersections of $I^s$ and this line allow to obtain
the period thus the frequency.
-The phase is computed via the equation :
+The phase is computed via the equation:
\begin{equation}
\theta = atan \left[ \frac{\sum_{i=0}^{N-1} sin(2\pi f x^s_i) \times I^s(x^s_i)}{\sum_{i=0}^{N-1} cos(2\pi f x^s_i) \times I^s(x^s_i)} \right]
\end{equation}
-Two things can be noticed :
+Two things can be noticed:
\begin{itemize}
\item the frequency could also be obtained using the derivates of
spline equations, which only implies to solve quadratic equations.
\subsubsection{Least square algorithm}
Assuming that we compute the phase during the acquisition loop,
-equation \ref{equ:profile} has only 4 parameters :$a, b, A$, and
+equation \ref{equ:profile} has only 4 parameters: $a, b, A$, and
$\theta$, $f$ and $x$ being already known. Since $I$ is non-linear, a
-least square method based an Gauss-newton algorithm must be used to
+least square method based on a Gauss-newton algorithm can be used to
determine these four parameters. Since it is an iterative process
ending with a convergence criterion, it is obvious that it is not
particularly adapted to our design goals.
Fortunatly, it is quite simple to reduce the number of parameters to
only $\theta$. Let $x^p$ be the coordinates of pixels in a segment of
size $M$. Thus, $x^p = 0, 1, \ldots, M-1$. Let $I(x^p)$ be their
-intensity. Firstly, we "remove" the slope by computing :
+intensity. Firstly, we "remove" the slope by computing:
\[I^{corr}(x^p) = I(x^p) - a.x^p - b\]
Since linear equation coefficients are searched, a classical least
-square method can be used to determine $a$ and $b$ :
+square method can be used to determine $a$ and $b$:
\[a = \frac{covar(x^p,I(x^p))}{var(x^p)} \]
-Assuming an overlined symbol means an average, then :
+Assuming an overlined symbol means an average, then:
\[b = \overline{I(x^p)} - a.\overline{{x^p}}\]
\[A = \frac{max(I^{corr}) - min(I^{corr})}{2}\]
-Then, the least square method to find $\theta$ is reduced to search the minimum of :
+Then, the least square method to find $\theta$ is reduced to search the minimum of:
\[\sum_{i=0}^{M-1} \left[ cos(2\pi f.i + \theta) - \frac{I^{corr}(i)}{A} \right]^2\]
-It is equivalent to derivate this expression and to solve the following equation :
+It is equivalent to derivate this expression and to solve the following equation:
\begin{eqnarray*}
2\left[ cos\theta \sum_{i=0}^{M-1} I^{corr}(i).sin(2\pi f.i) + sin\theta \sum_{i=0}^{M-1} I^{corr}(i).cos(2\pi f.i)\right] \\
- A\left[ cos2\theta \sum_{i=0}^{M-1} sin(4\pi f.i) + sin2\theta \sum_{i=0}^{M-1} cos(4\pi f.i)\right] = 0
\end{eqnarray*}
-Several points can be noticed :
+Several points can be noticed:
\begin{itemize}
\item As in the spline method, some parts of this equation can be
computed before the acquisition loop. It is the case of sums that do
- not depend on $\theta$ :
+ not depend on $\theta$:
\[ \sum_{i=0}^{M-1} sin(4\pi f.i), \sum_{i=0}^{M-1} cos(4\pi f.i) \]
\item The simplest method to find the good $\theta$ is to discretize
$[-\pi,\pi]$ in $nb_s$ steps, and to search which step leads to the
result closest to zero. By the way, three other lookup tables can
- also be computed before the loop :
+ also be computed before the loop:
\[ sin \theta, cos \theta, \]
\end{itemize}
-Finally, the whole summarizes in an algorithm (called LSQ in the following) in two parts, one before and one during the acquisition loop :
+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}
\subsubsection{Comparison}
-We compared the two algorithms on the base of three criterions :
+We compared the two algorithms on the base of three criteria:
\begin{itemize}
\item precision of results on a cosinus profile, distorted with noise,
\item number of operations,
deflection, which is smaller than the best precision they achieved,
i.e. 0.3nm.
-For each test, we add some noise to the profile : each group of two
+For each test, we add some noise to the profile: each group of two
pixels has its intensity added to a random number picked in $[-N,N]$
(NB: it should be noticed that picking a new value for each pixel does
not distort enough the profile). The absolute error on the result is
evaluated by comparing the difference between the reference and
-computed phase, out of $2\pi$, expressed in percents. That is : $err =
+computed phase, out of $2\pi$, expressed in percents. That is: $err =
100\times \frac{|\theta_{ref} - \theta_{comp}|}{2\pi}$.
Table \ref{tab:algo_prec} gives the maximum and average error for the two algorithms and increasing values of $N$.
\begin{figure}[ht]
\begin{center}
- \includegraphics[width=9cm]{intens-noise20-spl}
+ \includegraphics[width=\columnwidth]{intens-noise20}
\end{center}
\caption{Sample of worst profile for N=10}
\label{fig:noise20}
\begin{figure}[ht]
\begin{center}
- \includegraphics[width=9cm]{intens-noise60-lsq}
+ \includegraphics[width=\columnwidth]{intens-noise60}
\end{center}
\caption{Sample of worst profile for N=30}
\label{fig:noise60}
We assume that $M=20$, $nb_s=1024$, $k=4$, all possible parts are
already in lookup tables and a limited set of operations (+, -, *, /,
-<, >) is taken account. Translating the two algorithms in C code, we
+$<$, $>$) 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
+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
-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}
+The Spartan 6 used in our architecture has a hard constraint: it has no 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
+a 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}
+
+\section{Experimental tests}
+
+In this section we explain what we have done yet. Until now, we could not perform
+real experiments since we just have received the FGPA board. Nevertheless, we
+will include real experiments in the final version of this paper.
\subsection{VHDL implementation}
-\section{Experimental results}
+
+
+% - ecriture d'un code en C avec integer
+% - calcul de la taille max en bit de chaque variable en fonction de la quantization.
+% - tests de quantization : équilibre entre précision et contraintes FPGA
+% - en parallèle : simulink et VHDL à la main
+
+
+From the LSQ algorithm, we have written a C program which uses only integer
+values that have been previously scaled. The quantization of doubles into
+integers has been performed in order to obtain a good trade-off between the
+number of bits used and the precision. Finally, we have compared the result of
+the LSQ version using integer and double. We have observed that the results of
+both versions were similar.
+
+Then we have built two versions of VHDL codes: one directly by hand coding and
+the other with Matlab using simulink HDL coder feature. Although the approach is
+completely different we have obtain VHDL codes that are quite comparable. Each
+approach has advantages and drawbacks. Roughly speaking, hand coding provides
+beautiful and much better structures code while HDL coder provides code faster.
+In terms of speed of code, we think that both approaches will be quite
+comparable. Real experiments will confirm that. In the LSQ algorithm, we have
+replaced all the divisions by multiplications by a constant since divisions are
+performed with constants depending of the number of pixels in the profile
+(i.e. $M$).
+
+\subsection{Simulation}
+
+Currently, we only have simulated our VHDL codes with GHDL and GTKWave (two free
+tools with linux). Both approaches led to correct results. At the beginning with
+simulations our pipiline could compute a new phase each 33 cycles and the length
+of the pipeline was equal to 95 cycles. When we tried to generate the bitsream
+with ISE environment we had many problems because many stages required more than
+the 10$n$s availabe. So we needed to decompose some part of the pipeline in order
+to add some cycles and siplify some parts.
+% ghdl + gtkwave
+% au mieux : une phase tous les 33 cycles, latence de 95 cycles.
+% mais routage/placement impossible.
+\subsection{Bitstream creation}
+
+Currently both approaches provide synthesable bitstreams with ISE. We expect
+that the pipeline will have a latency of 112 cycles, i.e. 1.12$\mu$s and it
+could accept new line of pixel each 48 cycles, i.e. 480$n$s.
+
+% pas fait mais prévision d'une sortie tous les 480ns avec une latence de 1120
+
\label{sec:results}
