Article

Article title ANALYSIS OF THE RESULTS OF APPLYING THE RANDOM SEARCH METHOD IN THE PROBLEM OF BUILDING SEPARATIONS OF PARALLEL LOGIC CONTROL ALGORITHMS
Authors E.I. Vatutin, D.V. Kolyasnikov, V.S. Titov
Section SECTION II. MATHEMATICAL AND SOFTWARE OF SUPERCOMPUTERS
Month, Year 12, 2014 @en
Index UDC 681.3
DOI
Abstract The article describes the random search method in the problem of constructing suboptimal separations of parallel logic control algorithms within homogeneous multi-module multisystems design (logic control systems based on logical multicontrollers). Using developed program system PAE a number of computational experiments are organized. The analysis of the convergence rate and results of a comparison with the known quality optimization heuristic methods are given. Showed that a sufficient number of iterations (1000–10 000) provide acceptable quality of solutions but computing time costs increased by 10–100 times. The obtained results allow us to conclude that in a number of combinations of the problem dimension and power of technological limitations proposed method has the advantage in a number of private quality indicators, losing by a integral indicator. The random search method is well parallelized that allows using a wide range of modern parallel computing resources.

Download PDF

Keywords Discrete combinatorial optimization; heuristic methods; multicontrollers design; graph-schemes of algorithms; separations.
References 1. Zotov I.V. i dr. Organizatsiya i sintez mikroprogrammnykh mul'timikrokontrollerov [Organization and synthesis firmware multimilliondollar]. Kursk: Izd-vo «Kursk», 1999, 368 p.
2. Emel'yanov S.G., Zotov I.V., Titov V.S. Arkhitektura parallel'nykh logicheskikh mul'tikontrollerov [Architecture of parallel logical Multicontroller]. Moscow: Vysshaya shkola, 2009, 233 p.
3. Vatutin E.I., Zotov I.V., Titov V.S. i dr. Kombinatorno-logicheskie zadachi sinteza razbieniy parallel'nykh algoritmov logicheskogo upravleniya pri proektirovanii logicheskikh mul'tikontrollerov [Combinatorial logic synthesis problem splits parallel logic control algorithms when designing logical Multicontroller]. Kursk: Izd-vo ”Kursk”, 2010, 200 p.
4. Vatutin E.I. Proektirovanie logicheskikh mul'tikontrollerov. Sintez razbieniy parallel'nykh graf-skhem algoritmov[Designing logical Multicontroller. Synthesis of separations of parallel graph-schemes of algorithms]. Saarbrьcken: Lambert Academic Publishing, 2011, 292 p.
5. Available at: https://ru.wikipedia.org/wiki/Числа_Белла.
6. Baranov S.I., Zhuravina L.N., Peschanskiy V.A. Obobshchennyy metod dekompozitsii graf-skhem algoritmov [Generalized method of decomposition graph-schemes of algorithms], A i VT [Automation and Computer Engineering], 1982, No. 5, pp. 43-51.
7. Vatutin E.I. Biblioteka funktsiy postroeniya razbieniy metodom S.I. Baranova s zhadnym posledovatel'nym formirovaniem blokov [Library functions separations of method C. I. Baranova with greedy sequential formation of blocks], Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2010612902 ot 28.04.10.
8. Vatutin E.I., Leonov M.E. Ispol'zovanie smezhnoy okrestnosti pri zhadnom posledovatel'nom formirovanii blokov razbieniya graf-skhem parallel'nykh algoritmov [Using an adjacent neighborhood with greedy sequential formation of blocks of the partition graph-schemes of parallel algorithms], Izvestiya vysshikh uchebnykh zavedeniy. Priborostroenie [News of higher educational institutions. Instrumentation], 2013, Vol. 56, No. 6, pp. 30-35.
9. Vatutin E.I., Titov V.S. Biblioteka funktsiy dlya postroeniya razbieniy s ispol'zovaniem smezhnoy zhadnoy strategii i posledovatel'nym formirovaniem blokov [Library of functions for building partitions using adjacent greedy strategy and sequential formation of blocks], Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619395 ot 03.10.13.
10. Vatutin E.I., Zotov I.V. Metod formirovaniya suboptimal'nykh razbieniy parallel'nykh upravlyayushchikh algoritmov [A method of forming a suboptimal splits parallel logic control algorithms], Parallel'nye vychisleniya i zadachi upravleniya (PACO’04) [Parallel computing and control problems (PACO’04)]. Moscow: IPU RAN, 2004, pp. 884-917.
11. Vatutin E.I., Zotov I.V. Parallel'no-posledovatel'nyy metod formirovaniya subop-timal'nykh razbieniy parallel'nykh upravlyayushchikh algoritmov [Parallel-sequential method of forming
a suboptimal splits parallel logic control algorithms], Svidetel'stvo ob ofitsial'noy registratsii programmy dlya EVM № 2005613091 ot 28.11.05.
12. Vatutin E.I. Otsenka kachestva razbieniy parallel'nykh upravlyayushchikh algoritmov na posledovatel'nye podalgoritmy s ispol'zovaniem vesovoy funktsii [Assessment of the quality of the separations of parallel logic control algorithms on serial Podgorica using the weighting function], Intellektual'nye i informatsionnye sistemy (Intellekt-2005) [Intellectual and infor-
mation system (Mind 2005)]. Tula, 2005, pp. 29-30.
13. Vatutin E.I., Volobuev S.V., Zotov I.V. Kompleksnaya sravnitel'naya otsenka metodov vybora razbieniy pri proektirovanii logicheskikh mul'tikontrollerov [Comprehensive comparative evaluation of selection methods breaks when designing logical Multicontroller], Identifikatsiya sistem i zadachi upravleniya (SICPRO’08) [Systems identification and control problems (SICPRO’08)]. Moscow: IPU RAN, 2008, pp. 1917-1940.
14. Vatutin E.I., Volobuev S.V., Zotov I.V. Kompleksnyy sravnitel'nyy analiz kachestva razbieniy pri sinteze logicheskikh mul'tikontrollerov v usloviyakh prisutstviya tekhnologicheskikh ogranicheniy [A comprehensive comparative analysis of quality criteria in the synthesis of logical Multicontroller in the presence of technological constraints], Parallel'nye vychisleniya i zadachi upravleniya (PACO’08) [Parallelnye computing and control problems (PACO’08)]. Moscow: IPU RAN, 2008, pp. 643-685.
15. Vatutin E.I., Titov V.S. Sravnenie metodov sinteza razbieniy parallel'nykh algo-ritmov logicheskogo upravleniya s ispol'zovaniem dvukhparametricheskikh diagramm [Comparison of methods for the synthesis of separations of parallel logic control algorithms using two-parameter diagrams], Raspoznavanie [Detection], 2012, pp. 138-140.
16. Vatutin E.I., Titov V.S. Sravnenie metodov sinteza razbieniy graf-skhem parallel'-nykh algoritmov s ispol'zovaniem dvumernykh diagramm [Comparison of methods for the synthesis of partitions of a graph-schemes of parallel algorithms using a two-dimensional charts], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [News of the South-Western state University], 2012, No. 3 (42), pp. 66-74.
17. Vatutin E.I., Titov V.S. Ispol'zovanie dobrovol'nykh raspredelennykh vychisleniy na platforme BOINC dlya analiza kachestva razbieniy graf-skhem parallel'nykh algoritmov [The use of voluntary distributed computing on the BOINC platform to analyze the quality of the splits graph-schemes of parallel algorithms], Parallel'nye vychisleniya i zadachi upravleniya (PACO’12) [Parallel computing and control problems (PACO’12)]. Moscow: IPU RAN, 2012, Vol. 2, pp. 37-54.
18. Vatutin E.I., Dremov E.N., Martynov I.A., Titov V.S. Metod vzveshennogo sluchaynogo perebora dlya resheniya zadach diskretnoy kombinatornoy optimizatsii [The method of weighted random search for solving problems of discrete combinatorial optimization], Izvestiya VolGTU. Seriya: Elektronika, izmeritel'naya tekhnika, radiotekhnika i svyaz' [News of Volgograd state technical University. Series: electronics and instrumentation engineering,
radio engineering and communication], 2014, No. 10 (137), Issue 9, pp. 59-64.
19. Vatutin E.I., Kolyasnikov D.V., Martynov I.A., Titov V.S. Metod sluchaynogo perebora v zadache postroeniya razbieniy graf-skhem parallel'nykh algoritmov [The method of random search in the task of building a splits graph-schemes of parallel algorithms], Mnogoyadernye protsessory, parallel'noe programmirovanie, PLIS, sistemy obrabotki signalov [Multi-core processors, parallel programming, FPGA, signal-processing system]. Barnaul: Barnaul, 2014, pp. 115-125.
20. Vatutin E.I., Zotov I.V. Programmnaya sistema dlya postroeniya razbieniy parallel'nykh upravlyayushchikh algoritmov [A software system for separations of parallel logic control algorithms], Trudy V mezhdunarodnoy konferentsii «Identifikatsiya sistem i zadachi upravleniya (SICPRO’06)» [Proceedings of the V International conference "system Identification and control problems (SICPRO'06)"]. Moscow: Institut problem upravleniya im. V.A. Trapeznikova RAN, 2006, pp. 2239-2250.
21. Vatutin E.I., Zotov I.V. Vizual'naya sreda sinteza razbieniy parallel'nykh algoritmov logicheskogo upravleniya [The visual environment of synthesis of separations of parallel logic control algorithms], Svidetel'stvo ob ofitsial'noy registratsii programmy dlya EVM № 2007613222 ot 30.07.07.

Comments are closed.