Methods of concurrent computing during process of translation research

Done by Nebotov Eugene

In the given job various ways of concurrency are investigated during translation and the interpreter from language a Prolog using these ways for increase of productivity on multiprocessing systems, clusters and similar computing systems is created.

Contents

Introduction

In 70th years logic programming and databases developed simultaneously. The Prolog - the most popular programming language in LOGIC - has appeared as result of simplification more the common methods of the proof of theorems for achievement of an opportunity of effective programming. Similarly relational model of the data has arisen as a result of simplification of complex hierarchical and network models for a possibility of not procedural manipulation
The plural data. During 70 and in the beginning of 80th years the Prolog and relational databases have received a wide circulation not only in the academic or scientific environment, but also in the business world.
Intensive researches of interrelation of logic programming and relational databases were spent from the end of 70th years mainly from the theoretical point of view. The success of integration was promoted by that circumstance, that the Prolog has been chosen as a paradigm of the programming language in Japanese project IÂÌ of 5-th generation. The purpose of this project is development « the COMPUTER of the following generation », focused on application in the field of an artificial intellect and, hence, capable to carry out extremely big number of logic conclusions in unit of time. But to reach{achieve} the greater speed it is possible only two methods: extensive (the best architecture, processors, the big clock frequency) or intensive (optimization, unloading of a code, concurrency). Constantly to update and buy the new expensive equipment is less profitable, than to get the software which works more effectively and fastly on any available equipment. Concurrency during translation gives advantage in job of the program, in speed of a carried out code.

Motivation

the Urgency of job

In view of general hobby for object-oriented programming languages, logic programming has been forgotten, meanwhile there is a certain number of tasks which can be solved only with the help of logic programming languages.

Development of the hardware of the COMPUTER has approached to a hard barrier and now for reception is appreciable more powerful system insufficiently to wait for couple of months or buy more expensively, the increase in speed and efficiency at present is actual at the expense of the organization and expansion of clusters, complex multiprocessing systems which support by software products is limited enough.

Job also is devoted to research and the decision of the given questions.

the Purposes and research problems

the Basic purpose of research is the analysis of existing methods of concurrency during translation from the technological and functional points of view, creation thus of system of criteria for their rating, existing realizations of language the Prolog.

On the basis of the analysis of the received model and existing decisions, development of recommendations on creation a web - guided of systems and to increase of efficiency of their job

Methods of research

The main method of research is the qualitative and quantitative analysis of realizations of language the Prolog with the help of the produced system of criteria and their comparison to formal model.

Scientific novelty

Will consist in reception of results of the analysis of ready decisions, construction of formal model and development of offers on increase of an overall performance.

Practical value

Will consist in creation on the basis of results of research and creation of the new interpreter of language a Prolog using advantages of multiprocessing system during translation.

Contents of work

The Prolog very well approaches for the description of mutual relations between objects. Therefore the Prolog name relational language. And "relationship" the Prolog considerably more powerful and advanced, than "relationship" the languages used for processing of databases. Often the Prolog is used for creation of control systems by databases where very complex searches which are rather easy for writing down on the Prolog are applied.
In the Prolog very compactly, in comparison with imperative languages, many algorithms are described. On statistics, a line of the initial text of the program in language the Prolog corresponds to fourteen lines of the initial text of the program in the imperative language solving the same task. The Prolog - program, as a rule, is very easy for writing, understanding and debugging. It results to that time of development of the application in language the Prolog in many cases on the order is faster, than in imperative languages. In the Prolog it is easy to describe and process complex structures of the data. We shall check up these statements on own experience at studying the given rate.
A number of mechanisms which traditional programming languages do not possess is inherent in a Prolog: comparison to a sample, a conclusion to search and return. One more essential difference consists that for a data storage in the Prolog lists are used, instead of files. In language there are no operators of giving and unconditional transition, indexes. Natural and frequently a unique method of programming is recursion. Therefore often there are, that people which are possessing experience of job in procedural languages, master declarative languages, than those who never was engaged in programming as the Prolog demands other style of thinking earlier, refusal of stereotypes of imperative programming more slowly.
As the programming language the Prolog very well approaches for elementary education to programming as he is focused on human thinking as against the imperative languages focused on a computer. Those who only starts to study programming, the Prolog easily accustoms. Practically full absence of syntactic designs, such as branchings, cycles, etc. also influences speed of development of language. Besides programming on the Prolog as it seems to me, orders thinking and allows the person studying this programming language, it is better to understand the cogitative activity. Very often to program the decision of a task, the programmer (or to the expert in some subject domain) in the beginning needs to understand, how he solves this task, to lead a certain formalization, to translate the knowledge from implicit in obvious.
Let's consider, in what areas in the best way the Prolog has shown itself:
Fast development of prototypes of applied programs;
Machine translation from one language on another;
Creation of natural language interfaces for existing systems;
Symbolical calculations for the decision of the equations, differentiation and integration;
Designing of dynamic relational databases;
Expert systems and shells of expert systems;
Automated management by productions;
The automatic proof of theorems;
Semi-automatic drawing up of schedules;
Systems of the automated designing;
The software basing knowledge;
The organization of the server of the data or, more precisely, the server of knowledge to which the client application written in any programming language can address.
Areas for which the Prolog is not intended: great volume of arithmetic calculations (processing of audio, video, etc.); a spelling of drivers.

