A Hybrid CPU-GPU-MIC Algorithm for the Hitting Set Problem
Resumo
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.
Referências
Andrade, G., Ferreira, R., Teodoro, G., Rocha, L., Saltz, J. H., and Kurc, T. (2014). Efficient execution of microscopy image analysis on CPU, GPU, and MIC equipped cluster systems. In Computer Architecture and High Performance Computing (SBACPAD), 2014 IEEE 26th International Symposium on, pages 89–96. IEEE.
Carastan-Santos, D., de Camargo, R. Y., Martins, D. C., Song, S. W., and Rozante, L. C. (2017). Finding exact hitting set solutions for systems biology applications using heterogeneous gpu clusters. Future Generation Computer Systems, 67:418–429.
Carastan-Santos, D., Yokoingawa De Camargo, R., Correa Martins, D., Song, S. W., Silva Rozante, L., and Ferreira Borelli, F. (2015). A multi-gpu hitting set algorithm for grns inference. In Cluster, Cloud and Grid Computing (CCGrid), 2015 15th IEEE/ACM International Symposium on, pages 313–322.
Cardoso, N. and Abreu, R. (2013). Mhs2: A map-reduce heuristic-driven minimal hitting set search algorithm. In International Conference on Multicore Software Engineering, Performance, and Tools, pages 25–36. Springer.
Cendic, B. L. (2014). A genetic algorithm for the minimum hitting set. Scientific Publications of the State University of Novi Pazar, 6(2):107.
Duran, A. and Klemm, M. (2012). The intel0R many integrated core architecture. In High Performance Computing and Simulation (HPCS), 2012 International Conference on, pages 365–366. IEEE.
Gainer-Dewar, A. and Vera-Licona, P. (2017). The minimal hitting set generation problem: algorithms and computation. SIAM Journal on Discrete Mathematics, 31(1):63– 100.
Garey, M. R. and Johnson, D. S. (1999). Computers and Intractability - A guide to the Theory of NP-completeness. W. H. Freeman and Company.
Hochbaum, D. S. (1997). Aproximation Algorithms for NP-Hard Problems. PWS Publishi ng Company.
Hvidsten, T. R., Lægreid, A., and Komorowski, J. (2003). Learning rule-based models of biological process from gene expression time profiles using gene ontology. Bioinformatics, 19(9):1116–1123.
Ideker, T. E., Thorsson, V., and Karp, R. M. (2000). Discovery of regulatory interactions through perturbation: inference and experimental design. Pacific symposium on biocomputing, 5:302–313.
Jeffers, J. and Reinders, J. (2013). Intel Xeon Phi coprocessor high-performance programming. Newnes.
Knuth, D. E. (2005). The Art of Computer Programming, Fascicle 3: Generating All Combinations and Partitions, volume 4. Addison-Wesley, Reading.
Kolman, P. and Walen, T. (2007). Reversal distance for strings with duplicates: Linear time approximation using hitting set. The Electronic Journal of Combinatorics, 14(1):11.
Murakami, K. and Uno, T. (2014). Efficient algorithms for dualizing large-scale hypergraphs. Discrete Applied Mathematics, 170:83–94.
NVIDIA (2016). Maxwell: The Most Advanced CUDA GPU Ever Made. https://devblogs.nvidia.com/parallelforall/ maxwell-most-advanced-cuda-gpu-ever-made/. Online; last access 18 july 2016.
Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., and Phillips, J. C. (2008). GPU computing. Proceedings of the IEEE, 96(5):879–899.
Pearson, W. R., Robins, G., Wrege, D. E., and Zhang, T. (1996). On the primer selection problem in polymerase chain reaction experiments. Discrete Applied Mathematics, 71(1):231–246.
Reza, H., Aguilar, M., and Jalal, S. F. (2015). Regression testing of gpu/mic systems for hpcc. In Proceedings of the 2015 International Workshop on Software Engineering for High Performance Computing in Science, pages 30–37. IEEE Press.
Ruchkys, D. P. and Song, S. W. (2003). A parallel solution to infer genetic network architectures in gene expression analysis. International Journal of High Performance Computing Applications, 17(2):163–172.
Shi, L. and Cai, X. (2010). An exact fast algorithm for minimum hitting set. Int. Joint Conference on Computational Science and Optimization, 1:64–67.
Sîrbu, A. and Babaoglu, O. (2016). Power consumption modeling and prediction in a hybrid cpu-gpu-mic supercomputer. In European Conference on Parallel Processing, pages 117–130. Springer.
Wolfe, N., Liu, T., Carothers, C., and Xu, X. G. (2014). Heterogeneous concurrent execution of monte carlo photon transport on cpu, gpu and mic. In Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms, pages 49–52. IEEE Press.
Carastan-Santos, D., de Camargo, R. Y., Martins, D. C., Song, S. W., and Rozante, L. C. (2017). Finding exact hitting set solutions for systems biology applications using heterogeneous gpu clusters. Future Generation Computer Systems, 67:418–429.
Carastan-Santos, D., Yokoingawa De Camargo, R., Correa Martins, D., Song, S. W., Silva Rozante, L., and Ferreira Borelli, F. (2015). A multi-gpu hitting set algorithm for grns inference. In Cluster, Cloud and Grid Computing (CCGrid), 2015 15th IEEE/ACM International Symposium on, pages 313–322.
Cardoso, N. and Abreu, R. (2013). Mhs2: A map-reduce heuristic-driven minimal hitting set search algorithm. In International Conference on Multicore Software Engineering, Performance, and Tools, pages 25–36. Springer.
Cendic, B. L. (2014). A genetic algorithm for the minimum hitting set. Scientific Publications of the State University of Novi Pazar, 6(2):107.
Duran, A. and Klemm, M. (2012). The intel0R many integrated core architecture. In High Performance Computing and Simulation (HPCS), 2012 International Conference on, pages 365–366. IEEE.
Gainer-Dewar, A. and Vera-Licona, P. (2017). The minimal hitting set generation problem: algorithms and computation. SIAM Journal on Discrete Mathematics, 31(1):63– 100.
Garey, M. R. and Johnson, D. S. (1999). Computers and Intractability - A guide to the Theory of NP-completeness. W. H. Freeman and Company.
Hochbaum, D. S. (1997). Aproximation Algorithms for NP-Hard Problems. PWS Publishi ng Company.
Hvidsten, T. R., Lægreid, A., and Komorowski, J. (2003). Learning rule-based models of biological process from gene expression time profiles using gene ontology. Bioinformatics, 19(9):1116–1123.
Ideker, T. E., Thorsson, V., and Karp, R. M. (2000). Discovery of regulatory interactions through perturbation: inference and experimental design. Pacific symposium on biocomputing, 5:302–313.
Jeffers, J. and Reinders, J. (2013). Intel Xeon Phi coprocessor high-performance programming. Newnes.
Knuth, D. E. (2005). The Art of Computer Programming, Fascicle 3: Generating All Combinations and Partitions, volume 4. Addison-Wesley, Reading.
Kolman, P. and Walen, T. (2007). Reversal distance for strings with duplicates: Linear time approximation using hitting set. The Electronic Journal of Combinatorics, 14(1):11.
Murakami, K. and Uno, T. (2014). Efficient algorithms for dualizing large-scale hypergraphs. Discrete Applied Mathematics, 170:83–94.
NVIDIA (2016). Maxwell: The Most Advanced CUDA GPU Ever Made. https://devblogs.nvidia.com/parallelforall/ maxwell-most-advanced-cuda-gpu-ever-made/. Online; last access 18 july 2016.
Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., and Phillips, J. C. (2008). GPU computing. Proceedings of the IEEE, 96(5):879–899.
Pearson, W. R., Robins, G., Wrege, D. E., and Zhang, T. (1996). On the primer selection problem in polymerase chain reaction experiments. Discrete Applied Mathematics, 71(1):231–246.
Reza, H., Aguilar, M., and Jalal, S. F. (2015). Regression testing of gpu/mic systems for hpcc. In Proceedings of the 2015 International Workshop on Software Engineering for High Performance Computing in Science, pages 30–37. IEEE Press.
Ruchkys, D. P. and Song, S. W. (2003). A parallel solution to infer genetic network architectures in gene expression analysis. International Journal of High Performance Computing Applications, 17(2):163–172.
Shi, L. and Cai, X. (2010). An exact fast algorithm for minimum hitting set. Int. Joint Conference on Computational Science and Optimization, 1:64–67.
Sîrbu, A. and Babaoglu, O. (2016). Power consumption modeling and prediction in a hybrid cpu-gpu-mic supercomputer. In European Conference on Parallel Processing, pages 117–130. Springer.
Wolfe, N., Liu, T., Carothers, C., and Xu, X. G. (2014). Heterogeneous concurrent execution of monte carlo photon transport on cpu, gpu and mic. In Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms, pages 49–52. IEEE Press.
Publicado
17/10/2017
Como Citar
CARASTAN-SANTOS, Danilo; C. MARTINS-JR, David; C. S. ROZANTE, Luiz; W. SONG, Siang; Y. DE CAMARGO, Raphael.
A Hybrid CPU-GPU-MIC Algorithm for the Hitting Set Problem. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 18. , 2017, Campinas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 196-207.
DOI: https://doi.org/10.5753/wscad.2017.250.
