2017 № 2 (35)







Nazarov A.A., Anisimova A.A.

Tomsk State University,  634050, Tomsk, Russia


UDC 519.872

In this paper, we consider a M/M/1 retrial queuing system with two phases of essential service. Customers arrive at the system  according to a Poisson process with arrival rate lambda. Service times follow an exponential distribution with parameters mu1 and mu2 for the first and the second phase respectively. If a customer finds the server free, it is served immediately; otherwise the customer joins the orbit. Customers in an orbit come back to be served after intervals of time exponentially generated with parameters sigma1 and sigma2  for the first and the second phase respectively. If the server is free, it will receive the service; otherwise it will be re-inserted into the orbit. Each phase includes one server and one orbit. The aim of this paper is to obtain the mean values of the number of customers in the orbits using the asymptotic analysis method under delay condition of orbit. The results of asymptotic analysis and the results of simulation are compared.

Key words:  retrial queuing system, two-phase system, Poisson process, delays condition of orbit.

Bibliographic reference: Nazarov A.A., Anisimova A.A. Asimptotic analysis of two-phase retrial queuing system M/M/1 under delay condition of orbit //journal “Problems of informatics”. 2017. №2 P. 4-12


Pankratov S.B.

A. P. Ershov Institute of Informatics Systems (IIS), Siberian Branch of the Russian Academy of Sciences, 630090, Novosibirsk, Russia


UDC 004.43

High-level programming languages are the main development tool for software. The task of translating the source code of programs into a representation executable on a computer system is solved by the compiler. Compilers have high quality requirements since correctness of compiled programs significantly depends on compiler correctness. And software defects caused by errors in the compiler are difficult to identify, and impossible to correct without interference in the compiler itself. The correctness of the compiler is a necessary requirement for the correct operation of the software compiled by it. Therefore, the most important stage in the development of the compiler is verification.

Due to complexity of programs as compiler input data and their transformations, the task of compiler verification is very tedious and difficult. And in the case of using an optimizing compiler, it is also algorithmically unsolvable. But we can consider the behavior of the compiler on some limited class of programs. We cannot compare the result of the transformation with some reference, we can only consider some properties of the translation produced. For example, if the compilation of the same program without optimizations succeeds, and with optimizations leads fails in compiler, then we can talk about the presence of errors in the optimization code.

Recent widespread of multicore processors and graphics core integrated to CPU emphasized the problem of the transition from single-threaded to multithreaded computing and re-usage of graphics core for general purpose heterogeneous parallel computations in particular. Intel introduced GFX-offload extension for C++ language in addition to the some open standards for parallel computing: OpenMP, OpenCL, Cilk Plus. That helps to utilize the powers of integrated graphics for general purpose computation. Taking all these facts into account, verification of implementations of parallel C++ extension in compiler is particularly important.

Automatic test generation is an important part of the verification, because tests written by hand usually can't effectively cover all possible combinations of language constructions, as well as all situations of optimization's application. The QA command of the Intel compiler chose an approach using a parametric context-free grammar, described by a special meta-language for test generator. Parametric context-free grammars have proven themselves as a good formalism for constructing generators of semantically correct and compiler-specific tests with deterministic behavior. They were distinguished by the clarity of the description of generated test programs, as well as the flexibility and convenience in working with their context. However, this approach was used only to generate single-threaded tests executed on the central processor. Therefore it is an open question about the possibility of using an already existing generator of single-threaded tests based on parametric context-free grammars, for generating tests for multi-threaded extensions of the C ++ language, like GFX-offload.

In this paper, we presenting an approach to automate test creation for the verification of the GFX-offload compiler, based on a generator that uses grammars to generate syntactically correct executable tests. Also we will show some results of using this approach for compiler's verification at Intel Corporation.

Key words: QA, compilers, offload, test generation, GPU, grammar.

