Un Algoritmo para Multiplicación Rápida y Suma de Dos o Más Entradas y su Implementación para Computación In-Situ

Ponente(s): Juan Pablo Ramirez Ramirez

Esta platica expande en el tema de una sesión del área de Ciencias de Computación que se presentó en el CNM 55 el año pasado. En aquella sesion se propone un Sumador Rápido, Simple y Lineal en la forma de una máquina de estados que realiza la suma de dos entradas, en promedio, en tiempo logarítmico. Esta plática se centrará en una versión modificada de dicho algoritmo, pero que permite reducir la suma de 2^n sumandos a 'n' sumandos donde la complejidad de tiempo es 'log(2)+log(3)+...+log(n)' en el peor casp. Vemos que este método se puede aplicar para un número arbitrario de sumandos y analizamos los casos en que se pueden esperar ventajas respecto a otras implementaciones de multiplicación. También se analiza su aplicación y comportamiento para la multiplicación rápida de dos entradas, a nivel Software y Hardware. El diseño en HW es escalable y la lógica se puede pensar en una implementación In-Situ (computacion-en-memoria o computación local) ya que es una malla rectangular de Half-Adders con conexiones horizontales y verticales entre sí, y colocados directamente arriba del elemento de memoria correspondiente al sumando y bit significativo donde se guardará la salida. Por último vemos cuales serían las ventajas de este circuito en el pipeline para la multiplicación de matrices.