2017 № 2 (35)

Nazarov A.A., Anisimova A.A. ASIMPTOTIC ANALYSIS OF TWO-PHASE RETRIAL QUEUING SYSTEM M/M/1 UNDER DELAY CONDITION OF ORBIT
Pankratov S.B. AUTOMATIC TEST GENERATION FOR INTEL GFX-OFFLOAD COMPILER
Samigulina G.A., Nyussupov A.T. OVERVIEW OF SMART SYSTEMS IN DISTANCE LEARNING BASED ON MULTIAGENT APPROACH
Bredikhin S.V., Lyapunov V.M., Shcherbakova N.G. THE STRUCTURE OF THE CITATION NETWORK OF SCIENTIFIC JOURNALS
Markova V.P., Ostapkevich M.B. THE COMPARISON OF MPI AND LUNA CAPABILITIES USING THE IMPLEMENTATION OF CELLULAR AUTOMATA WAVE INTERFERENCE

Tomsk State University, 634050, Tomsk, Russia

ASIMPTOTIC ANALYSIS OF TWO-PHASE RETRIAL QUEUING SYSTEM M/M/1 UNDER DELAY CONDITION OF ORBIT

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.

References

1. Artalejo J. R., Gomez-Corral A. Retrial Queuing Systems: A Computational Approach. Berlin, Springer, 2008.
2. Falin G. I., Templeton J. G. C. Retrial queues. London, Chapman & Hall, 1997.
3. Gnedenko B. V., Kovalenko I. N. Vvedenie v teoriyu massovogo obsluzhivaniya [Introduction to Queuing Theory]. Moscow, Nauka, Gl. red. fiz.-mat.lit., 1987.
4. Krishna C. M. and Lee Y. H. A study of two-phase service. Operations Research Letters, 1990, Vol. 9. P. 91–97.
5. Doshi, B. T. Analysis of a two phase queuing system with general service times // Operations Research Letters. 1991. Vol. 10. P. 265–272.
6. Krishnakumar B. and Arivudainambi D. An M/G/1 retrial queuing system with two phases of services and preemptive resume // Annals of Operations Research. 2002. Vol. 113. P. 61–79.
7. Choudhury G. A single server queuing system with two-phases of service and vacations. // QTQM. 2008. Vol. 5 (1). P. 33–49.
8. Nazarov A. A., Sudyko E. A. Method of asymptotic semi invariants for studying a mathematical model of a random access network // Problems of information transmission. 2010. Vol. 46. N 1. P. 86–102.
9. Anisimova A. A. Imitatsionnoe modelirovanie dvukhfaznoi RQ-sistemy [Simulation modeling of two-phase retrial queuing system] // Nauchnoe tvorchestvo molodezhi. Matematika. Informatika: materialy XX Vserossiiskoi nauchno-prakticheskoi konferentsii (28–29 aprelya 2016 g.), sost . Y. A. Naumkina. Tomsk, Izd-vo Tom. un-ta, 2016, Part 1, P. 81–85.

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

Article

Pankratov S.B.

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

AUTOMATIC TEST GENERATION FOR INTEL GFX-OFFLOAD COMPILER

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.

Reference

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.

Article

Samigulina G.A., Nyussupov A.T.

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

OVERVIEW OF SMART SYSTEMS IN DISTANCE LEARNING BASED ON MULTIAGENT APPROACH

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.

References

