DOI: 10.5176/978-981-08-7656-2 A-16
Authors: Bernd Steinbach, Christian Posthoff
Abstract: This paper aims at better possibilities to solve problems with exponential complexity. Our special focus is on the combination of using four cores of a standard PC together with better models in the application domain. As 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 this problem, explain the classical solution, and evaluate it by using a benchmark set. Subsequently we study
sources of parallelism in the application domain and explore sources of improvements given by the parallel utilization of the available four cores of a PC. Starting with a uniform division 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 in the application domain and in the algorithmic domain lead to a
remarkable speedup and an overall improvement factor of more than 35 millions in comparison to the improved basic approach.
Keywords: covering; XBOOLE; ternary vector; parallel; message
passing interface; unate SAT problems
Updating...