Analiza efektywności wybranych równoległych implementacji algorytmu Gaussa-Seidela

pol Article in Polish DOI: 10.14313/PAR_215/29

send Jan Sadecki , Marek Machaczek Instytut Automatyki i Informatyki, Wydział Elektrotechniki, Automatyki i Informatyki, Politechnika Opolska

Download Article

Streszczenie

W artykule przedstawiono analizę porównawczą dotyczącą badania efektywności kilku równoległych implementacji algorytmu Gaussa-Seidela. Analizowany w artykule algorytm pozwala na osiągnięcie dosyć dobrych pod względem szybkości zbieżności oraz wartości współczynnika przyspieszenia obliczeń wyników w porównaniu do standardowej sekwencyjnej oraz równoległej implementacji metody Gaussa-Seidela. Obliczenia praktyczne przeprowadzono w środowisku procesorów wielordzeniowych oraz w środowisku klastrów obliczeniowych.

Słowa kluczowe

algorytmy optymalizacji, obliczenia równoległe, równoległe algorytmy optymalizacji

Efficiency Analysis of Some Parallel Implementations of the Gauss-Seidel Algorithm

Abstract

The paper presents the results of the efficiency analysis of some parallel implementations of Gauss-Seidel algorithm. The main idea of the presented method consists in successive modification of the search directions used in the computations. This modification is performed on the basis of solutions of local optimization subproblems received for all stages of the algorithm. The analyzed algorithm enable to achieve a good efficiency of parallel computation in terms of speed of convergence and value of speedup factor in comparison to standard sequential and parallel implementation of Gauss-Seidel method. Parallel computation were implemented in the multicore processor and multiprocessor cluster.

Keywords

algorithm, optimization, parallel computation

Bibliography

  1. Chazan D., Miranker W.L., A Nongradient and Parallel Algorithm for Unconstrained Minimization, “SIAM Journal on Control”, vol.8, No. 2, May 1970, 207–217. DOI: 10.1137/0308015.
  2. Dennis J.E., Torczon V., Direct Search Methods on Parallel Machines, SIAM Journal on Optimization, Vol. 1, No.4, November 1991, 448–474. DOI: 10.1007/978-3-642-48417-9_2.
  3. Findeisen Wł., Szymanowski J., Wierzbicki A., Metody obliczeniowe optymalizacji, Wydawnictwo Politechniki Warszawskiej, Warszawa 1973.
  4. Findeisen Wł., Szymanowski J., Wierzbicki A., Teoria i metody obliczeniowe optymalizacji. PWN, Warszawa 1980.
  5. Kaliczyńska M., Sadecki J., Obliczenia równoległe – klastry obliczeniowe, Zeszyty Naukowe PO, s. Elektryka, z. 57, 2006, 101–114.
  6. Karbowski A., Niewiadomska-Szynkiewicz E., Programowanie równoległe i rozproszone, Oficyna Wydawnicza PW, Warszawa 2009.
  7. Korytkowski A., Ziółko M., Metody optymalizacji z ćwiczeniami laboratoryjnymi, Wydawnictwo AGH, Kraków 1992.
  8. Lewis A., Parallel Optimization Algorithms for Continuous, Non-linear Numerical Simulation, PhD thesis, 2004, Griffith University, Brisbane, Australia.
  9. Molga M., Smutnicki Cz., Test functions for optimization needs, 2005, www.robertmarks.org/Classes/ENGR5358/Papers/functions.pdf.
  10. Press W. H., Flannery B. P., Teukolsky S.A., Vetterling W. T., Numerical Recipes, The Art of Scientific Computing, Cambridge University Press, 1986.
  11. Sadecki J., Algorytmy równoległe optymalizacji i badanie ich efektywności; systemy równoległe z rozproszoną pamięcią, Oficyna Wydawnicza Politechniki Opolskiej, Opole 2001.
  12. Sadecki J., Równoległe implementacje algorytmu Gaussa-Seidela w środowisku OpenMP, PAK, 2011, nr 03, 301–304.
  13. Sobczyk J., Wierzbicki A. P., Obliczenia równoległe w optymalizacji liniowej i nieliniowej. Algorytm pulsacyjny w optymalizacji nieliniowej, [w:] I Konferencja Granty-Automatyka’95. Warszawa, 27–29.06.1995.