2019 № 4(45)

CONTENTS

1. Khachaturov R. V. Application of the equivalence set method for solving multicriterial optimization problems and inverse problems of mathematical physics

2. Moiseenko V. V. Scientific Design at the Academic Institute (Retrospective analysis)

3. Tynymbayev S., Aitkhozhayeva Y. Zh., Adilbekkyzy S., Berdibayev R. Sh. Development and simulation of the schematic diagram for the modular reduction device

4. Akhmed-Zaki D. Zh., Lebedev D. V., Malyshkin V. E., Perepelkin V. A. Automation of distributed numerical programs construction in LuNA system on a model application example

Khachaturov R. V.

Dorodnicvn Computing Centre, FRC CSC RAS, 119333, Moscow, Russia

APPLICATION OF THE EQUIVALENCE SET METHOD FOR SOLVING MULTICRITERIAL OPTIMIZATION PROBLEMS AND INVERSE PROBLEMS OF MATHEMATICAL PHYSICS

UDK 519.7

Currently, in various fields of science, economics, when planning the development of countries, regions, mineral deposits, solving inverse problems of mathematical physics, in the space industry, etc. it becomes highly important to solve multicriteria problems when it is necessary to find the optimal solution not by one, but simultaneously by several criteria. This paper describes the application of the equivalence set method for solving multicriteria discrete optimization problems and inverse incorrect problems of mathematical physics. A comparison of the proposed method with the method of finding the Pareto optimal solutions and the method of successive concessions is given. The advantages of the equivalence set method are shown in comparison with these well-known methods for solving multicriteria problems.

The multicriteria optimization problems arise when it is necessary to optimize a vector function

F (X) = of dimension m > 1:

that is, when there are several independent criteria y₁ = ,..., y_m = by which to find the best solution. In this case, it is necessary to apply more complex methods than in the case of a single criterion. There are various approaches to solving such problems. In this paper, the equivalence set method is considered, its main properties are described, and its advantages are shown in comparison with other methods for solving multicriteria discrete optimization problems.

The essence of this method is as follows:

For each criterion the problem of single-criterion optimization is solved and the optimal solution is found.
For each criterion in the multidimensional pseudometric space of criteria, is found a set of solutions that are close to optimum by this criterion, that is, differing from the optimal value by no more than a given number which we will call tolerance by the corresponding criterion. The found set itself is denoted by . In the case of maximization, it will be determined as follows:

Then a set of solutions is found, which is the intersection of all such sets by all criteria . We denote this set by , formally defined as follows:

The resulting set is called the equivalence set (Fig. 1). Any solution from it satisfies all formalized criteria and can be taken by an expert as a final decision. The described method does not have a disadvantage of the method of finding the set of Pareto optimal solutions, since when adding an additional criterion the equivalence set never grows, but, on the contrary, narrows as a rule, which will be formally proved below in Theorem 1.

On example of the problem of self-focusing of plane x-ray pulses in a plasma, it is shown how this method can be used to solve inverse problems of mathematical physics.

Thus, a generalized equivalence set method is obtained that has the following properties:

The obtained equivalence set

is always obviously not empty.

The equivalence set always contains at least one Pareto-optimal solution. If the equivalence set contains a unique solution, then this solution is Pareto optimal.
The search area of the equivalence set is significantly narrowed without loss of any solutions.

It is shown that the determining methods of are regularization methods [10] for incorrect problems in the pseudometric space of criteria (even if there are some more informal

criteria), and each solution is a solution to such a problem. Thus, the equivalence set method can be considered a generalization of the regularization method for ill-posed problems in a multidimensional pseudometric space D of several criteria in the discrete case. This makes it possible to apply the equivalence set method both for solving multicriteria optimization problems and for solving inverse problems of mathematical physics.

Key words: equivalence set method, set of Pareto-optimal solutions, multicriteria problems, discrete optimization, self-focusing, inverse ill-posed problems, regularization method.

References

