Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 13 | 2 | 205-214

Tytuł artykułu

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


Treść / Zawartość

Warianty tytułu

Języki publikacji



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.








Opis fizyczny




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


  • 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 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
  • 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
  • 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
  • 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
  • Wysocki M. and Kwolek B. (1994): Parallel Computations and Transputers in Automatic Control Engineering. - Rzeszów: Technical University Press, (in Polish).

Typ dokumentu



Identyfikator YADDA

JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.