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

Sadecki, Jan

International Journal of Applied Mathematics and Computer Science, Tome 13 (2003), p. 205-214 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2003-01-01

Zbl 1050.65060

EUDML-ID : urn:eudml:doc:207637

Bibliographie

[000] 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. | Zbl 0813.65089

[001] Bellman R. (1957): Dynamic Programming. - Princeton: Princeton Univ. Press. | Zbl 0077.13605

[002] Baker M. (Ed.) (2000): Cluster computing white paper. - University of Portsmouth, UK, available at http://www.dcs.port.ac.uk/ mab/tfcc/WhitePaper.

[003] 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.

[004] Brochard L. (1989): Efficiency of some parallel numerical algorithms on distributed systems. - Parall. Comput., Vol. 12, No. 1, pp. 21-44. | Zbl 0681.65110

[005] 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. | Zbl 0187.42004

[006] 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. | Zbl 0213.45305

[007] 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.

[008] 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.

[009] Findeisen W. (1974): Multilevel Control Systems. - Warsaw: Polish Scientific Publishers, (in Polish). | Zbl 0376.93003

[010] Findeisen W., Szymanowski J. and Wierzbicki A. (1980): Theory and Computational Optimization Methods. - Warsaw: Polish Scientific Publishers, (in Polish). | Zbl 0455.49001

[011] Interi G. (1991): Using the SN1000. - Liverpool: Liverpool University Press.

[012] Karbowski A. and Niewiadomska-Szynkiewicz E. (Eds.) (2001): Parallel and Distributed Computations. - Technical University of Warsaw, Warsaw, (in Polish).

[013] Larson R. (1968): State Increment Dynamic Programming. - New York: Elsevier. | Zbl 0204.47101

[014] 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).

[015] Occam 2 (1988): Occam 2, Reference Manual. - London: Prentice Hall, INMOS Ltd. | Zbl 0676.68005

[016] 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).

[017] 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). | Zbl 0800.68431

[018] 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).

[019] 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).

[020] 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).

[021] TAN (1989): The Transputer Applications Notebook, System and Performance. - Melksham, Wiltshire: Redwood Press Ltd., INMOS Ltd.

[022] 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. | Zbl 0388.93004

[023] Van der Steen A.J and Dongarra J.J. (2001): Overview of recent supercomputers. - Available at http://www.top500.org/ORSC/2001/.

[024] Wysocki M. and Kwolek B. (1994): Parallel Computations and Transputers in Automatic Control Engineering. - Rzeszów: Technical University Press, (in Polish).