Khachaturov R. V. Mnogokriterial’naya optimizatsiva v psevdometricheskom prostranstve kriterivev na primere obshchev modeli devatel’nosti predprivativa // ZHVM i MF. 2016. V. 56. N 9. P. 1602-1613.
Khachaturov R. V. Single- and Multiobjective Optimization on the Lattice of Cubes // Computer and Systems Sciences International. 2018. V. 57. N 5. P. 750-758.
PODINOVSKIY V. V., Nogin V. D. Pareto — optimal’nyye resheniva mnogokriterial’nvkh zadach. M.: Nauka, 1982.
MAS-COLLEL A., Whinston M. D., Green J. R. Microeconomic theory. N. Y.: Oxford University Press, 1995.
Mulen E. Kooperativnove prinvative resheniv: aksiomv i modeli. M.: Mir, 1991.
SHTOYYER R. Mnogokriterial’naya optimizatsiva (teoriva, vvchisleniva i prilozheniva). M.: Radio i svvaz’, 1992.7
Gubko M. V., Novikov D. A. Teoriva igr v upravlenii organizatsionnvmi sistemami. M.: Sinteg, 2002.
Nogin V. D. Prinvative resheniv vo mnogokriterial’nov srede: kolichestvennvy podkhod. M.: Fizmatlit, 2002.
Lotov A. V., Pospelova I. I. Mnogokriterial’nyye zadachi prinvativa resheniv: Uchebnove posobive. M.: MAKS Press, 2008.
Tikhonov A. N., Arsenin V. YA. Metody resheniva nekorrektnykh zadach. M.: Nauka, 1979.
Elton R. C. X-ray lasers. New York: Acad. Press, 1990.
Akhmanov S. A. Sverkhsil’nyye svetovvve polva v nelinevnov optike, fizike plazmv i tekhnike rentgenovskikh istochnikov // Itogi nauki i tekhniki. Sovremennvve problemv lazernov fiziki. M.: VINITI, 1991. T. 4. S. 15-18.
Shen I. R. Printsipv nelinevnov optiki. M.: Nauka, 1985.
Andreyev A. V., Khachaturov R. V. Samofokusirovka impul’snogo rentgenovskogo izlucheniva v plazme // Vestnik MGU. Seriva 3: Fizika, astronomiva. 1995. T. 36. N 3. S. 25-33.
Khachaturov R. V. Vychislitel’nyy metod issledovaniva protsessa samofokusirovki rentgenovskogo izlucheniva v plazme // ZHVM i MF. 1996. T. 36. N 1. S. 103-111.

article

Bibliographic reference: Khachaturov R. V. Application of the equivalence set method for solving multicriterial optimization problems and inverse problems of mathematical physics //journal “Problems of informatics”. 2019, № 4. P. 7-41. DOI: 10.24411/2073-0667-2019-00014

Moiseenko V. V.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

SCIENTIFIC DESIGN AT THE ACADEMIC INSTITUTE
(RETROSPECTIVE ANALYSIS)

UDK 004

The article is devoted to the analysis of performance indicators, subsystems design". It is

part of the system „The scientific process of an academic institute." The functioning of this subsystem, those, the implementation of scientific projects of various kinds, provide the scientific staff of the institute. The process of carrying out scientific projects includes writing reports, scientific articles, monographs, development of software packages. This activity of scientific personnel and is the result of the functioning of the subsystem.

The article calculates and analyzes the financial indicators of the subsystem, age characteristics of managers and executors of scientific projects and indicators the activity of scientists in concluding contracts and agreements, bringing additional financing.

Using the integrated databases „Scientific Personnel" and „Scientific Projects", as well as data from the Institute’s annual reports, values are calculated and dynamics determined these values of the following indicators for the period 2001-2017:

The ratio of the proportion of funding for tenders and projects included in the state task. It is defined as a share. State-funded project financing from total funding;
The ratio of the proportion of financial receipts for work performed on grants, competitive projects, contracts and contract negotiations. This ratio is defined as the share of financial receipts for completed works on grants, competitive projects, contracts and economic agreements of the total funding:
The average number of ongoing research projects (grants and competitive projects, contracts and agreements) per scientific worker;
The average age of managers of scientific projects of all kinds;
The average age of executors of scientific projects of all kinds.

