logo móvil
Contáctanos

Un eficaz solucionador de FPGA en distribución de probabilidad y preprocesamiento

Autores: Ma, Kefan; Xiao, Liquan; Zhang, Jianmin

Idioma: Inglés

Editor: MDPI

Año: 2019

Descargar PDF

Acceso abierto

Artículo científico
2019

Un eficaz solucionador de FPGA en distribución de probabilidad y preprocesamiento


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería Eléctrica y Electrónica

Palabras clave

Satisfacibilidad booleana
Algoritmo
Probsat+
Solucionador de hardware
Distribución de probabilidad
Búsqueda centralizada

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 26

Citaciones: Sin citaciones


Descripción
El problema de satisfacción booleana (SAT) es el problema clave en la teoría y aplicación de la computación. Se introduce un algoritmo novedoso para implementar un solucionador de hardware SLS llamado probSAT+. El algoritmo no tiene heurísticas complejas, sino que depende únicamente de los conceptos de tecnología de preprocesamiento, distribución de probabilidades y búsqueda centralizada. Al restringir las asignaciones iniciales de las variables, se redujo el número de variables invertidas mientras el solucionador encuentra una solución. Además, el algoritmo ya no adopta algunas decisiones no continuas de si-entonces-sino que depende de una única función continua. La probabilidad de inversión no se obtiene mediante cálculos complejos, sino que se selecciona mediante tablas de búsqueda, lo que mejora efectivamente el rendimiento del solucionador. Hasta donde sabemos, la estrategia de selección de distribución de probabilidades descrita por el lenguaje de descripción de hardware es adoptada por primera vez por un solucionador de SAT de hardware, lo que puede ser fácilmente trasplantado a cualquier dispositivo lógico programable. Los resultados experimentales muestran que el solucionador probSAT+ es generalmente inferior al solucionador de software avanzado en el número de inversiones (hasta 9.8), y la aceleración es aproximadamente 2.6 veces con un solo hilo, lo que muestra que el probSAT+ tiene mejores resultados con menos veces de inversión de variables cuando se puede encontrar una solución. Además, la tasa de éxito del solucionador al encontrar una solución al problema en un tiempo adecuado es del 100%.

Otros recursos que podrían interesarte

Temas Virtualpro