For today there are very many realizations of the Prolog. Most known of them the following: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, MProlog, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic Knowledge Workbench, Strawberry Prolog, SWI Prolog, UNSW Prolog, etc.
In our country such versions of the Prolog as the Prolog - a (Sergey Grigorjev), Actor Prolog (Alexey Morozov), and also Fleng (by A.Mantsivoda, Vyacheslav Petuhin) have been developed.
The table of realizations of a Prolog

Realizations of the Prolog

*nbsp;

Architecture of Computing systems with the parallel organization of calculations

Flynn's classification

Apparently, the earliest and the most known is classification of architecture of the computing systems, M.Flinnom suggested in 1966. Classification is based on concept of a stream which is understood as sequence of elements, commands or the data, processable by the processor. On the basis of number of streams of commands and dataflows Flynn allocates four classes of architecture: SISD, MISD, SIMD, MIMD.

Figure 2.1 - SISD
SISD (single instruction stream / single data stream) - a single stream of commands and the single dataflow. Classical consecutive machines concern to this class, or otherwise, machines a background - íåéìàíîâñêîãî of type, for example, PDP-11 or VAX 11/780, first of all. In such machines there is only one stream of commands, all commands are processed consistently one after another and each command initiates one operation with one dataflow. Has no value that fact, that conveyor processing can be applied to increase in speed of processing of commands and speed of performance of arithmetic operations - as machine CDC 6600 with scalar functional devices, and CDC 7600 with conveyor get in this class.

Figure 2.2 - SIMD
SIMD (single instruction stream / multiple data stream) - a single stream of commands and the plural dataflow. In architecture of a similar sort one stream of commands including, as against the previous class, vector commands is saved. It allows to carry out one arithmetic operation at once above many data - elements of a vector. The way of performance of vector operations is not stipulated, therefore processing of elements of a vector can is made or a processor matrix, as in ILLIAC IV, or with the help of the conveyor, as, for example, in machine CRAY-1.

Figure 2.3 - MISD

MISD (multiple instruction stream / single data stream) - a plural stream of commands and the single dataflow. Definition means presence in architecture of many processors processing the same dataflow. However neither Flynn, nor other experts in the field of architecture of computers till now could not present a convincing example of the real-life computing system constructed on the given principle. A line of researchers is carried with conveyor machines to the given class, however it has not found a final recognition in scientific community. We shall consider, that while the given class is empty.

