Acceleration of information-theoretic data analysis with graphics processing units

• Autorzy: Sluga D. , Curk T. , Zupan B. , Lotrič U.

Warianty tytułu

PL

Przyspieszenie analizy danych opartej o teorię informacji przy pomocy programowalnych kart graficznych

• Języki publikacji: EN

Abstrakty

EN

Information-theoretic measures are frequently employed to assess the degree of feature interactions when mining attribute-value data sets. For large data sets, obtaining these measures quickly poses an unmanageable computational burden. In this work we examine the applicability of consumer graphics processing units supporting CUDA architecture to speed-up the computation of information-theoretic measures. Our implementation was tested on a variety of data sets, and compared with the performance of sequential algorithms running on the central processing unit.

PL

Miary informacji takie jak informacja wzajemna są często używane do określania stopnia współzależności cech podczas eksploracji zbiorów danych opisanych atrybutami. Dla dużych zbiorów danych, proste wyliczanie tych miar prowadzi wprost do znacznego wzrostu nakładów obliczeniowych. Praca jest poświęcona możliwościom zastosowania programowalnych kart graficznych do przyspieszenia wyznaczania miar informacji. Nasza implementacja została przetestowana na różnych zbiorach danych oraz porównana z implementacją sekwencyjną na procesorze głównym.

Słowa kluczowe

EN

information theoretic measures; data mining; parallelization; CUDA

PL

CUDA; miary informacji; eksploracja danych; algorytmy równoległe

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 2
• Strony: 136--139
• Opis fizyczny: Bibliogr. 15 poz., rys., wykr.

Twórcy

autor

Sluga D.

autor

Curk T.

autor

Zupan B.

autor

Lotrič U.

• Faculty of Computer and Information Science, Univeristy of Ljubljana, Tržaška ulica 25, 1000 Ljubljana, Slovenia,

Bibliografia

• [1] Hild Il K.E., Erdogmus D., Torkkola K., Principe J.C.: Feature Extraction Using Information-Theoretic Learning, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (2006), No. 9, 1385–1392.
• [2] Cover T., Thomas J.: Elements of Information Theory, New York, Wiley (2006).
• [3] Lee C., Landgrebe, D.: Feature Extraction and Classification Algorithms for High Dimensional Data, TR-EE 93-1, School of Electrical Engineering, Purdue University, Indiana (1993).
• [4] Owens J.D., Houston M., Luebke D., Green S., Stone J.E., Phillips J.C.: GPU Computing, Proceedings of the IEEE, 96 (2008), No. 5, 879–899.
• [5] Mazurek P.: Optimization of Bayesian Track-Before-Detect algorithms for GPGPUs Implementations, Przegla˛d elektrotechniczny, 86 (2010), No. 7, 187–189.
• [6] M. Borysiak, Z. Krawczyk, J. Starzy´nski, R. Szmurło, S.Wincenciak, CUDA accelerated finite element mesh morpher, Przegla˛d elektrotechniczny, 87 (2011), No. 5, 176–178.
• [7] Shi H., Schmidt B., Liu W., Mueller-Wittig W.: A Parallel Algorithm for Error Correction in High-Throughput Short-Read Data on CUDA-enabled Graphics Hardware, Journal of Computational Biology, 17 (2010), No. 4, 603–615.
• [8] Payne J., Sinnott-Armstrong N.A., Moore J.H.: Exploiting graphics processing units for computational biology and bioinformatics, Interdisciplinary Sciences 2 (2010), No. 3, 213–220.
• [9] Liu Y., Schmidt B., Maskell D.: CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions, BMC Research Notes, 3 (2010), No. 1, 93–104.
• [10] Lindholm E., Nickolls J., Oberman S., Montrym J.: NVIDIA Tesla: A Unified Graphics and Computing Architecture, IEEE Micro, 28 (2008), No. 2, 39–55.
• [11] Richards F.C., Mayer T.P., Packard N.H.: Extracting Cellular automaton rules directly from experimental data, Physica D, 45 (1990), No. 1-3, 189–202.
• [12] Nickolls J., DallyW.J: The GPU Computing Era, IEEE Micro, 30 (2010), No.2, 56–69.
• [13] Ulery J., Computing Integer Square Roots. [web page] http:// www.azillionmonkeys.com/qed/ulerysqroot.pdf. [Accessed on Aug 19, 2011].
• [14] Toplak M., Curk T., Demsar J., Zupan B.: Does replication groups scoring reduce false positive rate in SNP interaction discovery?, BMC Genomics, 11(2010), No. 1, 58–62.
• [15] Jakulin A., Bratko I.: Analyzing Attribute Dependencies, In: 7th European Conference on Principles and Practice of Knowledge Discovery in Databases, 2003.