1. Stasenko A. P. Generation of executable tests for compiler //  Parallel programs construction and optimization. 2008. 16. P. 301–313,
2. Aho A. V., Sethi R., Ullman J. D. Compilers: principles, techniques, and tools. Boston: Addison-Wesley Longman Publishing Co., Inc., 1986. P. 796.
3. Hanford K. V. Automatic generation of test cases // IBM Systems Journal. NY: IBM, Dec. 1970. Vol. 9. P. 242–257.
4. Purdom P. A sentence generator for testing parsers // Behavior and Information Technology, July 1972. Vol. 12. N 3. P. 366–375.
5. Hutchison J. S., Duncan A. G. Using Attributed Grammars to Test Designs and Implementation // In Proc. of the 5th international conference on Software engineering, 1981. P. 170–178.
6. Bazzichi F, Spadafora I. An automatic generator for compiler testing // IEEE transactions on Software Engineering. NY: IEEE, 1982. Vol. SE-8. P. 343 –353.
7. Kossatchev A. S., Posypkin M. A. Survey of compiler testing methods // Programming and Computing Software. NY: Plenum Press, 2005. Vol. 31, N 1. P. 10–19.

Bibliographic reference: Pankratov S.B.  Automatic test generation for intel GFX-offload compiler //journal “Problems of informatics”. 2017. №2. P. 13-23.


Samigulina G.A., Nyussupov A.T.

Institute of Information and Computational Technologies, 050010, Republic of Kazakhstan, Almaty


UDC 004.85:004.89

The article has been conducted an analytical review of the current state of  distance learning (DL) on the basis of multiagent approach. The most widespread intelligent systems in DL have been discussed. The hybrid systems have been isolated based on various combinations of intelligent methods (artificial neural networks, evolutionary algorithms, artificial immune systems, fuzzy logics, etc.). Such systems provide an opportunity to identify a global strategy of supplying of educational material, and effectively arrange for the training in DL and personalize it for specific groups of learners. The expert systems have been marked which have the ability to plan courses in DL and use the problem-oriented methodology of knowledge formalization, which increase the speed and efficiency of designing educational courses.

Smart learning is widely used in education, which improves DL due to the penetration of smart components. It is revealed that Smart-learning can provide many useful opportunities for the learners, but it also positively affects the efficiency of assimilation of course material. Using the multiagent system (MAS) is of immediate interest in DL on the basis of such intelligent agents, such as: gaming, cloud, cognitive, personal, ontological, collective, support, and decision-making, etc. The cognitive factors have particular importance of interaction of students with the DL system which is based on emotion and mental opinions tracking by agents, among leaners during the learning process. Emotional mechanism allows to know the most appropriate pattern of interaction with the learner, on the basis of desires and emotions demonstrated by the students. Cognitive agents improve communication between users and provide personal support compared to neutral agents. It is revealed that this technology gives the opportunity to study the causes of different events and make predictions of learning outcomes.

The attention is focused on flexible ways of organizing knowledge with the help of agents based on personal or collective training as well as ontological methods of structuring data. Agents of collective learning can analyze the activity of students in the group to identify their role in the team and diagnose the state of cooperation (taking into account the balance of team roles in an ideal situation). Multiagent systems of personal training are able to adapt to the characteristics of the students and to use the experience gained for the modelling of optimal education process. The features of the ontological approach are distinguished, which allow to efficiently distribute agents and to improve performance for МАS.

The importance of cloud MAS has been noted, which allows to get an education on computers with small computing power. The effectiveness of the cloud-based MAS DLapplication has been highlighted in comparison with traditional DL: the expansion of learning opportunities, broad access to information from various devices (computers, smartphones and tablets), stronger collective and collaborative studying, individualized learning, etc. Cloud technology allows agents to process multi-dimensional data directly on the servers and reduce the load information transmission in DL. The activities of these agents open the way for the creation of a common training base, in which both private and public educational institutions will involve. It is analyzed that this technology can treat multidimensional data directly on the servers and reduces the load on leaner’s devices.

MAS support and decision-making in DL have been also reviewed enabling the students to find the right decisions when problems arise. These systems generate the process of learning and support the work of the student and the teacher, and in a timely manner to assist them in the learning environment. It is found out that through the support of students, efficiency is increased and the process of learning in DL is significantly simplified.

