Profiling and optimizing K-means algorithms in a beowulf cluster environment

Thibodeau, Éric (2009). Profiling and optimizing K-means algorithms in a beowulf cluster environment. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (56MB) | Prévisualisation
Prévisualisation	PDF Télécharger (8MB) | Prévisualisation

Résumé

The K-means algorithm is a well known statistical agglomeration algorithm used to sort a database of unlabeled items into K groups. As part of the fitness function of an Evolutionary Algorithm (EA), the optimization of the K-means algorithm has become a point of great interest. Although many approaches have been proposed for its parallelization and optimization, very few address the question of scalability and efficiency. In most cases, the description of the execution environment remains opaque and precise profiles of the program are mostly absent. Performance and efficiency issues are quickly relegated to communicafion issues.

We address these deficiencies by presenting a detailed description of two parallel environments, the Beowulf style clusters and the Symmetric Multi-Processors (SMP) parallel machines. A mixture of theoretical and empirical models were used to characterize these environments and set baseline expectations pertaining to the K-means algorithm. Due to the necessity of a multidisciplinary expertise, a detailed use of Tuning and Analysis Utilities (TAU) is provided to ease the parallel performance profiling task. Coupled with the high precision counter interface provided by Performance Application Programming Interface (PAPI), we present a grey box method by which a parallel master-slave implementation of the K-means is evolved into a highly efficient island version of itself. Communications and computational optimization were guided by prior theoretical and empirical models of the parallel execution environment.

Our work has revealed that there is much more to parallel processing than the simple balance between computation and communications. We have brought forth the negative impact of using mathematical libraries for specific problems and identified performance issues specific to some versions of the same series of Message Passing Inerface (MPI) libraries. High precision profiling has shown that data representation and processing can be a more significant source of scalability bottleneck than computation and communications put together.

Titre traduit

Profilage et optimisation de l'algorithme du K-means dans un environnement de grape de calcul de type Beowulf

Résumé traduit

L'algorithme d'agglomeration statistique K-means sert a classer des bases de donnees non libellees en K groupes. Faisant partie de la fonction d'evaluation d'un Algorithme Ecolutionnaire (AE), I'optimisation de ce dernier est devenu un point d'interet. Malgre les multiples approches proposees pour son optimisation et sa parallelisation, tres pen de recherche s'est attardee aux questions entourant la performance et I'efficacite parallele des implantations. Dans la plupart des cas, les descriptions entourant I'environnement d'execution demeurent opaques et la presentation precise de profiles d'execution est souvent absente.

Nous pallions a ces lacunes en presentant une description detaillee de deux environnements, le grappes de calcul Beowulf et les machines paralleles de type Symmertric Multi-Processors (SMP). Une combinaison de modeles theoriques et empirique sert ensuite d'etalon dans la mesure de performance du K-means dans ces environnements. Etant la necessite d'une expertise pluridisciplinaire, une utilisation detaillee de la suite d'outils Tuning and Analysis Utilities (TAU) est presentee pour simplifier la tache du profilage de code parallele. Couplee aux compteurs haute precisions foumies par I'interface Performance Applicafion Programming Interface (PAPI), nous presentons une approche «grey box »ayant permis de muter une implementation parallele maitre-esclave du K-means vers une version hautement efficace utilisant le paradigme d'llots de calculs. Les optimisations sont guidees grace a 1'utilisation des modeles théoriques et empiriques que nous avons obtenus.

Notre travail revele que I'opfimisation de programmes paralleles releve de bien plus qu'un equilibre entre calcul et communications. Nous revelons les impacts negatifs de I'utilisation de bibliotheques de fonctions mathematiques ainsi que de certaines versions des bibliotheques de communications. Un profile d'execution de haute precisions a permis d'etablir que la representation et le pre-traitement des donnees peuvent s'averer etre plus couteux que le calcul et les communications combines.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Memorandum presented to l'École de technologie supérieure in partial fulfillment of the requirements for a master's degree in electrical engineering". Bibliogr. : f. [141]-146.
Mots-clés libres:	Algorithmes. Beowulf (Systèmes informatiques) calcul, environnement, grappe, k-means, optimisation, profilage
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Wong, Tony
Codirecteur:	Codirecteur Sabourin, Robert
Programme:	Maîtrise en ingénierie > Génie électrique
Date de dépôt:	16 août 2010 18:37
Dernière modification:	17 janv. 2017 22:50
URI:	https://espace.etsmtl.ca/id/eprint/85

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt