Równoległe implementacje algorytmu Gaussa-Seidela w środowisku OpenMP

• Autorzy: Sadecki J.

Warianty tytułu

EN

Parallel implementation of Gauss-Seidel algorithm by using OpenMP

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono przykładowe rezultaty analizy efektywności równoległych realizacji algorytmu Gaussa-Seidela zaimplementowanych w środowisku procesorów wielordzeniowych. Jak pokazano, standardowa równoległa implementacja tego algorytmu, prowadzi do gorszych w sensie szybkości zbieżności wyników w porównaniu do sekwencyjnej wersji tej metody. Zaproponowana nowa wersja równoległa metody Gaussa-Seidela posiada analogiczną szybkość zbieżności jak jej realizacja sekwencyjna, zachowując przy ty łatwość implementacji równoległej. W artykule przedstawiono przykładowe rezultaty obliczeń przeprowadzonych przy wykorzystaniu procesora czterordzeniowego. Rozważana implementacja algorytmu Gaussa-Seidela posiada też możliwości jej zastosowania dla szerszej niż rozważana w pracy klasy problemów optymalizacji.

EN

The paper presents results of the efficiency analysis for some parallel realization of optimisation algorithms in multicore processors. The results concern a simple Gauss-Seidel optimization algorithm. In the paper both standard parallel and new parallel implementations of the Gauss-Seidel algorithm are presented. As it is pointed out, the standard parallel algorithm leads to worse numerical results (in terms of the rate of computation convergence) than the sequential version of this algorithm. The new parallel algorithm achieves the same numerical ef?ciency of computations as the sequential algorithm and, additionally, can be aesily implemented in multicore processors. It is prooved that, for the quadratic optimization problem, the modified parallel Gauss-Seidel algorithm leads to the same computational results as for the sequential implementation of the method. Some examples of parallel implementations of the method in fourcore processors are presented. The proposed new algorithm enables achieving good efficiency of parallel computations both in terms of the execution time and the speedup factor value. The new algorithm can also be used to solve broader classes of optimization problems, which in the nearest neighbourhood of the optimal solution can be sufficiently precisely approximated by the square function.

Słowa kluczowe

PL

klastry; algorytmy równoległe; procesory wielordzeniowe

EN

clusters; parallel algorithms; multicore processors

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 3
• Strony: 301--304
• Opis fizyczny: Bibliogr. 7 poz., rys., wykr., wzory

Twórcy

autor

Sadecki J.

• Politechnika Opolska, Wydział Elektrotechniki, Automatyki i Informatyki, ul. Sosnkowskiego 31, 45-272 Opole,

Bibliografia

• [1] Findeisen W., Szmanowski J., Wierzbicki A.: Teoria i metody obliczeniowe optymalizacji, PWN, 1980.
• [2] Karbowski A., Niewiadomska-Szynkiewicz E. (eds): Programowanie równoległe i rozproszone. Oficyna Wydawnicza Politechniki Warszawskiej, 2009.
• [3] Kumar V., Grama A., Gupta A., Karypis G.: Introduction to Parallel Computing, Addison Wesley, 2002.
• [4] Majer M.: Process of Modeling Pollutants Dispersion in the Atmosphere. Education, Research, Innovation-ERIN 2009, Conference, Ostrava 2009.
• [5] Podpora M., Sadecki J.: Biologically reasoned point-of-interest image compression for mobile robots, ISBN: 978-3-642-03201-1, DOI: 10.1007/978-3-642-03202-8_29, pp 389-401, Springer, 2009.
• [6] Sadecki J.: Algorytmy równoległe optymalizacji i badanie ich efektywności; systemy równoległe z rozproszoną pamięcią, Studia i monografie, Politechnika Opolska, Opole 2001.
• [7] Wyrzykowski R.: Klastry komputerów PC i architektury wielordzeniowe: budowa i wykorzystanie. AOW EXIT, Warszawa, 2009.