Speaker
Eduard Vatutin
(Southwest State University)
Description
One of promising approaches to the logic control systems (LCS) design is their implementation within logic multicontrollers (LMC) basis which are presented as the collective of similar controllers connected by network with regular topology [1]. One of the problems corresponding to a class of discrete combinatorial optimization problems [2] that arise during LMC design is a problem of getting separations [3]. Quality of its decision has direct influence on hardware complexity and speed characteristics of designed LMC. To solve the problem in practice heuristic methods are used which are characterized by different quality of decisions and different computing time costs for its forming.
Computing experiments performed with samples of graph-schemes of parallel control algorithms with pseudorandom structure and customizable settings show dependencies of separations quality as on the size of the problem (number of vertices N within graph-scheme) as on power of restrictions. For more detailed analysis significant computing resources are necessary therefore needed computations were organized within volunteer computing project Gerasim@Home based on BOINC platform. The main aim of computations was getting separations for selected points of space formed by the size of the problem N and restrictions and (for number of logic control signals received from controlling object and for size of microprogram memory respectively) followed by pair comparison of samples with estimated quality parameters, calculating two dimensional slices of parameters space and its analysis.
At this moment analysis of two slices of space was performed (1≤N≤700, 3≤Xmax≤150 and 1≤N≤600, 3≤Wmax≤200) for methods of S.I. Baranov, its modification with adjacency restriction and for parallel-sequential decomposition method. For small area of space (1≤N≤200) research opportunities of random search method with fixed number of iterations was performed. Corresponding computations were performed within Gerasim@Home project from July 2010 to March 2016 (with some breaks for data analysis, server works and different problems computations). Resulting volume of raw experimental data was more than 500 GB. During calculations within the project real performance made up about 2–3 TFLOPS that was provided by more than 2000 volunteers from 69 countries, attracted more than 1000 personal computers.
After analyzing of given results a set of conclusions and recommendations was formulated and published. First, strong zone dependence of decisions quality on the point of parameters space was confirmed. It is revealed that the area of preferable use of S.I. Baranov method is the zone of weak or absent restrictions, for method of parallel-sequential decomposition – zone of strong and very strong restrictions, and adjacent modification of S.I. Baranov method has compromise position in the area of mean force restrictions. Random search method may be used in the strong restrictions zone for graph-schemes with small number of vertices. With use of given dependences zones of insensitivity are identified where changing the power of restrictions has influence only on hardware complexity of controllers and doesn’t change its functions characteristics. This feature may be used during structural-parametric optimization of LMC structure and allows (by some times) to reduce significantly its hardware complexity through selecting optimal structure with big number of relatively simple controllers.
As future investigations it is planned to expand studied areas of parameter space (by N to 800, by Xmax to 200 and by Wmax to 300), at this moment post processing of corresponding experiments results is taking place. Also development, program optimization and approbation of additional program implementations are planned that correspond to more intellectual well known iterative heuristic methods of getting separations and its multistage modifications that has less computing time costs, higher quality of decisions and convergence rate.
The work was performed within the base part of the state assignments for the Southwest State University in 2014–2017, number 2246 and under support of President grant MK-9445.2016.8. The authors would like to thank all volunteers who took part in the calculation within the distributed computing project Gerasim@Home. The authors also wish to thank Anna Vayzbina for assistance in preparing the English version of the article.
Bibliography
1. Organization and synthesis of microprogram multimicrocontrollers (in Russian) / Zotov I.V., Koloskov V.A., Titov V.S. et al. Kursk, 1999. 368 p.
2. Vatutin E.I., Titov V.S., Emelyanov S.G. Basics of discrete combinatorial optimization (in Russian). M.: ARGAMAC-MEDIA, 2016. 270 p.
3. Vatutin E.I. Logic multicontrollers design. Getting separations of parallel graph-schemes of algorithms (in Russian). Saarbrucken: Lambert Academic Publishing, 2011. 292 p.
Primary author
Eduard Vatutin
(Southwest State University)
Co-authors
Mr
Sergey Valyaev
(BOINC.ru portal)
Mr
Vataly Titov
(Southwest State University)
