Parallel Solution of Covering Problems Super-Linear Speedup on a Small Set of Cores

Abstract

This paper aims at better possibilities to solve
problems of exponential complexity. Our special focus is the
combination of the computational power of four cores of a
standard PC with better approaches in the application domain.
As the main example we selected the unate covering problem
which must be solved, among others, in the process of circuit
synthesis and for graph-covering (domination) problems.
We introduce into the wide field of problems that can be
solved using Boolean models. We explain the models and the
classic solutions, and discuss the results of a selected model by
using a benchmark set. Subsequently we study sources of parallelism
in the application domain and explore improvements
given by the parallel utilization of the available four cores of
a PC. Starting with a uniform splitting of the problem, we
suggest improvements by means of an adaptive division and
an intelligent master. Our experimental results confirm that
the combination of improvements of the application models
and of the algorithmic domain leads to a remarkable speedup
and an overall improvement factor of more than 35 millions
in comparison with the improved basic approach.