Implementacja oraz porównanie algorytmów tekstowych w środowiskach przetwarzania równoległego na przykładzie procesorów wielordzeniowych i kart graficznych

• Autorzy: Pietroń M. , Wielgosz M. , Wiatr K.

Warianty tytułu

EN

Multicore and GPGPU implementation of chosen text algorithms

• Języki publikacji: PL

Abstrakty

PL

Artykuł przedstawia implementację algorytmów tekstowych w wybranych platformach przetwarzania równoległego. Dostępność procesorów wielordzeniowych oraz kart graficznych ogólnego przeznaczenia sprawia, iż badania nad równoległą implementacją algorytmów w celu ich akceleracji nabierają coraz większego znaczenia. Algorytmy tekstowe są niezwykle istotnym i często niezbędnym elementem zaawansowanych algorytmów analizy tekstu oraz są także składowymi funkcji wyszukiwania wzorców w tekście wielu języków programowania. W pracy dokonano analizy najpopularniejszych algorytmów tekstowych oraz dokonano ich analizy pod kątem ich zrównoleglenia w celu ich implementacji w procesorze wielordzeniowym oraz karcie graficznej ogólnego przeznaczenia. Analizowanymi algorytmami są: boyer-moore, algorytm naiwny oraz algorytm knuth-morris-pratt. Następnie dokonano porównania efektywności ich realizacji na wymienionych platformach sprzętowych.

EN

This paper presents implementation of text algorithms in multicore CPU and GPGPU. The text algorithms are very common algorithms used in text analysis process and they are a part of functions used for text patterns recognition. The library functions for text searching implemented in many languages very often use most popular text-algorithms. The paper describes the analysis of these algorithms for parallel implementations in multicore processors and general purpose graphic cards. The research work presented in this paper shows that text algorithms can be partially parallelized. The process of acceleration can be done by appropriate dividing the input text between parallel threads (data parallelism). The comparative studies were performed for the following algorithms: boyer-moore (horspool) , naive and knuth-morris-pratt algorithm. The presented results show the efficiency of these algorithms in the case of different type and size of patterns. In the case of GPU the implementation was made in the CUDA framework. The OpenMP library was used for a multicore version.

Słowa kluczowe

PL

algorytmy tekstowe; GPGPU; obliczenia równoległe; text mining

EN

text algorithms; GPGPU; parallel computing; text mining

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 5
• Strony: 301--304
• Opis fizyczny: Bibliogr. 6 poz., wykr.

Twórcy

autor

Pietroń M.

• Akademia Górniczo-Hutnicza, ACK – CYFRONET, ul. Nawojki 11, 30-950 Kraków
• Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza, 30-059 Kraków

autor

Wielgosz M.

• Akademia Górniczo-Hutnicza, ACK – CYFRONET, ul. Nawojki 11, 30-950 Kraków
• Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza, 30-059 Kraków

autor

Wiatr K.

• Akademia Górniczo-Hutnicza, ACK – CYFRONET, ul. Nawojki 11, 30-950 Kraków
• Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza, 30-059 Kraków

Bibliografia

• [1] Kouzinopoulus C.S., Margaratis K.G.: String matching on a multicore GPU using CUDA, PCI'09, Informatics, pp. 14-16, September 2009.
• [2] Intel, Intel Cilk++ SDK programmer's guide. http://software.intel.com/ en-us/articles/intel-cilk/, 2009.
• [3] OpenMP, Summary of OpenMP 3.0 C/C++ syntax. http://openmp.org/ mp-documents/OpenMP3.0-SummarySpec.pdf ,2009.
• [4] Cormen T., Leierson H., Rivest E.: Introduction to algorithms, MIT Press and McGraw-Hill, 1990.
• [5] Wielgosz M., Jamro E., Russek P., Pietroń M., Żurek D., Janiszewski M., Wiatr K.: Implementation of algorithms for fast text search and files comparison , KU KDM 2013, Marzec, Zakopane, Proceedings, pp. 83 – 84.
• [6] Sunday D.M.: A very fast substring search algorithm. Communications of the ACM, 33(8): 132-142, 1990.