The calculated values of the first coefficient showed that the proportion of financing projects included in the state assignment is reduced. The second and third coefficients are interpreted as indicators of the activity of scientists Institute in the implementation of scientific projects of various kinds, bringing additional funds allocated both for raising wages and for acquiring equipment and scientific trips. From the calculation results it is clear that this activity increased. Analysis of age characteristics allows us to conclude that the most active both as managers and as project executors, are scientists aged 50-60 years.

Key words: subsystem „Scientific Design", indicators of the subsystem, research funding, age characteristics of performers projects.

References

Moiseenko V. V. Imitacionnoc modclirovanic nauchnogo processa akadcmichcskogo instituta // Problemv informaliki. 2014. № 4. S. 80-87.
Rudko T. V. Grantovava poddcrzhka nauchno-issicdovatcl’skill procktov: vozmozhnosti, istochniki, rekomendacii // Tomsk, SibMGU. [Electron, res.]: http://www.ssmu.ru.
Diligenskij N. V., Capenko М. V., Davydov А. N. Ierarhicheskava sistema obobshchennyh harakteristik effektivnosti nauchnyh issledovanij // Materialy 14-go Vseross. simp., Moskva, 9-11 apr. 2013 g. S. 61-63.
Troshin D. V. Metodika ocenki rezul’tatov nauchno issledovatel’skih rabot // Ekonomicheskij analiz: teoriva i praktika. 2014. № 4. S. 50-59.
Usol’cev I. A. Konceptual’nye osnovv ocenki potenciala intellektual’nyh produktov nauchnoj sferv // ZHurnal ekonomicheskoj teorii. 2011. № 2. S. 159-163.
Moiseenko V. V., Rodionov A. S. Vozrastnaya zavisimost’ soavtorstva pri provedenij nauchnyh issledovanij v akademicheskom institute // Problemv informatiki. 2017. № 1. S. 62-73.
Karpachev G. I., Moiseenko V. V. Nekotorve voprosv retrospektivnogo analiza strukturv i devatel’nosti nauchnyh kadrov akademicheskogo instituta // Problemv informatiki. 2009. № 1.

article

Bibliographic reference: Moiseenko V. V. Scientific design at the academic institute (retrospective analysis) //journal “Problems of informatics”. 2019, № 4. P. 33-41. DOI: 10.24411/2073-0667-2019-00015

Tynymbayev S., Aitkhozhayeva Y. Zh., Adilbekkyzy S., Berdibayev R. Sh.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

DEVELOPMENT AND SIMULATION OF THE SCHEMATIC DIAGRAM FOR THE MODULAR REDUCTION DEVICE

UDK 004.312; 004.056.55

The article is devoted to the development of a schematic diagram of a high-speed modular reduction device for the hardware implementation of asymmetric cryptographic algorithms. The problem of increasing the speed of asymmetric cryptosystems through the use of hardware implementation and accelerating the most complex basic operation of asymmetric cryptographic algorithms - modular reduction has been the subject of much research. However, in most solutions, an increase in speed is achieved by increasing hardware costs, which are directly proportional to the capacity of the given numbers. Therefore, their use is problematic when converting multi-bit numbers.

One of the solutions to the problem is the development of not only high-speed, but also optimal in terms of hardware costs, circuit solutions of modular reduction devices. The structure of a high-speed device for reducing a 2n-bit number A by an n-bit module P(R = A mod P) with optimal hardware costs was proposed. This structure consists a control unit, a shift register unit, a former of partial remainder and block of multiples of module P. The device implements a modified and adapted method of division with a shift of the dividend, where at each step of the calculation, the value of either tripled, doubled, or single value of the module P is subtracted from the higher bits of the previous remainder shifted two bits to the left. This approach allows to accelerate the calculation bv reducing a 2n-bit number A by the n-bit module P twice.

