A Hybrid CPU-GPU-MIC Algorithm for the Hitting Set Problem - Carastan-Santos, Danilo; C. Martins-Jr, David; C. S. Rozante, Luiz; W. Song, Siang; Y. de Camargo, Raphael (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2017: Anais do XVIII Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2017.250, 2017)
We present a hybrid exact algorithm for the Hitting Set Problem (HSP) for highly heterogeneous CPU-GPU-MIC platforms. With several techniques that permit an efficient exploitation of each architecture, low communication cost and effective load balancing, we were able to solve large HSP instances in reasonable time, achieving good performance and scalability. We obtained speedups of up to 25.32 in comparison with using two six-core CPUs and exact HSP solutions for instances with tens of thousands of variables in less than 5 hours. These results reinforce the statement that heterogeneous clusters of CPUs, GPUs and MICs can be used efficiently for high-performance computing.