Un nuevo procedimiento para la minimización and-exor y su paralelización en sistemas de memoria didtribuida

Abstract

En los ultimos años ha surgido un gran interes por la realizacion de circuitos logicos utilizando sintesis and-

exor debido a que, en general, este tipo de circuitos

requieren menor numero de puertas que los and-or para su

realizacion, y a una serie de trabajos que indican que el

test de estructuras and-exor resulta mas simple. este

hecho es especialmente relevante en el diseño de circuitos

integrados vlsi por la gran importancia y complejidad que

presenta el proceso del test en tales circuitos, y en

implementaciones con fpgas, donde se consigue un gran

ahorro de puertas frente a la sintesis and-or. las

interesantes propiedades de la logica and-exor son

conocidas desde hace cierto tiempo, pero no han podido ser

aprovechadas hasta la actualidad por dos inconvenientes

que presentaba este tipo de sintesis: a) la puerta exor

requeria mayor area que la or para su integracion. b) no

existia un procedimiento de minimizacion and-exor que

proporcionara resultados satisfactorios en un tiempo

razonable. la cuestion a) se ha resuelto con los avances

en la tecnologia de fabricacion de circuitos integrados, y

queda totalmente eliminada si se utilizan dispositivos

programables del tipo pla o fpga. el inconveniente b) no

se encuentra resuelto, aunque la disponibilidad de

ordenadores con mayor capacidad de procesamiento y memoria

esta permitiendo grandes avances en este terreno. en esta

tesis se desarrolla una solucion a la cuestion b) basada

en un nuevo planteamiento de la minimizacion and-exor como

problema de optimizacion combinatoria. el procedimiento de

minimizacion desarrollado, a diferencia de los demas que

aparecen en la literatura, utiliza un algoritmo no

determinista como es el enfriamiento simulado para

controlar la aplicacion de un conjunto de reglas de

reescritura sobre las funciones a minimizar. la

utilizacion de un metodo no determinista permite decidir

que calidad de la solucion se va a obtener segun el tiempo

de ejecucion que se este dispuesto a esperar. un

procedimiento determinista no admite esta posibilidad, y

no puede mejorarse la solucion mediante un aumento del

tiempo de ejecucion. el procedimiento desarrollado en la

memoria, denominado rrmin2, permite la minimizacion and-

exor de funciones completamente o incompletamente

especificadas, con una o varias salidas. se han realizado

pruebas experimentales, comparando el procedimiento con

los metodos mas importantes que aparecen en la literatura;

obteniendose unas prestaciones mucho mejores por parte de

rrmin2. por otra parte, se ha tratado de aprovechar la

disponibilidad actual de sistemas multiprocesador o, en su

defecto, de una serie de ordenadores conectados en red, de

la que se dispone en cualquier departamento dedicado al

diseño de sistemas digitales y/o circuitos integrados con

el objetivo de reducir los tiempos de ejecucion. para ello

se ha procedido a paralelizar el procedimiento

desarrollado usando el software de dominio publico pvm

(parallel virtual machine), muy extendido y utilizado por

una gran cantidad de plataformas multiprocesador, y que

ademas permite de forma sencilla utilizar una red de

estaciones de trabajo como un sistema multiprocesador de

memoria distribuida