Much attention is paid to the role of the agent-oriented approach to improving the flow of knowledge in public educational institutions. It has been found out that such systems can act as a regulatory component of the state educational system.

The implementation of agents in a learning environment where the behavioral factor dominates,allows to understand in what direction to develop basic education and increase its effectiveness. It is determined that such MAS can simulate training program before applying it in the real education environment. The game approach of MAS has been considered for better assimilation of information in DL. The method used allows students to gain experience of conversational interaction with the virtual world, based on various learning criteria. Such agents can be represented visually in the form of cartoon characters or orally with the help of machine-simulated voice. This approach increases the efficiency of information perception.

Thus the review considers DL based on intelligent systems and MAS. The conditions of implementation of DL educational systems, learning resources, and interaction between the teacher and the students are considered. Also education forms have been analyzed, the main directions of DL development based on intelligent systems have been presented, and the differences of these DL from traditional learning have been illustrated.

The problems have beenhighlighted that are solved by learners and teachers in DL. It has been shown that the effectiveness of the DL is determined by the use of agent-based technologies that underlie the design and implementation of online courses.

It was concluded that DL based on MAS can be considered as an effective form of learning through intelligent approaches that are rarely implemented in traditional form of education.It was determined that introduction of DL into teaching practice allows to develop students 'abilities to think critically, make informed decisions and acquire the skills of communication, both in business and in everyday life. Also the importance of the DL developmenthas been emphasized on the basis of intelligent systems for persons with different disabilities.

It is clarified that due to the MAS underlying DL systems, the effectiveness of the training is increased and many of the processes of educational organizations are automatized. Agent-oriented technology allows to significantly facilitate the perception and awareness of the information in DL and creates available individual learning environment of students. Advantages of MAS have been identified, main ones are: flexibility in the development of various software and hardware solutions, the ability to use in conjunction with other programming languages, the versatility and the stability of the system as a whole, and also speed of processing of multidimensional data and independence of the individual parts.

Key words: intelligent system, distance education, multi-agent approach, agents, cognitive approach.

Bibliographic reference: Samigulina G.A., Nyussupov A.T. Overview of smart systems in distance learning based on multiagent approach //journal “Problems of informatics”. 2017. №2. P. 24-37.


Bredikhin S.V., Lyapunov V.M., Shcherbakova N.G.

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


UDC 001.12+303.2

The idea of determination of a scientific journal reputation by measurement of its citations, was for the first time offered in the work P. Gross & E. Gross (1927). Before the second half of the 20th century metrics like the impact factor ignored the network when ranking scholarly journals and only counted incoming links. In the pioneer work D. Price (1965) a network structure is considered as a basis of the bibliometric analysis. It was shown that the distributions of citation frequencies (in and out) approximately follow a power law. This observation let to formulate the hypothesis that the network growth can be modelled as a preferential attachment process.

Modern tools of the citation network analysis are grounded in graph and social networks theories, for example, node centrality measures for finding out of influential persons or key players. Technique of spectral ranking of scientific journals introduced in F. Pinski & G. Narin (1976) and C. Bergstrom & J. West (2008) uses the dominant eigenvector of an adjacency matrix of a citation network. Thus the foundation for identification of authoritative journals and the structure of scientific fields in terms of network have been established.
Now the journal is considered as a set of articles published in a certain period. This work studies different variants of networks consisting of scientific journals archived in the bibliographic database. A journal citation network is modelled by valued digraph G=(V,E), journals correspond to vertices , and citations to arcs  if a journal i  contains articles that have references to articles (cite) of a journal j. Edge weights are represented by a function , which assigns each edge the number  that indicates the number of references from the articles of i journal to the articles of j journal.
In accordance with M. Kessler, (1963), two journals are said to be bibliographically coupled if at least one cited source appears in the bibliographies or reference lists of articles published in both journals. So, coupling states the similarity between journals. On the base of the bibliographical coupling relation  a network can be constructed that is modelled by the valued undirected graph G=(V,E), with journals corresponding to vertices , and edges EÎV´V, e=(i,j)ÎE, if . A vector-space model G. Salton & M. McGill (1983) is used for defining edge weights. Co-citation relation  H. Small (1973) and independently I. V. Marshakova (1973) can be seen as the counterpart of bibliographic coupling. Co-citation of two journals means that both are cited together by other journals. Thus co-citation network can be constructed on the base of .
Three bibliometric networks of journals retrieved from the bibliographic DB RePEc were analyzed. The average distance D. Watts (1999), the edge density S. Wasserman & K. Faust (1994), the radius and diameter F. Harary (1973) were calculated. The results are presented in the form of tables and diagrams.

