Parallel programs construction and optimization

Edited by prof. V.N. Kasyanov
Novosibirsk 2008

This volume is the sixteenth in the series on the problems of program construction and optimization, published by the A.P. Ershov Institute of Informatics Systems. The volume is devoted to problems dealing with methods and tools of parallel system and program construction and optimization.

It may be of interest to system programmers, students and postrgraduates specializing in the area of system and theoretical programming, as well as all those interested in modern informatics and programming.

The articles are available in Russian only as PDF document


Data dependency index analysis in Sisal programs

The paper describes a compiler technology called index analysis which allows the presentation of information about the existence of cycled intra-operational depenencies referring to memory. Such information is used in many optimizations, especially the cyclic ones. The formation of this system takes several preparatory steps of searching for cycle nests and inductive variables, and the direct construction of dependency equations and inequality systems.

The paper is available in Russian only as PDF document


Calculation of Minkowsky integrals of cross measures, Minkowsky sums and building of Blaschke diagram for convex polyhedrons in euclidean space R3

The article presents a description of key features of convex polyhedrons. The main content of the article is the building of Blaschke diagram. Achieving this includes solving numerous intermediate tasks. The total time of computation reduces to a minimum because of the optimal selection of algorithms. The article also contains a description of a software product created for performing all required computations.

The paper is available in Russian only as PDF document


Visualization of internal representation in the SFP functional programming system

The paper introduces an algorithm of visualization of internal representation of programs. Internal representation can be viewed as a hierarchical directed acyclic graph, each vertex of which contains two ordered sets of input and output points. The algorithm is based on the Sugiyama algorithm. The algorithm was used to create a visualization component. The paper shows what kind of images can be generated.

The paper is available in Russian only as PDF document


Technologies of satellite image processing

The article presents a description of image processing technology applied to images received from satellite. The algorithms of brightness recalculation and panorama stitching are suggested. At the end of the article details of program implementation and results are brought.

The paper is available in Russian only as PDF document


Algorithms of image analysis for feature detection problem in order to diagnose plants diseases

This article is dedicated to algorithms of image analysis for feature detection problem in order to diagnose plants diseases. Statistical and textural features are analyzed, which helps to define the disease. The data gathered is used in future analyses to detect similar images. Several algorithms of contrast objects contour and texture features detection are described in this article.

The paper is available in Russian only as PDF document


Constant propagation for the SISAL internal representation graph IR2

Sisal is the functional data flow single assignment language, developed at A.P. Ershov Institute of Informatics Systems. In a SISAL compiler, most optimizations are performed on the intermediate representation IR2, which is the hierarchical acyclic data flow graph of the program. IR2 consists of vertices and ports. Vertices correspond to operations in the source program. Ports are used to mark the beginning and end of the value transfer edge between two operations.

The paper is available in Russian only as PDF document


Integrated visual environment for supporting of parallel program construction

The paper is devoted to the functional programming system SFP that is under development at the Institute of Informatics Systems in Novosibirsk with financial support from RFBR. The SFP system is intended to support construction of high quality portable software for parallel computers on low cost sequential computers (PC).

The paper is available in Russian only as PDF document


IFIP World Computer Congresses

The paper is an extended text of paper which was presented by the author in 28 October 2008 at the meeting N 696 of the United seminar "Program construction and optimization" of the Institute of Informatics Systems and the Novosibirsk State University, and was devoted to the 50th anniversary of the Programming Department of the Institute of Mathematics, SB AS USSR.

The paper is available in Russian only as PDF document


Using the clusters for computing the Mellin transform of functions in tomography tasks

An experiment of function reconstruction from its integrals on the family of straight lines cross the segment [-1, 1] on the x-axis is described. The carrier of intergrable function of two variables f(x, y) is concentrated in the region -1 ≤ x ≤ 1. Two-dimensional direct and reverse Mellin transformations are used in the algorithm of reconstruction, and their computations are performed in parallel.

The paper is available in Russian only as PDF document


Automatic taxonomy detection in the field of program transformations based on the analysis of semantic connections in publications

This article continues the approach described in [1] and extends the offered model, which allows solving several applied problems, particularly those related to building automatic taxonomy of application domain based on the set of publication.

The paper is available in Russian only as PDF document


About Zykov's seminar in Novosibirsk

The aim of these notes is to present a brief glance upon the seminars held by Zykov from the point of view of a student of the Novosibirsk State University, later a research intern of the Institute of Mathematics of the SB AS USSR. The article contains personal impressions of the author in 1964-1969. In a way, it's a view upon that period.

The paper is available in Russian only as PDF document


History of development of supercomputers

In the paper, the historical review of development of supercomputers is given, and statistics and analysis of tendencies in the area of high-performance computations are briefly considered.

The paper is available in Russian only as PDF document


Manual in writing different kind of business texts

This paper aims to help students in writing different kinds of documents, such as term papers and research works, accounts, program instructions, letters and so on. As a rule, students facing such tasks are those specializing in science, and not humanities. They may experience certain difficulties in creating such texts.

The paper consisits of two parts: theory and application. There are questions for self-control after each section. In the end of each part there is a list of literature. Exercises with explanations and references are given in the appendix of the second part.

The paper is available in Russian only as PDF document


Searching system with elements of linguistic analysis

This work is dedicated to the relevant problem of effective context-related text search in the Internet. The main goal is to develop new efficient algorithms of sentence comparison based on syntactic analysis schemes and consequently develop a search system based on this approach. Worth mentioning is that it suffices to stay on the level of syntax and grammar constructions while evaluating the relevance of templates in the text. Syntactic diagrams set up a primary structure in the text which allows to select and evaluate sentences and phrases from the text which have corresponding semantic links between keywords. As the result a search system which automates Internet searching was developed. Test have shown good result relevance.

The paper is available in Russian only as PDF document


Parallel calculations on the graphic processors

CUDA (Compute Unified Device Architecture) is the technology, developed by the company Nvidia, which makes possible for programmers to realize in the programming language C the algorithms, feasible on the graphic processors GeForce of the eighth generation and older (GeForce of 8 Series, GeForce of 9 Series, GeForce of 200 Series), Nvidia Quadro and Tesla of the company Nvidia. The article presents an instant analysis of the CUDA technology; equipment and special features of programming are described.

The paper is available in Russian only as PDF document


Generation of executable tests for compiler

The paper describes a generator that uses the formalism of parametric context-free grammar and allows generation of context-sensitive languages suitable for automatic construction of programs that can be compiled and have deterministic and finite execution. By analyzing differences in the output of these programs compiled with optimizations and without them, subtle errors in beta version of the industrial level compiler were found.

The paper is available in Russian only as PDF document


The clique tree of chordal graph and subgraph trees in graph theory

Generalizing clique trees by selecting other sorts of induced subgraphs allows certain concepts and results of chordal graphs to be transferred to other classes of graphs, such as strongly chordal graphs, totally balanced hypergraphs, chordal bipartite graphs etc.

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.