Parallelization of the K-Means Algorithm on a Reconfigurable System Application to Hyper-Spectral Images. Parallélisation de L’Algorithme du K-Means sur un Système Reconfigurable Application aux Images Hyper-Spectrales

Parallelization of the K-Means Algorithm on a Reconfigurable System Application to Hyper-Spectral Images

Parallélisation de L’Algorithme du K-Means sur un Système Reconfigurable Application aux Images Hyper-Spectrales

Dominique Lavenier

CNRS/IRISA Campus de Beaulieu - 35042 Rennes cedex

Page: 
437-445
|
Received: 
8 June 2001
|
Accepted: 
N/A
|
Published: 
31 December 2001
| Citation

OPEN ACCESS

Abstract: 

The article presents a parallel architecture dedicated to the k-means algorithm used for clustering objects in a non hierachical way. We propose an implementation on a reconfigurable system made of a PC and a FPGA board closely coupled through the I/O bus. Experimentations have been carried on a set of hyper-spectral images and show that the computation time is reduced from a few hours to a few minutes. We also points out the influence of the channel quality between the processor and the FPGA board over the global system performances.

Résumé

L’article présente une architecture parallèle spécialisée pour l’algorithme du K-means, un algorithme de classification qui regroupe les objets de manière non hiérarchique. Nous proposons une mise en œuvre sur un système reconfigurable composé d’un PC couplé à une carte FPGA par l’intermédiaire de son bus d’entrées/sorties. L’expérimentation porte sur la segmentation d’images hyper-spectrales et démontre que les temps de traitement peuvent être réduits de quelques heures à quelques minutes. Cette réalisation met également en évidence l’influence de la qualité de la liaison entre le processeur et la carte FPGA sur les performances globales du système.

Keywords: 

reconfigurable system, parallel architecture, hyper-spectral images, K-means algorithm

Mots clés

Système reconfigurable, architecture parallèle, images hyper-spectrales algorithmes du K-means.

1. Introduction
2. L’Algorithme du K-Means
3. Parallélisation
4. Expérimentation
5. Conclusion
  References

[1] M. Estlick, M. Leeser, J. Szymanski, J. Theiler, « Algorithmic Transformation in the Implementation of the K-means Clustering on Reconfigurable Hardware », 9th ACM International Symposium on FPGA, Monterey, CA, 2001.

[2] M. Gokhale, J. Frigo, K. McCabe, J. Theiler, D. Lavenier, « Early Experience with a Hybrid Processor: K-Means Clustering », First Internationnal Conference on Engineering of Reconfigurable Systems and Algorithms, Las Vegas, Nevada, 2001. 

[3] M. Leeser, J. Theiler, M. Estlick, V. Kitaryeva, J. Szymanski, « Effect of data truncation in an implementation of pixel clustering on a custom computing machine », SPIE Proceedings, Reconfigurable Technology: FPGA for Computingand Applications, vol 4212, Boston, MA, 2000. 

[4] M. Leeser, J. Theiler, M. Estlick, J. J. Szymanski, « Design tradeoffs in a hardware implementation of the k-means clustering algorithm », First IEEE SensorArray and Multiprocessing Workshop, 2000. 

[5] J. Theiler, M. Leeser, M. Estlick, J. Szymanski, « Design issues for hardware implementation of an algorithm for segmenting hyperspectral imagery », Imaging Spectrometry, SPIE Proceedings, vol 4132, San Diego, CA, 2000. 

[6] D. Lavenier, « FPGA implementation of the K-means Clustering Algorithm for Hyper-Spectral Images », rapport de recherche Los Alamos National Laboratory, LAUR 00-3079,20001. 

[7] D. Lavenier, « An FPGA systolic array Using Pseudo Random Bit Generator for Computing Goldbach Partitions », The VLSI Journal, vol 30, n° 1, 2000.

[8] S. Guccione, « List of FPGA-based Computing Machines », http://www.io.com/~guccione/HW\_list.html, 1999. 

[9] J. Theiler, G. Gisler, « A contiguity-enhanced k-means clustering algorithmfor unsurpervised multispectral images segmentation », Proc SPIE 3159, pp. 108-118, 1997. 

[10] S. Rubini, D. lavenier, « Les Architectures Reconfigurables », Calculateurs Parallèles, vol 9, n° 1, 1997. 

[11] K. Vuillemin, P. Bertin, D. Roncin, M. Shand, H. Touati, P. Boucard, « Programmable Active Memories: the Comming of Age », IEEE Trans. onVLSI, vol 4, n° 1, pp. 56-69, 1996. 

[12] P. Guerdoux-Jamet, D. Lavenier, « Systolic Filter for Fast DNA Similarity Search », ASAP’95, International Conference on Application Specific Array Processor, Strasbourg, France, 1995. 

[13] J. MacQueen, « Some methods for classification and analysis of multivariate observations », Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, vo1, University of California Press, 1967. 

[14] Programmable Logic Boards, The Programmable Logic Jump Station, Optimagic http://www.optimagic.com/boards [15] Spyder, User’s Manual, X2E, (http://www.x2e.de), 1999.