Tools and techniques of programm construction

Edited by prof. V.N. Kasyanov
Novosibirsk 2007

This volume is the fifteenth one in a series of books published in A.P. Ershov Institute of Informatics Systems. This volume is devoted to the tools and techniques of program construction and optimization.

The volume is of interest for system programmers, students and postgraduates working in the field of system and theoretical programming.

The articles are available in Russian only as PDF document


Experimental research of new strategy of testing

In this paper we present an experimental evaluation of several data dependence algorithms, including the new strategy , Epsilon-test and algorithm of Maydan. We compare these algorithms in terms of accuracy and efficiency. We conducted our experiments using the Petit Tool V1.1, developed at the University of Maryland as an extension to the Tiny Tool and using system SUIF, developed at the University of Stanford. Two types of data are used for experiment. The first type is a set of test scientific programs of NASA and PERFECT Club benchmarks, where each program consists of 500 to 18000 lines. The second type is a set of 16 cycles collected from papers similar to ours.

The paper is available in Russian only as PDF document


The dynamic distributed SL-Algorithm for coloring w-perfect graphs

The given work is devoted to coloring w-perfect graphs within the framework of the distributed model of calculations, which uses a well-known strategy of SL-algorithm. The w-perfect graphs class is rather wide and comprises such practically interesting graph classes, as for example, the chordal graph class, which is one of the most actively investigated and widely used graph classes.

The paper is available in Russian only as PDF document


Time tracing for SISAL 3.1 internal representation IR2

In this paper we present an experimental evaluation of several data dependence algorithms, including the new strategy , Epsilon-test and algorithm of Maydan. We compare these algorithms in terms of accuracy and efficiency. We conducted our experiments using the Petit Tool V1.1, developed at the University of Maryland as an extension to the Tiny Tool and using system SUIF, developed at the University of Stanford. Two types of data are used for experiment. The first type is a set of test scientific programs of NASA and PERFECT Club benchmarks, where each program consists of 500 to 18000 lines. The second type is a set of 16 cycles collected from papers similar to ours.

The paper is available in Russian only as PDF document


Methods of interprocedural analysis

Interprocedural analysis is an inalienable part of modern optimizing compiler. Such analysis gives the compiler facts about the environmental changes caused by procedure call and the execution context of the procedure. Some parts of interprocedural analysis may be simplified or even eliminated according to the optimizations used. For example, alias analysis may be insignificant for sequential code compiler. Automatic parallelization systems require more precise interprocedural information for loop parallelization and interprocedural optimizations. In automatic parallelization system any information may increase parallelism. Precise interprocedural alias information is required in the software engineering systems for type control systems. It is possible to exclude interprocedural analysis when optimization algorithms don't use any information on interprocedural data flow; it reduces the set of possible optimizations. Procedure boundaries can be eliminated by replacing each procedure call by a copy of the called procedure; it makes the code exponential larger which is undesired and not always possible.

This paper observes main the interprocedural analysis methods from the point of an automatic parallelization system.

The paper is available in Russian only as PDF document


Sisal 3.2 programming language

The paper describes the syntax and semantics of a new version of the Sisal 3.2 programming language designed to write data-flow programs for scientific computations. The main features of Sisal 3.2 language (as compared to Sisal 3.1 language) include the support of multidimensional arrays, parametric user types, generalized procedures, foreign types and procedures. Sisal 3.2 is a source language of the system of functional programming (SFP) which is currently being developed in the A.P.Ershov Institute of Informatics Systems.

The paper is available in Russian only as PDF document


Wavelet data processing in geophysical investigation in boreholes

The article presents an overview of geophysical investigation in boreholes and data processing methods. The problem of filtering logging data and setting borders (determination of layers) is the main subject of the article. The original usage of wavelet transformations gives some results that may be better than the results obtained by traditional methods of setting borders in geophysical data processing.

The paper is available in Russian only as PDF document


Developing graphical user interfaces and data visualization in geophysical software

This article contains some information about developing graphical user interfaces in geophysical software. Also there is an example how geophysical software "EMF Pro" GUI was developed - main requirements, solutions, data visualization, etc.

The paper is available in Russian only as PDF document


Using non-specific ontologies in factographic data storage

In the article, the work is described which was carried out within the framework of the "Electronic photo archive of the Siberian Branch of the Russian Academy of Sciences" project. The task was to create an information system for storage of documents and supplying them with metadata.

The paper is available in Russian only as PDF document


Organization of the historical-cultural space in Internet using information technologies

Problems of informational and comminucational technologies and its use for conservation of Russian and global cultural heritage are discussed. The definitions of cultural heritage, object of cultural heritage are given, classification of cultural heritage objects and technologies of their conservation are suggested. Examples of Russian and global network of cultural heritage are presented.

The paper is available in Russian only as PDF document


Automaton model of visual description of syntax parsing

The paper introduces and investigates the automaton model suitable for clear visual description of effective descending syntax analysis of programming languages. It is shown that in the deterministic case the presented automaton model allows class of LL1 languages. The presented automaton model indirectly allows more powerful languages via its context states and supports hierarchical processing of indeterminacy for implementing syntax error handling without overhead of completely specified automaton. The paper shows the ways to improve efficiency of automaton of the presented model such as state minimization, removal of ε-transitions and unreachable states.

The paper is available in Russian only as PDF document


The middle-level internal representations for the Sisal language compilers

The paper considers some technologies of memory optimization in the Sisal language compilers. It also presents the middle-level internal representations IR1 and IR2 developed for the Sisal 3.1 compiler. This compiler is a part of SFP functional programming system which is currently being developed in the A.P. Ershov Institute of Informatics Systems SB RAS. The methods of building, translation and optimization of these representations are briefly described.

The paper is available in Russian only as PDF document


Technology of automation of monitoring and control of legality of financial operations of the modern credit organizations

The article considers problems of modern commercial banks connected with an essential growth of number of financial services and control of legality of operations. The description of the automated system of analysis of financial documents is given: the architecture and logic of work. Internal linguistic algorithms of search and process of integration with information system of bank are described. Development is conducted according to regulations of the central bank of the Russian Federation (207-P) and requirements of business.

The paper is available in Russian only as PDF document


Some methods of modelling the equipment of electromagnetic well logging (carotage)

In the article, mathematical formulations of problems of electric and electromagnetic well logging are described and the list of methods of their solutions is given.

The paper is available in Russian only as PDF document





You are reporting a typo in the following text:
Simply click the "Send typo report" button to complete the report. You can also include a comment.