INVESTIGATION OF KROHN’S ALGORITHM AND ITS MODIFICATION FOR VARIOUS BASIC DATA
Abstract
The problem on the task distribution among the multiple homogeneous computing devices by the minimax criterion is considered. The problem definition with the detailed description of the subject of inquiry and its basics is given. It is proposed to use approximate algorithms for the solution to the problem. Both Krohn’s classical and modified algorithms, and the techniques of improving them through the initial task distribution among the computer system devices are considered. The critical-path algorithm and Pashkeyev’s algorithm are used for this purpose. The output values of a number of computational experiments at various input parameters are given in the paper for estimating the efficiency of the obtained Krohn’s algorithm modifications. The modified algorithms efficiency has been evaluated by the operate time and by the departure of the obtained load values from the optimum. The software to analyze the modified algorithm efficiency is developed.
About the Authors
Valery Grigoryevich Kobak
Don State Technical University.
Russian Federation
Russian Federation
Dmitry Vyacheslavovich Titov
Don State Technical University.
Russian Federation
Russian Federation
Oleg Anatolyevich Zolotykh
Don State Technical University.
Russian Federation
Russian Federation
References
1. Kofman, E.G. Teoriya raspisaniy i vychislitelnyye mashiny. [Scheduling theory and computing machines.] Moscow: Nauka, 1987, 334 p. (in Russian).
2. Kobak, V.G., Ivanov, M.S. Sravnitelnyy analiz algoritmov resheniya zadachi planirovaniya v odnorodnykh vychislitelnykh sistemakh. [Comparative analysis of solution algorithms to planning problems in homogeneous parallel computing systems with distributed memory.] Matematicheskiye metody v tekhnike i tekhnologiyakh — MMTT-20: sb. tr. XX Mezhdunar. nauch. konf. [Mathematical techniques in methods and technology – MMTT-20: Proc. XX Int. Sci. Conf.] Yaroslavl, 2007, vol. 2, sect. 2, pp. 56–57 (in Russian).
3. Kobak, V.G, Zolotykh, O.A., Titov, D.V. Povysheniye effektivnosti algoritma Krona za schet modifikatsii nachalnogo raspredeleniya zadaniy. [Improvement of Kron algorithm at the expense of modification of starting allocation of tasks.] Sovremenyye problemy informatizatsii v modelirovanii i sotsialnykh tekhnologiyakh: sb. tr. XVI Mezhdunar. otkrytoy nauch. konf. [Modern problems of informatization in modeling and social technologies: Proc. XVI Int. Open Sci. Conf.] Voronezh: Nauchnaya kniga, 2011, pp. 246–251 (in Russian).
Review
For citations:
Kobak V.G., Titov D.V., Zolotykh O.A. INVESTIGATION OF KROHN’S ALGORITHM AND ITS MODIFICATION FOR VARIOUS BASIC DATA. Vestnik of Don State Technical University. 2012;12(8):62-67. (In Russ.)
Views:
450
Email this article 