Parallel solving model for quantified boolean formula based on machine learning

doi:10.1007/s11771-013-1839-6

Parallel solving model for quantified boolean formula based on machine learning

2013-11-13

0

PRE

AI

DOI：10.1007/s11771-013-1839-6

原文链接

原文求助

摘要

En 中文

A new parallel architecture for quantified boolean formula (QBF) solving was proposed, and the prediction model based on machine learning technology was proposed for how sharing knowledge affects the solving performance in QBF parallel solving system, and the experimental evaluation scheme was also designed. It shows that the characterization factor of clause and cube influence the solving performance markedly in our experiment. At the same time, the heuristic machine learning algorithm was applied, support vector machine was chosen to predict the performance of QBF parallel solving system based on clause sharing and cube sharing. The relative error of accuracy for prediction can be controlled in a reasonable range of 20%-30%. The results show the important and complex role that knowledge sharing plays in any modern parallel solver. It shows that the parallel solver with machine learning reduces the quantity of knowledge sharing about 30% and saving computational resource but does not reduce the performance of solving system.

Keyword:

machine learning

quantified boolean formula

parallel solving

knowledge sharing

feature extraction

performance prediction

Parallel solving model for quantified boolean formula based on machine learning

摘要

期刊

机构