Analiza efektywności wybranych równoległych implementacji algorytmu programowania dynamicznego

• Autorzy: Koropiecki, D. , Sadecki, J.

Warianty tytułu

EN

Efficiency analysis of some parallel implementations of the dynamic programming algorithm

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono analizę porównawczą dotyczącą badania efektywności kilku równoległych implementacji algorytmu programowania dynamicznego. Analizowane w artykule algorytmy pozwalają na osiągnięcie dosyć dobrych pod względem wartości współczynnika przyspieszenia obliczeń wyników w porównaniu do standardowej sekwencyjnej implementacji metody. Obliczenia praktyczne przeprowadzono w środowisku procesorów wielordzeniowych.

EN

The paper presents the results of the efficiency analysis of some parallel implementations of dynamic programming algorithm. The analyzed algorithms enable to achieve a good efficiency of parallel computation in term speedup factor in comparison to standard sequential method. Parallel computation were implemented in the multicore processor.

• Czasopismo: Zeszyty Naukowe. Elektryka / Politechnika Opolska
• Rocznik: 2016
• Tom: z. 74
• Strony: 55--66
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Koropiecki, D.

• Wydział Elektrotechniki, Automatyki i Informatyki Instytut Automatyki i Informatyki

autor

Sadecki, J.

• Wydział Elektrotechniki, Automatyki i Informatyki Instytut Automatyki i Informatyki

Bibliografia

• [1] LARSON R.: State Increment Dynamic Programing, American Elsevier Publishing Comp. Inc. New York 1968
• [2] SADECKI J.: Algorytmy równoległe optymalizacji i badanie ich efektywności; systemy równoległe z rozproszoną pamięcią, Politechnika Opolska, Opole 2001
• [3] FINDEISEN W., SZYMANOWSKI J,. WIERZBICKI A.: Metody obliczeniowe optymalizacji, Wydawnictwo Politechniki Warszawskiej, Warszawa 1973
• [4] CASTI J., RIACHARDSON M., LARSON R.: Dynamic Programming and Parallel Computers, JOTA, Vol. 12, No. 4, 1973, 423–438
• [5] HORLA D.: Metody obliczeniowe optymalizacji w zadaniach: Wydawnictwo Politechniki Poznańskiej, Poznań 2008
• [6] CORMEN T.H.: Wprowadzenie do algorytmów, Wyd. Naukowo-Techniczne, Warszawa 2001
• [7] Programowanie aplikacji rozproszonych i równoległych, dr inż. Tomasz Olas, Politechnika Częstochowska, http://icis.pcz.pl/~olas/parr/wyklad2.4.pdf, [Dostęp: marzec 2016]