Download DISEÑO DE MULTIPLICADORES PARALELOS DE 16 BITS EN

DISEÑO DE MULTIPLICADORES PARALELOS DE 16 BITS EN FPGAS
Gustavo E. Ordóñez-Fernández, Lewin A. López-López, Jaime Velasco-Medina
Grupo de Bioelectrónica y Nanoelectrónica, EIEE, Universidad del Valle
A.A. 25360, Cali, Colombia
E-mail: [email protected], [email protected], [email protected]
ABSTRACT
The system-on-a-chip offers the best technical advantages to develop new and innovative electronic products. In this context,
the use of embedded processors is greater every time and one of the main functional blocks of the processor is the multiplier.
This article presents efficient designs for the multiplication using FPGAs. In this case, for the performance analysis the
design parameters such as speed, area and dissipated power are considered. The designs proposed are seven parallel
multipliers and two sequential ones of 16 bits: ripple carry, carry save, Wallace, parameterized multiplier: megafunction,
Baugh-Wooley, parallel multiplier based on the algorithm of Booth, pipeline multiplier, sequential multiplier based on sum
and displacements, and sequential multiplier based on modified Booth algorithm. The designs are implemented in the FPGA
EPF10K70RC240-4 of board UP2 of Altera and are simulated in the tools, Max+Plus II and Quartus II version 3.0.
RESUMEN
Los sistemas en un solo chip “system-on-a-chip” ofrecen las mejores ventajas técnicas para desarrollar nuevos e
innovadores productos electrónicos. En este contexto, el uso de procesadores embebidos es cada vez mayor y uno de los
principales bloques funcionales del procesador es el multiplicador. Este artículo presenta diseños eficientes para la
multiplicación usando FPGAs. En este caso, para el análisis de desempeño se tienen en cuenta los parámetros de diseño tales
como velocidad, área y potencia disipada. Los diseños realizados son siete multiplicadores paralelos y dos secuenciales de 16
bits: ripple carry, carry save, Wallace, multiplicador parametrizado: megafunción, Baugh-Wooley, multiplicador paralelo
basado en el algoritmo de Booth, multiplicador pipeline, multiplicador secuencial basado en sumas y desplazamientos, y
multiplicador secuencial basado en algoritmo de Booth modificado. Los diseños son implementados en la FPGA
EPF10K70RC240-4 de la tarjeta UP2 de Altera y son simulados en las herramientas Max + Plus II y Quartus II versión 3.0.
DISEÑO DE MULTIPLICADORES PARALELOS DE 16 BITS EN FPGAS
Gustavo E. Ordóñez-Fernández, Lewin A. López-López, Jaime Velasco-Medina,
Grupo de Bioelectrónica y Nanoelectrónica, Escuela EIEE
Universidad del Valle, A.A. 25360, Cali, Colombia
E-mail: [email protected], [email protected], [email protected]
RESUMEN
Los sistemas en un solo chip “system-on-a-chip” ofrecen las
mejores ventajas técnicas para desarrollar nuevos e
innovadores productos electrónicos. En este contexto, el uso
de procesadores embebidos es cada vez mayor y uno de los
principales bloques funcionales del procesador es el
multiplicador. Este artículo presenta diseños eficientes para
la multiplicación usando FPGAs. En este caso, para el
análisis de desempeño se tienen en cuenta los parámetros de
diseño tales como velocidad, área y potencia disipada. Los
diseños realizados son siete multiplicadores paralelos y dos
secuenciales de 16 bits: ripple carry, carry save, Wallace,
multiplicador parametrizado: megafunción, Baugh-Wooley,
multiplicador paralelo basado en el algoritmo de Booth,
multiplicador pipeline, multiplicador secuencial basado en
sumas y desplazamientos, y multiplicador secuencial basado
en algoritmo de Booth modificado. Los diseños son
implementados en la FPGA EPF10K70RC240-4 de la
tarjeta UP2 de Altera y son simulados en las herramientas
Max + Plus II y Quartus II versión 3.0.
optimizados para los diferentes parámetros de diseño. En
este caso, el bloque funcional que realiza la multiplicación es
siempre un bloque esencial en cualquier sistema de
procesamiento digital de señales. Sin embargo, para el
diseño digital basado en FPGAs, es importante mencionar
que diseñar el bloque funcional para la multiplicación
usando la megafunción no siempre es la mejor alternativa de
diseño. Por ejemplo, en aplicaciones tales smart-cards y
telefonía celular, los principales criterios de diseño son
relacionados con el área y la potencia disipada.
Teniendo en cuenta las consideraciones anteriores, el
artículo presenta diseños eficientes para la multiplicación
considerando los parámetros de diseño tales como área,
velocidad y potencia disipada.
El artículo esta organizado de la siguiente manera, en la
sección 2 se presenta una descripción detallada del diseño de
los multiplicadores paralelos y secuenciales. En la sección 3
se presentan las tablas de comparación y resultados de
simulación de los multiplicadores diseñados y en la sección
4 se presentan las conclusiones y el trabajo futuro.
2. DISEÑOS DE MULTIPLICADORES
1. INTRODUCCIÓN
Las operaciones de multiplicación y división son más
complejas que las operaciones de adición o sustracción.
Inicialmente en algunos procesadores, la multiplicación y la
división eran llevadas a cabo como rutinas de software, las
cuales básicamente, realizan la multiplicación como una
secuencia de sumas y desplazamientos, y la división como
una secuencia de sustracciones y desplazamientos. Sin
embargo, los microprocesadores de alto desempeño,
disponen de multiplicadores y divisores implementados en
hardware para incrementar la velocidad de las operaciones
aritméticas.
De otro lado, hace algunos años era muy difícil realizar
diseños complejos, para volúmenes pequeños o medianos de
producción. Sin embargo, el vertiginoso avance de la
tecnologia permite realizar fácilmente diseños complejos y
de bajo costo, es decir, es posible diseñar sistemas
embebidos totalmente a medida para una aplicación dada, y
aún para volúmenes muy pequeños, usando dispositivos
FPGAs.
En este contexto, los procesadores embebidos son cada
día más utilizados para diferentes aplicaciones. Por lo tanto,
los principales bloques funcionales del procesador deben ser
En esta sección se presenta una breve descripción de cada
una de las arquitecturas para los multiplicadores paralelos y
secuenciales diseñados en este trabajo.
2.1 Multiplicador Ripple Carry
El multiplicador basado en un arreglo de sumadores de
acarreo propagado es una primera aproximación para
implementar
el
algoritmo
de
sumas
sucesivas
y
desplazamientos, este tipo de multiplicador tiene la
característica de transferir la propagación del acarreo a la
siguiente suma parcial hasta que terminen los productos
parciales correspondientes a esta fila, en este instante el
acarreo generado se propaga al último producto de la
siguiente fila de productos parciales y así sucesivamente
hasta culminar la multiplicación [1]. El bloque principal es
un sumador completo de 1 bit, y el diagrama de bloques de
un multiplicador ripple carry de 4 bits se muestra en la
Figura 1.
Figura 1. Multiplicador Ripple Carry de 4 bits
Figura 3. Multiplicador de Wallace de 4 bits
2.2 Multiplicador Carry Save
2.4 Multiplicador Parametrizado: Megafunción
El multiplicador basado en el arreglo de sumadores con
acarreo salvado es una segunda aproximación para
implementar
el
algoritmo
de
sumas
sucesivas
y
desplazamientos. La idea es romper la cadena de acarreo
propagado del sumador ripple para disminuir el retardo de
cada suma, lo cual permite acelerar la multiplicación. El
multiplicador tiene la característica de permitir salvar el
acarreo generado en las sumas parciales y transferirlo como
acarreo de entrada a la siguiente suma parcial de la fila de
productos parciales siguiente. Este multiplicador es también
conocido con el nombre de Multiplicador de Braun [2]. El
diagrama de un multiplicador carry save de 4 bits, se
muestra en la Figura 2.
Altera provee una librería de Megafunciones, incluyendo
una Librería de Módulos Parametrizados (LPM). Para la
multiplicación, se dispone de la Megafunción lpm_mult, la
cual es un bloque parametrizado y es descrito en un lenguaje
de alto nivel. El diagrama de la Megafunción se puede
observar en la Figura 4.
Figura 4. Megafunción para la multiplicación lpm_mult
2.5 Multiplicador Paralelo basado en el Algoritmo de
Booth
Figura 2. Multiplicador Carry Save de 4 bits
2.3 Multiplicador de Wallace
El multiplicador de Wallace es una variante del algoritmo de
sumas sucesivas y desplazamientos, donde se utilizan los
bloques de sumadores completos con sus tres entradas
recibiendo términos productos y generando un termino suma
que se adiciona con otro termino suma [3]. El diagrama de
bloques de un multiplicador de Wallace de 4 bits se muestra
en la Figura 3.
El Algoritmo de Booth presenta dos ventajas importantes:
Primero unifica los multiplicadores tanto para números
binarios positivos como negativos de n bits,
transformándolos en versiones adecuadas de multiplicandos
de n bits que se suman para generar productos de 2n bits de
signo correcto, en el sistema de representación numérica de
complemento a dos. Segundo, logra cierta eficiencia
respecto al número de productos parciales generados,
cuando el multiplicador tiene algunos bloques grandes de
unos [4].
El Algoritmo de Booth está basado en la observación
que existen múltiples formas de calcular un producto usando
la suma y la resta, por lo tanto si se tiene una ALU que
pudiera sumar o restar se podría obtener el mismo resultado
utilizando diferentes modos [5]. En las Figuras 5 y 6 se
presentan la celda básica y el arreglo para el multiplicador
paralelo basado en el Algoritmo de Booth, respectivamente
[6].
Figura 5. Celda de control para: adición / sustracción /
desplazamiento (CASS)
En este caso, las ecuaciones para las salidas Pout y
Cout, son:
POUT = PIN ⊕ (a ⋅ H ) ⊕ (cIN ⋅ H )
cOUT = ( PIN ⊕ D ) ⋅ ( a + c IN ) + a ⋅ cIN
Figura 7. Multiplicador de Baugh–Wooley de 4 bits
2.7 Multiplicador Pipeline
Los multiplicadores paralelos son arreglos iterativos, los
cuales utilizan estructuras basadas en sumadores ripple carry
o carry save, pero sin elementos de almacenamiento [8].
Estos multiplicadores pueden ser implementados
usando la técnica pipeline, es decir se introducen latches o
registros en una apropiada posición dentro del arreglo. En las
Figuras 8 y 9 se muestran las celdas principales del
multiplicador pipeline. Y en la Figura 10, el diagrama de
bloques del multiplicador pipeline de 5 bits [9].
Figura 6. Multiplicador paralelo basado en el Algoritmo de
Booth
2.6 Multiplicador de Baugh-Wooley
El multiplicador de Baugh-Wooley permite realizar la
multiplicación
de
números
con
signo
usando
la
representación en complemento a dos. Este multiplicador es
una adecuación del algoritmo de sumas sucesivas y
desplazamientos que permite realizar la multiplicación de
números con signo [7]. Este tipo de multiplicador esta
basado en arreglos de sumadores de acarreo salvado. El
diagrama de un multiplicador de Baugh–Wooley de 4 bits se
muestra en la Figura 7.
Figura 8. Sumador completo con latch y compuerta AND
Figura 9. Semisumador con latch
Figura 11. Estructura del data path y control path para el
multiplicador secuencial.
2.9 Multiplicador Secuencial basado en el Algoritmo de
Booth
En la Figura 12 se muestra el diagrama del Multiplicador
basado en el Algoritmo de Booth. En este caso el diseño se
realizó usando un circuito secuencial.
Figura 10. Multiplicador pipeline de 5 bits para números
con signo
2.8 Multiplicador Secuencial basado en el algoritmo de
sumas y desplazamientos
El multiplicador secuencial de números binarios sin signo de
N bits, basado en sumas y desplazamientos sucesivos, utiliza
un sumador completo y registros de almacenamiento y/o
desplazamiento, para acumular los productos parciales.
Existen otros multiplicadores secuenciales que utilizan otros
algoritmos para acelerar la multiplicación, como por ejemplo
el Algoritmo de Booth. El diagrama bloques del
multiplicador secuencial se muestra en la Figura 11.
Figura 12. Diagrama ASM del Algoritmo de Booth
3. RESULTADOS DE SIMULACIÓN
UP2 de Altera.
En esta sección, se presentan los resultados de
simulación para los diferentes multiplicadores, en este
caso los parámetros de diseño presentados son:
velocidad o frecuencia máxima, área o número de
elementos lógicos y potencia disipada. El dispositivo
utilizado es la FPGA FLEX10K70RC240-4 de la tarjeta
3.1 Multiplicadores Paralelos:
Los resultados de simulación usando MAX+Plus II, para
optimización en velocidad y área son presentados en las
Tablas 1 y 2, respectivamente.
ALTERA MAX+PLUS II v.10.1
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Mega Función
Ripple Carry
Wallace
Carry Save: Braun
Mega Función
6,71
3,70
5,12
5,41
7,06
854
606
585
590
937
143,02
78,25
92,25
95,9
159,45
Algoritmo de Booth (paralelo)
4,78
926
118,81
Baugh-Wooley
5,48
564
94,02
Sin
signo
Tipo de Multiplicador de 16 bits
Con
signo
Optimización en Velocidad
Tabla 1. Multiplicadores paralelos optimizados en velocidad usando MAX+plus II.
ALTERA MAX+PLUS II v.10.1
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Frecuencia Máxima
(MHz)
Mega Función
Ripple Carry
Wallace
Carry Save: Braun
Mega Función
5,63
3,46
5,14
5,18
5,43
767
534
532
534
871
116,81
70,93
87,41
88
124,44
Algoritmo de Booth paralelo
4,42
841
105,65
Baugh-Wooley
5,10
539
87,68
Sin
signo
Tipo de Multiplicador de 16 bits
Con
signo
Optimización en Área
Tabla 2. Multiplicadores paralelos optimizados en àrea usando MAX+plus II.
Los resultados de simulación usando QUARTUS II versión 3.0, para optimización en velocidad y área, son presentados en
las Tablas 3 y 4, respectivamente.
QUARTUS II versión 3.0
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Mega Función
Ripple Carry
Wallace
Carry Save: Braun
Multiplicador pipeline
Mega Función
11,56
3,68
8,82
9,32
13,21
12,17
583
639
399
403
620
640
161,75
80,32
101,97
106,37
189,03
181,23
Algoritmo de Booth paralelo
8,24
632
133,32
Baugh-Wooley
9,44
385
104,11
Sin signo
Tipo de Multiplicador de 16 bits
Con
signo
Optimización en Velocidad
Tabla 3. Multiplicadores paralelos optimizados en velocidad usando QUARTUS II versión 3.0.
QUARTUS III web edition
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Mega Función
Ripple Carry
Wallace
Carry Save: Braun
Multiplicador pipeline
Mega Función
9,49
5,83
8,66
8,73
10,12
9,15
505
352
350
352
512
573
125,61
74,74
92,91
93,69
132,83
133,97
Algoritmo de Booth paralelo
7,45
554
113,26
Baugh-Wooley
8,59
355
93,26
Sin signo
Tipo de Multiplicador de 16 bits
Con
signo
Optimización en Área
Tabla 4. Multiplicadores paralelos optimizados en àrea usando QUARTUS II versión 3.0.
Los resultados de simulación para los multiplicadores paralelos son mostrados en las Figuras 13a, 13b, 13c, 13d, 13e.
Figura 13a. Simulación detallada del Multiplicador Ripple Carry.
Figura 13b. Simulación detallada del Multiplicador Carry Save.
Figura 13c. Simulación detallada del Multiplicador de Wallace.
Figura 13d. Simulación detallada de la Megafunción.
Figura 13e. Simulación detallada del Multiplicador paralelo basado en el Algoritmo de Booth
3.2 Multiplicadores Secuenciales
Los resultados de simulación usando MAX+Plus II, para optimización de velocidad y área, son presentados en las Tablas 5
y 6, respectivamente.
ALTERA MAX+PLUS II v.10.1
Optimización en Velocidad
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Basado en Sumas y Desplazamientos
15,82
150
80,70
Algoritmo de Booth
6,68
175
58,35
Tipo de Multiplicador de 16 bits sin signo
Tabla 5. Multiplicadores secuenciales optimizados en velocidad usando MAX+plus II.
ALTERA MAX+PLUS II v.10.1
Optimización en Área
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Basado en Sumas y Desplazamientos
13,48
134
70,17
Algoritmo de Booth
6.29
155
54,77
Tipo de Multiplicador de 16 bits sin signo
Tabla 6. Multiplicadores secuenciales optimizados en área usando MAX+plus II.
Los resultados de simulación usando QUARTUS II versión 3.0, para optimización en velocidad y área, son presentados en
las Tablas 7 y 8, respectivamente.
QUARTUS II versión 3.0
Optimización en Velocidad
Tipo de Multiplicador de 16 bits sin signo
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Basado en Sumas y Desplazamientos
24,25
94
78,96
Algoritmo de Booth
10,24
110
57,56
Tabla 7. Multiplicadores secuenciales optimizados en velocidad usando QUARTUS II versión 3.0.
QUARTUS II versión 3.0
Optimización en Área
Tipo de Multiplicador de 16 bits sin signo
Frecuencia Máxima
(MHz)
Elementos
Lógicos (LE)
Potencia Estimada
(mW)
Basado en Sumas y Desplazamientos
23,26
93
76,80
Algoritmo de Booth
10,85
108
58,40
Tabla 8. Multiplicadores secuenciales optimizados en área usando QUARTUS II versión 3.0.
Los resultados de simulación para los multiplicadores secuenciales son mostrados en las Figuras 14a, 14b.
Figura 14a. Simulación detallada del Multiplicador secuencial basado en sumas y desplazamientos
Figura 14b. Simulación detallada del Multiplicador secuencial basado en el Algoritmo de Booth Modificado
Para los multiplicadores secuenciales se presenta un nuevo análisis, el cual es el número máximo de señales de reloj que se
utiliza para una operación de multiplicación (en su peor caso).
4. CONCLUSIONES Y TRABAJO FUTURO
Este trabajo presenta una descripción detallada del
diseño
de
diferentes
arquitecturas
para
los
multiplicadores, los cuales fueron diseñados usando
dispositivos lógicos programables de Altera. Los diseños
fueron
compilados
sobre
el
dispositivo
EPF10K70RC240-4.
Los resultados de simulación obtenidos permiten
presentar las siguientes conclusiones:
• En muchos casos, el uso de la Megafunción
lpm_mult para implementar la multiplicación no es
la mas adecuada, especialmente en donde el
compromiso de área y consumo de potencia son
criterios de diseño primordiales.
• Desde las simulaciones para cada multiplicador se
puede observar los efectos de retardo en el
resultado, al cambiar algún operando. En este
•
contexto, la frecuencia en la que los datos son
confiables, se toma a partir de la peor respuesta del
sistema, después de haber simulado y verificado los
tiempos con los resultados de la Matriz de Retardos
que entrega Max+Plus II y los análisis de tiempos
en Quartus II versión 3.0.
El multiplicador Ripple Carry es bastante fácil de
comprender, pero no es práctico, ya que presenta el
menor rendimiento en comparación con los demás
multiplicadores paralelos, diseñados en este artículo.
Sin embargo, este presenta el menor consumo de
potencia promedio, y en algunas aplicaciones este
parámetro puede ser primordial para sistemas
embebidos en donde la frecuencia máxima no es
determinante.
•
•
•
•
•
El software Quartus II versión 3.0, la herramienta de
Altera, posee mejor capacidad de síntesis en cuanto
a los factores de frecuencia máxima y número de
elementos lógicos utilizados (área) que el software
Max+Plus II, llagando a mejorar en casi dos veces
el rendimiento de cada multiplicador.
El
multiplicador
de
Baugh-Wooley
y
el
multiplicador basado en el algoritmo de Booth,
permiten realizar la multiplicación de números
positivos y negativos, y además son una buena
alternativa para sistemas de bajo consumo de
potencia y alta velocidad.
Los multiplicadores secuenciales, presentan una
ventaja con respecto a los paralelos debido a que
utilizan poca área o elementos lógicos, y por lo tanto
su potencia promedio disipada también es pequeña.
Sin embargo, el resultado de la multiplicación es
obtenido después de un número entero de ciclos de
reloj.
El multiplicador pipeline presenta el mejor
desempeño desde el punto de vista de velocidad. Sin
embargo, presenta la desventaja que ocupa
demasiada área, pero es una muy buena alternativa.
Se
presentan
algunas
arquitecturas
de
multiplicadores cuyos resultados muestran que son
una opción viable para implementarlos en sistemas
en un solo chip, con bajo consumo de potencia y
que justifican la escasa perdida de velocidad con
respecto a la megafuncion lpm_mult.
5. AGRADECIMIENTOS
Este trabajo ha sido patrocinado por Altera Corporation
a través del Programa Universitario. Los autores dan
especial agradecimientos a Mrs. Ralene Marcoccia de
Altera Corporation.
6.
BIBLIOGRAFÍA
[1] D. Gajski, “Principios de Diseño Digital”,
Prentice Hall, 1997.
[2] M. Davio, “Digital Systems with Algorithm
Implementation”, John Wiley & Sons, 1983.
[3] K.C. Chang, “Digital Systems Design with
VHDL and Synthesis: An Integrated
[4] Approach”, IEEE Computer Society, 1999.
[5] D. Pucknell, K. Eshraghian, “Basic VLSI
Design”, Prentice Hall, 1994.
[6] A. Tanenbaum, “Organización de
Computadores un Enfoque Estructurado”,
Prentice Hall, 1992.
[7] W. Stallings, “Organización y Arquitectura
de Computadores”, Prentice Hall, 1999.
[8] V.C. Hamacher, Z.G. Vranesic y S.G.
Zaky, “Organización de Computadoras”, Mc
Graw Hill, 1987.
[9] D.A. Paterson y S.L. Hennessy,
Computer Organization and Design: the
Hardware / Software Interface”, Morgan
Kaufmann Publishers, 1998.
[10] I. Koren, “Computer Arithmetic Algorithms”, A.K. Peters,
2002.
[11] B. Parhami, “Computer Arithmetic:
Algorithms and Hardware Design”, Oxford