Figure 2.4 - MIMD
MIMD (multiple instruction stream / multiple data stream) - a plural stream of commands and the plural dataflow. This class assumes, that in the computing system there are some devices of processing of the commands incorporated into a uniform complex and working everyone with the stream of commands and the data.
So, what itself represents each class? In SISD as it was already spoken, uniprocessor consecutive computers such as VAX 11/780 enter. However, by many critics it is noticed, that it is possible to switch on in this class and vector-conveyor machines if to examine a vector as one indivisible given for the corresponding command. In that case in this class such systems, as CRAY-1, CYBER 205, machines of family FACOM VP and many others will get also.
Matrixes of processors are considered as indisputable representatives of class SIMD: ILLIAC IV, ICL DAP, Goodyear Aerospace MPP, Connection Machine 1, etc. In such systems the uniform managing device supervises set of processor elements. Each processor element receives from the device of management during each fixed moment of time the identical command and carries out it above the local data. For classical processor matrixes of any questions does not arise, however it is possible to switch on in the same class and vector-conveyor machines, for example, CRAY-1. In this case each element of a vector should be examined as a separate element of the dataflow.
Class MIMD is extremely wide, as includes every possible multiprocessor systems: Cm * , C.mmp , CRAY Y-MP, Denelcor HEP , BBN Butterfly, Intel Paragon, CRAY T3D and many others. Interestingly that if conveyor processing to examine as performance of set of commands (operations of steps of the conveyor) not above the single vector dataflow, and above a plural scalar stream all vector-conveyor computers considered above can be arranged and in the given class.
The suggested circuit of classification down to present time is the most used at the initial characteristic of this or that computer. If it is spoken, that the computer belongs to class SIMD or MIMD at once there is understandable a base principle of its job, and in some cases of it it happens enough. However patent defects are visible also. In particular, some worthy architecture, for example dataflow and vector - conveyor machines, precisely are not entered in the given classification. Other lack is excessive overflow class MIMD. The means more selectively systematizing architecture which on Flynn get in one class is necessary, but are completely various on number of processors, the nature and topology of communication{connection} between them, on a way of the organization of memory and, certainly, on technology of programming.
Presence of an empty class (MISD) should not be counted lack of the circuit. Such classes, in opinion of some researchers in the field of classification of architecture, can become extremely useful to development of essentially new concepts in the theory and practice of construction of computing systems.

Classification Hockney

R.Hokni - known English expert in the field of parallel computing systems, has developed the approach to the classification entered by him for ordering of computers, getting in class MIMD on Flynn's systematization.
As it was marked above, class MIMD is extremely wide, and alongside with the big number of computers he unites also the whole set of various types of architecture. Hockney trying to systematize architecture inside this class, has received the hierarchical structure submitted in figure:

Classification MIMD of systems
The basic idea of classification will consist in the following. The plural stream of commands can be processed by two ways: or one conveyor device of the processing, working in time sharing for separate streams, or each stream is processed by the own device. The first opportunity is used in MIMD computers which the author names conveyor (for example, processor modules in Denelcor HEP). The architecture using the second opportunity, in turn again share on two classes:
-MIMD computers in which the direct communication of each processor with everyone is possible, sold with the help of the switch;
-MIMD computers in which the direct communication of each processor is possible only with the nearest neighbours on a network, and interaction of the removed processors is supported by special system of routing through processors - intermediaries.
Further, among MIMD machines with switch Hokni allocates in what all memory is distributed among processors as their local memory (for example, PASM, PRINGLE). In this case dialogue of processors is realized with the help of very complex switch making a significant part of a computer. Such machines carry name MIMD of machines with the distributed memory. If memory is the divided{shared} resource accessible to all processors through the switch such MIMD are systems with the total memory (CRAY X-MP, BBN Butterfly). According to type of switches it is possible to spend classification and further: the simple switch, the multicascade switch, the general trunk.
Many modern computing systems have both the common shared memory, and allocated local. The author examines such systems as hybrid MIMD c the switch.
By consideration MIMD of machines with network structure it is considered, that all of them have the distributed memory, and the further classification is spent according to topology of a network: a star-shaped network (lCAP), regular lattices of different dimension (Intel Paragon, CRAY T3D), hypercubes (NCube, Intel iPCS), networks with hierarchical structure, such, as trees, pyramids, clusters (Cm*, CEDAR) and, at last, the networks changing the configuration.
Let's notice, that if the architecture of a computer is designed with use of several networks with various topology, that, most likely, by analogy with hybrid MIMD with switches, they should be named hybrid network MIMD, and using ideas of different classes - simply hybrid MIMD. The typical representative of last group, in particular, is computer Connection Machine 2, having on an external level topology of a hypercube which each site is a cluster of processors with full communication.

Conclusions

In my masters work I'm in process of translation, ways of realization of processes of translation, stages of the lexical analysis of an initial code, parsing, the analysis and generation of mistakes will be analysed. Architecture of parallel computers will be investigated.
Creation of the interpreter from the language the Prolog having high speed of job thanking making concurrent at a stage of translation on multiprocessing or cluster systems is started.

the List of the used sources *