1. Tony D. Triggs Pitman, Sir Isaac (1813–1897) // Oxford Dictionary of National Biography. UK: Oxford University Press (online edition), 2014. [Electron. res.]. http://www.oxforddnb.com/index/22/101022322/.
2. Tyurikova E. M. Distancionnoe obuchenie — novaya forma informacionno-pedagogicheskoj sredy // Gumanitarnyj vektor. Seriya: Pedagogika, psihologiya, 2013. N 33 (1). P. 72–76.
3. Zaharov, V. N. Intellektual’nye sistemy upravleniya: osnovnye ponyatiya i opredeleniya // Izvestiya RAN. Teoriya i sistemy upravleniya, 1997. N 3. P. 138–145.
4. Dzhorzh F. Lyuger. Iskusstvennyj intellekt: strategii i metody resheniya slozhnyh problem. Kiev: Izd. dom Vil’yams, 2003.
5. Jeffrey P. Bakken, Vladimir L. Uskov, Archana Penumatsa, Aishwarya Doddapaneni. Smart Universities, Smart Classrooms and Students with Disabilities // Smart Universities, Smart Classrooms and Students with Disabilities. Switzerland: Springer International Publishing, 2016. P. 15–27.
6. Samigulina G. A., Shayakhmetova A. S. The information system of distance learning for people with impaired vision on the basis of artificial intelligence approaches // Proceedings of the II International conference on Smart Education and E-learning. Italy, Sorrento: Springer, 2015. P. 255–265.
7. Samigulina G. A., SHayahmetova A. S. Kombinirovannaya ontologicheskaya model’ dlya distancionnogo obucheniya lyudej s ogranichennymi vozmozhnostyami zreniya // Problemy informatiki. Novosibirsk, 2015. N 3. P. 28–35.
8. Rong, S. Application of Multi-agent in Personalized Education System // Advances in Computer Science, Environment, Ecoinformatics, and Education. Berlin: Springer-Verlag, 2011. P. 518–522.
9. Samigulina G. A., Shayakhmetova A. S. Development of the Smart — system of distance learning visually impaired people on the basis of the combined OWL model (Razrabotka Smart — sistemy distancionnogo obucheniya lyudej s ogranichennymi vozmozhnostyami zreniya na osnove kombinirovannoj OWL modeli) // Proceeding of the 3rd International KES Conference on Smart Education and E-learning (KES-SEEL-16). Puerto de la Cruz, Tenerife, Spain, 2016 (Springer). P. 109–118.
10. 10. Tiago T. Primo, André B., Rosa, M. Vicari A Semantic Web Approach to Recommend Learning Objects // Highlights on Practical Applications of Agents and Multi-Agent Systems. Berlin: Springer-Verlag, 2013. P. 340–350.
11. Paula R., Néstor D., Demetrio A. Ovalle Multi-agent System for Knowledge-Based Recommendation of Learning Objects Using Metadata Clustering // Highlights of Practical Applications of Agents, Multi-Agent Systems, and Sustainability. The PAAMS Collection. Switzerland: Springer International Publishing, 2015. P. 356–364.
12. Valdés-Pasarón S., Marquez B.Y., Gaxiola L. Knowledge and Data Engineering for Analyzing the Quality of Education Using Fuzzy Logic // Electrical Power Systems and Computers. Berlin: Springer-Verlag, 2011. P. 567–573.
13. Lian-duo Yan, Xiu-lan Ma, Li-ling Wang Intelligent Interaction System of Distance Education Based on Natural Language Matching // Advances in Future Computer and Control Systems. Berlin: Springer-Verlag, 2013. P. 237–242.
14. Laura K. Allen, Danielle S. McNamara Promoting Self-Regulated Learning in an Intelligent Tutoring System for Writing // Artificial Intelligence in Education. Switzerland: Springer International Publishing, 2015. P. 827–830.
15. David Wen-Shung Tai, Hui-Ju Wu, Pi-Hsiang Li A Hybrid System: Neural Network with Data Mining in an e-Learning Environment // Knowledge-Based Intelligent Information and Engineering Systems. Berlin: Springer-Verlag, 2007. P. 42–49.
16. Chin-Ling Lee, Chih-Hui Huang, Cheng-Jian Lin // Test-Sheet Composition Using Immune Algorithm for E-Learning Application // New Trends in Applied Artificial Intelligence. Berlin: Springer-Verlag, 2007. P. 823–833.
17. Fabrizio M., Giuseppe P., Domenico R., Corrado S., Giuseppe M. L. Sarne? A Distributed Agent-Based Approach for Supporting Group Formation in P2P e-Learning // AI*IA 2013: Advances in Artificial Intelligence. Switzerland: Springer International Publishing, 2013. P. 312–323.
18. Rubén F., Rosanna C. A Multi-agent Model That Promotes Team-Role Balance in Computer Supported Collaborative Learning // Advances in New Technologies, Interactive Interfaces and Communicability. Berlin: Springer-Verlag, 2012. P. 85–91.
19. Xiaohan Z., Honghua X., Lin H., Shuying Z. Collaborative Learning on Multi-agent in M-Learning // Advances in Multimedia, Software Engineering and Computing Vol.2. Berlin: Springer-Verlag, 2012. P. 595–601.
20. Stamatis P., Panagiotopoulos I., Goumopoulos C., Kameas A. APLe: Agents for Personalized Learning in Distance Learning // Computer Supported Education. Switzerland: Springer International Publishing, 2016. P. 37–56.
21. Rong, S. Application of Multi-agent in Personalized Education System // Advances in Computer Science, Environment, Ecoinformatics, and Education. Berlin: Springer-Verlag, 2011. P. 518–522.
22. Dejan R., Kristijan K., Olivera P., Dragan R. Agent-Based Approach for Game-Based Learning Applications: Case Study in Agent-Personalized Trend in Engineering Education // Agent and Multi-Agent Systems: Technologies and Applications. Switzerland: Springer International Publishing, 2015. P. 453–466.
23. Kristijan K., Ivan M., Dejan R., Petar S. Designing Intelligent Agent in Multilevel Game-Based Modules for E-Learning Computer Science Course // E-Learning Paradigms and Applications. Berlin: Springer-Verlag, 2012. P. 397–405.
24. Shuhua H., Xuemei S. The Study on University Library Information Service for Regional Characterized Economy Construction Based on Integrated Agent // Computer Supported Education. Berlin: Springer-Verlag, 2013. P. 289–294.
25. Godfrey O., Jude T. Lubega, Gilbert M., Richard O. Angole Towards an Interactive Agent-Based Approach to Real-Time Feedback (IAARF) in E-Learning System // Hybrid Learning. Berlin: Springer-Verlag, 2012. P. 317–328.
26. Wen, S. Duan, Yan, M., Lun, P. Liu, Tian, P. Dong Research on an Intelligent Distance Education System Based on Multi-agent // Proceedings of the International Conference on Information Engineering and Applications (IEA) 2012. London: Springer-Verlag, 2013. P. 579–586.
27. Ahmetova L.V. Metody kognitivnogo obucheniya: psihologo-didakticheskij podhod // Vestnik Tomskogo gosudarstvennogo pedagogicheskogo universiteta. Tomsk: Tomskij gosudarstvennyj pedagogicheskij universitet, 2009. P. 48–52.
28. Nagoev, Z. V. Metody prinyatiya reshenij i upravleniya v nestrukturirovannyh zadachah na osnove samoorganizuyushchihsya mul’tiagentnyh rekursivnyh kognitivnyh arhitektur: dis. d. i. n.: 30.10.13 / FGBUN Institut informatiki i problem regional’nogo upravleniya Kabardino-Balkarskogo nauchnogo centra RAN. Nal’chik, 2013.
29. Roger A., Jason H., Gregory T., Melissa D., Reza F., Francois B., Ronald L. Using Trace Data to Examine the Complex Roles of Cognitive, Metacognitive, and Emotional Self-Regulatory Processes During Learning with Multi-agent Systems // International Handbook of Metacognition and Learning Technologies. New York: Springer Science, 2013. P. 427–449.
30. Jingying C., Nan L., Yuanyuan L., Leyuan L., Kun Z., Joanna K. A hybrid intelligence-aided approach to affect-sensitive e-learning // Computing. Wien: Springer-Verlag, 2014. P. 215–233.
31. Usef F., Philippe F., Roger N. CELTS: A Cognitive Tutoring Agent with Human-Like Learning Capabilities and Emotions // Intelligent and Adaptive Educational-Learning Systems. Berlin: Springer-Verlag, 2013. P. 339–365.
32. Chatzara K., Karagiannidis C., Stamatis D. Cognitive support embedded in self-regulated e-learning systems for students with special learning needs // Education and Information Technologies. New York: Springer Science, 2014. P. 283–299.
33. Fabrice L., Nicolas G., Stéphane G., Vincent H. Ipseity — A Laboratory for Synthesizing and Validating Artificial Cognitive Systems in Multi-agent Systems // Machine Learning and Knowledge Discovery in Databases. Berlin: Springer-Verlag, 2013. P. 641–644.
34. Zalimkhan N., Olga N., Dana T. System Essence of Intelligence and Multi-agent Existential Mappings // Hybrid Intelligent Systems. Switzerland: Springer International Publishing, 2015. P. 67–76.

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.

