Congreso FPGAs 2011 Tenerife PDF
Congreso FPGAs 2011 Tenerife PDF
Como en pasadas ediciones, JCRA 2011 se convierte en un lugar de encuentro entre personas y
de intercambio de conocimientos en un campo donde constituye la reunión más importante que,
a nivel nacional, se celebra en el campo de las tecnologías asociadas a la lógica reconfigurable.
Para finalizar, la isla de Tenerife nos ofrece un marco incomparable para la celebración de este
evento, posibilitando a los participantes disfrutar de sus paisajes, gastronomía, historia y de la
hospitalidad de sus habitantes.
Feliz estancia.
PRÓLOGO
España sin duda es un país dado a las FPGAs. Esta relación probablemente se origina por la
escasa implantación en la industria local de tecnologías alternativas como Gate Arrays o
Standard Cells, que ya existían en los años ´90. Los ingenieros españoles acogieron la lógica
programable sin preconceptos, y sin la necesidad de descartar opciones que de otro modo
estarían formando parte de sus productos. En otros países, los usuarios de FPGAs debieron
vencer durante años la resistencia de los especialistas en las tecnologías que estos dispositivos
iban a reemplazar. Gracias a los esfuerzos de los ingenieros de producto de ATD y ADM
comenzaron a ser utilizadas rápidamente por empresas punteras como PESA, CESELSA o
Alcatel. También ayudó la rápida incorporación de estos chips en la docencia de grado. Como
ejemplo, en 1989 ya eran obligatorios en el Laboratorio de Electrónica Digital de la ETSIT
UPM.
Fabricar un ASIC programable por el usuario era un tema que estaba maduro en la década de los
´80. Las primeras FPGAs de Xilinx - originariamente llamadas LCAs (Logic Cell Arrays) –
salieron al mercado en 1985. La nueva idea era sencilla y se basaba en 3 conceptos conocidos.
En primer lugar, utilizar multiplexores para realizar funciones lógicas, en lugar del típico arreglo
de transistores P y N de los gate arrays. Esta aplicación particular de los multiplexores era
enseñada de generación en generación a los estudiantes de Circuitos Lógicos desde la época de
los TTL pues que permitía ahorrar chips, soldaduras y pistas.
1
La segunda innovación también era sencilla y estaba a la vista de todos. La red telefónica de la
época no requería tender un hilo de cobre fijo entre cada par de abonados. En su lugar, existía
una interconexión matricial de cables que se iban conectando mediante conmutadores hasta
formar una unión galvánica entre los puntos a enlazar. Lo que valía para teléfonos también
valdría para los circuitos integrados: no era necesario realizar la metalización fija final de los
masked-programmed chips para mapear un diseño particular sobre una estructura VLSI estándar.
Sólo se necesitaba difundir en el silicio un patrón de pistas más un conjunto de recursos de
interconexión. Entre ambos formarían caminos programables mediante multiplexores y llaves
CMOS activadas por el usuario.
La última idea de las FPGAs era consecuencia de las anteriores: una memoria almacenaría todos
los valores de configuración del dispositivo. En el caso de Xilinx, esta memoria era externa y se
utilizaría una cadena de scan-path para ingresar los bits para configurar los multiplexores que
mapeaban las funciones lógicas y los elementos que rutaban las señales internas. Altera sorteó el
problema mediante una EPROM interna, Lattice con una EEPROM también interna, y Actel con
antifusibles. Sin embargo, los inconvenientes evidentes de la solución de Xilinx no produjeron
rechazo alguno: la utilización de una EPROM auxiliar para arrancar un circuito programable
complejo era algo cotidiano para los miles usuarios de microprocesadores.
Las FPGAs fueron inventadas con la idea de evitar los riesgos de fabricar un masked-ASIC. Este
proceso temible era parecido (y sigue siéndolo) a escribir un programa que se puede compilar
una única vez. Por ello, la reconfigurabilidad se consideraba una característica esencial para
poder corregir los errores de diseño. Pero hubo muchas sorpresas. Poner a disposición de miles
de ingenieros e investigadores un producto como la FPGA, que permite probar soluciones sin
más coste que el tiempo que lleva implementarlas, fue como soltar conejos en Australia.
Los usuarios de μP y DSPs descubrieron que solidificar los algoritmos en el silicio producía
unas aceleraciones muy importantes. Poner 100 multiplicadores en lugar de pasar 100 veces los
datos por el multiplicador de la ALU del procesador realmente cambiaba la cosa. Nacen así los
primeros custom DSPs. Otros ingenieros montaron centenas de FPGAs en tarjetas y racks, junto
con memorias, FIFOS y matrices de conmutación, de modo de poder abordar problemas de
mayor tamaño. Surge así un nuevo acrónimo, FCCMs (FPGA-based custom computer
machines), para indicar supercomputación a precios populares.
2
JCRA 2011 | Tenerife 7-9 de Septiembre
vista de producción, la programabilidad de los dispositivos resultó crucial para poder manejar el
stock de componentes electrónicos en áreas como las telecomunicaciones, donde los cambios de
estándares son aún vertiginosos. Y todas estas opciones están disponibles sin necesidad de
asumir el riesgo de fabricar un circuito integrado. Como decía el irrepetible Peter Alfke de
Xilinx: “nosotros fabricamos ASICs pero vendemos FPGAs”.
Este libro, editado por los profesores Manuel Rodríguez Valido y Eduardo Magdaleno Castelló
de la Universidad de La Laguna, es una fotografía actual de la diversidad de temas de
investigación y aplicaciones relacionados con FPGAs. Cabe destacar las aportaciones en Diseño
de System-on-Chips, Microscopía, Robótica, Custom DSPs, Procesamiento de Imágenes,
Educación, Benchmarking, Supercomputación, Bioingeniería, Análisis Financiero, o codiseño
HW. Los lectores de este libro encontrarán 37 artículos separados en 9 capítulos, que con
seguridad serán fuente de motivación y nuevas ideas para avanzar en este apasionante campo
tecnológico.
Eduardo Boemo
Universidad Autónoma de Madrid
3
JCRA 2011 | Tenerife 7-9 de Septiembre
ÍNDICE
5
6
JCRA 2011 | Tenerife 7-9 de Septiembre
COORDINADORES GENERALES
Manuel Rodríguez Valido
Universidad de La Laguna
Eduardo Magdaleno Castelló
Universidad de La Laguna
COMITÉ LOCAL
Alejandro Ayala Alfonso
Universidad de La Laguna
Silvestre Rodríguez Pérez
Universidad de La Laguna
Oswaldo González Hernández
Universidad de La Laguna
Beatriz Rodríguez Mendoza
Universidad de La Laguna
Moisés Domínguez García
Universidad de La Laguna
Fernando Pérez Nava
Universidad de La Laguna
David Díaz Martín
Universidad de La Laguna
Cristian Sobota Rodríguez
Universidad de La Laguna
COMITÉ DE DIRECCIÓN
Gustavo Sutter Capristo
Universidad Autónoma de Madrid
Miguel Ángel Aguirre Echánove
Universidad de Sevilla
Eduardo Boemo Scalvinoni
Universidad Autónoma de Madrid
Joan Cabestany
Universidad Politécnica de Cataluña
Jordi Carrabina Bordoll
Universidad Autónoma de Barcelona
Sergio Cuenca Asensi
Universidad de Alicante, Coordinador
Denis Navarro
Universidad de Zaragoza
Francisco Pelayo Valle
Universidad de Granada
Juan Manuel Sánchez Pérez
Universidad de Extremadura
José Ignacio Martínez Torre
Universidad Rey Juan Carlos
Juan Suardíaz Muro
Universidad Politécnica de Cartagena
7
COMITÉ DE PROGRAMA
Gustavo Sutter Capristo José Luis Martín González
Universidad Autónoma de Madrid Universidad del País Vasco
Nelson Acosta Manuel Mazo Quintas
Universidad Nacional del Centro, Argentina Universidad de Alcalá de Henares
Miguel Ángel Aguirre Echánove Javier Morán Carreras
Universidad de Sevilla SIDSA, Madrid
Carlos Amuchastegui Manuel Moreno Aróstegui
Universidad del País Vasco Universidad Politécnica de Cataluña
Eduardo Boemo Scalvinoni Fernando Pardo
Universidad Autónoma de Madrid Universidad de Valencia
Joan Cabestany Francisco Pelayo Valle
Universidad Politécnica de Cataluña Universidad de Granada
João M. P. Cardoso Antoni Portero
Universidade do Porto/FEUP (Portugal) Universidad Autónoma de Barcelona
Jordi Carrabina Bordoll Alberto Prieto Espinosa
Universidad Autónoma de Barcelona Universidad de Granada
Javier Castillo Villar Lluis Ribas
Universidad Rey Juan Carlos Universidad Autónoma de Barcelona
Sergio Cuenca Asensi Fernando Rincón
Universidad de Alicante Universidad de Castilla la Mancha
Eduardo de la Torre Eduardo Ros
Universidad Politécnica de Madrid Universidad de Granada
Jean Pierre Deschamps Ricard Sanahuja
Universidad Rovira i Virgill Universidad Politécnica de Cataluña
Luis Entrena Arrontes Juan Manuel Sánchez Pérez
Universidad Carlos III de Madrid Universidad Extremadura
Joan Figueras Eduardo Sánchez
Universidad Autónoma de Madrid Escuela Politécnica Federal de Laussane, Suiza
Antonio García Ríos César Sanz Álvaro
Universidad de Granada Universidad Politécnica de Madrid
Francisco Gómez Arribas Moisés Serra
Universidad Autónoma de Madrid Universidad de Vic
Juan Antonio Gómez Pulido Juan José Serrano Martín
Universidad de Extremadura Universidad Politécnica de Valencia
Diego Gómez Vela Jose T. de Sousa
Universidad de Cádiz INESC-ID Lisboa (Portugal)
Jose Maria Granado Criado Lluis Terés
Universidad de Extremadura Centro Nacional de Microelectrónica, CSIC,
Román Hermida Barcelona
Universidad Complutense de Madrid Antonio Torralba
Francisco Ibarra Picó Universidad de Sevilla
Universidad de Alicante José Torres
Andrés Iborra Universidad de Valencia
Universidad Politécnica de Cartagena Javier Valls Coquillat
Sergio López-Buedo Universidad Politécnica de Valencia
Universidad Autónoma de Madrid Miguel Ángel Vega Rodríguez
Enrique Mandado Pérez Universidad Extremadura
Universidad de Vigo Juan Suardíaz Muro
Francisco Javier Marín Martín Universidad Politécnica de Cartagena
Universidad de Málaga
8
JCRA 2011 | Tenerife 7-9 de Septiembre
SESIÓN I:
ARQUITECTURA Y DISEÑO DE SOC I
9
10
JCRA 2011 | Tenerife 7-9 de Septiembre
(2) Dept. of Electronic, Electric and Automatic Eng., Rovira i Virgili University, Tarragona, Spain
During the last decades, the application of Ga- phases of rapid prototyping and validation.
bor lters to computer vision problems has These languages propose dierent design ab-
been constantly increasing. In this sense, the straction levels. As a result, in short time, this
research have been focused on improving both has led to the quick development of specic
the eciency and the response time of the pro- hardware designs for a wide range of applica-
posals, but as a result, their complexity has tions. Following those motivations, this paper
Gabor lters were originally introduced by tations of Gabor lters and proposes possible
11
Sesión I: Arquitectura y Diseño de SoC I
12
JCRA 2011 | Tenerife 7-9 de Septiembre
diculty when designing a lter bank. The the Gabor decomposition in codec designs for
vague and empirical nature of parameter selec- progressive image transmission. They use only
tion has motivated explicit optimization pro- one Gabor lter and they assume that the Ga-
cedures. Among them, one of the most suc- bor coecients form a banded matrix. They
cessful approaches is the one proposed in [9], estimate that a Gabor decomposition of a 512
which aims at reducing the redundancy pro- x 512 image could be achieved in 13 ms with
duced by the non-orthogonality of the Gabor 512 processing elements (PE).
lters by making the half-peak magnitude sup-
port of the lter responses in the frequency 3.2 Face tracking
spectrum touch each other.
This approach introduced in [9] has been Among the applications related to digital im-
proved to be eective for a large amount of age processing, one of the most widely studied
pattern recognition tasks. For that reason, the is detecting human faces in photos or videos.
new ideas proposed in this paper are especially In [11], a VLSI architecture for the imple-
the category of Gabor lters designed in the work is part of a framework for the design and
13
Sesión I: Arquitectura y Diseño de SoC I
work in [12], the design in [13] provides higher and the right retinas. In the presented sys-
output rates due to the pipeline techniques. tem, the spatial ltering emulating a simple
Finally, a new implementation in Verilog cell function is executed by an analog multi-
HDL of an algorithm for ngerprint recog- chip device, and the disparity energy is com-
nition is introduced in [14]. Since the cap- puted by a digital circuit implemented using
tured images are noisy and have poor quality, a an FPGA.
small window of 3x3 is used. Morevover, they The work presented in [17] proposes the
proposed an optimization of the algorithm by hardware implementation of a simple and fast
implementing a serial multiplier-accumulator technique for depth estimation based on phase
unit (MAC). measurement. This technique avoids the prob-
lem of phase warping and is less susceptible
to camera noise and distortion than standard
3.4 Machine vision
block-matching stereo systems. To exploit
In [15], using a biologically inspired model, a the parallelism of the FPGAs, they designed
systolic pipeline architecture of processing el- a structure of ne big pipeline that can be
ements is implemented to calculate the convo- adapted with a frame capture module. They
lution based on Gabor lters. The implemen- are able to process 52 frames per second at a
14
JCRA 2011 | Tenerife 7-9 de Septiembre
the authors apply several steps to improve the traction of features of the image are obtained
quality of the input image and, thus, obtain depending on the size of the analyzed image
better results in the nal segmentation. They window. Puig and Garcia [19] showed that
conclude that the signal-noise ratio can be im- dierent evaluation window sizes are bene-
proved by using Gabor lters and the EM algo- cial when dealing with dierent texture meth-
rithm. Therefore, the EM algorithm segments ods and classication tasks. The main prob-
images more eciently by using the texture lem regarding the denition of a proper evalua-
features of the image. tion window size is that complementary tasks,
such as texture classication and texture seg-
mentation, have contradictory requirements to
4 Improvements on Gabor Filter
perform well.
implementation
4.2 Our research focus
The previous Gabor lter implementations
were made for specic applications. The re- Our goal is to design a Gabor lter unit to be
sources consumed as well as the response times used as a co-processor in a texture classica-
also play a crucial role in those applications. tion system.
That is why optimization mechanisms are very The Gabor lter bank will be set accord-
important. ing to [9] with 4 scales and 6 orientations,
In the following subsections we discuss and a range of frequencies between 0.05 and
the limitations of previous applications and 0.4. After ltering an input image, the tex-
present our research line. ture features that will characterize every pixel
and its surrounding neighborhood (evaluation
window) are the mean and the standard de-
4.1 Limitations of previous Gabor imple-
viation of the module of the resulting coef-
mentations
cients. Therefore, every feature vector will
In some of these implementations the perfor- have a total of 6 (scales) ×4 (orientations) ×2
mance can be increased, either because they (mean and standard deviation) = 48 dimen-
have not been optimized enough or because sions. In order to take advantage of the output
they make an inecient use of resources. For produced by the lter bank, the texture fea-
instance, completely parallelizable implemen- tures mentioned above must be computed for
tations, such as [10], despite having good re- W dierent evaluation window sizes as sug-
sponse times consume large amounts of hard- gested in [19, 20] (e.g., W is set to 5 sizes:
ware resources. This makes their use in em- 3 × 3, 5 × 5, 9 × 9, 17 × 17 and 33 × 33), which
bedded complex systems more dicult. improves the accuracy of the texture classier.
Another important factor to consider is The design of the architecture is shown in
that, when designing FPGAs for specic ap- Figure 3. The proposed architecture analyzes
plications, in certain cases, the design is made the input image window in a serial way, but
for a high level of abstraction and not fully ex- every pixel belonging to the current window w
ploit the capabilities of FPGAs. In addition, will be processed in a set of parallel PEs that
the type of data is an important factor to con- correspond to the number of Gabor lters.
sider, as seen in [14], where the use of IEEE - When all the pixels in the w are processed
754 for the Gabor coecients consume a large by the PEs, the resulting components G (real
amount of memory and operations are com- and imaginary) are used to compute the norm.
plex. Then, an easy way to solve this problem The computation of the vector norm is carried
is to use xed-point data types. out with the CORDIC [21] algorithm. Once
The window size is another important factor all the windows of the input image are cal-
to consider in pixel-based image classication culated, we compute the mean and standard
and image segmentation tasks. In [13] the au- deviation. This operation is performed over
thors mention that dierent results in the ex- the same window size, but taking the results
15
Sesión I: Arquitectura y Diseño de SoC I
This paper has given an overview of the [2] S.-J. Huang and S.-S. Wu, Vision-
FPGA implementation of the most outstand- based robotic motion control for non-
ing Gabor lters. We also analyzed the lim- autonomous environment, J. Intell.
itations of current implementations and de- Robotics Syst., vol. 54, pp. 733754, 2009.
scribed a line of improvement in the implemen-
tation of a new architecture of Gabor lters [3] R. Schneiderman, Trends in video
on FPGAs that has been successfully used in surveillance give dsp an apps boost [spe-
the eld of texture classication and segmen- cial reports], Signal Processing Mag.,
tation. IEEE, vol. 27, no. 6, pp. 612, 2010.
16
JCRA 2011 | Tenerife 7-9 de Septiembre
[4] J. Diaz Alonso, et al., Lane-change deci- and Integrated Circuit Technology (IC-
sion aid system based on motion-driven SICT), 2010 10th IEEE Int. Conf. on,
Vehicular Technology,
vehicle tracking, 2010, pp. 584586.
IEEE Trans. on, vol. 57, no. 5, pp. 2736
2746, 2008. [14] M. Idros, et al., Improvisation of ga-
bor lter design using verilog hdl, in
[5] A. Bovik, M. Clark, and W. Geisler,
Multichannel texture analysis using lo-
ICEDSA, 2010 Int. Conf. on, 2010, pp.
Trans. on, vol. 12, no. 1, pp. 5573, 1990. [15] C. Torres-Huitzil, B. Girau, and
M. Arias-Estrada, Biologically-inspired
[6] D. A. Clausi and M. E. Jernigan, Design-
digital architecture for a cortical model
ing gabor lters for optimal texture sep-
arability, Pattern Recognition, vol. 33,
of orientation selectivity, in ICANN, ser.
LNCS, 2008.
no. 11, pp. 18351849, 2000.
les, Vision Research, vol. 20, no. 10, pp. high-image resolution disparity estima-
tion, Image Processing, IEEE Trans. on,
847856, 1980.
vol. 16, no. 1, pp. 280285, 2007.
data, PAMI, IEEE Trans. on, vol. 18, M. Malarvizhi, VLSI implementa-
2005 Fifth Int. Conf. on, 2005, pp. 172 Ecient distance-based per-pixel texture
classication with gabor wavelet lters,
176.
Pattern Analysis & Applications, vol. 11,
[12] M. Lopez, E. Canto, and M. Fons, pp. 365372, 2008.
IEEE IECON 2006 - 32nd Annual Conf. Pipelined cordic architectures for fast
[13] J. bao Liu, et al., Congurable pipelined IEEE Int. Conf. on ICASSP '84., vol. 9,
gabor lter implementation for nger- 1984, pp. 250253.
17
JCRA 2011 | Tenerife 7-9 de Septiembre
Joaquín Olivares
olivares@[Link]
University of Córdoba
19
Sesión I: Arquitectura y Diseño de SoC I
of ME, because of its simplicity, regularity, and 2.3 Signed Digit Representation
optimum result [4].
The most commonly used metric to deter-
Signed-Digit (SD) representation [8] is used in
mine the best match for FSBMA is the Sum this paper. This codication allows bit-serial
Reduced-bit SAD (RBSAD) is a technique that Radix-2 SD in the presented architecture are:
Typical RBSAD implementations are not dierence and the conversion on the y.
recongurable because they work with tradi- Finally the system does not require to
tional arithmetic, being based on the use of convert the SAD from SD to traditional
just the most signicative bits of the pixel, representation, because the value of the
and the reduction from an 8-bit to a 4-bit rep- SAD is not important, the ME target is
posed, with which the architecture can be re- of SD in the proposed architecture allows
congured in real-time to improve the perfor- to choose the pixel precision in real-time,
20
JCRA 2011 | Tenerife 7-9 de Septiembre
3.1 Absolute Dierences when they are zero (00 or 11). If the rst non-
zero digit received is positive (01), this and all
A signed-digit number can be interpreted as the remaining digits correspond directly with
the dierence between two unsigned numbers, the output. Nevertheless, if the rst non-zero
one composed of positively weighted bits for digit received is negative (10), the bits of this
each digit, minus the one composed of nega- and all the remaining digits are exchanged to
tively weighted bits. obtain the output.
This property is used to simultaneously con-
vert each pixel value into an SD representation
3.2 The Adder Tree
and to compute the dierence between the pix-
els of the reference block and the ones of the The adder shall sum two numbers in SD rep-
current block. In this way, each digit of the resentation, each of them consisting of one SD
value di,j = ci,j − ri,j is obtained in SD rep- digit, and consisting each digit of two bits.
resentation by only taking the corresponding Due to this, the on-line arithmetic basic adder
bit of ci,j as the positively weighted one and implements the adding in two stages [9]. Fur-
the corresponding bit of ri,j as the negatively thermore, it is necessary to take into account
weighted one, since ci,j and ri,j are unsigned that each SD digit has a negative weight and
numbers. a positive one. The architecture of the OLA
To compute the absolute value of di,j (AD), adder is shown in Fig. 2. Two types of OLA
the sign of this value has to be changed if di,j adders will be used, with or without nal ip-
is negative. In SD representation, the negation ops.
operation is performed by exchanging both From it, an adder tree which is able to
bits of each digit, the AD is the Process El- sum 16 absolute dierences is developed. This
ement (PE) of this architecture, and is shown adder tree is called 16-OLA Adder tree and
in Fig. 1. will be used afterwards, see Fig. 3.
Since the MSD-rst mode of computation When the processing on the SAD over VB-
is being used, the sign detection of di,j is per- SME is carried out, it is common in other ar-
formed on-the-y by checking whether the rst chitectures to need more than one round, as
non-zero digit of di,j is positive (01) or nega- the block is not fully processed in each itera-
tive (10). The digits of di,j are received in tion [10][11]. This architecture works with a
21
Sesión I: Arquitectura y Diseño de SoC I
A+ A- B+ B- A+ A- B+ B-
16 16 16 16
FA FA
D D D D
R R R R
FA FA
8x8
D D
R R
D D
Representation: Legend:
Z- Z+
R R
VBSME-N8 16-OLA adder tree
64 16
Z- Z+
SAD comparison
Representation
64 64 64 64
16 x 8 - A 16 x 8 - B 8 x 16 - A 8 x 16 - B
16 x 16
Representation
16
Representation: Legend:
VBSME-N16 VBSME-N8
VBSME-N16 64
tors of all possible sub-blocks in parallel. For built. This adder is shown in Fig. 5 and is
this purpose, a rst adder called VBSME-N8, called VBSME-N16. It is built by adding two
which is characterized by processing the SAD adders on a common adder tree, just as has
for a sub-block of 8×8 and for all its smaller happened with VBSME-N8, so as to obtain
size sub-blocks, has been designed, and 4 16- the SAD of the 8 × 16 sub-blocks. Each pro-
OLA adder tree adder trees are used in it. The cessed SAD needs to be compared. The design
adding two more adders in order to obtain the The global hardware increment respect to
SAD of the 4×8 sub-blocks. a conventional 16 × 16 adder tree is only ten
Using the adder VBSME-N8 as the base, SD OLA adders. Also, 41 registers are used to
22
JCRA 2011 | Tenerife 7-9 de Septiembre
AD AD AD
2 2 2
VBSME-N16
SAD
moment
22 ... d12 0 d2 d5 d6
SAD; since SD digits are in [−1, 1], 23 d11 0 d1 d4 d5
this operation can be in [−2, 2]. 24 ... d13 d0 d3 d4
25 d12 0 d2 d3
26 ... d14 d1 d2
3.4 RBSAD Architecture for VBSME 27 d13 d0 d1
28 ... d15 d0
29 d14 d15
Once the components have been presented, the
architecture is formed from those components,
beginning on a rst level for the processing of Figure 8: Timing: Full precision
all absolute dierences of a block, that is to
2
say, N = 256 absolute dierences elements.
On a second level, the VBSME-N16 structure segment is used for the processing of the abso-
can be found, which includes the adder tree lute dierences, being the following ones used
and which will have embedded the 41 com- for the adder tree. A last segment has to be
parators. This is presented in Fig. 7. added for the comparator.
Fig. 8 presents the timing for full precision.
23
Sesión I: Arquitectura y Diseño de SoC I
Nokia N900; HTC Touch HD; WVGA 800×480 54.8 62.6 73.1 87.7
24
JCRA 2011 | Tenerife 7-9 de Septiembre
Nokia N900; HTC Touch HD; 5:3 208.1 182.1 156.1 130.1
25
Sesión I: Arquitectura y Diseño de SoC I
while the smartphone is operating to save pro- [4] M. Sayed, W. Badawy, G. Jullien, To-
cessing, extending battery life. Most smart- wards an H.264/AVC HW/SW Integrated
phone and tabs screen resolutions are studied, Solution: An Ecient VBSME Archi-
and the throughput in function of the NTB for tecture, IEEE Trans. on Circuits and
a Virtex-5 FPGA is presented. Moreover, the Systems-II: Express Briefs, vol. 55, no. 9,
frequency to operate in real-time is calculated, pp. 912916, Sept. 2008.
using hardware cost results and the frequency
[5] S. Agha, V.M. Dwyer, V. Chouliaras, Mo-
estimation for real-time, a designer can choose
tion estimation with low resolution distor-
the technology idoneous where implement the
tion metric, Electronics Letters, vol. 41,
presented processor. The recongurable pixel
no. 12, pp. 693694, June 2005.
precision and the frequency required to oper-
ate at 30 fps facilitates the integration of this [6] V. M. Dwyer, S. Agha, V. A. Chouliaras,
architecture in future devices. Reduced-Bit, Full Search Block-Matching
Reducing power consumption and increas- Algorithms and their Hardware Realiza-
ing the throughput, are interesting benets, tions, Lecture Notes in Computer Science,
because of this, in future works the proposed vol. 3708, pp.372380, 2005.
architecture will be implemented on Spartan6.
The low cost, and, the high throughput [7] M. R. H. Fatemi, H. F. Ates, R.
makes this architecture suitable for resource- Salleh, A Cost-Ecient Bit-Serial Archi-
This architecture is patented by the Univer- H.264/AVC, Int. Conf. on Intelligent In-
sity of Córdoba, Spain. Ref: P201031628. formation Hiding and Multimedia Signal
Processing, pp. 818821, 2008.
26
JCRA 2011 | Tenerife 7-9 de Septiembre
Patricia López (1), Jon Mabe(1), David Cantero(1), Armando Astarloa(2) , Iñigo Oyarbide(2)
plopezalonso@[Link], jmabe@[Link], dcantero@[Link], [Link]@[Link],
oiharbide@[Link]
(1)
Fundación Tekniker-IK4.
(2)
Universidad del País Vasco / Euskal Herriko Unibertsitatea.
27
Sesión I: Arquitectura y Diseño de SoC I
28
JCRA 2011 | Tenerife 7-9 de Septiembre
Test de
Diseño del Integración
ASIC (módulos)
Diseño Test
módulos módulos
Síntesis y simulación
place&route post‐layout
Codificación final
Se observa que además de las necesidades de • Construcción: Fallos físicos que por
seguridad requeridas por la parte mecánica del construcción tiene el chip o que se han
flywheel, como puede ser un sistema de parada de producido al integrarlo en el sistema.
emergencia en caso de sobretemperatura o fallo de • Uso o desgaste: Fallos físicos causados por
los sensores, es necesario incluir un mecanismo de un uso continuado o de almacenamiento.
seguridad que actúe en caso de fallo en la tarjeta • Externos: Fallos físicos causados por el
de control. El mecanismo de seguridad deberá entorno en el que se está utilizando el
detener el sistema haciendo que el volante deje de sistema.
levitar de manera controlada para evitar el
descontrol del mismo. Aunque esta solución evita 3.1. Diseño e implementación
daños mayores, detener el sistema puede provocar
una serie de pérdidas económicas que deberían ser
La norma IEC 61508 (Edición 2) plantea el uso de
contempladas. Por lo tanto, reducir la probabilidad
un modelo de diseño en V. La figura 3 muestra
del fallo del módulo de procesamiento
este modelo que facilita las tareas de
implementado en la FPGA garantizaría una mayor
identificación y control de los fallos que puedan
fiabilidad del sistema.
producirse durante las etapas de diseño e
En las siguientes secciones se van a presentar
implementación. Se da gran importancia al hecho
distintos mecanismos y técnicas para minimizar y
de verificar y validar cada una de las etapas de
controlar la aparición de fallos en dicho módulo.
diseño para garantizar que se van cumpliendo
cada uno de los requisitos impuestos.
3. Seguridad en FPGAs Además, la norma sugiere el uso de una serie
de técnicas, dependiendo del nivel de seguridad
Como se ha indicado en el apartado anterior, un que se desee alcanzar, entre las que se encuentran
fallo en el módulo de la FPGA puede provocar el análisis de tiempo, simulación o el uso de
que el sistema entre en una situación de peligro. checklists. Estas técnicas se presentan en las
Por esta razón es importante determinar las partes 2 y 7 de la norma IEC61508 en su segunda
posibles fuentes de fallo en este tipo de edición.
componentes. En [5] se presenta una clasificación
de los tipos de fallos en función de su origen: 3.2. Fallos hardware
• Diseño: Mal diseño.
• Implementación: Fallos introducidos al En [1] se presenta entre las posibles causas de
generar el bitstream, al cargarlo y al arrancar fallo del hardware: la radiación, los tiempos de
la FPGA.
29
Sesión I: Arquitectura y Diseño de SoC I
subida de las señales, las máquinas de estado, la En el caso de las FPGAs de tecnología
alimentación y las conexiones de los pines. SRAM, la redundancia se aplica a un mismo
Las radiaciones de partículas energéticas son módulo funcional. La TMR consiste en triplicar el
una de las mayores fuentes de fallo externa en módulo que necesita mayor fiabilidad y mediante
FPGAs [1, 6]. Aunque durante la pasada década un votador decidir la salida correcta. De esta
sus efectos han sido únicamente considerados en manera se obtiene un sistema tolerante a fallos.
los diseños para aplicaciones espaciales y
militares, hoy en día, debido al aumento de la Scrubbing
densidad de integración, a la reducción del voltaje
de funcionamiento y a las altas frecuencias de Xilinx [13] propone la técnica de scrubbing en
trabajo, los dispositivos son cada vez más FPGAs de la serie Virtex para corregir los efectos
sensibles a la radiación y sus efectos deben ser que los SEUs pueden provocar en la memoria de
considerados incluso a nivel terrestre [6]. configuración del dispositivo. Esta técnica
Estas radiaciones provocan los denominados consiste en recargar periódicamente el bitstream
Single Event Effects (SEE), entre los que se de configuración para reparar la memoria SRAM.
distinguen [7]: En las FPGAs de última generación., como los
• Single Event Upset (SEU): Es un cambio en dispositivos Virtex-5 de Xilinx, se incluyen
el estado de un transistor modificando el bloques hardware específicos de Xilinx para
valor de un único bit. corregir los frames de configuración mediante
• Single Event Transient (SET): Se trata de un técnicas de corrección de errores (ECC – Error
pulso transitorio creado por la partícula Correcting Code). De esta forma se evita la
incidente que deriva en un almacenamiento necesidad de recargar el bitstream completo.
erróneo en memoria.
• Multiple Bit Upset (MBU): Cuando una única Reconfiguración parcial dinámica
partícula modifica más de un bit.
La reconfiguración parcial dinámica [14] se basa
Artículos como [5, 7, 8, 9, 10, 11] proponen en reprogramar una determinada área de la FPGA
técnicas para mitigar los fallos producidos por para cambiar el comportamiento de la misma sin
estos efectos. Se suelen utilizar técnicas de diseño necesidad de resetear el dispositivo completo. La
seguro como redundancia, scrubbing y FPGA seguirá funcionando normalmente hasta
reconfiguración parcial dinámica. A la hora de que esa zona sea reprogramada, que será cuando
realizar un diseño confiable con FPGAs de la FPGA adoptaría el nuevo comportamiento.
tecnología SRAM para aplicaciones críticas se En el contexto de este artículo, interesaría
suelen combinar técnicas de tolerancia a fallos reprogramar la zona de la FPGA en la que se ha
como la redundancia, con técnicas específicas detectado un fallo con el bitstream parcial
para FPGAs como el scrubbing. correcto. Además, si el circuito implementado
tiene un layout diferente al que se había cargado
Redundancia física o Hardware previamente podrían llegar a tolerarse errores
permanentes producidos en el sustrato de la
FPGA.
La técnica redundante más empleada hoy en día es
la Triple Modular Redundancy (TMR) [12], cuya
estructura se muestra en la siguiente figura. 4. Diseño confiable del modulo de
procesamiento del flywheel
Entradas
Módulo Redundante 0 Para garantizar la fiabilidad del módulo de
Salida procesamiento (Figura 5) descrito en la sección 2
Módulo Redundante 1 Votador es necesario tener en cuenta dos aspectos. Por un
Módulo Redundante 2 lado, es necesario que el filtro sea estable para
obtener valores de salida adecuados y además, que
Figura 4. Esquema de Triple Modular Redundancy el modulo sea robusto frente a los fallos definidos
en la sección 3.
30
JCRA 2011 | Tenerife 7-9 de Septiembre
31
Sesión I: Arquitectura y Diseño de SoC I
Figura 6. Estructura del filtro IIR y de una sección de orden 2 en System Generator
32
JCRA 2011 | Tenerife 7-9 de Septiembre
33
Sesión I: Arquitectura y Diseño de SoC I
34
JCRA 2011 | Tenerife 7-9 de Septiembre
Congurable-System-on-Programmable-Chip
implementation of a Global Navigation Satellite Systems
Receiver
(1) (2) (1) (1)
Victor Garcia , Mikel Garay , Asier Ibañez and Armando Astarloa
35
Sesión I: Arquitectura y Diseño de SoC I
36
JCRA 2011 | Tenerife 7-9 de Septiembre
but reduces it to a Low Noise Amplier and tions give a choice between a high accuracy
a lter for each satellite band, a Diplexer and even with a noisy incoming or a low compu-
a Combiner. This means that all the desired tational load, which has attached low power
signals are mixed when entering the AD con- consumption. Changing between IP Cores im-
verter and it is possible, using a dierent Base- plemented with dierent algorithms allows a
band Converter for each band to implement dynamically adjustment of the sensitivity of
solutions which employ the multiband possi- the device to the ambient noise level, reducing
bilities which are oered by many satellite sys- the power consumption.
tems like Galileo or GPS and make use of the
data received from dierent bands and GNSS. 3.4 Loop Filter
37
Sesión I: Arquitectura y Diseño de SoC I
Figure 3: Comparison table between the IP Core variants. (*) shows which cores must change and (-) which
not.
38
JCRA 2011 | Tenerife 7-9 de Septiembre
39
Sesión I: Arquitectura y Diseño de SoC I
Only the ability to switch between reception Digital Signal Processing, 2008, pp. 256-
bands without doubling the hardware needs is 259.
worth the study. Nevertheless the employed
approach allow to think in many other appli- [2] E.D. Kaplan, "Understanding GPS Prin-
cations for receivers that need to perform rea- ciples and Applications", Artech House,
sonably in changing situations. This project INC., 1996
is still in development stage and the presented [3] European GNSS (Galileo) Open Service,
implementation results are preliminary, there- Signal In Space Interface Control Docu-
fore, there are not yet advanced results such as ment. European Comission for Enterprise
reconguration time or ICAP clock maximum, and Industry.
but the future options are many. Linux envi-
ronment can be added for example to provide [4] A. Astarloa, U. Bidarte, J. Lazaro, J. An-
a stable and controlled scenario for the appli- dreu, J.L. Martin. "Congurable-System-
cation. As an immediate step a single repro- on-Programmable-Chip for Power Elec-
gramming unit that performs a single change tronics Control Applications". In Recong-
like the correlation code will be implemented. urable Computing and FPGAs, 2008. Re-
However the main objective will be to create ConFig '08. International Conference.
a GNSS receiver that performs like described. [5] H. Hurskainen, T. Paakki, Zhongqi Liu,
As said, these are some of the improvements J. Raasakka, J. Nurmi; . "GNSS Receiver
that can be added in a nearly future. Reference Design". In 4th Advanced Satel-
lite Mobile Systems, 2008.
[6] GLONASS Satellite Navigation System.
Acknowledgment Russian Federation Ministry of Defence,
This work has been developed in Tecnalia En- [Link] .
terprise Classroom (2010-11) [7] C. Claus, R. Ahmed, F. Altenried, W.
Stechele; Towards Rapid Dynamic Par-
References tial Reconguration in Video-Based Driver
Assistance Systems. In Recongurational
[1] A. Alonso, J.M. Perre, and I. Arizaga, Computing: Architectures, Tools and Ap-
"SDR direct sampling device for multi- plications, 2010 6th International Sympo-
standard GNSS signals", 6th Symposium sium, ARC 2010.
on Communication Systems, Networks and
40
JCRA 2011 | Tenerife 7-9 de Septiembre
SESIÓN II:
FPGAS VERSUS MULTICORES/GPUS
Comparativa del uso de HLLs en FPGA, GPU y Multicore para la aceleración de una aplicación
de red IP ...................................................................................................................................... 43
FPGA Acceleration of a Monte Carlo method for pricing Asian Options using High Level
Languages .................................................................................................................................... 59
41
42
JCRA 2011 | Tenerife 7-9 de Septiembre
43
Sesión II: FPGAs versus Multicores/GPUs
44
JCRA 2011 | Tenerife 7-9 de Septiembre
rendimiento. El punto de partida es una sistema 240 cores de procesamiento, que pueden
arquitectura similar a la de un servidor de hacer uso de una memoria interna compartida por
computación multicore con memoria compartida todos ellos de 4GB.
en el que se pueda incorporar según las
necesidades capacidad de coprocesamiento por 4. Implementaciones desde lenguajes de
GPU o con FPGA. Como paso previo se van a alto nivel
comparar las diferentes tecnologías sobre una
misma plataforma de prototipado que se describe 4.1. OpenMP en multicore (MPC)
en la siguiente sección. La arquitectura del
sistema final se decidirá en función de los La solución al problema planteada desde el
resultados obtenidos en la comparación punto de vista puramente MPC (Multi-Processor
considerando su escalabilidad y el rendimiento Computer) es la más sencilla posible, basándose
máximo que se puede extrapolar en cada caso. en el paradigma de programación de memoria
compartida, concretamente en el uso de OpenMP.
3. Plataforma de prototipado La aplicación consta de un bucle que recorre todos
El sistema en el que se ha llevado a cabo el los paquetes que se desean analizar, y que para
estudio es un servidor con una placa base dual cada paquete se recorre los TamVENTANA paquetes
Xeon, a la cual están conectados un procesador siguientes en busca del primer paquete que
Intel Quad-Core L5408 y un acelerador In-Socket cumpla la condición de duplicado. Para ejecutar el
basado en FPGA: el XD2000i de XtremeData [7]. programa aprovechando el paralelismo existente
El acelerador XD2000i, conectado al segundo en la arquitectura destino, simplemente se ha
socket de procesador de la placa, utiliza la colocado un pragma OpenMP delante del bucle
infraestructura de CPU existente en la placa base más externo.
para crear un entorno de coprocesamiento La compilación de esta implementación se ha
completamente funcional. realizado el compilador de libre distribución gcc,
La conexión entre el procesador Intel y el añadiéndole la opción –O3 con vistas a obtener
acelerador re realiza a través del Front-Side Bus los mejores resultados de rendimiento ofrecido
(FSB), pudiendo así sacar partido del alto ancho por esta herramienta de compilación.
de banda y la baja latencia de este método de 4.2. CUDA en manycore (GPU)
interconexión.
El acelerador In-Socket XD2000i se compone Tomando la solución MPC como punto de
de tres FPGAs Altera Stratix III [8]. Una de estas partida, se ha creado una solución basada en
FPGAs ejerce la labor de bridge hacia el FSB tecnología GPGPU. Mientras que la solución
(Stratix III SL150), mientras que las otras dos MPC puede parece demasiado burda, encaja en la
(Stratix III SE260, con 255K puertas lógicas, 768 filosofía de ejecución de las GPGPU: tenemos
multiplicadores embebidos y 15 Mb de memoria muchos paquetes, de modo que cada uno de los
interna) están disponibles para alojar la lógica cores de la GPU se encargará de realizar el
implementada por el usuario. Estas dos FPGAs procesamiento necesario para uno de los paquetes.
están a su vez directamente conectadas a través de El tiempo requerido para desarrollar la
dos canales unidireccionales de 64-bits solución GPU es también muy reducido utilizando
funcionando a una velocidad de 400 MT/s el paradigma de programación CUDA que ofrece
(millones de transacciones por segundo). Además, el fabricante NVidia para sus dispositivos.
el módulo XD2000i dispone de dos bancos de 4.3. Impulse-C en FPGA
memoria QDRII+ SRAM de 8 Mb cada uno, cada
uno de ellos conectado a una de las FPGAs de Para el desarrollo del sistema basado en
usuario. Toda la placa XD2000i funciona a una FPGA, se ha elegido utilizar una metodología
frecuencia de 100 MHz. basado en el empleo de lenguajes de alto nivel,
En la misma máquina, hay además conectada con vistas a agilizar el tiempo transcurrido hasta la
a través del bus PCI-Express una GPU Tesla obtención de un producto funcional.
C1060 de Nvidia [9]. Este coprocesador gráfico se Concretamente, se ha optado por el lenguaje
conecta a través de un bus PCIe x16, y aporta al Impulse-C [10-11]. La elección de este HLL para
45
Sesión II: FPGAs versus Multicores/GPUs
la realización del desarrollo se debe por un lado a paquetes (o todavía no ha llegado un paquete con
la existencia de un paquete de soporte de la ese valor de hash), entonces el paquete no es un
plataforma de la que se disponía (Plattform duplicado.
Support Package - PSP) y por otro lado a 3.) Si no se cumplen las condiciones de la etapa
anterior, se procede a comparar el paquete entrante
resultados previos obtenidos en otros trabajos con
con el paquete almacenado en la memoria que tenía
resultados muy satisfactorios [12]. Este lenguaje el mismo valor de hash. Si los paquetes son iguales,
tiene además un paradigma de programación el paquete entrante es entonces un duplicado.
basado en streams de datos, que facilita en gran
medida su utilización para propósitos de Llegado este punto, no podemos afirmar que si
coprocesamiento. el paquete es diferente al que residía en la
La primera aproximación es una comparación memoria, el paquete entrante no es un duplicado:
“por fuerza bruta”, análogo con los desarrollos puede ocurrir que hayan llegado otros paquetes
llevados a cabo en MPC y GPGU. De este modo, con el mismo valor de hash que el entrante antes
a la FPGA le irían llegando los paquetes en serie, que el que nos apuntaba la tabla. Por tanto, hemos
y para cada paquete realizaría la comparación de de tener una segunda tabla (que nos resuelve las
duplicidad con los TamVENTANA anteriores. Una vez “dobles colisiones”) que nos indica cuando fue el
terminadas estas comparaciones, se almacena el instante de tiempo en que llegó el último paquete
paquete en la memoria interna de la FPGA y se con un valor de hash igual al paquete entrante,
retorna el resultado (duplicado/no duplicado) a pero diferente del que se tiene almacenado en la
través de una interfaz de streaming. tabla. Una vez se cuenta con esta tabla, el
Debido a que Impulse-C permite explotar la algoritmo puede continuar:
característica de las memorias internas de la 4.) Se comprueba en la segunda tabla si hace
FPGA de permitir el acceso a dos datos en cada menos de TamVENTANA paquetes llegó un paquete con
ciclo de reloj, tendríamos que para obtener el el mismo valor hash que el entrante, pero diferente
resultado de cada paquete tardaríamos al que apuntaba la primera tabla hash. Si no se
TamVENTANA/2 ciclos de reloj. En el caso nuestra cumple esta condición, entonces el paquete es no es
aplicación (TamVENTANA =600) esto nos limita (sin un duplicado.
tener en cuenta otro tipo de overheads) a un 5.) Si se cumple la condición de la etapa
throughput de: anterior, se ha de comparar el paquete con todos los
−1 paquetes residentes en memoria en busca de
⎛ TamVENTANA 1 ⎞ −1 duplicados.
⎜ ⋅ ⎟ = (300 ⋅10ns) ≈ 3,3 ⋅10 pps
5
⎝ 2 100Mhz ⎠
La idea de esta aproximación es por lo tanto
Con vistas a obtener una solución cuyo reducir la cantidad de veces que se ha de recorrer
rendimiento no sea tan dependiente del tamaño de toda la memoria en busca de los posibles
ventana, se propone una arquitectura un poco más duplicados.
elaborada, ilustrada en la figura 2. En esta Puede realizarse un análisis teórico para
aproximación, se basa en la utilización de un hash comprobar si compensa o no una solución de este
que resuma el contenido del paquete. De este tipo. Si aceptamos que la función de hash genera
modo, dos paquetes con distintos valores de hash valores de manera uniforme, y suponemos
no pueden ser duplicados. Basándonos en esta independencia entre todos los paquetes (o más
idea, creamos una tabla indexada con los valores bien entre sus valores de hash), tenemos que la
del hash en la que se almacena la posición del probabilidad de que se produzca una colisión (que
último paquete que llegó con ese mismo valor. generen el mismo valor de hash) entre dos
Puesto que sólo se desea comparar con los últimos paquetes es:
TamVENTANA paquetes, a cada paquete entrante se le 1
asigna un timestamp que será almacenado en la p = P(colisión) = (1)
TamTABLA _ HASH
misma tabla en que se guarda su posición. Los
pasos del algoritmo seguidos son los siguientes: Queremos calcular ahora la probabilidad de
que se produzca una colisión entre el paquete
1.) Para cada paquete entrante se calcula un entrante con cualquiera de los TamVENTANA
valor de hash. anteriores. Para obtener este valor, se ha de
2.) Si el timestamp del último paquete con ese
valor de hash es de hace más de TamVENTANA
46
JCRA 2011 | Tenerife 7-9 de Septiembre
47
Sesión II: FPGAs versus Multicores/GPUs
48
JCRA 2011 | Tenerife 7-9 de Septiembre
Figura 5. Efecto del driver del fabricante en el Figura 6. Efecto del tamaño de la ventana en el
tiempo de cómputo del acelerador FPGA rendimiento del sistema
comparaciones, se utiliza un contador que se
En base a los resultados obtenidos, las
incrementa módulo TamVENTANA. La operación “%”,
comúnmente utilizada en programación de alto soluciones basadas en GPU y en FPGA son las
nivel, tiene en este caso efectos colaterales. Cuando que ofrecen un mayor rendimiento en términos de
el módulo se realiza con 2k, simplemente hay que capacidad de proceso del sistema. Ambas
quedarse con los k bits menos significativos del soluciones poseen como atractivo adicional la
contador. En el resto de casos, Impulse instancia un propiedad de dejar libres los cores de la máquina
componente de su librería que posee una gran para poder encargarse de la transferencia de los
latencia. Realizar un sencillo cambio de la sentencia datos desde/hacia la red de comunicaciones. Se ha
contador=(contador+1)%TamVENTANA; comprobado de forma empírica que este proceso
por un incremento seguido de una sentencia de envío/recepción de los paquetes por las
condicional: diversas interfaces de red es el cuello de botella
contador++; que limita el rendimiento del sistema, de modo
if(contador==TamVENTANA)
que la utilización de coprocesadores adquiere un
contador=0;
interés mucho mayor que las basadas en MPC.
se traduce en un rendimiento considerablemente
superior al de la GPU con nuestra FPGA (7,3·106 Impulse-C
OpenMP GPU Impulse-C
paquetes por segundo con la FPGA frente a los HASH
2,6·106 de la GPU manteniendo un tamaño de
ventana igual a 600). Throughput 3· 105 2,6·106 2,9·105 2,3·106
(pps)
2.) Separando los casos en que el tamaño de
ventana es potencia de dos y los que no, al aumentar Tabla 2. Throughput máximo de las cuatro
el tamaño de la ventana de comparación el implementaciones llevadas a cabo con TamVENTANA=600
rendimiento no se ve prácticamente afectado. Esto
Una comparación más justa supondría
es debido a que gracias a la utilización de los valores
de hash, la cantidad de veces que se ha de recorrer la incorporar una tabla hash también en las
memoria en busca de los paquetes es muy reducida. aproximaciones GPU y MPC. Sin embargo, el
paralelismo SIMD inherente en estas abstracciones
requiere de mecanismos de sincronización que
6. Discusión del rendimiento obtenido
complican la implementación. Para la aplicación
sobre tráfico real de red considerada, el procesamiento en stream de
la FPGA, en el que los paquetes se procesan de
La Tabla 2 resume los resultados de uno en uno, favorece la aplicación de soluciones
rendimiento representados en la figura 4, basadas en hash para esta tecnología.
comparando en términos de cantidad de paquetes
por segundo que cada solución es capaz de 7. Conclusiones y trabajo futuro
procesar con tráfico real.
Se ha comprobado la utilidad de varias
aproximaciones de programación de alto nivel
49
Sesión II: FPGAs versus Multicores/GPUs
para diferentes plataformas hardware. Este tipo de computing: A survey”. ACM Computing Surveys
enfoque ha servido para agilizar el tiempo de (CSUR), Vol.42 nº.4, páginas1-65, June 2010.
desarrollo de un prototipo funcional respecto a
otras aproximaciones con un nivel de abstracción [2] El-Araby E.; Nosum, P.; El-Ghazawi, T.;
menor: threads POSIX para la programación en “A Framework for Evaluating High-Level Design
MPC, NVAPI (un API que provee Nvidia para Methodologies for High-Performance
comunicarse directamente con el driver de la Reconfigurable Computers”, IEEE Transactions
tarjeta) en GPU, y lenguajes HDL para FPGA. on Parallel and Distributed Systems, pag. 33-45,
La curva de aprendizaje del lenguaje Impulse- Jan. 2011.
C es la más lenta de las tres. No obstante, es una [3] T.R. Halfhill; “Parallel Processing with
curva considerablemente más rápida que su Cuda Nvidia’s High-Performance Computing
equivalente en lenguajes de descripción hardware, Platform Uses Massive Multithreading”,
HDLs. La utilización de aproximaciones de alto Microproc. Report, Vol. 22, No. 1, Enero 2008.
nivel para la utilización de FPGAs hace accesible
a un público mucho más amplio que los HDLs la [4] Song Jun Park; Dale R. Shires; Brian J.
posibilidad de explotación de la capacidad de Henz.”Coprocessor Computing with FPGA and
cómputo de las mismas. GPU”. Proceedings Of The Hpcmp Users Group
De los resultados se concluye que las Conference 2008, páginas 366-370.
soluciones basadas en el uso de coprocesadores [5] L. Dagum; R. Menon; “OpenMP: an
han aportado un nivel de rendimiento superior a la industry standard API for shared-memory
aplicación que se deseaba acelerar. De cara al programming”. IEEE Computational Science &
sistema final en producción, estas alternativas son Engineering, Jan-Mar 1998.
especialmente interesantes por dejar libres los
cores de procesamiento para la realización de las [6] Alonso, P.; Cortina, R.; Martinez-
operaciones de entrada/salida de/hacia la red de Zaldvar, F.; Ranilla, J.; “Neville elimination on
comunicaciones. multi and many-core systems: OpenMP, MPI and
Para la versión en producción, se ha utilizado CUDA”, The Journal of Supercomputing, pag. 1-
la solución basada en GPU. En esta misma 11, 2009.
versión, se ha procedido a implementar la parte de
[7] XtremeData, Inc., “XtremeData XD2000i
discriminación del tráfico saliente en la propia
in-socket_accelerator”,
GPU, lo que ha supuesto una significativa
[Link]
degradación en la capacidad de cómputo del
in-socket-accelerator/xd2000i.
sistema. Esta discriminación del tráfico se hace en
base a unas reglas similares a los de los [8] Altera Corporation, “Altera FPGA
mecanismos de filtrado de red tradicionales devices”, [Link]
(basadas en rango de direcciones IP, rango de
puertos, protocolos,…). Este tipo de operaciones [9] Nvidia Tesla Computing Processor.
degradan en gran medida el rendimiento de la [Link]
GPU debido a que provocan que cada uno de los esla_C1060_US_Jan10_lores_r1.pdf.
hilos de ejecución vaya por una rama de ejecución [10] Impulse Accelerated Technologies,
diferente. “Impulse-C”, [Link]
Por esta razón, como línea de trabajo futuro se
propone realizar una versión basada en FPGA, en [11] D. Pellerin; S. Thibault; “Practical fpga
la que la parte de decisión de la interfaz de salida programming in C”. Prentice Hall Press.
de cada paquete pueda realizarse de forma muy ISBN:131543180 .
eficiente. [12] D. Sanchez-Roman; G. Sutter; S. López-
Buedo; I. González; F.J. Gomez-Arribas; J.
8. Referencias Aracil; “An Euler solver accelerator in FPGA for
computational fluid dynamics applications”. VII
[1] J.M.P. Cardoso; P.C. Diniz; M. Southern Programmable Logic Conference,
Weinhardt; “Compiling for reconfigurable SPL2011.
50
JCRA 2011 | Tenerife 7-9 de Septiembre
Martínez P.(1), Ureña R.(1), Morillas C.(1), Gómez J.M.(1), Pelayo F.J.(1)
pablomc@[Link], {ruperez, cmorillas, jmgomez}@[Link], fpelayo@[Link]
1
Departamento de Arquitectura y Tecnología de Computadores, CITIC, ETSIIT, Universidad de Granada
51
Sesión II: FPGAs versus Multicores/GPUs
limitado. La dificultad de este proceso radica en componente de brillo sin alterar el resto
cómo hacer corresponder los niveles de intensidad de componentes. De esta forma se puede
entre los distintos rangos de forma que la imagen trabajar el contraste de la imagen sin
visualizada presente el contraste más adecuado. alterar su tonalidad.
En la literatura existente se pueden encontrar 2. Filtrado espacial basado en un modelo de
múltiples operadores que realizan esta función y retina. La salida de esta etapa es una
cuya clasificación se puede establecer en dos imagen en escala de grises que enfatiza
grandes campos: globales o locales. determinadas características como son
Los operadores globales, como el propuesto los bordes y que atenúa otras como son
por Drago et al. [2], aplican una única función de las zonas excesivamente brillantes.
transformación global a todos los píxeles de la 3. Ecualización local adaptativa con objeto
imagen. Los operadores locales, sin embargo, de distribuir los niveles de grises del
realizan un tratamiento de la imagen por histograma de forma que se puedan
subzonas. Un ejemplo de operador local es el de resaltar aquellas zonas de la imagen mal
Hu et al. [5], que emplea filtros bilaterales y que contrastadas.
divide la imagen en diferentes regiones en base al 4. Combinación lineal de las etapas 2 y 3 en
histograma global y después realza dichas base al nivel de intensidad promedio
regiones de acuerdo a sus propiedades presente en la imagen.
individuales. 5. Conversión de nuevo al espacio de color
Otra distinción puede establecerse entre RGB a partir de las componentes
operadores estáticos y dinámicos. La mayoría de inalteradas (H y S) y de la componente
los operadores son estáticos y están ideados para de brillo (V) procesada.
procesar imágenes fijas. Por otra parte, los
dinámicos están explícitamente diseñados para 2.1. Procesamiento basado en el modelo de
procesar flujos de imágenes y pueden ir adaptando retina
a lo largo del tiempo sus parámetros de
configuración. Usando como entradas las componentes RGB
Muchos de estos operadores han sido podemos diseñar una serie de filtros espaciales
implementados en FPGA, como es el caso del que modelan la función de las células bipolares de
ecualizador adaptativo del histograma diseñado la retina. La oposición entre el centro y la periferia
por Ali M. Reza en [12], que será adaptado para de los campos receptivos de estas células puede
funcionar dentro de una etapa de nuestro diseño ser modelada con un filtro de Diferencia de
en FPGA. Gaussianas (DoG), de acuerdo a la ecuación (1):
Sin embargo, todos estos algoritmos tienen 1 1 +
dificultades para procesar imágenes que combinen = − = exp −
2
√2 (1)
zonas con intensidades luminosas muy altas y 1 +
zonas muy oscuras en una misma escena. Es por − exp −
2
ello que hemos implementado un algoritmo que
donde las Gaussianas y son aplicadas a
supere estas dificultades de cara a poder ser
las diferentes componentes de color.
utilizado en baja visión. Este algoritmo puede ser
Este modelo de visión realiza dos operaciones
clasificado como local, estático y adaptativo ya
de filtrado: mejora del contraste de color (magenta
que puede realizar el procesamiento requerido en
frente al verde y amarillo frente al azul) y un
función de las condiciones de iluminación.
filtrado adicional de mejora del contraste de la
En definitiva, el algoritmo aquí planteado
intensidad que resalta los bordes de la escena.
puede dividirse en las siguientes etapas
Hemos elegido esta combinación de canales de
funcionales:
color a la entrada con el objetivo de imitar la
1. Extracción de las componentes de
forma en que la retina humana combina la señal
tonalidad (H), saturación (S) y brillo (V)
de los tres tipos de conos.
de la imagen de video entrante. El
Este procesamiento inspirado en el modelo de
cambio del espacio de color RGB al
retina ha sido previamente utilizado y contrastado
espacio HSV permite realizar un
en sistemas de procesamiento más generales como
tratamiento individualizado de la
Retiner [7,10] y Vis2Sound [6].
52
JCRA 2011 | Tenerife 7-9 de Septiembre
SAA7113H
AD CONVERTER
INPUT
VIDEO SRAM RETINA LINEAR
READ FILTER COMBINATION
MODULE
OUTPUT
RGB
HSV TO RGB
FIFO (DATA) SRAM RGB TO HSV INTENSITY CONVERTER
FIFO (ADDRESS) CONTROL CONVERTER EQUALIZER
53
Sesión II: FPGAs versus Multicores/GPUs
WEIGHT
DECISION
2
ACCUM RED_09 C1
FIFO SHIFT REGISTER
X2 ACCUM
M U X
FIFO SHIFT REGISTER … 16
COMBINATION
54
JCRA 2011 | Tenerife 7-9 de Septiembre
de 215 posiciones de 8 bits cada una con los por bloque y el espacio de memoria compartida
valores de H. Esta tabla emplea un 36% de la entre las hebras de cada bloque.
memoria disponible (262 Kbits). Para la La figura 4 resume el flujo de cómputo
optimización del resto de operaciones aritméticas seguido por las imágenes de video desde que son
(divisiones para obtener las componentes S y V) y capturadas a la entrada hasta que se obtiene la
funciones trigonométricas (cosenos para la imagen procesada a la salida.
conversión de HSV a RGB), se han usado IP La interfaz entre la CPU y la memoria global
cores de Xilinx. El diseño escogido está de la GPU, vía PCI-express, constituyen el cuello
totalmente segmentado y se puede conseguir un de botella de la aplicación. Así pues cada canal de
rendimiento de una división por ciclo de reloj. color se codifica con enteros de 1 byte sin signo,
empleándose 3 bytes para codificar cada píxel.
4. Implementación en GPU
4.1. Implementación del filtro de retina
Manteniendo los requisitos de portabilidad,
consumo reducido y ejecución en tiempo real se La implementación en GPU del procesamiento de
ha elegido la GPU NVIDIA ION2 [8]. Esta GPU retina se basa en realizar operaciones de
es compatible con la NVIDIA CUDA API [9], por convolución 2D separables cuyo alto grado de
lo que se ha usado CUDA para paralelizar el paralelismo a nivel de datos encaja a la perfección
operador de realce del contraste. Los detalles de con la arquitectura de la GPU. Para llevar a cabo
implementación de una versión similar del sistema esas operaciones en tiempo real se han
de ayuda basado en esta GPU pueden encontrarse desarrollado dos kernels de filtrado en CUDA,
en [15]. uno para las filas y otro para las columnas. Ya que
Esta GPU dispone de 16 procesadores y está ambos son muy similares, detallaremos las
disponible en un ligero netbook, el ASUS características del de filas únicamente.
EEEPC PN 1201 [1], con una batería que La operación de convolución requiere una
proporciona autonomía de 4 horas. Además, el vecindad con el mismo tamaño que la máscara de
sistema aprovecha el procesador Intel Atom N450, filtrado para el cálculo de cada píxel. Esto
integrado en el netbook utilizado. significa que cada hebra transfiere un dato desde
La GPU incorpora dos multiprocesadores. la memoria global a la memoria compartida. Para
Cada multiprocesador tiene una unidad de obtener la máxima precisión y evitar conflictos de
instrucción, 8 procesadores elementales (SP) que banco en la memoria compartida, estos datos se
ejecutan la misma instrucción sobre distintos almacenan en punto flotante. Por lo tanto, hay n-1
datos (SIMD) y una memoria local (16 KB). Con hebras por bloque que sólo cargan datos, pero que
objeto de extraer el máximo rendimiento de los no calculan ningún píxel procesado. Para no
SPs, minimizando los retardos asociados a los emplear demasiadas hebras en esta etapa de carga,
accesos a memoria, necesitamos asignar 4 hebras el tamaño del bloque debe ser lo suficientemente
a cada SP, que son entrelazadas en el SP. Por grande comparado con el tamaño de la máscara.
tanto, debemos asignar al menos 32 hebras a cada Se ha ajustado el tamaño de bloque a 1x128, y el
multiprocesador. tamaño de la máscara de 7x7.
La utilización de cada multiprocesador de la Cuando todos los datos están guardados en la
GPU debe ser máxima para poder aprovechar memoria compartida, cada hebra multiplica los
realmente este mecanismo de minimización de la coeficientes del filtro, guardados en la memoria
latencia del hardware. Para optimizar el uso de los para constantes, con el correspondiente píxel y su
procesadores disponibles, los parámetros que vecindad. El resultado se guarda en la memoria
deben ser determinados son el número de hebras global. Cada hebra repite este procedimiento dos
veces, una vez por cada máscara.
55
Sesión II: FPGAs versus Multicores/GPUs
- Image capture
- Memory management
RGB input image
Contrast enhancement
- RGB2HSV conversion
HSV image
- Coarse-to-fine control
V sub-histograms
- Sub-histograms combination
- Histogram equalization
T V Global histogram
I - Look-up-table substitution
M Look-up table
E Retina-like processing
- Weighting factors calculation - 1D convolutions
Weighting factors
- Linear combinations
- Memory management Retina output
- Enhanced Brightness channel computations
Enhanced Brightness channel
- HSV 2 RGB conversion
Output image
- Final Image visualization
Figura 4. Secuencia de procesos que se ejecutan en CPU y GPU, las flechas en línea continua y discontinua indican
transferencias de datos grandes y pequeñas respectivamente.
56
JCRA 2011 | Tenerife 7-9 de Septiembre
Figura 5. De izquierda a derecha: la primera imagen se corresponde con la entrada de vídeo del sistema; el resto de
imágenes se corresponden con las siguientes etapas de procesamiento: salida del filtrado de retina, salida del ecualizador
y salida final procesada.
57
Sesión II: FPGAs versus Multicores/GPUs
58
JCRA 2011 | Tenerife 7-9 de Septiembre
59
Sesión II: FPGAs versus Multicores/GPUs
important. Big eort have been done in com- section 6. Here we compare the multicore CPU
puter science to produce high quality pseudo- solution with the FPGA implementation using
random uniform samples, since they allow to several Monte Carlo parallel cores. Finally,
produce samples of any other distribution. In- some conclusions are drawn in section 7.
deed, let ui be a sample of the uniform dis-
tribution in (0, 1), X the target distribution
2 Impulse C
and ICDF its Inverse Cumulative Distribu-
tion Function. Then,
Impulse C extends standard ANSI-C using
60
JCRA 2011 | Tenerife 7-9 de Septiembre
inside each process. Instruction parallelism is the tool that we want a matrix inferred this
automatically generated by the scheduler. Im- way. Instead, we declared each element of the
pulse C automatically generates and analyses matrix as a dierent 32-bit unsigned integer
the instruction dependence graph so that inde- variable and we generated the Impulse C code
pendent instructions are performed in parallel. with the help of a python script. However, the
In the case of loops, further level of parallelism area required for this implementation was not
can be achieved by means of precompiler direc- worth the eort and it is preferable to instanti-
tives or pragmas. They are loop unrolling and ate several Block RAM based Mersenne cores
loop pipelining, which are specied by placing if more throughput is required.
#pragma CO UNROLL and #pragma CO
PIPELINE just after the header of a loop.
4 Box-Muller
The Mersenne Twister is a high quality uni- erate whichever other distribution. Here we
form random number generator with a period use the Box-Muller transformation which pro-
of 2
19937
− 1 and a 623-dimensional equidis- duces two independent Gaussian samples from
tributed property [2]. The original C source two uniform ones. Let u1 and u2 be two sam-
code can be found in that reference and it is ples of the uniform distribution in (0, 1], then
This implementation is not HW friendly be- is the huge area required for the transcen-
cause it lacks a constant throughput. Instead, dental and trigonometric oating-point oper-
we have rewritten the algorithm so that once ators from the Altera Megafunctions [6], that
the value of the matrix is used, it is replaced limit the number of Monte Carlo cores that
by the new one. In fact, since the matrix is can be implemented in the FPGA. In order to
mapped to a Block RAM, which is limited up slightly reduce this area utilization, the iden-
2 2
to two ports, we need two dierent matrices to tity sin α + cos α = 1 is utilized, saving one
61
Sesión II: FPGAs versus Multicores/GPUs
1 payOffSum = 0 ;
2 for (i = 0; i < nSims ; i ++){
3 priceSum = S0 ;
4 for ( j = 0; j < nSteps ; j ++){
5 W = getGaussian ( ) ;
6
√
7 S = S ∗exp((r − v 2 /2)∆t + v ∗ ∆T W ) ;
8 p r i c e S u m += S ;
9 }
10 p a y O f f = max ( 0 , priceSum / ( n S t e p s +1) − K) ;
11 payOffSum += p a y O f f ;
12 }
13 price = exp(−r ∗ T )∗ payOffSum / nSims ;
Listing 2: Impulse C pseudo-code for the payO computation in a pipeline with rate 1
62
JCRA 2011 | Tenerife 7-9 de Septiembre
In order to accelerate this algorithm with sitions of an array with a size BUFF_SIZE
Impulse C, loop pipelining must be used. greater or equal to the addition latency, as
This is trivially achieved by simply insert- shown in Listing 4. This way, the additions
ing #pragma CO PIPELINE after the head can be performed with rate 1 plus a negligi-
of the body. However, Impulse C does ble penalization to add the nal values stored
not allow pipeline nesting and the two loops in the array. As before, we must only ensure
should be attened into a single loop exe- that BUFF_SIZE is bigger than the pipeline
cuted nSim*nSteps iterations. However, there latency so that it is true that there is no depen-
is loop dependence between iterations which dence between all the stages in the pipeline.
prevents a pipeline with rate 1, i.e, a pipeline Therefore the extra time needed for adding
computing iterations every clock cycle. To the nSims values would be approximately of
avoid the loop dependence, we must take ad- nSims +la + BUFF_SIZE ·la ≈ nSims clock cy-
vantage of the independence of the stock prices cles, where la is the addition latency. However,
among dierent simulations, so that PARAL- the overall computation time of our Monte
LEL_PATHS (PP) simulations are concur- Carlo core is essentially of nSteps*nSims cy-
rently computed. cles, since there is overlapping between the
To this end we split the problem in two payO computation and the sum reduction.
63
Sesión II: FPGAs versus Multicores/GPUs
Listing 3: Impulse C pseudo-code for the payO accumulation in a pipeline with a rate equal to
the latency of the addition operation (7 cycles for the lowest latency Altera Megafunction)
1 payOffSum = 0 ;
2 for (i = 0; i < nSims ; i ++){
3 #pragma CO PIPELINE
4
5 co_stream_read ( s P a y o f f I n , &p a y O f f , sizeof ( float ) ) ;
6 payOffSum += p a y O f f ;
7
8 }
Listing 4: Impulse C pseudo-code for the payO accumulation in a pipeline with rate 1
1 payOffSum = 0 ;
2 for (i = 0; i < nSims ; i ++){
3 #pragma CO PIPELINE
4 #pragma CO NONRECURSIVE s u m s B u f f e r
5
6 co_stream_read ( s P a y o f f I n , &p a y O f f , sizeof ( float ) ) ;
7
8 if ( initStage ( i ) )
9 payOffSum = 0 ;
10 } else {
11 payOffSum = s u m s B u f f e r [ i % BUFF_SIZE ] ;
12 }
13
14 payOffSum += p a y O f f ;
15 s u m s B u f f e r [ i % BUFF_SIZE ] = payOffSum ;
16 }
17
18 // F i n a l addition
19 payOffSum = 0 ;
20 for (i = 0; i < BUFF_SIZE ; i ++){
21 payOffSum += s u m s B u f f e r [ i ] ;
22 }
64
JCRA 2011 | Tenerife 7-9 de Septiembre
CPU (1 core) CPU (2 cores) CPU (4 cores) FPGA (25 cores) Speed-up
We have implemented a Monte Carlo method ating low-discrepancy sequences from the
for pricing Asian Options in FPGAs using normal distribution: Box-muller or inverse
65
JCRA 2011 | Tenerife 7-9 de Septiembre
67
Sesión II: FPGAs versus Multicores/GPUs
68
JCRA 2011 | Tenerife 7-9 de Septiembre
69
Sesión II: FPGAs versus Multicores/GPUs
foreach Pixel pr
(with coordinates (xr , yr )) do
xi = xr cos(βr ) + xy sin(βr ) + ∆x
Figure 2: Rotation of an image. yi = xr sin(βr ) − xy cos(βr ) + ∆y
if (xi , yi ) is inside i then
Get 4 neighbors p1 , p2 , p3 , p4
eraging their values using the distance to the Compute distance to pr
position of the rotated pixel. The procedure d x k = x r − xp k
for rotation and translation is in algorithm 4. dyk = yr − ypk )
Summarizing, the transformation of images r(xr , yr ) =
4
requires: i) the computation of the equivalent d · dyk · i(xpk , ypk )
k=1 xk
coordinates of the transformed image onto the else
original image grid; and, ii) the averaging of r(xr , yr ) = 0
the values of the four closest pixels from the end
original image. end
end
5 Implementations
5.1 GPGPU
The GPGPU implementations are shown in
We use CUDA to program a parallel version table 1. In RA each block deals with the ro-
of the ane transformation using a TESLA tation of an image, so there are 10000 active
C1060 card from NVidia. We selected single- blocks for SPA and 150 active blocks for ET.
precision arithmetic operations. The GPGPU Each thread computes the rotation of a col-
chosen has 64K blocks, a maximum of 512 umn (64 columns for SPA and 512 columns
threads per block, 4GB of global memory, for ET). There is no need to use more threads,
16KB of shared memory per block and a since the parallelization is determined by the
wrap size of 32. warp size of 32. Having Fig. 2 in mind, it is
In algorithm 4, it is shown that for each clear that the reading of the neighbors cannot
pixel in the transformed image, it is necessary be coalesced, unless α = 0. Implementations
to read four pixels from the original image and RB1 and RB2 process the image in tiles, thus,
to write the new pixel itself. We will see the promoting the use of the fast shared mem-
impact of this below. We develop four dierent ory and the coalesced access to global mem-
implementations that were tested under two ory. Again, each block deals with a dierent
dierent scenarios: image, but now each tile is rst moved coa-
lescedly to shared memory, then, rotated us-
• SP A: 10.000 64x64 images ing only shared memory, and the rotated tile
is saved onto DRAM coalescedly. In RB1 the
• ET : 150 512x512 images rotated image is divided into 8x8-pixel tiles.
70
JCRA 2011 | Tenerife 7-9 de Septiembre
Rotated image
DRAM1
FPGA
odd images even images
irOginal RAM
RAM11 RAM
RAM22
image
p1,p2,p3,p4
PIPELINE1 PIPELINE2
PIPELINE1 PIPELINE2
71
Sesión II: FPGAs versus Multicores/GPUs
RAM1ÆPIPE1 DRAM1ÆRAM2
Image’1
PIPE1ÆDRAM2 seen in Fig. 5, that it is possible to have a
constant access to both DRAM1 and DRAM2 ,
Image2
Latency
thus, maximizing throughput.
The total amount of data that needs to be
Image3
DRAM1ÆRAM1 RAM2ÆPIPE2
Image’2
...
... PIPE2ÆDRAM2
stored for both SPA and ET is approximately
...
163 MB if single-precision oating point is
Pipeline 1 Pipeline 2 used. Therefore, the DRAM capacity of the
board is ne. The FPGA have an embedded
memory capacity of 972KB for M9K blocks
Figure 5: Processing ow for FPGAs.
and 864KB for M144K blocks. A 64 × 64-pixel
image require 16KB, so the device can hold
the two local memories required. However, for
SPA the memory needed for a 512 × 512-pixel
so it is possible to read the required 4 data image is 1MB, more than the available embed-
at a time. The processing ow shows that it ded memory. For this study we will assume
is possible to overlap processing with memory that there is enough memory to implement the
reading and writing. First, the original image two local memories.
must be stored into local FPGA memory (i.e. Regarding arithmetic resources, we com-
RAM1 ). Then, the processing is performed in puted a lower bound on the resources
72
JCRA 2011 | Tenerife 7-9 de Septiembre
ET SPA
including control logic there will be plenty of ×32 ×37 ×64 ×120 ×74 ×86 ×32 ×28
resources left. This situation is advantegous, ×28 ×35 ×59 ×64 ×30 ×89 ×105 ×28
since it could be desireable to implement more SPA ≡ 104 64 × 64 images; ET ≡ 150 512 × 512 images
processing blocks that can work in parallel.
The performance results are in the next
subsection and they are based on actual 80
Speedup
GPGPU 512x512
40 FPGA 64x64
30
quency. 0
1 80 160 240 320 400 480
Iterations
6 Results
The speedup obtained by the dierent im- Figure 6: Impact of I/O bottleneck.
plementations are shown in Table 2. Note,
that the FPGA implementation presents only
a single implementation (F P GA), since its erated application, we carried out an estima-
throughput does not depend on the trans- tion of the speedup that could be obtained if
formation applied (i.e. rotation or transla- the data transfer time is included and the pro-
tion). The speedup is computed compar- cessing is repeated several times before send-
ing a software implementation of the rota- ing the data back to PC main memory. The
tion/translation to the processing time of the estimation is shown in Fig. 6, where the esti-
GPGPU and FPGA without considering data mated speedup vs. the number of iterations is
transfer from the PC to the boards. The soft- displayed. It is clear that a single iteration
ware version was run on a a single core of presents a very poor performance, specially
an Intel Core2 Quad at 2.66 GHz. Regard- for the GPGPU. This is due to the fact that
ing rotations, the speedup of GPGPUs ranges the PCIe data rate is very low for the selected
from ×28 to ×64. The implementations us- GPGPU (≈ 1.5 Gbps). As long as the number
ing shared memory produce the best results. of iterations increases, the speedup converges
The FPGA speedup is of ×28. The transla- to a maximum value. This shows that: i) it is
tion operation produces more heterogeneous misleading to use the speedup without consid-
results, since the access to global memory is ering the I/O bottleneck; and, ii) in order to
now much more ecient. This leads to ex- make the most of a hardware accelerator, it is
treme behaviors, where SPA performs the best necessary to parallelize the whole algorithm.
without using shared memory (SA ) and ET
1 Let us now compare the performance of
performs the best using it (SB ). The speedup
2 GPGPU and FPGA. The GPGPU clearly out-
ranges from ×30 to ×120. The FPGA imple- performs the FPGA for the presented experi-
mentation shows a speedup of ×28. ments. It is also cheaper and the development
In order to present more realistic results and time is much reduced. Moreover, it is easy
to emulate the behavior of a completely accel- to change the functionality by reprogramming
73
Sesión II: FPGAs versus Multicores/GPUs
dynamically the kernel. This change of func- University CEU San Pablo) and FastCFD
tionality is hard to do on an FPGA. The best (Universidad Politécnica de Madrid). We
option would be to have the whole set of algo- thank Nvidia Corp. and Altera Corp. for their
rithms implemented on the device so a high- support to the project.
end device is required. Reconguration might
not be fast enough to be used to change the References
functionality of the device. Finally, an obvious
handicap of FPGA board is the communica- [1] C. Sorzano, J. Bilbao-Castro, Y. Shkol-
tion speed between the FPGA and the exter- nisky, M. Alcorlo, R. Melero, G. Caarena,
nal DRAM. M. Li, G. Xu, R. Marabini, and J. Carazo,
However, it would not be fair to determine A clustering approach to multireference
at this early stage in the research which tech- alignment of single-particle projections in
nology suits the best to implement electron electron microscopy, Journal of Structural
microscopy applications. For instance, power Biology, vol. 171, no. 2, pp. 197 206, 2010.
consumption of the FPGA is at least one or-
der of magnitude lower than that of GPGPUs. [2] C. Sorzano, C. Messaoudi, M. Eibauer,
Also, the limitation of executing the very same J. Bilbao-Castro, R. Hegerl, S. Nickell,
kernel in all parallel processors is not present S. Marco, and J. Carazo, Marker-free im-
in FPGAs. It must be further investigated age registration of electron tomography
the possibilities of chaining dierent process- tilt-series, BMC Bioinformatics, vol. 10,
ing blocks before sending them back the im- no. 1, p. 124, 2009.
ages to the external DRAM (i.e. FFT, corre-
lation, correntropy, etc.). These aspects are to [3] A. Brodtkorb, C. Dyken, T. Hagen,
be studied in the near future. J. Hjelmervik, and O. Storaasli, State-
of-the-Art in heterogeneous computing,
ACM Trans. Des. Autom. Electron. Syst.,
7 Conclusions vol. 18, no. 1, pp. 133, 2010.
Preliminary results on the acceleration of elec- [4] T. El-Ghazawi, E. El-Araby, M. Huang,
tron microscopy applications are presented. In K. Gaj, V. Kindratenko, and D. Buell,
particular, the acceleration of ane transfor- The promise of high-performance recon-
mations by means of FPGAs and GPGPUs is gurable computing, Computer, vol. 41,
addressed and accelerations of up to ×120 for no. 2, pp. 69 76, 2008.
GPGPUs and ×28 for FPGAs are reported.
Several GPGPU implementations are pre- [5] J. Nickolls and W. Dally, The gpu com-
sented and the speedup obtained under dif- puting era, Micro, IEEE, vol. 30, no. 2,
ferent scenarios including the eect of the pp. 56 69, 2010.
data transfer throughput is reported and
analyzed. Some preliminary conclusions are [6] Centro Nacional de Biotecnología.
drawn about the use of GPGPUs and FPGAs [Link]
as accelerators. bin/view/Xmipp/WebHome.
Future work includes the acceleration of the [7] Nvidia Corp., NVIDIA CUDA reference
dierent functions involved in SPA and ET. manual 2.0, 2008.
Also, alternatives architecture for FPGA will
be studied (i.e. tiling, etc.). [8] G. Caarena, C. Pedreira, C. Carreras,
S. Bojanic, and O. Nieto-Taladriz, FPGA
Acknowledgment Acceleration for DNA Sequence Align-
ment, J. of Circuits and Systems, vol. 16,
This work was supported by research projects pp. 245266, apr 2007.
USP-BS PPC05/2010 (Banco Santander and
74
JCRA 2011 | Tenerife 7-9 de Septiembre
SESIÓN III:
ARITMÉTICA COMPUTACIONAL
75
76
JCRA 2011 | Tenerife 7-9 de Septiembre
1. Introducción
77
Sesión III: Aritmética Computacional
Xj-1
Xj Xj+1
Xj+2
C8
C1 C6 C7
C2 C3
C4 C5
78
JCRA 2011 | Tenerife 7-9 de Septiembre
u=A(:,k)
Durante la fase de bidiagonalización, las sigma=norma(u)
rotaciones de Givens se aplican a la matriz A tanto u(k)=u(k)+sigma
rho=1/sigma·u(k)
a la izquierda como a la derecha. v= rho·u’A
Las mismas rotaciones se realizan sobre las A=A-uv
matrices IL e IR. De esta manera se obtiene la 2
Givensizq=I-2sigma uu’
matriz bidiagonal llamada B0 en la memoria U0=U0Givensizq
donde se almacenaba la matriz de partida A. Las
matrices unitarias resultantes tras las rotaciones %Introduce ceros derecha
U0 y V0 se almacenas en las memorias de IL e IR, %superdiagonal (fila k)
u=A(k,:)
donde debe cumplirse que A=U0B0V0. sigma=norma(u)
En la figura 3 se muestra el proceso de u(k)=u(k)+sigma
bidiagonalización de una matriz de 8x9 elementos. rho=1/sigma·u(k)
Se precisan 7 iteraciones (el mínimo de M ó N v= rho·Au’
menos 1) para realizar el cómputo, donde en cada A=A-vu
iteración se realiza una rotación a la izquierda y Givensder=I-2sigma2u’u
V0=GivensderV0
una rotación a la derecha. El pseudocódigo para
actualizar cada una de las memorias se muestra a end
continuación:
Algoritmo 1. Algoritmo de bidiagonalización
U0=IL, V0=IR
for k=1:min(L,M)-1
%Introduce ceros bajo la
%diagonal (columna k)
izq der
=B0
It. 7 It. 7
79
Sesión III: Aritmética Computacional
80
JCRA 2011 | Tenerife 7-9 de Septiembre
vectores, u·v ó v·u) y finalmente una resta Para la actualización de las matrices unitarias
matricial de este resultado con la matriz A de se necesita un nuevo multiplicador matricial
partida en la iteración, con lo que se actualiza el (u·u’), un multiplicador escalar (σ2) y un restador
contenido de la memoria A para la siguiente para obtener Givensizq ó Givensder.
iteración.
81
Sesión III: Aritmética Computacional
Sólo queda una última multiplicación La síntesis del sistema total emplea 24
matricial para obtener la nueva matriz (U0 ó V0) y circuitos DSP48E1, 48335 slice registers y 19725
actualizar la matriz unitaria de turno. slice LUTs. En la Virtex-6 XC6VCX75T supone
una ocupación del 8.3% de bloques
4. Estimación de recursos y tiempo de multiplicadores, un 52% de slice registres y un
cómputo 42% de slice LUT. En la Virtex-7 XC7V285T
supone una ocupación del 3.5% de bloques
multiplicadores, un 13% de slice registres y un
La mayor parte del hardware empleado en el
11% de slice LUTs respectivamente. Ambos
diseño del módulo se debe a los cálculos
dispositivos son las FPGAs más pequeñas de sus
aritméticos. Estos suponen la implementación
correspondientes familias.
física de:
Operando a una frecuencia de 100MHz, el
módulo diseñado emplea 49.9μs en realizar la
3 memorias de 64x16 bits bidia-gonalización de matrices de tamaño 8x8. El
1 memoria de 8x16 bits mismo algoritmo ejecutado en MATLAB necesita
2 multiplicadores matriciales [8x1] x [1x8] una media de 560 μs lo que supone una
1 multiplicador matricial [1x8] x [8x8] aceleración de un factor mayor de 10 en dicho
1 multiplicador matricial [8x8] x [8x8] cómputo.
1 multiplicador escalar-matriz [8x8]
1 multiplicador escalar-vector [8x1] 5. Conclusiones
3 multiplicadores escalares
2 restadores matriciales 8x8 La implementación de la bidiagonalización de
2 sumadores escalares matrices en FPGA usando el core Linear Algebra
1 divisor Toolkit ha supuesto una computación 10 veces
más rápida que el cálculo empleando Matlab. Esta
La interfaz de usuario de los cores empleados operación es la primera fase que se debe realizar
para el desarrollo de los circuitos aritméticos para la obtención de los valores singulares de
empleados dan una estimación de la latencia que matrices por el método de Golub-Kahan que es la
es necesaria para realizar los cálculos así como la operación principal que debe realizarse para el
cantidad de bloques DSP48 a utilizar. calibrado de un array de cámaras. Este cálculo
debe realizarse múltiples veces para ajustar los
Latencia parámetros característicos de cada una de las ocho
DSP48E1
[ciclos] cámaras, empleando para ello unos 30 minutos
Multiplicador usando Matlab. La realización de todo el proceso
2x1 82
[8x1][1x8] en FPGA permitirá, en un futuro, realizar la
Multiplicador misma calibración en un tiempo un orden de
8 89
[1x8][8x8] magnitud por debajo al menos.
Multiplicador Se observa que el módulo implementado
8 89
[8x8][8x8] ocupa relativamente pocos recursos de las FPGA
Divisor 52 estudiadas (que son las más pequeñas de cada
Restador 8x8 0 5 familia). Una posible mejora consiste en aumentar
Multiplicador el grado de paralelismo de la arquitectura diseñada
1 7 y realizar un circuito completamente pipeline.
escalar-matriz
Multiplicador Próximamente se tratará de implementar la
1 7 descomposición QR [9]. Este algoritmo supone la
escalar-vector
Multiplicador segunda fase del cálculo del SVD de matrices.
3x1 2
escalar
Tabla 1. Recursos y latencia de bloques aritméticos
82
JCRA 2011 | Tenerife 7-9 de Septiembre
83
JCRA 2011 | Tenerife 7-9 de Septiembre
85
Sesión III: Aritmética Computacional
ciones [10], [11]. El artículo se ha estructurado Dado que se está trabajando en un cuerpo fi-
de la siguiente forma: la sección 2 se dedica al nito, el cuadrado se puede calcular como:
problema de la inversión en cuerpos finitos de-
finidos sobre bases polinómicas, introduciendo p2 (x) = C · p(x) (3)
el algoritmo de Itoh-Tsujii para su obtención.
donde C es una matriz m × m. En la sección
La sección 3 se dedica a los multiplicadores,
3 se obtendrá la expresión para esta matriz en
exponiendo diversas soluciones y proponiendo
función del polinomio F(x) de definición del
la más apropiada para cuerpos finitos de orden
cuerpo.
elevado, concretamente para GF(2233 ). La sec-
Así, el problema queda reducido a calcular
ción 4 presenta una serie de nuevas arquitectu- m−1
−1
ras para realizar la inversión rápida basadas en p2 , tratando de utilizar exponenciacio-
el pre-cálculo de matrices de exponenciación, nes a partir de la matriz del cuadrado. Una
y finalmente en la Sección 5 se proporcionan solución es utilizar el desarrollo en serie:
las conclusiones. n−1
n Y i
−1
p2 = p2 (4)
i=0
2. Inversión en cuerpos finitos
GF(2m ) donde haciendo n = m − 1, se obtiene el in-
m
verso aplicando m − 2 veces la matriz del cua-
Los cuerpos finitos GF(2 ) presentan espe- drado consecutivamente y realizando los m − 2
cial interés en codificación y criptografía. En productos de polinomios correspondientes. Si
caso de utilizar bases polinómicas o están- ambas operaciones se realizan combinacional-
dar, estos cuerpos se construyen sobre poli- mente, es posible completar el cálculo usando
nomios irreducibles, de manera que las opera- m − 2 ciclos de reloj (la elevación al cuadrado
ciones de suma y multiplicación quedan per- final se supone combinacional). Para m = 4
fectamente definidas. Por ejemplo, uno de los resulta razonable, pero para un cuerpo como
cuerpos utilizados en el estándar FIPS 186-2 el GF(2233 ), resulta un número de ciclos de re-
[3] es GF(2233 )/(x233 + x74 + 1), de manera loj excesivo. Para reducir el número de ciclos
que la multiplicación dentro del cuerpo impli- de reloj puede recurrirse al algoritmo de Itoh-
ca una multiplicación de polinomios y una re- Sujii (ITA) [8] modificado para su aplicación
ducción modular sobre el polinomio utilizado en base estándar (ITA generalizado) [5]. Es-
para construir el cuerpo. m−1
−1
te algoritmo permite calcular p2 usando
matrices de elevación al cuadrado, a partir de
2.1. Inversión a partir del Pequeño Teore-
cadenas aditivas de Brauer [9], tal y como se
ma de Fermat
expone a continuación.
El cálculo del inverso multiplicativo sobre un
cuerpo de este tipo puede realizarse apli- 2.2. Inversión mediante ITA generalizado
cando una extensión del Pequeño Teorema k
−1
de Fermat (LFT) [5], de manera que dado Definiendo αk (p) = p2 , es inmedianto de-
p(x) ∈ GF (2m )/F (x) el inverso p−1 (x) ∈ mostrar que:
GF (2m )/F (x) se puede calcular como: k j
αk+j = (αj )2 αk = (αk )2 αj (5)
m
p−1 = p2 −2
(1)
de manera que es posible ir escribiendo
m−1
−1
Teniendo en cuenta que: p2 en función de potencias más peque-
ñas relacionadas siempre a partir de matri-
m m−1
−2 −1 2 ces de elevación aplicadas sucesivamente. La
p2 = (p2 ) (2)
cuestión es ahora ir eligiendo k y j en cada
se puede calcular el inverso obteniendo paso para pasar de 1 (α1 (p) = p) a m − 1
m−1 m−1
−1 −1
p2 , y elevando el resultado al cuadrado. (αm−1 (p) = p2 ) con el menor número de
86
JCRA 2011 | Tenerife 7-9 de Septiembre
21 23 −1 41 43 −1
3 α3 (p) α2+1 (p) (α2 ) α1 = p 3 β3 (p) β2+1 (p) (β2 ) β1 = p
3 6 3 6
−1
4 α6 (p) α3+3 (p) (α3 )2 α3 = p2 4 β6 (p) β3+3 (p) (β3 )4 β3 = p4 −1
21 27 −1 1 7
−1
5 α7 (p) α6+1 (p) (α6 ) α1 = p 5 β7 (p) β6+1 (p) (β6 )4 β1 = p4
7 14
−1
6 α14 (p) α7+7 (p) (α7 )2 α7 = p2 6 β14 (p) β7+7 (p)
7
(β7 )4 β7 = p4
14
−1
14 28
−1
7 α28 (p) α14+14 (p) (α14 )2 α14 = p2 7 β28 (p) β14+14 (p) 414
(β14 ) β14 = p 428 −1
1 29
−1
8 α29 (p) α28+1 (p) (α28 )2 α1 = p2 8 β29 (p) β28+1 (p)
1
(β28 )4 β1 = p4
29
−1
29 58
−1
9 α58 (p) α29+29 (p) (α29 )2 α29 = p2 9 β58 (p) β29+29 (p) 429
(β29 ) β29 = p 458 −1
58 116
−1
10 α116 (p) α58+58 (p) (α58 )2 α58 = p2 10 β116 (p) β58+58 (p)
58
(β58 )4 β58 = p4
116
−1
2116 2232 −1
11 α232 (p) α116+116 (p) (α116 ) α116 = p
87
Sesión III: Aritmética Computacional
Sin embargo, en este caso no se obtiene ningu- opción para contener el área. Por otra parte,
na ventaja porque el valor inicial γ1 (p) = p7 en [4] se propone el desarrollo de multiplica-
precisa de varios ciclos de reloj, y matrices adi- dores híbridos de Karatsuba, que permiten
cionales (la unidad básica en este caso es C 3 ). mejorar los resultados en área y retardo,
Independientemente del procedimiento de in- combinando adecuadamente multiplicación
versión que se utilice, se precisan de dos ele- clásica y recursiva. Este tipo de multiplicador
mentos básicos: un multiplicador y la matriz es el que se utiliza en la implementación del
del cuadrado C o una de sus potencias. En la quad-ITA [11]. En este artículo proponemos
siguiente sección se aborda la implementación utilizar una variación del multiplicador de
de estos dos elementos. Karatsuba en el que no se generan solapa-
mientos, reduciendo apreciablemente el área
y el retardo. Este multiplicador se describe en
3. Multiplicación en cuerpos [13], y en el presente artículo se ha mejorado
GF(2m )/F (x) convirtiéndolo en un multiplicador híbrido sin
solapamiento.
La multiplicación en cuerpos finitos binarios
definidos sobre bases estándar GF(2m )/F (x)
3.1. Mutiplicador de Karatsuba-Ofman
se realiza en dos fases: en primer lugar se efec- sin solapamiento
túa el producto de los dos polinomios, y a con-
tinuación una reducción modular sobre el po- Dados dos polinomios p(x), q(x) ∈ GF (2m ),
linomio de definición del cuerpo. La Figura 1 éstos se pueden escribir como [13]:
muestra el esquema general de un multiplica-
m−1 n−1 n−1
dor para cuerpos finitos definidos sobre poli- p(x) =
X i
pi x =
X
p2i x
2i
+
X 2i+1
p2i+1 x
nomios irreducibles. i=0 i=0 i=0
(9)
m−1 n−1 n−1
i 2i 2i+1
X X X
q(x) = qi x = q2i x + q2i+1 x
Multiplicador i=0 i=0 i=0
Figura 1: Multiplicador sobre GF(2m )/F (x) y análogamente qe (y) y qo (y) de manera que:
p(x) = pe (y) + xpo (y)
(11)
Dados dos polinomios p(x), q(x) ∈ q(x) = qe (y) + xqo (y)
GF (2m )/F (x) de grado m − 1, su pro-
ducto de polinomios dará como resultado un EL producto p(x) × q(x) puede escribirse en-
polinomio r de grado 2 · (m − 1), que se puede tonces:
representar mediante 2m − 1 componentes pq =(pe (y) + xpo (y))(qe (y) + xqo (y))
binarias. En el caso de valores elevados de m, 2
=[pe (y)qe (y) + x po (y)qo (y)]+
el bloque multiplicador de polinomios precisa x[pe (y)qo (y) + po (y)qe (y)]
de una gran cantidad de área, que además (12)
=[pe (y)qe (y) + ypo (y)qo (y)]+
aumenta como m2 si se implementa como x{[(pe (y) + po (y))(qe (y) + qo (y))]−
un multiplicador clásico. El multiplicador de [pe (y)qe (y) + po (y)qo (y)]}
Karatsuba [6] permite diseñar multiplicadores
recursivos cuyo número de puertas aumenta Teniendo en cuenta que la resta sobre GF(2)
como mlog2 (3) , perfilándose como una buena es equivalente a la suma y que multiplicar por
88
JCRA 2011 | Tenerife 7-9 de Septiembre
89
Sesión III: Aritmética Computacional
Una vez obtenido el producto polinómico, de- (xc5vtx240t-2ff1759). Los datos se han obte-
be realizarse la reducción modular sobre el po- nido a partir de los procesos de síntesis y pla-
linomio F (x), usando la matriz RM . Es in- ce&route proporcionados por la herramienta
mediato ver a partir de (16) que la operación ISE 12.2. En el caso del retardo, los resultados
de elevar al cuadrado sobre GF(2m )/F (x) se de síntesis difieren bastante de los obtenidos
puede representar mediante una matriz m × m tras la fase de place&route debido a la gran
construida tomando las columnas de RM co- cantidad de LUTs implicadas, que generan re-
rrespondientes a los coeficientes pares. tardos de enrutamiento difíciles de estimar con
precisión. No obstante, se han incluido para
realizar comparaciones con los inversores pre-
4. Arquitecturas rápidas basadas en sentados en [11], donde solo se proporcionan
matrices precalculadas resultados de síntesis. Así, en la tabla se han
incluido el número de LUTS, el retardo, el nú-
Las implementaciones basadas en el algorit-
mero de ciclos de reloj, el tiempo total pa-
mo ITA precisan de varios ciclos de reloj para
ra calcular el inverso, T , y el parámetro de
obtener la multiplicación por las potencias de
desempeño de área-prestaciones, definido co-
la matriz C en el caso del squarer-ITA, o C 2 si
mo P = 1/(#LU T S × retardo × #ciclos), tras
se aplica el quad-ITA. Además, se necesita un
las fases de síntesis y de place&route. Señalar
ciclo adicional para realizar la multiplicación
también que en [11] no se han incluido en los
de polinomios. En el presente articulo se pro-
resultados los ciclos de inicialización, por lo
pone realizar el precálculo de las matrices ne-
que a efectos de comparación se han omitido
cesarias e implementarlas como circuitos com-
también en la Tabla 5, aunque se ha indica-
binacionales, de manera que puede realizarse
do entre paréntesis el número de tales ciclos
el cálculo en un solo ciclo de reloj. Incluso, te-
para cada una de las implementaciones. Como
niendo en cuenta que el multiplicador de poli-
puede verse en la tabla, para la arquitectura
nomios propuesto es también puramente com-
prc-ITA, el área necesaria es un 50 % mayor,
binacional, se puede realizar cada uno de los
pero el número de ciclos de reloj se ha dis-
pasos de la Tabla 1, en un sólo ciclo de reloj,
minuido en un 300 %. El retardo es superior,
reduciéndolo de 33 (30 usando quad-ITA) a so-
al tener dos módulos combinacionales en serie
lamente 10 (más 1 de inicialización). La prin-
(la matriz correspondiente y el multiplicador
cipal dificultad que presenta consiste en pre-
de polinomios), pero el tiempo necesario pa-
calcular las matrices C, C 3 , C 7 , C 14 , C 29 , C 58
ra realizar el cálculo total es considerablemen-
y C 116 e implementar los correspondientes cir-
te menor, resultando una mejora global, como
cuitos combinacionales teniendo en cuenta el
muestra el parámetro P . No obstante, a partir
elevado número de puertas lógicas que contie-
de esta primera arquitectura, se pueden reali-
nen algunas de ellas (por ejemplo C 58 requiere
zar modificaciones para optimizar el área y/o
26957 puertas). Ha sido necesario desarrollar
el retardo, como se muestra a continuación.
un conjunto de herramientas software, deno-
minadas gftools para generar de forma auto-
4.1. Optimizaciones en área
mática estos circuitos, y plantear la arquitec-
tura que se muestra en la Figura 2, denomina- Para mejorar el área, pueden eliminarse algu-
da prc-ITA. Como puede verse, son necesarios nas de las matrices de mayor tamaño, y gene-
los módulos combinacionales de las 7 matrices rar cadenas de matrices, a costa de añadir al-
mencionadas, dos multiplexores, el multiplica- gún ciclo de reloj. Así, puede eliminarse C 116 ,
dor de polinomios, una unidad de control y y añadir un ciclo de reloj para calcularla a par-
un registro. En la Tabla 5 se muestran los re- tir de dos iteraciones sobre C 58 . Por otra parte,
sultados de implementación y retardos para el como el tamaño de C 14 es superior a 2 matri-
cuerpo GF(2233 )/(x233 + x74 + 1), compara- ces C 7 , se ha sustituido por dos matrices C 7
dos con el squarer-ITA y quad-ITA [11] para en serie. La arquitectura puede verse en la Fi-
un dispositivo de la familia Virtex-5 de Xilinx gura 3, y se ha denominado prcop1-ITA. Una
90
JCRA 2011 | Tenerife 7-9 de Septiembre
Tabla 5: Resultados de síntesis para inversores sobre GF(2233 ) sobre un dispositivo Virtex-5
Algoritmo #LUTS Retardo sint.(ns) Retardo p&r (ns) #ciclos T(ns) T p&r (ns) P P p&r
squarer-ITA 21379 7.09 - 33 (1) 234 - 199.9 -
quad-ITA 20950 7.79 - 30 (2) 233.7 - 204.2 -
prc-ITA 32511 14.83 37.4 10 (1) 148.3 370.4 207.4 82.24
prcop1-ITA 26448 16.00 26.71 11 (1) 176.0 293.8 214.8 128.7
prcop2-ITA 20414 16.58 25.52 14 (1) 232.1 357.3 211.0 137.1
prcops-ITA 21938 6.41 15.96 24 (1) 153.8 383.0 296.3 119.0
prcquad-ITA 22008 6.80 16.14 22 (1) 149.6 355.1 303.7 128.0
p p
p-1 p-1
mux
C
C
mux
Multiplicador
Multiplicador C3 sobre GF(2233)
C3 sobre GF(2233) clk sel clk
C7
sel
mux
C7
mux
C7 R
mux
C14
mux
R C29 sel
mux
C29 qsel Rsel
Unidad de csel Renable
sel Control Rsel
C58
C58 qsel Rsel Renable
Unidad de csel
Control Rsel RC
C116 Renable Renable qsel
fin clk
reset clk
qsel
inicio fin
clk
reset
inicio
Figura 3: Inversor sobre GF(2233 )/x233 + x74 +
1 con matrices precalculadas optimizado en área
Figura 2: Inversor sobre GF(2233 )/x233 + x74 + 1 (prcop1-ITA)
con matrices precalculadas
91
Sesión III: Aritmética Computacional
mux
mux
C Renable
150, 1989.
Multiplicador
C3 sobre GF(2233)
sel R
C7
mux
mux
C7 clk
C29 RC
186-2, 2000.
Renable csel
csel
qsel
RCenable Unidad de sel [4] F. Rodríguez-Henríquez, C.K. Koc¸, “On Fully
Control qsel
RCenable
Rsel
Parallel Karatsuba Multipliers for GF(2m ),”
clk Proc. Int. Conf. Computer Sci. and Tech. (CST
reset
inicio fin 2003), pp. 405-410, 2003.
92
JCRA 2011 | Tenerife 7-9 de Septiembre
Ignacio Bravo, Alfredo Gardel, José L. Lázaro, Carlos Fernández, Jorge García
ibravo@[Link]; alfredo@[Link], lazaro@[Link] [Link]@[Link]
Departamento de Electrónica. Escuela Politécnica Superior, Universidad de Alcalá
Campus Universitario. Carretera Madrid Barcelona km. 33.600
28871 – Alcalá de Henares. Madrid
93
Sesión III: Aritmética Computacional
En este sentido la solución propuesta, permite entrada reduciendo así el número de operaciones
extender la arquitectura para un tamaño de matriz aritméticas dentro del cálculo de autovalores.
distinto, ya que la arquitectura diseñada utiliza En lo que se refiere a la dimensión de las
módulos con estructuras regulares y por ello se matrices, la solución desarrollada permite una
puede ampliar sin necesidad de grandes cambios fácil expansión a diferentes tamaños. Inicialmente,
en la configuración de la arquitectura global. La en el presente proyecto se detalla la explicación
solución además aporta la ventaja de emplear del sistema para un tamaño de matriz de entrada
módulos que se ejecutan en paralelo, evitando al de 8x8 (M = 8) y 10x10 (M=10) elementos,
máximo un alto grado de dependencia de datos siendo todos ellos números reales.
entre los distintos módulos, lo que permite La elección de trabajar inicialmente con estos
alcanzar una elevada velocidad en el cómputo. tamaños de M viene justificada principalmente
El resto del trabajo se divide de la siguiente por el estudio experimental desarrollado en [6]
forma: en el capítulo 2 se presentan los donde se afirma que el número óptimo de
fundamentos matemáticos básicos para el cálculo imágenes para construir el modelo de fondo de
de autovalores y autovectores. En el capítulo 3 se PCA aplicado a visión artificial para la detección
presenta la arquitectura hardware desarrollada. El de objetos, se establece entorno entre 8 y 12
capítulo 4 presenta los resultados más imágenes (M = 8, M = 12), estando por tanto los
significativos alcanzados y por último el capítulo resultados para M = 8 y 10 imágenes dentro del
5 muestra las conclusiones y futuros trabajos rango idóneo.
derivados del presente trabajo. Con respecto al cálculo de autovalores y
autovectores, habitualmente éste se desarrolla en
2. Cálculo de autovalores y autovectores. sistemas basados en procesadores digitales [7].
Debido a las características internas de sus
El cálculo de autovalores y autovectores es arquitecturas, el proceso de cálculo es
una operación que requiere gran carga eminentemente secuencial, empleando un elevado
computacional, lo cual se convierte en un gran tiempo de cómputo en ello. Con el fin de mejorar
inconveniente para su implementación en FPGAs la velocidad del sistema, en algunas arquitecturas
debido a su naturaleza interna. Existen propuestas se guardan en tablas de memoria los valores
previas al auge de las FPGAs como [2] y [3] las trigonométricos necesarios para realizar el cálculo
cuales están basadas en una arquitectura sistólica. de autovalores y autovectores [9].
Sin embargo dichas propuestas no fueron Dentro de las diferentes alternativas para la
implementadas físicamente ya que la tecnología diagonalización, la basada en el método propuesto
del momento no permitía una implementación en por Jacobi [10] es la más utilizada, ya que facilita
dispositivos ASIC para matrices mayores de 3x3. su implementación en estructuras hardware de
En el presente caso el diseño ha sido realizado procesamiento paralelo.
íntegramente en el entorno XSG de Mathworks- Refiriéndonos ya al cálculo matemático de
Xilinx. La elección de esta herramienta viene autovalores (λ) y autovectores (V) de una matriz
justificada ante la dificultad de variar los valores y de entrada simétrica y real (C), existen varios
tamaños de las matrices de entrada así como el métodos posibles ya demostrados, aunque todos se
número de iteraciones del algoritmo desarrollado. basan matemáticamente en la siguiente expresión:
De esta forma, se permite agilizar y variar la C⋅V = λ ⋅I⋅V (1)
búsqueda de parámetros que mediante [4] (base en
la que se fundamente el presente trabajo) Para la obtención de los autovalores de una
conllevaban un elevado tiempo de desarrollo y matriz utilizando hardware específico, se precisa
simulación. Esta propuesta, al igual que en [3] y de alguna técnica recurrente para la
[4], el funcionamiento del sistema está basado en diagonalización de la matriz. Una vez obtenida la
módulos CORDIC (COordinate Rotation Digital matriz diagonal, D, los valores que aparecen en su
Computer) [5] que se encargan de resolver las diagonal principal coinciden con sus autovalores.
operaciones trigonométricas que se poseen. Esto es debido a que, dada una matriz inicial C,
Además, en la solución desarrollada en este que se denomina de aquí en adelante como S para
proyecto se aprovecha la simetría de la matriz de simplificar su notación, sus autovalores asociados
(λ) y su matriz de autovectores (V) se obtienen a
94
JCRA 2011 | Tenerife 7-9 de Septiembre
95
Sesión III: Aritmética Computacional
dos módulos CORDIC con una estructura en similares a las que se obtendrían con un
pipeline cada uno de ellos, para poder realizar las array sistólico.
operaciones trigonométricas demandadas por el • Bajo número de recursos de la FPGA
algoritmo, trabajando así a una alta velocidad de consumidos comparado con estructuras
ejecución. sistólicas para el cálculo de autovalores
Basándose en la reducción del número de y autovectores e independiente del
datos a operar, la Figura 1 muestra un diagrama de tamaño de las matrices de entrada [12].
bloques de la arquitectura planteada para la • Empleo de módulos CORDIC
ejecución concurrente y con un consumo eficiente trabajando en coordenadas circulares,
de recursos internos, del cálculo de autovalores y para resolver las multiplicaciones con
autovectores. Su funcionamiento interno ejecuta el matrices y operaciones trigonométricas.
método de Jacobi aplicado a matrices de 2x2 • Flexibilidad para trabajar con diferentes
elementos. Así, su estructura interna está tamaño de matrices (M) y tamaños de
compuesta únicamente de dos módulos CORDIC, datos (n)
memorias, registros y multiplexores. • Arquitectura interna concurrente.
• Cálculo de autovalores y autovectores
realizado mediante una misma
arquitectura con una estructura interna
en pipeline.
Inicialmente la matriz de covarianza de entrada
está almacenada en una memoria de datos DUAL-
PORT (DP). Una máquina de estados FSM (Finite
State Machine) gobierna el sistema en todo
instante y ejecuta las micro-instrucciones
necesarias, leídas de una memoria ROM de
programa. Este código contiene los valores
binarios correspondientes a la activación o
desactivación de las señales de control de la
arquitectura general.
De la Figura 1 destacan dos CORDIC, que son
los bloques destinados a llevar a cabo todas las
operaciones trigonométricas de (6). Ello hace
referencia al cálculo de ángulos (modo
vectorización) de (5) y rotación de vectores
pertenecientes a las submatrices 2x2 (modo
rotación) de (6).
Figura 1. Diagrama de bloques de la arquitectura Al emplearse dos módulos trabajando
implementada simultáneamente, acelera el tiempo de ejecución
global del algoritmo. El CORDIC B está diseñado
Esta propuesta de implementación tiene como de tal forma que es capaz de trabajar en los dos
características destacables: modos posibles (rotación y vectorización).
• Ejecución del algoritmo de cálculo de Mientras que el CORDIC A únicamente está
autovalores y autovectores de forma diseñado para poder trabajar en modo rotación. Se
íntegra en una FPGA. emplean únicamente dos CORDIC ya que debido
• Cálculo de autovalores y autovectores a la secuencia de funcionamiento del algoritmo y
de S a partir de su matriz triangular a la dependencia de datos, con 2 módulos se
superior gracias a la condición de alcanza la máxima eficiencia posible.
simetría de S. Se puede observar también en la Figura 1 una
• La arquitectura física propuesta no memoria RAM para el almacenamiento temporal
responde a la de un array sistólico, pero de ángulos de cada iteración. Para solventar
desde el punto de vista de conflictos de uso de la DP, se emplean dos
procesamiento, las características son memorias FIFO con la finalidad de almacenar los
96
JCRA 2011 | Tenerife 7-9 de Septiembre
97
Sesión III: Aritmética Computacional
Sin embargo, las experiencias prácticas realizadas desde XSG con los obtenidos en MATLAB.
para diferentes matrices, mostraron que para la Dichas matrices poseían en algunos casos tamaño
arquitectura propuesta el valor óptimo de de 8x8 (M=8) o de 10x10 (M=10). Además de
iteraciones es el expuesto en (8). variar el número de iteraciones (N) con objeto de
extraer el valor de h óptimo (8) (ver Figura 4)
h = M log(M ) (7) también se varió el ancho de la palabra (n) desde
18 a 22 bits (ver Figura 5 y Figura 6).
h = 5 + M log( M ) Analizando el error obtenido en los
(8) autovalores (Figura 4), se puede comprobar como
Con respecto a los errores entre la arquitectura el número óptimo de iteraciones se establece en
propuesta y los ofrecidos por MATLAB, el error 22 que es el resultado redondeado de sustituir M
se ha medido acorde a (9), siendo en dicha por 8 en (8). Este análisis también se extendió a
expresión, Vi un valor genérico de autovalor o los autovectores, alcanzándose en ambos casos la
autovector. misma conclusión.
Por su parte, en cuanto al tamaño ideal del
Vi − Vi ancho de los datos (n) también desde un punto de
XSG MATLAB
errori (%) = × 100 vista de autovalores, se observa en las gráficas de
Vi (9) la Figura 5 y Figura 6, que el error es mínimo para
MATLAB
n=22 (para valores superiores el error aumenta).
De esta forma se podría suponer que el valor ideal
En base a este error se establecen como para n fuera 22, sin embargo, analizando el
índices de comparación el error máximo (10) y el número de recursos consumidos por la FPGA para
error cuadrático medio (11). distintos n se puede comprobar en la Tabla 1
como éste aumenta notablemente para tamaños
eMAX (%) = max(errori (%)) (10) grandes de datos. Estos resultados fueron
alcanzados mediante la versión Xilinx ISE 10.1.
Por ello y tal como ocurre en numerosas
∑ (errori (%) )
k
2 ocasiones, nos encontramos ante el compromiso
i =0 (11) de priorizar entre errores y recursos consumidos.
eSQRT (%) =
k
Las principales fuentes de error durante de la
ejecución del algoritmo se encuentran en los dos
subsistemas CORDIC de la arquitectura, ya que es
en ellos donde se lleva a cabo toda la carga
matemática.
Comparando los resultados generados en
MATLAB mediante la función eig, con los
obtenidos en XSG, existe el problema de
establecer el número de bits óptimo de la palabra
y dentro de ésta cuántos para parte decimal y
Figura 4. Errores en autovalores más significativos
cuántos para parte fija (aritmética en coma fija). para matrices de 8x8 en función del
Gracias a las prestaciones de XSG, podemos ir número de iteraciones (N).
variando de forma cómoda la posición del punto
decimal con objeto de obtener la precisión idónea. Tabla 1. Número y porcentaje de recursos internos
Inicialmente para un tamaño de datos (n) de 18 consumidos para una XCV2P7 en
bits, se concluyó que la mejor resolución se función de n.
obtenía con 2 bits para parte entera y el resto para
decimal. n 18 19 20 21 22
Slices 2559 3020 3151 3495 3635
Así, se seleccionaron 100 matrices de
% uso 51.9 61.2 63.9 70.9 73.7
covarianza diferentes como entradas del sistema y
se procedió a evaluar los resultados alcanzados
98
JCRA 2011 | Tenerife 7-9 de Septiembre
Una vez comprobada la validez del diseño En este trabajo se ha expuesto el desarrollo de
realizado en XSG para el cálculo de autovalores y un sistema de cálculo de autovalores y
99
Sesión III: Aritmética Computacional
100
JCRA 2011 | Tenerife 7-9 de Septiembre
Manuel Rodríguez Valido, Cristian Sobota Rodríguez, Mario Jakas Iglesias y Eduardo
Magdaleno CaVtelly
mrvalido@[Link], csobota@[Link], mmateo@[Link], emagca@[Link]
Dpto. Física Fundamental Exp., Electrónica y Sistemas,
Facultad de Física,
Universidad de La Laguna.
101
Sesión III: Aritmética Computacional
Figu
ura 2. Algorritmo de simulaciión de absorción de
d
particuulas
102
JCRA 2011 | Tenerife 7-9 de Septiembre
103
Sesión III: Aritmética Computacional
5. Interfaz de Comunicacion
C nes y Softwarre
de Visualiza
ación
La ventaja de esta transsformación es que Aun nque en esta simmulación hardwware de absorció ón
ah
ahora debemos evaluar log2(m)) en el intervallo 1≤ de partículas
p no se
s generan dato tos masivamentte.
m < 2, salvandoo los problemass de convergenccia o Creíímos necesario o que por esstar creando un u
nnúmeros muyy grandes que provo quen sisteema escalab
ble para lla aceleracióón
ddesbordamientos. A partir del valor calcuulado commputacional de simulaciones más generalees,
loog2(m) obtenem mos –ln(x) sumáándole n. impplementar una in nterfaz que no ffuera el cuello de
La complejjidad del cálcu ulo del logariitmo, boteella del sistema.
teeniendo en cuuenta, los accesos a mem moria,
mmultiplicacioness y desplazamientos para los
cálculos en puntto fijos con signo, consume cuuatro
ciclos de reloj. Como quereemos optimizaar al
mmáximo la veloccidad de compu utación creamoss una
estructura pipelline formada porp cuatro de eestos
mmódulos logarittmo trabajando o en paralelo y un
circuito de conttrol de flujo dee datos que altterna
enntre ellos de foorma síncrona lo
os datos de entrrada.
AAsí el primer opperando ingresa en el primer
104
JCRA 2011 | Tenerife 7-9 de Septiembre
105
JCRA 2011 | Tenerife 7-9 de Septiembre
SESIÓN IV:
SISTEMAS TOLERANTES A ERRORES/TEST
A demonstration FPGA symbol generator for DSN telemetry testing ....................................... 109
107
108
JCRA 2011 | Tenerife 7-9 de Septiembre
[Link] MDSCC.
June 21, 2011
Abstract
Introduction
Randomizer
Simple designs are often very robust and pro-
Implements CCSDS recommendation using
vide reliable operation in the long run. Avail-
generator polynomial
ability of modern FPGAs has made possible 8 7 5 3
X +X +X +X +1
the implementation of very exible, recong-
urable data generators that can be tailored to
the DSN needs without costly hardware board Subcarrier modulator
design. Such is the case of the demo hardware
Modulates square subcarrier with data
symbol generator that uses a commercial low
cost FPGA development board. Fig 1 identi-
es the major vhdl software components. Encoders
109
Sesión IV: Sistemas Tolerantes a Errores/Test
N= =f ·k (1)
200 · 106
where N =increment
f= desired frequency
k = 21.47483648
sponse is read from the rows of generator ma-
trix which in turn,is determined by tapping.
Since convolution is a linear operation, su-
perimposition applies. Thus, response from a
given input sequence, can be obtained from
convolution, or weighted addition of impulse
responses, as shown in g 3. The manual pro-
cedure is carried out in two phases, rst, omit-
ting the inverter, and secondly, inverting ev-
ery other [Link] this methodology is un-
derstood, VHDL coding poses no major prob-
[Link] core of the code that is implemented
Figure 2: DDS. in the F SG is displayed on g 9 on appendix
A
110
JCRA 2011 | Tenerife 7-9 de Septiembre
scaling.
Example Compute 456 mod 223 = 10
24
using 1/223 scaled up by 2 ( 75234.15247)
Table 1: Formulas
Interleaver
111
Sesión IV: Sistemas Tolerantes a Errores/Test
long division
the normal path data while port B has the in- complex to implement. In 1982, E.R.
112
JCRA 2011 | Tenerife 7-9 de Septiembre
Four eight bit CPUs cooperate to provide hu- PCM set PCM format cpu2
HELP dump cmd list cpu2
man interface, parse commands and perform DF dump frame while being output cpu3
the necessary calculations needed to drive the DM dump frame buer cpu3
FIX select hard coded data for frame buer load cpu3
generator hardware. Monitor and control is
implemented in assembly language on an eight
Table 3: Command implementation
bit CPU design provided free by the ven-
[Link] code is limited to 1k instructions
which was insucient to implement the ba-
sic set of directives.A single CPU ocupies 6 implemented directives. Some of them have
% of real state of the target FPGA, and - no operational value, they were meant to as-
nally four instances of the design were used. sist in [Link] 4 is not listed since it
Parts of the rmware were replicated (direc- mostly conmtains monitor routines and the lcd
tive parser, arithmetic routines) but the design display sign on.
gained simplicity (other approaches like mod-
ifying the vendor assembly language compiler
were discarded ). Monitor and control appears Conclusions
like a single CPU to the user. All directives are
routed to all CPUs but the command is tar- Even lower end FPGAs are suitable for logic
geted only to one, which decodes and cong- implementations of moderate complexity, such
ures the generator hardware according to the is the case of coders used in the DSN. Their
instruction. The acting CPU answers as re- best implementation is in hardware. Moni-
quired. The output RS-232 is accessed by all tor and control was also implemented in the
CPUs through a priority encoding scheme to same FPGA to favor autonomy of the unit.
avoid contention. Master CPU 0 has the high- The multiprocessor scheme was dictated by
est priority and can reset/restart all other via the necessity of keeping the code below 1K
a reset command. At the time of this writ- instructions (CPU design constraint). Cur-
ing, three CPUs are full, while the fourth still rent FPGA spartan 6 (vs spartan 3e) would
can be used to implement additional directives have obviated this requirement ( 4K instruc-
without having to recompile the whole design. tions ). Data generators are tied to particular
The advantage of this scheme is that only the [Link] not desirable ."General purpose"
aected CPU has to be compiled, and the bit are more advisable since they can be instan-
le can be patched, an extremely fast proce- tiated as needed. Simulation plays a very im-
dure ( compared to other compiling processes, portant role in system building. Getting to
of course). Directives listed below, are all the know well the simulation tool can spare much
113
Sesión IV: Sistemas Tolerantes a Errores/Test
114
JCRA 2011 | Tenerife 7-9 de Septiembre
References
115
Sesión IV: Sistemas Tolerantes a Errores/Test
Appendix A
116
JCRA 2011 | Tenerife 7-9 de Septiembre
Table 4: α powers
The coecients of equation ( 6 ) belong to the
α exp α2 α 1
α0
ground eld {0,1} in which addition is de-
ned to be the same as subtraction, therefore
0 0 0 1
3 5 1 1 1
If α is a root of eq x +x+1 = 0 , this is
equivalent to write
6 1 0 1
Table 5: coes
α3 = α + 1 (7)
3 4 7 0
α ·α =α =α related to A by
117
Sesión IV: Sistemas Tolerantes a Errores/Test
α0 0 0 1 1 β0 1 0 0 4
α1 0 1 0 2 β2 0 0 1 1
α2 1 0 0 4 β1 0 1 0 2
α3
α4
0
1
1
1
1
0
3
6
β3
β4
1
0
0
1
1
1
5
3
Figure 11: Feedback register .
α5 1 1 1 7 β5 1 1 1 7
α6 1 0 1 5 β6 1 1 0 6
b = b2 α + b1 α 2 + b0
c = c2 α + c 1 α 2 + c 0
c=a×b
C =A×B
Figure 13: Constant multiplication .
Matrix B leads itself to hardware implementa-
tion. It can be realized with recirculating reg-
ister and an adder( a shift register with feed-
A toy RS encoder
back and and one exclusive or gate as shown in
g g 11) The rst column is equates to shift
A RS codeword results from appending the re-
register initial load. The second and third are
mainder of a polynomial division to the origi-
obtained adding the two bottom bits and re-
nal data. In equations
circulating the shift register. Fig g 11 shows
the scheme. The successive bits of number c
C(x) = I(x) · xn + R(x) (12)
are obtained by multiplying the row vector A n
by the columns of B. Multiplication by rst
I(x)x
R(x) = − Q(x) (13)
column produces the least signicant bit, the G(x)
next column the middle bit and the last col- where
umn produces the most signicant digit.
Fig g 12 provides an overall view of the
I(x) = input sequence
serial product. First registers are preloaded
G(x)= generating polynomial
with the number a and b. After three clocks,
C(x)= code word
the c register contains the result product .
. Our toy RS encoder will be of type RS(7,5,3)
But circuitry simplies even further when which encoding terminology means 7 symbols
one of the multipliers is a constant as shown in codeword,5 symbols data word,2 check sym-
3 3
in g 13 ( α ). This is the case when dividing bols and dened over a GF (2 ) Galois eld.
118
JCRA 2011 | Tenerife 7-9 de Septiembre
119
Sesión IV: Sistemas Tolerantes a Errores/Test
applying on IP cores' HDL (Hardware De- on whether a clock line is transmitted along-
scription Language) models a set of analy- side the data line. Likewise, control blocks
sis and transformation rules to produce spe- can command checksums to be sent following,
cic CRC instances suitable for each IP-core. among others, i) a frame size strategy, which
The reusability of such metaprograms is pro- transmits the checksum after a xed number
moted through the use of open compilation of data words, ii) a ags strategy, which trans-
tools [9, 10, 8], which enables the automatic mits the checksum after an end-of-frame ag,
deployment of the metaprograms on concrete or iii) a time-out strategy, which transmits the
IP core models. Finally, fault injection tech- checksum after a xed period of inactivity.
niques are used to assess the level of fault tol- The degree of resilience provided by the
erance attained by resulting HW designs. mechanism will depend on the generator poly-
The rest of the paper structures as follows. nomial [12, 3]. Koopman studies the theoreti-
Section 2 presents the context of this research. cal properties of a huge set of polynomials in
Section 3 reports on the design of a CRC [4], and highlights the importance of parame-
metaprogram, which is later deployed on real ters like Hamming Distance (HD) -minimum
case study in Section 4. Results and conclu- amount of bits to be changed to miss detec-
sions are nally detailed in Sections 5 and 6. tion for a given message size-, and Hamming
Weight (HW) -number of combinations for a
2 Research context specic amount of wrong bits in a xed mes-
sage size which would go undetected. The rst
This section presents the basic notions about HW 6= 0 is the HD for that message.
CRC mechanisms, metaprogramming of de- Balancing the error detection capabilities
pendability mechanisms and their automatic and data overhead of a CRC, in dierent con-
deployment using open compilation. texts of use, will require the parametrisation
of the polynomial in use and the message size.
2.1 CRCs and fault tolerance In the root of this paper, our research is
focused on deploying CRC detection mecha-
CRC tted transmitters send original data nisms on serial asynchronous frame size based
with extra bits calculated from applying a gen- components. There are some noteworthy con-
erator polynomial. In the receiver an identical straints to be taken into account: i) the se-
calculation is performed to the original+extra rial asynchronous frame size strategy has been
bits received to obtain a match signal indicat- chosen due to its simplicity and common use
ing no bit has been altered. If the result is in UART/USART protocols, but an exten-
negative, the packet has to be retransmitted. sion to include other strategies is present in
Dierent transmission strategies are candi- our roadmap, ii) only the transmitter is im-
date to include CRCs (see Figure 1). They are plemented, iii) an enable input signal must
classied into serial or parallel i/o structures. be activated every clock cycle data has to be
Further on, serial structures comprise syn- sent, and iv) no start/end bits are supported
chronous or asynchronous modes, depending yet. The aforementioned mechanism will be
dened as a metaprogram.
Frame size
2.2 Metaprograms and open compilation
Asynchronous Flags
120
JCRA 2011 | Tenerife 7-9 de Septiembre
Input HDL
Model
2. Input code parsing 1. Input comments parsing
(HDL to AST conversion) (Parameter extraction)
4. Statement analysis and transformation
AST Parser Directives M
Parser e
Default Meta-program
t
3. Apply Mechanisms (AST) a (Neutral code transformations)
i
AST representation of n
the input HDL model t
AST HandleStatement(AST in){
e
5. Customized AST r
return in;
f }
a
Customized AST c specializes …
e
representation of
User-defined Meta-programs
the input HDL model saved at… (Transformations for
6. Output file generation fault tolerance or security)
(AST to HDL conversion) AST HandleStatement(AST in){
AST out =
Analyze_and_Customize (in);
Output HDL CODESH Library return out;
(Metaprograms and
Model templates)
}
CODESH tool, which provides an open COm- techniques. Next section describes how to
pilation process for the design of DEpendable metaprogram a CRC strategy.
and SEcure Hdl-based systems.
121
Sesión IV: Sistemas Tolerantes a Errores/Test
122
JCRA 2011 | Tenerife 7-9 de Septiembre
Encapsulated uart_buf_crc1021.vhd
(CRC_protected: Original+CRC_adapted)
Original vhd module Metaprogram Rules library ieee;
--* CODESH ON Metaprogram input use ieee.std_logic_1164.all;
--* CODESH (...) parameters Generation Rule g1: use ieee.numeric_std.all;
--* CODESH OFF Step 1 - Original Compo-
(...) COMPONENT => uart_buf entity uart_buf_crc1021 is
INSTANCE => UART1 nent entity elements fetch port (
OUTPUT_DATA_PORT => tx_out Step 2 – Customisation of reset, txclk, ld_tx_data, tx_enable : in std_logic;
Parameter ENABLE_PORT => tx_enable tx_data : in std_logic_vector(7 downto 0);
EMPTY_PORT => tx_empty entity name & introduction tx_out, tx_empty : out std_logic;
extraction CLOCK_PORT => txclk of other elements tx_over_run tx_buf_empty: out std_logic;);
performed RESET_PORT => reset end uart_buf_crc1021;
STRATEGY => FSser Generation