CAD Quartus Prime Lite Edition was used for staged development of schematic diagram of the device. The implementation of the circuit is focused on the low-budget board DEO-CV with a Field-Programmable Gate Array (FPGA) of the Cyclone VE base family, manufactured by Altera - 5CEBA4F23C7. The main units of the device were designed, the operation of which was checked using functional and timing simulations and their symbol modules were obtained. Schematic diagram of the device is developed by using symbol modules. The results of timing modeling of the device and the block of the shift register - one of the main blocks of the modular reduction device are presented. Functional and timing modeling with specific examples showed the correctness operation of the device. A circuit of the device for high-speed reduction of numbers modulo at the level of register transfers (RTL) is obtained. After compiling the schematic diagram, a report was received on the specialized FPGA resources Cyclone VE 5CEBA4F23C7 involved, which shows low hardware costs. A comparative analysis of the used and available resources shows that approximately 0.6 % of the available resources of the low-budget FPGA Cyclone VE 5CEBA4F23C7 device were used to implement the modular reduction device for n = 6. This confirms the possibility of using the specified FPGA for the implementation of modular reduction device for big numbers n 1000. A high-speed device can be used both in crypto-processors and in digital computing devices to accelerate the division operation.

Key words: asymmetric crypto algorithms, hardware encryption, modular reduction, schematic diagram, simulation.

References

Hars L., Joye M., Quisquater J. J. (eds). Long Modular Multiplication for Cryptographic Applications // Cryptographic Hardware and Embedded Systems — CHES 2004. Lecture Notes in Computer Science, 2004. V. 3156. Springer, Berlin, Heidelberg.
Petrenko V. I., Sidorchuk A. V., Kuz’minov J. V. Ustrovstvo diva formirovaniva ostatka po proizvol’nomu modulvu // Patent RU 2368942 C2 (2009).
Pankratova I. A. Teoretiko-chislovve metodv kriptografii. Tomsk State University. 2009. S. 120.
Zakharov V. M., Stolov E. L., Shalagin S. V. Ustrovstvo diva formirovaniva ostatka po zadannomu modulvu // Patent RU 2421781 C2 (2011).
Kopytov V. V., Petrenko V. I., Sidorchuk A. V. Ustrovstvo diva formirovaniva ostatka po proizvol’nomu modulvu ot chisla // Patent RU 2445730 C2 (2012).
Skryabin I., Sakhin Iu. Kh. Operatsii podderzhki algoritmov shifrovaniva s otkrvitym klvuchom i ih realizatsiva v mikroprotsessore Elbrus. 2013 / [Electron, resource]: http://www. myshared.ru/slide/213088.
Pisek E., Henige T. M. Method and apparatus for efficient modulo multiplication // Patent US 8417756 B2 (2013).
Lambert R. J. Method and apparatus for modulus reduction // Patent US 08862651 B2. (2014).
Aitkhozhayeva E. Zh., Tynymbayev S. T. Aspektv apparatnogo privedeniva po modulvu v asimmetrichnov kriptografii // Bulletin of National Academy of Sciences of the Republic of Kazakhstan. N 5 (375). P. 88-93.
BOCKES M., Pulkus J. Method for arbitrary-precision division or modular reduction // Patent US 9042543 B2 (2015).
Yu H., Bai G., Hao H., Wang J., Yap C. (eds). Efficient Modular Reduction Algorithm Without Correction Phase // Frontiers in Algorithmics. FAW 2015. Lecture Notes in Computer Science,
V. 9130. Springer, Cham.
Aitkhozhaeva Y. Zh., Tynymbayev S. T. Formirovatel’ ostatka po proizvol’nomu modulvu ot chisla // Patent KZ 30983 (2016).
Kovtun M., Kovtun V. Obzor i klassifikaciva algoritmov deleniva i privedeniva pomodulvu bol’shih celvh chisel diva kriptograficlieskili prilozheniv / Kompaniva Savfer. 2017. [Electron, resource]: http://docplayer.ru/30671408-0bzor-i-klassifikaciya-algoritmov-deleniya-i-privedeniya-po-modulyu-bolshih-celyh-chisel-dlya-kriptograficheskih-prilozheniy.html.
Tynymbayev S. T., Aitkhozhayeva Y. Zh., Adilbekyzy S. Ustrovstvo bvstrogo privedeniva chisel po modulvu // Svidetel’stvo MYU RK о gosudarstvennov registracii prav na ob’ekt avtorskogo prava. 2018. N 1422 (IS 2562).
Tynymbayev S. T., Aitkhozhayeva Y. Zh., Adilbekkyzy S. High speed device for modular reduction // Bulletin of National Academy of Sciences of the Republic of Kazakhstan. 2018. V. 6 (376). S. 147-152.
Adilbekkyzy S., Aitkhozhayeva Y. Zh., Tynymbayev S. T. Modelirovanie formirovatelva chastichnvh ostatkov ustrovstva privedeniva po modulvu // Evraziskiv Soyuz Uchenvh (ESU). 2019. N 6 (63), 2 chast’. S. 17 51.

