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
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
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%.
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%.