Reglas de multiplicación del árbol de Wallace

Los pares de 3 se envían a un sumador carry-save, que toma una suma de 3 entradas y lo reduce a una suma de 2 entradas (x + y + x = > c + s). El tiempo de propagación de un sumador de acarreo-guardado es constante, mientras que el tiempo de propagación de un sumador de entrada tradicional es proporcional al ancho de los operandos. También puede usar un medio sumador, que realiza la reducción (a + b = > 2 * c + s) en tiempo constante.

Para que el multiplicador sea lo más rápido posible, desea que las capas usen solo carry-save y half-adders, así como que la adición de las 2 entradas finales tenga el ancho más bajo posible. De esta manera, todas las capas se desempeñan en tiempo constante, y la última tiene el menor tiempo de propagación posible.

Debería encontrar que si reduce los pares de 2 en las primeras capas con medias sumadoras, no guardará ninguna capa ni reducirá el ancho de la adición final, por lo que la multiplicación no será más rápida.

Estoy de acuerdo con usted en que la descripción del procedimiento de reducción en la página de Wikipedia es inconsistente con el procedimiento de reducción utilizado en la imagen. Lo curioso es que las diferentes fuentes parecen tener una idea diferente de lo que es exactamente un árbol de Wallace. Parece que no hay una descripción rigurosa de la fase de reducción de Wallace.

Durante la conferencia, aprendí a reducir los árboles Wallace de la forma en que se explica en Wikipedia: la forma "codiciosa" (reduce tanto como puedas). Pero también encontré este sitio, donde usan un esquema de reducción similar como en la imagen de su pregunta (de hecho, debe ser el mismo, pero la imagen de Wikipedia contiene un error , en el diagrama del cuarto punto, la séptima fila de la derecha contiene un punto demasiados), y considérelo como "reducción de Wallace tradicional". Por lo tanto, hay al menos dos esquemas de reducción que tienen el nombre de Wallace (y los muchos documentos que se refieren a los árboles de Wallace o los multiplicadores de Wallace sugieren de alguna manera que hay muchos más).

En tales casos de confusión, a menudo es útil buscar papel original , Como suele ayudar a entender el contexto histórico del término. No es muy difícil de leer, y es, en algunos puntos, menos formal de lo que uno podría esperar (lo que podría ser una fuente de confusión).

Al leer el documento, queda claro que los árboles de Wallace no fueron diseñados teniendo en cuenta los diagramas de puntos. Una vez que uno ha adaptado este concepto, resulta muy fácil mejorar la reducción propuesta por Christopher Wallace. Mi conjetura es que la gente simplemente usó el término 'árbol de Wallace' para referirse a estos esquemas mejorados también. La riqueza de papeles y diseños distintos que se encuentran al buscar en Google el 'multiplicador del árbol de Wallace' parece indicar que el término se usa de manera bastante relajada.

Ahora, echemos un vistazo al diagrama de puntos del árbol de Wallace en tu pregunta. En comparación con un árbol Dadda, se destacan dos cosas:

1. El árbol no tiene forma de triángulo, sino más bien como un diamante o paralelogramo
2. Parece que hay alguna división de filas en grupos de tres, y los sumadores no cruzan los límites. Después de un paso de reducción, los puntos se mantienen dentro de grupos de dos filas.

Para entender esto, es útil tener en cuenta que en el documento original, Christopher Wallace no usa diagramas de puntos. En lugar de eso, describe la estrategia de manera general como "agrupar tres números y reducirlos a dos usando sumadores". La forma en que construye árboles es tomar varios bits con el mismo peso y construir un árbol de aquellos que usan solo sumadores completos. Esto se ilustra en la figura 1 del documento, en la que se agregan 39 operandos: para agregar 39 números de n bits , necesitaría n de estos árboles (más alguna estructura para manejar los bits de acarreo, lo que se podría hacer con versiones simplificadas de este árbol, ya que implica agregar menos de 39 bits: aquí es donde los diagramas de puntos son útiles). p>