article

Bibliographic reference: Tynymbayev S., Aitkhozhayeva Y. Zh., Adilbekkyzy S., Berdibayev R. Sh. Development and simulation of the schematic diagram for the modular reduction device //journal “Problems of informatics”. 2019, № 4. P. 42-52. DOI: 10.24411/2073-0667-2019-00016

Akhmed-Zaki^1,2 D. Zh., Lebedev^1,2 D. V., Malyshkin^3,4,5 V. E., Perepelkin^3,4 V. A.

¹A1-Farabi Kazakh National University,050040, Almaty, Kazakhstan
²University of International Business,050010, Almaty, Kazakhstan
³Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

⁴Novosibirsk State University, 630090, Novosibirsk, Russia

⁵Novosibirsk State Technical University, 630092, Novosibirsk, Russia

AUTOMATION OF DISTRIBUTED NUMERICAL PROGRAMS CONSTRUCTION IN LUNA SYSTEM ON A MODEL APPLICATION EXAMPLE

UDK 004.4’2

The paper concerns the problem of efficient execution of a distributed numerical program, defined in a high-level language LuNA. LuNA is a programming language and a parallel program construction automation system for implementation of numerical algorithms on multicomputers (parallel computers with distributed memory). In LuNA system an application algorithm is described in a portable way, which brings the problem of its efficient execution on given hardware and data. To overcome this generally hard problem supplementary information called recommendations is demanded from the programmer. The programmer describes key properties of the application algorithm, as well as his insight on the preferred way of its efficient execution with a domain-specific language (part of the LuNA language), having no need to do low-level parallel programming, such as programming communications, resources distribution, workload balancing, etc. LuNA system takes advantage of the provided information by constructing more efficient parallel program, which implements the application algorithm. Implementation of this approach in LuNA programming system is concerned. The application algorithm is represented as an enumeration of two sets - the set of immutable pieces of data called data fragments and the set of side-effect-free sequential processes on these data called computational fragments. Computational fragments have a number of input and output data fragments assigned to define informational dependencies between computational fragments. Supplementary information (the recommendations) is provided as code annotations to express two kinds of programmer’s knowledge. The first is informational recommendations, which describe key properties of the application algorithm, which are hard to obtain automatically, but are significant from the execution performance viewpoint. The second is prescriptive recommendations, which prescribe the way the application algorithm should be executed. In particular, resources distribution and computations scheduling are described. Recommendations are orthogonal to application algorithm specification in sense that they do not affect the values computed, but only influence on how the computations are conducted. In LuNA system the application algorithm is described with LuNA language (LuNA stands for Language for Numerical Algorithms), while the bodies of computational fragments are defined with sequential procedures in C++- The procedures are compiled by a conventional serial compiler, therefore LuNA compiler only has to deal with distributed execution issues. Instead of run-time interpretation of the algorithm, i. e. distributed management of data and computational fragments, which was the case for the previous LuNA releases, the multi-agent approach is employed. With this approach each computational fragment is considered an agent, operating in a passive run-time environment. Each agent is controlled by a program, which is statically generated by LuNA-compiler (each kind of computational fragment has a different program generated). This program generally consists of migrating the agent to a remote computing node, requesting and awaiting input data fragments, compution output data fragments and doing some finalization jobs. The agent’s program is formulated in C++, which allows to employ a well-developed conventional compiler to optimize it and significantly reduce run-time overhead, previously imposed by interpretation of the same logic. Despite the fact, that agents’ programs are generated statically, the behavior of the multiagent system is dynamic, leaving the room for dynamic load balancing, computations scheduling, dynamic network routing, etc. In particular, the exact node for an agent to migrate to may be defined in run-time. The performance tests were conducted on a model 3D heat equation iterative solver on a rectangular mesh. Each iteration mainly consists of solving tridiagonal equations in each of directions using the pipelined Thomas algorithm. The tests conducted showed significant performance improvement of LuNA system over its previous releases, but the reference hand-coded MPI-based implementation still outperforms LuNA in about 10 times. System code optimization and intelligent system algorithms are to be developed. However, 10 times slowdown may be tolerated in some cases due to the fact that LuNA-program development is easier and less error-prone, and that future LuNA releases will improve the performance without the need to change existing applications.

