P-means, a parallel clustering algorithm for a heterogeneous multi-processor environment

摘要

G-means is a data mining clustering algorithm based on k-means, used to find the number of Gaussian distributions and their centers inside a multi-dimensional dataset. This paper presents the performance gain obtained from the development of a parallel G-means algorithm for a heterogeneous multi-processor environment using the StarSs framework, called here P-means. The P-means execution was divided into 6 well-defined steps, where each step was analyzed to create a hierarchical task structure in order to parallelize the execution enabling it to explore the hierarchy and heterogeneity of the Cell BE blades and others heterogeneous architectures. The algorithm implementation was also adapted to perform sequential timing measures to evaluate the Amdahl's law, to compare the theoretical calculation and the execution times' measurements and to introduce parallel computation by using the StarSs framework. The algorithm was executed using a 30 clusters dataset containing 600 thousand points of 60 dimensions in different hardware configurations in order to compare its execution time and speedup, and it showed a overall speedup of more than 18 times. A successful experimentation with real data demonstrated the usefulness of the algorithm.