Parallel-FST: aceleración de algoritmos de selección de características mediante computación paralela

Abstract

[Resumo] Na actualidade estase a producir un auxe da produción e consumo de grandes cantidades de información (big data), que deben procesarse e prepararse para o seu posterior uso. Entre as ferramentas que se utilizan para analizar estes datos atópanse as de aprendizaxe máquina (machine learning), o que constitúe outro campo de investigación que gañou importancia nos últimos anos. A pesar dos seus bos resultados, as técnicas de aprendizaxe automática contan cun custo computacional alto, que se incrementa notablemente ao aumentar a cantidade de datos a procesar. Para reducir a dimensionalidade destes datos, existen algoritmos de selección de características que, a través de modelos matemáticos, son capaces de eliminar información redundante e innecesaria. Porén, a selección de características tamén é un proceso custoso, pero que pode acelerarse adaptando os algoritmos e técnicas xa existentes para o seu uso en sistemas de computación paralela (coñecidos como HPC polas súas siglas en inglés). Ao longo dos últimos anos xurdiron moitos traballos de investigación centrados no desenvolvemento de diferentes métodos de selección de características, cada un aplicando uns criterios de cara á devandita selección. Polo xeral, estes criterios deben tentar maximizar a relevancia das características seleccionadas e minimizar a redundancia entre as mesmas, de forma que o subconxunto escollido represente da mellor forma posible ao dataset orixinal. Tamén existen estudos que traballan con varios destes métodos para atopar o grao de conformidade entre os mesmos, para buscar similitudes a nivel de estrutura ou con intención de determinar cal presenta un mellor comportamento en termos de precisión, estabilidade e flexibilidade ante datasets de certas propiedades. Para este tipo de estudos moitas veces é necesario o desenvolvemento de librarías que conteñan os métodos de selección de características a estudar, de forma que se poidan comparar os resultados. Este é o caso de FEAST, unha libraría que conta con oito métodos de selección de características baseada en información mutua. Neste Traballo Fin de Grao desenvolveuse unha optimización de FEAST con técnicas paralelas, adaptando os seus métodos para que poidan ser executados e aproveiten as vantaxes dos sistemas HPC. As paralelizacións implementadas desenvolvéronse aplicando unha distribución da carga de traballo entre elementos de procesado. Dado que os sistemas HPC adoitan ser sistemas multinodo con nodos multinúcleo, esta nova versión aproveita as posibilidades que achegan ambos cunha aproximación híbrida baseada en MPI e tecnoloxías multifío. A estratexia aplicada en ambos niveis foi a descomposición de dominio, i.e. a distribución dos datos cos que traballa o programa para que cada elemento de procesado realice os cálculos sobre un anaco diferente. Deste xeito conseguiuse, por unha parte, reducir o tempo de cómputo; e por outra, posibilitar a análise de datasets de gran tamaño que exceden as limitacións de memoria dos sistemas habituais. As probas de rendemento realizáronse nun clúster de 16 nodos, con 64GB de memoria e 16 núcleos por nodo (256 núcleos en total). Os resultados obtidos foron moi satisfactorios, xa que se acadaron unhas aceleracións de ata 229x para catro datasets representativos. A maiores, conseguiuse executar cada algoritmo cun dataset de 512GB de tamaño, o que non sería posible nun único nodo.

[Abstract] Currently, there is a boom in the production and consumption of large amounts of information (big data), which must be processed and prepared for later use. Machine learning techniques are among the tools used to analyze this data. Therefore, it is another field of research that has gained importance in recent years. Despite their good results, machine learning techniques have a high computational cost, which is significantly increased as the amount of data to be processed grows. To reduce the dimensionality of this data, there are feature selection algorithms able to remove redundant and unnecessary information with the use of mathematical models. However, feature selection is also an expensive process, but it can be accelerated by adapting existing algorithms and techniques to be run in high performance computing systems (HPC). In recent years, many research projects have been focused on the development of different methods for feature selection, which apply some specific criteria to this selection. Usually, these criteria should try to maximize the relevance of the selected features and minimize the redundancy between them, so that the chosen subset represents the original data set in the best possible way. There are also studies that take into account several of these methods to find the degree of conformity between them, to look for similarities at the structure level or to determine which one performs best in terms of precision, stability and flexibility when applied to data sets of certain properties. For this kind of research, the development of libraries with several feature selection methods to be studied is often necessary in order to compare their results. This is the case of FEAST, a library that presents eight feature selection methods based on mutual information. In this work a parallelization of the FEAST library has been developed, adapting its methods so that they can be executed and take advantage of HPC systems. The implemented parallelizations were developed by applying a workload distribution among processing elements. Since HPC systems are often multinode systems with multicore nodes, this new version takes advantage of the possibilities that both offer with a hybrid approach based on MPI and multithreading technologies. The strategy applied at both levels was the domain decomposition, that is, the distribution of the data used in the program, so that each processing element performs the calculations on a different part. This way, it was possible, on the one hand, to reduce execution times; and, on the other hand, to allow the analysis of large data sets that exceed memory limitations of common systems. Performance tests were carried out on a 16-node cluster with 64GB of memory and 16 cores per node (256 total cores). The obtained results are very satisfactory, since accelerations of up to 229x were achieved for four representative data sets. In addition, every algorithm was able to analyze a 512GB dataset, which would not have been possible on a single node.