Key words: distributed programs construction automation, fragmented programming technology, LuNA system.

References

ANSYS Fluent Web Page / [Electron. Res.]: https://www.ansys.com/products/fluids/ ansys-fluent, accessed: 2019.08.01.
Phillips, J., Braun, R., Wang, W., Gumbart, J., Tajkhorshid, E., Villa, E., Chipot, C., Skeel, R., Kale, L. Schulten, K. Scalable molecular dynamics with NAMD // Journal of Computational Chemistry. 2005. N 26. P. 1781-1802.
MathWorks MATLAB official web-site / [Electron. Res.]: https://www.mathworks.com/ products/matlab.html, accessed: 2019.08.01.
GNU Octave Web Site / [Electron. Res.]: https://www.gnu.org/software/octave/, accessed: 2019.08.01.
WOLFRAM MATHEMATICA Web Site / [Electron. Res.]: http://www.wolfram.com/ mathematica/, accessed: 20195.04.01.
Robson, M., Buch, R., Kale, L. Runtime Coordinated Heterogeneous Tasks in Charm++ // In: Proceedings of the Second Internationsl Workshop on Extreme Scale Programming Models and Middleware, 2016.
Wu W., Bouteiller A., Bosilca G., Faverge M., Dongarra J. Hierarchical DAG Scheduling for Hybrid Distributed Systems // In: 29th IEEE International Parallel & Distributed Processing Symposium, 2014.
Bauer, M., Treichler, S., Slaughter, E., Aiken, A. Legion: Expressing Locality and Independence with Logical Regions // In: the International Conference on Supercomputing (SC 2012), 2012.
MALYSHKIN, V., Perepelkin, V. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // In: Parallel Computing Technologies. LNCS. 2011. N 6873. P. 53-61.
Sterling, Т., Anderson, М., Brodowicz, М. A Survey: Runtime Software Systems for High Performance Computing // Supercomputing Frontiers and Innovations: an International Journal. 2017. N 4 (1). P. 48-68. DOI: 10.14529/jsfil70103.
Thoman, P., Dichev, K., Heller, T. et al. A taxonomy of task-based parallel programming technologies for high-performance computing // The Journal of Supercomputing. 2018. N 74 (4). P. 1422-1434. DOI: 10.1007/sll227-018-2238-4.
Valkovsky, V., MALYSHKIN, V. Synthesis of parallel programs and systems on the basis of computational models. Nauka, Novosibirak, 1988.
Akhmed-Zaki, D., Lebedev, D., Perepelkin, V. // J Supercomput, 2018. [Electron. Res.]: https://doi.org/10.1007/sll227-018-2710-1.
Sapronov, I., Bykov, A.: Parallel pipelined algorithm // Atom 2009. N 44. P. 24-25 (in Russian).
Joint Supercomputing Centre of Russian Academy of Sciences Official Site / [Electron. Res.]: http://www.jscc.ru/, accessed: 2019.08.01

article

Bibliographic reference: Akhmed-Zaki^1,2 D. Zh., Lebedev^1,2 D. V., Malyshkin^3,4,5 V. E., Perepelkin^3,4 V. A. Automation of distributed numerical programs construction in luna system on a model application example //journal “Problems of informatics”. 2019, № 4. P. 53-64. DOI: 10.24411/2073-0667-2019-00017

Main menu

You are here

2019 № 4(45)