Exploiting CPU Bit Parallel Operations to Improve Efficiency in Search

It is the authors´ belief that the ability of processors to compute bit parallel operations should have a right to exist as an optimization discipline, rather than a state-of- the-art technique. This paper is a step forward in this direction analysing a number of key issues related to bit model design and implementation of search problems. Building efficient search algorithms optimized at bit level is a difficult task It requires not only a good implementation but also an adequate model so as to make bitwise operations meaningful, and only by addressing design and implementation globally an improvement in efficiency can be obtained. On the other hand, we have proved in this paper that the improvement can conceivably be exponential on the size of the CPU register for problems in NP. This global approach has been used to implement the fastest complete algorithm, to the best of our knowledge, for the maximum clique problem, an important NP-hard combinatorial problem from the graph domain. Our solver clearly outperforms other existing algorithms for hard instances, in some cases by nearly an order of magnitude.