Article

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

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

THE STRUCTURE OF THE CITATION NETWORK OF SCIENTIFIC JOURNALS

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.

References

1. Gross P. L. K., Gross E. M. College Libraries and Chemical Education // Science. 1927. V. 66, iss. 1713. P. 385–389.
2. Price D. Networks of scientific papers // Science. 1965. V. 149, N 3683. P. 510–515.
3. Garfield E., Sher I. H. New factors in the evaluation of scientific literature through citation indexing // Amer. Document. 1963. V. 14, N 3. P. 195–201.
4. Pinski G., Narin F. Citation influence for journal aggregates of scientific publications: Theory with application to literature of physics // Inform. Processing and Management. 1976. V. 12. P. 297–312.
5. Bergstrom C. T., West J. D. Assessing Citations with the Eigenfactor Metrics // Neurology. 2008. V. 71. P. 1850–1851.
6. Freeman L. C. Centrality in social networks. Conceptual clarification // Soc. Networks. 1978/79. V. 1. P. 215–239.
7. Leydesorff L., Rafols R. Indicators of the interdisciplinarity in journals diversity, centrality and citations // J. of Informetrics. 2011. V. 5, iss. 1. P. 87–100.
8. Structural analysis of complex networks. (Dehmer M. Ed.) Birkhauser, 2011. 486 p.
9. RePEc. General principles. [Electron. resource]. http://repec.org/.
10. Bredikhin S. V., Lyapunov V. M., Shcherbakova N. G., Yurgenson A. N. Parametry "tsentral’nosti" seti tsitirovaniya nauchnykh statey // Problemy informatiki. 2016. No 1. P. 39–57.
11. Kessler M. M. Bibliographic coupling between scientific papers // American Documentation. 1963. V. 14. P. 10–25.
12. Salton G., MacGill M. J. Introduction to modern information retrieval. N. Y.: McGraw-Hill, 1983. 448 p.
13. Small H. Co-citation in the scientific literature: A new measure of the relationship between two documents //J. of the American Society for Information Science. 1973. V. 24. P. 265–269.
14. Marshakova I. System of document connections based on references // Scientific and Technical Information Serial of VINITI. 1973. N 6(2). P. 3–8.
15. Watts D. J. Networks, dynamics and the small-world phenomenon // Amer. J. of Sociology. 1999. V. 105, iss. 2. P. 493–527.
16. Milgram S. The small world problem // Psychol. Today. 1967. V. 2. P. 60–67.
17. Newman M. E. J. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. // Physical Review E 64, 016132. 2001.
18. Brandes U. On variants of shortest-path betweenness centrality and their generic computation // Social Networks. 2008. V. 30. P. 136–145.
19. Opsahl T. Shortest paths in weighted network. [Electron. resource]. https://toreopsahl.com/tnet/ weighted-networks/shortest-paths/
20. Wasserman S., Faust K. Social network analysis: Methods and applications. Cambridge, ENG, New York: Cambridge University Press, 1994.
21. Barrat A., Barthelemy M., Pastor-Satorras R., Vespignani A. The architecture of complex weighted networks // Proc. of the National Acad. of Sci. 2004. V. 101, iss. 11. P. 3747–3752.
22. Guimei L., Wong L., Chua H. Complex discovery from weighted PPI networks // Bioinformatics. 2009. V. 25, iss. 15. P. 1891–1897.
23. Harary F. Graph theory. Addison-Wesley, 1969.
24. Borassi M., Crescenzi P., Habib M., Kosters W. A., Marino A., Takes F. W. Fast diameter and radius BFS-based computation I (weakly connected) real-world graphs: With an application to the six degrees of separation games // Theoretical Comput. Sci. 2015. V. 585. P. 59–80.
25. Cormen T. et.al. Introduction to algorithms. MIT Press and McGraw-Hill, 2001.
26. Csárdi, Nepusz. Network analysis with igraph, 2006.

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.

Article

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

THE COMPARISON OF MPI AND LUNA CAPABILITIES USING THE IMPLEMENTATION OF CELLULAR AUTOMATA WAVE INTERFERENCE

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.

References
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.

Article

Main menu

2017 № 2 (35)

Contents

Main menu

You are here

2017 № 2 (35)

Contents