Entonces, Chris Wallace no estaba pensando en los diagramas de puntos cuando ideó su método (lo cual es una razón por la que es una forma bastante ineficiente de reducir números en algunos aspectos). Estaba pensando en términos de números (más específicamente, números de múltiples bits).

Cuando lo piensas, esto explica el diseño del diagrama de puntos. Las agrupaciones de filas son grupos de tres números que se suman. Desde esta perspectiva, no tiene mucho sentido mezclar bits de los números. Este método "tradicional" de reducción de Wallace es realmente trivial cuando piensas en las filas de puntos como números de múltiples bits, y simplemente reduces cada grupo de tres números a dos números.

página del generador de CNF de Amr Sabry solo cita a link a la página de inicio de Chris Wallace antes de describir el circuito del árbol de Wallace:

  

En el circuito del árbol de Wallace, las filas (con los cambios apropiados) son   añadido en grupos de tres para producir sumas y acarreos. Las sumas y   los acarreos (con los turnos apropiados) se vuelven a agregar en grupos de tres ,   y esto se repite hasta que solo hay una suma y una carga. Entonces un   se utiliza un sumador especial para sumar la suma final y el arrastre final. los   los productos de cualquier fila deben pasar solo por un número logarítmico de   Adders antes de que lleguen al sumador especial.   (énfasis añadido)

No hay mención de medias sumas. Esto es consistente con Wallace ' papel original , como señala Ruben.

Los semidirigidos parecen ser una discreción del diseñador del circuito y (a diferencia del texto de Wikipedia) no deben ser aplicados con avidez.

Jonathan D. explicó la motivación para no utilizar un enfoque codicioso.

La adición indiscriminada de cada grupo de 2 o 3 cables aumentará innecesariamente el ancho de la adición final, y en realidad gastará más puertas antes de eso (en las 'reducciones' adicionales) solo para hacerlo.

Pero esto no explica ninguna regla o heurística para elegir cuándo agregar un grupo o cuándo no.

La ilustración de Wiki muestra la discriminación por capa. Por ejemplo, en la 3ª capa, a los dos grupos de cables 3 de la izquierda solo se les da un medio sumador cada uno, mientras que en la siguiente capa todos grupos de 3 cables se dan agregados completos:

SeríaútiltenerunaheurísticaparagenerarunárboldeWallaceconmediassumasprogramáticamente.Nosoyingeniero,asíquenosésilarespuestaesobviaparalosingenieros(?).Perolomáscercaquepudediseñarproduceunresultadofinalsimilaral ilustración de Wikipedia .

  

Aplicar las reglas con avidez siempre que hacerlo no incremente la   número de cables de cualquier peso cuyo número de cables sea 1 o 2,    a menos que :

     

1. Es necesario hacerlo para reducir un peso cuyo número de cables es mayor que 2 (incluido el acarreo), o
  
2. aumenta el número de cables de peso mínimo consecutivos que pasan directamente a la salida (es decir, la cadena de "puntos individuales" en el lado derecho).
  

Esto produce diferentes pasos en comparación con la ilustración, pero el resultado final es similar:

• transiciones de 4 capas (iguales)
• adición final de 11 bits (igual)
• paso de lado bajo de 6 bits (vs Wiki de 5 bits)
• Salida final de 18 bits (vs Wiki de 17 bits)

Ejemplo :

  •••••••••••••••
   •••••••••••••
    •••••••••••
     •••••••••
      •••••••
       •••••
        •••
         •
-----------------
  •••••••••••••••
  •••••••••••••
     •••••••••
     •••••••
        •••
        •
-----------------
 ••••••••••••••••
  ••••••••••••
     •••••••
       •••
-----------------
 ••••••••••••••••
 •••••••••••
       •••
-----------------
•••••••••••••••••
 ••••••••••

Actualizaré esto si puedo encontrar una regla mejor.