An efficiency analysis of the parallel multitransputer implementation of two-level optimization algorithms

• Autorzy: Jan Sadecki
• Języki publikacji: EN

Abstrakty

EN

The paper presents an approach to improve the efficiency of some two-level optimization algorithms by their implementation in parallel MIMD multiprocessor systems. Diagonal decomposition dynamic programming and parametric optimization methods are considered, and some concepts of their parallelization are discussed. Results regarding the implementation of computations in a parallel multitransputer system are presented. For the analysed problems, the obtained values of speedup are close to the theoretical maximum values.

Słowa kluczowe

EN

parallel computations; parallel optimization algorithms; two-level optimization methods; multitransputer systems

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2003
• Tom: 13
• Numer: 2
• Strony: 205-214

Daty

wydano

2003

otrzymano

2001-06-01

poprawiono

2002-11-05

Twórcy

autor

Jan Sadecki

• Department of Electrical Engineering and Automatic Control, Technical University of Opole, ul. Sosnkowskiego 31, 45-233 Opole, Poland

Bibliografia

• Averick B.M. and More J.J. (1994): Evaluation of large-scale optimization problems on vector and parallel architectures. - SIAM J. Optim., Vol. 4, No. 4, pp. 708-721.
• Bellman R. (1957): Dynamic Programming. - Princeton: Princeton Univ. Press.
• Baker M. (Ed.) (2000): Cluster computing white paper. - University of Portsmouth, UK, available at http://www.dcs.port.ac.uk/ mab/tfcc/WhitePaper.
• Birge J.R. and Rosa C.H. (1995): Parallel decomposition of large-scale stochastic nonlinear programs. - Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, available at http://users.iems.nwu.edu/~jrbirge/Public/html/rsann.html.
• Brochard L. (1989): Efficiency of some parallel numerical algorithms on distributed systems. - Parall. Comput., Vol. 12, No. 1, pp. 21-44.
• Collins D.C. (1970): Reduction of dimensionality in dynamic programming via the method of diagonal decomposition. - J. Math. Anal. Appl., Vol. 30, No. 1, pp. 223-234.
• Collins D.C. and Lew A. (1970): Dimensional approximation in dynamic programming by structural decomposition. - J. Math. Anal. Appl., Vol. 30, No. 2, pp. 375-384.
• Dongarra J.J. (2002): Performance of various computers using standard linear equations software. - Computer Science Department, University of Tennessee, Knoxville, available at http://www.netlib.org/benchmark/performance.ps.
• Eldred M.S. and Hart W.E. (1998): Design and implementation of multilevel parallel optimization on the Intel teraflops. - Sandia National Laboratories, Albuquerque, available at http://endo.sandia.gov/DAKOTA/papers/MDO98_paper.pdf.
• Findeisen W. (1974): Multilevel Control Systems. - Warsaw: Polish Scientific Publishers, (in Polish).
• Findeisen W., Szymanowski J. and Wierzbicki A. (1980): Theory and Computational Optimization Methods. - Warsaw: Polish Scientific Publishers, (in Polish).
• Interi G. (1991): Using the SN1000. - Liverpool: Liverpool University Press.
• Karbowski A. and Niewiadomska-Szynkiewicz E. (Eds.) (2001): Parallel and Distributed Computations. - Technical University of Warsaw, Warsaw, (in Polish).
• Larson R. (1968): State Increment Dynamic Programming. - New York: Elsevier.
• Malinowski K. and Sadecki J. (1990): Parallel implementation of dynamic programming methods in multiprocessor systems of different structures: Analysis of efficiency. - Archives of Automatic Control and Remote Control, Vol. XXXV, No. 3-4, pp. 119-140, (in Polish).
• Occam 2 (1988): Occam 2, Reference Manual. - London: Prentice Hall, INMOS Ltd.
• Sadecki J. (1987): Parallel implementation of dynamic programming methods in multiprocessor systems and investigation of their efficiency. - Ph.D. thesis, Warsaw University of Technology, (in Polish).
• Sadecki J. and Galewicz St. (1991): Parallel computations in real two-processor system: Dynamic programming method. - Archives of Automatic Control and Robotics, Vol. XXXVI, No. 1, pp. 193-203, (in Polish).
• Sadecki J. (1992): Possibilities of speedup of optimization computations by their implementation in parallel two-processor system: Decomposition algorithms in dynamic programming. - Sci. Papers of the Higher School of Eng. in Opole, Series: Electrical Eng., No. 35, pp. 5-27, (in Polish).
• Sadecki J. (1996): Parallel optimization algorithms of complex systems and hierarchical control: Parallel distributed memory systems. - Research project carried out for the State Committee for Scientific Research in Poland, No. 3 P403$;$02706, Final Report, Higher School of Eng. in Opole, Poland, pp. 142, (in Polish).
• Sadecki J. (2001): Parallel Optimization Algorithms and Investigation of Their Efficiency: Parallel Distributed Memory Systems. - Series: Studies and Monographs, Technical University of Opole, Opole, Poland, (in Polish).
• TAN (1989): The Transputer Applications Notebook, System and Performance. - Melksham, Wiltshire: Redwood Press Ltd., INMOS Ltd.
• Titli A., Singh M.G. and Hassan M.F. (1978): Hierarchical optimisation of dynamical systems using multiprocessors. - Comp. Electric. Eng., Vol. 5, No. 1, pp. 3-14.
• Van der Steen A.J and Dongarra J.J. (2001): Overview of recent supercomputers. - Available at http://www.top500.org/ORSC/2001/.
• Wysocki M. and Kwolek B. (1994): Parallel Computations and Transputers in Automatic Control Engineering. - Rzeszów: Technical University Press, (in Polish).