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

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.

Level thesis:degree_level

masters

Grantor dc:publisher

École de technologie supérieure

Year dc:date

2009

Author dc:creator

• Thibodeau, Éric

• Algorithmes. Beowulf (Systèmes informatiques) calcul, environnement, grappe, k-means, optimisation, profilage

Language dc:language

en

Identifier

INSERT-YOUR-LIBRARY-ID-HERE85

OAI record oai:identifier

https://espace.etsmtl.ca/cgi/oai2?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aespace.etsmtl.ca%3A85