Key words: valued digraph, valued average distance, valued density, valued radius and diameter.

Bibliographic reference: Bredikhin S.V., Lyapunov V.M., Shcherbakova N.G. The structure of the citation network of scientific journals //journal “Problems of informatics”. 2017. №2. P. 38-52.


Markova* V.P., Ostapkevich** M.B.

The Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russian Federation
*The Novosibirsk National Research State University, 630090, Novosibirsk, Russian Federation
**The Novosibirsk State Technical University, 630073, Novosibirsk, Russian Federation


UDC 519.688

In this paper, a parallel implementation of the cellular-automata interference algorithm for two waves using the fragmented programming technology and Luna system based on it is proposed. The technology is based on a strategy of data flow control. Unlike existing systems and technologies, LuNA provides a unified technology for implementing parallel programs on a heterogeneous multicomputer. The LuNA program contains a description of data fragments, computational fragments, and information dependencies between them. In the work, the LuNA program was executed on a computational cluster with homogeneous nodes. The results of comparison of the LuNA and MPI implementations showed that the execution time of the LuNA program exceeded that of the MPI program. This is due to the peculiarities of algorithms used for the distribution, search and transfer of data and computation fragments between the nodes of a cluster. The complexity of writing the LuNA program is much lower than for the MPI program.

Key words: parallel programming, fragmented programming, graph of information dependencies, LuNA system, cellular automata, lattice gas, interference simulation.

1. StreamIt Project Homepage. [Electron. resource]. http://groups.csail.mit.edu/cag/streamit/, last accessed 2017/03/01.
2. Language for Streaming Applications // Proceeding CC ’02. Proceedings of the 11th International Conference on Compiler Construction. 2002. P. 179–196.
3. Michel Steuwer, Toomas Remmelg, and Chistophe Dubach. Lift: a functional data-parallel IR for high-performance GPU code generation // CGO’17 Proceedings of the 2017 International Symposium on Code Generation and Optimization. 2017. P. 74–85.
4. V. Malyshkin. Active Knowledge, LuNA and Literacy for Oncoming Centuries  // LNCS. Springer, Heidelberg. 2015. V. 9465. P. 292–303.
5. M. Zhang, D. Cule, L. Shafai, G. Bridges and N. Simons. Computing Electromagnetic Fields in Inhomogeneous Media Using Lattice Gas Automata // Proceedings of 1998 Symposium on Antenna Technology and Applied Electromagnetic. 1998. Aug. 14–16, Ottawa, Canada.
6. V. Markova. Designing a collision matrix for a cellular automaton with rest particles for simulation of wave processes // Bull. Nov. Comp. Center, Comp. Science. NCC Publisher, Novosibirsk. 36. 2014. P. 47–56.
7. Conditions for interference. [Electron. resource]. http://physics.bu.edu/~duffy/sc545_notes09/interference_conditions.html
8. V. Malyshkin, V. Perepelkin The PIC implementation in LuNA system of fragmented programming // Journal of Supercomputing. 2014. V. 69, I. 1. P. 89–97.

Bibliographic reference:  Markova V.P., Ostapkevich M.B. The comparison of MPI and LuNA capabilities using the implementation of cellular automata wave interference //journal “Problems of informatics”. 2017. №2. P. 53-64.