A vectorized k-means algorithm for compressed datasets: design and experimental analysis
| Autor: | Lasse Natvig, Juan M. Cebrian, Abdullah Al Hasib |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
020203 distributed computing
Memory hierarchy Computer science k-means clustering 020207 software engineering 02 engineering and technology Parallel computing Mixture model Theoretical Computer Science Hardware and Architecture 0202 electrical engineering electronic engineering information engineering SIMD Cluster analysis Software Xeon Phi Information Systems |
| Zdroj: | Journal of Supercomputing |
| Popis: | Clustering algorithms (i.e., Gaussian mixture models, k-means) tackle the problem of grouping a set of elements in such a way that elements from the same group (or cluster) have more similar properties to each other than to those elements in other clusters. This simple concept turns out to be the basis in complex algorithms from many application areas, including sequence analysis and genotyping in bioinformatics, medical imaging, antimicrobial activity, market research, social networking, etc. However, as the data volume continues to increase, the performance of clustering algorithms is heavily influenced by the memory subsystem. In this paper, we propose a novel and efficient implementation of Lloyd’s k-means clustering algorithm to substantially reduce data movement along the memory hierarchy. Our contributions are based on the fact that the vast majority of processors are equipped with powerful Single Instruction Multiple Data (SIMD) instructions that are, in most cases, underused. SIMD improves the CPU computational power and, if used wisely, can be seen as an opportunity to improve on the application data transfers by compressing/decompressing the data, specially for memory-bound applications. Our contributions include a SIMD-friendly data layout organization, in-register implementation of key functions and SIMD-based compression. We demonstrate that using our optimized SIMD-based compression method, it is possible to improve the performance and energy of k-means by a factor of 4.5x and 8.7x, respectively, for a i7 Haswell machine, and 22x and 22.2x for Xeon Phi: KNL, running a single thread. This is a post-peer-review, pre-copyedit version of an article published in [Journal of Supercomputing]. The final authenticated version is available online at: https://doi.org/10.1007/s11227-018-2310-0 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|