Parallel dynamic programming algorithms: Multitransputer systems

Jan Sadecki

International Journal of Applied Mathematics and Computer Science (2002)

  • Volume: 12, Issue: 2, page 241-255
  • ISSN: 1641-876X

Abstract

top
The present paper discusses real parallel computations. On the basis of a selected group of dynamic programming algorithms, a number of factors affecting the efficiency of parallel computations such as, e.g., the way of distributing tasks, the interconnection structure between particular elements of the parallel system or the way of organizing of interprocessor communication are analyzed. Computations were implemented in the parallel multitransputer SUPER NODE 1000 system using from 5 to 50 transputers.

How to cite

top

Sadecki, Jan. "Parallel dynamic programming algorithms: Multitransputer systems." International Journal of Applied Mathematics and Computer Science 12.2 (2002): 241-255. <http://eudml.org/doc/207584>.

@article{Sadecki2002,
abstract = {The present paper discusses real parallel computations. On the basis of a selected group of dynamic programming algorithms, a number of factors affecting the efficiency of parallel computations such as, e.g., the way of distributing tasks, the interconnection structure between particular elements of the parallel system or the way of organizing of interprocessor communication are analyzed. Computations were implemented in the parallel multitransputer SUPER NODE 1000 system using from 5 to 50 transputers.},
author = {Sadecki, Jan},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {parallel computations; parallel optimization algorithms; transputers; dynamic programming; multitransputer systems},
language = {eng},
number = {2},
pages = {241-255},
title = {Parallel dynamic programming algorithms: Multitransputer systems},
url = {http://eudml.org/doc/207584},
volume = {12},
year = {2002},
}

TY - JOUR
AU - Sadecki, Jan
TI - Parallel dynamic programming algorithms: Multitransputer systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2002
VL - 12
IS - 2
SP - 241
EP - 255
AB - The present paper discusses real parallel computations. On the basis of a selected group of dynamic programming algorithms, a number of factors affecting the efficiency of parallel computations such as, e.g., the way of distributing tasks, the interconnection structure between particular elements of the parallel system or the way of organizing of interprocessor communication are analyzed. Computations were implemented in the parallel multitransputer SUPER NODE 1000 system using from 5 to 50 transputers.
LA - eng
KW - parallel computations; parallel optimization algorithms; transputers; dynamic programming; multitransputer systems
UR - http://eudml.org/doc/207584
ER -

References

top
  1. Baker S.A. and Milner K.R. (1991): Performance monitoring and dynamic load balancing, ESPRIT Project 2701. - Royal Signals and Radar Establishment, Malveren, UK. 
  2. Bellman R. (1957): Dynamic Programming. - Princeton: PrincetonUniv. Press. Zbl0077.13605
  3. Brochard L. (1989): Efficiency of some parallel numerical algorithms on distributed systems. - Parallel Comput., Vol. 12, No.1, pp. 21-44. Zbl0681.65110
  4. Casti J., Richardson M. and Larson R. (1973): Dynamic programming and parallel computers. - JOTA, Vol. 12, No. 4, pp. 423-438. Zbl0248.65043
  5. Debbage M., Hill M. and Nicole D. (1991): Virtual channel router, Ver. 2.0, User guide, ESPRIT Project 2701. - University of Southampton. 
  6. Findeisen W., Szymanowski J. and Wierzbicki A. (1980): Theory and Computation Methods of Optimization. - Warsaw: Polish Scientific Publishers, (in Polish). Zbl0455.49001
  7. Flynn M.J. (1972): Some computer organizations and their effectiveness. - IEEE Trans. Comp., Vol. C-21, No. 9, pp. 948-960. Zbl0241.68020
  8. Harp G. (1989): Transputer Applications. - London: Pitman Publishing. Zbl0761.68013
  9. Interi G. (1991): Using the SN1000. - Liverpool: Liverpool University Press. 
  10. Kozielski S. and Szczerbiński Z. (1993): Parallel Computers: Architecture, Elements of Programming. - Warsaw: WNT, (in Polish). 
  11. Larson R. (1968): State Increment Dynamic Programming. - New York: Elsevier. Zbl0204.47101
  12. Malinowski K. and Sadecki J. (1986): Dynamic programming: A parallel implementation, In: Parallel Processing Techniques for Simulation (Singh M.G., Allidina A.Y. and Daniels B.K., Eds). - New York: Plenum Press, pp. 161-170. 
  13. 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 Engineering, Vol. XXXV, No. 3-4, pp. 119-140. 
  14. Occam 2 (1988): Occam 2, Reference Manual. - London: INMOS Ltd. Zbl0676.68005
  15. Sadecki J. (1987): Parallel implementation of dynamic programming methods in multiprocessor systems and investigation of their efficiency. - Ph.D. Th., Warsaw University of Technology (in Polish). 
  16. Sadecki J. and Galewicz St. (1991): Parallel computations in real two-processor system: Dynamic programming method. - Archives of Automatic Control Engineering and Robotics, Vol. XXXVI, No. 1, pp. 193-203. Zbl0800.68431
  17. Sadecki J. (1992): Possibilities of speedup of optimization computations by their implementation in parallel two-processor system: Decomposition algorithms in dynamic programming. - Scientific Papers of the Higher School ofEng. in Opole, Poland, Electrical Engineering, No. 35, pp. 5-27 (in Polish). 
  18. 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 ofEng. in Opole, Poland, pp. 142 (in Polish). 
  19. Sadecki J. (1999): The analysis of efficiency of parallel implementation of some optimization algorithms. - Proc. 13-th Nat. Conf. Automatic Control, Opole, Poland, pp. 341-344 (in Polish). 
  20. Sadecki J. (2001): Parallel Optimization Algorithms and Investigation of Their Efficiency: Parallel Distributed Memory Systems. - Studies and Monographs, Technical University of Opole, Opole, Poland (in Polish) 
  21. Sadecki J. (2002): The analysis of efficiency of parallel implementation of selected two-level optimization algorithms. - Multitransputer Syst. (to appear). Zbl1050.65060
  22. TAN (1989): The Transputer Applications Notebook, System and Performance. - Melksham, Wiltshire: Redwood Press Ltd., INMOS Ltd. 
  23. TDS (1988): Transputer Development System. - London: Prentice Hall, INMOS Ltd. 
  24. Wysocki M. and Kwolek B. (1994): Parallel Computations and Transputers in Automatic Control. - Rzeszów: Technical University Press (in Polish). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.