Object-transactional models of programs in algorithmic languages

Pekunov Vladimir Viktorovich Doctor of Technical Science Software Engineer, JSC "Informatika" 153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90 pekunov@mail.ru Other publications by this author

Transactional memory ^{[1, 2]} is a fairly well–studied formalism for building parallel programs, characterized by the simplicity of parallelization associated with the absence of the need for explicit synchronization ^[3]. Theoretically, an interesting question is whether it is possible to build arbitrary (sequential or parallel) programs using a single algorithmic construct, branching, using some formalism based on one or another extreme modification of transactional memory. In this case, explicit loops can be replaced by multiple conditional renegotiation of the transaction. It is quite obvious that such a replacement requires working with data that retains its values when a transaction is rolled back ^[4], and hence the transition from complete isolation of transactions to their partial isolation. This approach to the implementation of transactional memory is known ^[5]. In this work, the author's version of such memory ^[6] is used – the marginal partially transactional memory, which includes a single special transactional cell.

Thus, the purpose of this work is to study the problem of describing sequential and parallel algorithms based on formalisms based on the use of marginal partially transactional memory in conditions of a single algorithmic branching design. This formulation of the problem is new. Let's set the task of developing and researching the properties of such a formalism based on the most general ideas about the concepts used to build an algorithm that solves a certain problem.

General statement of the problem

Let's solve a problem in an arbitrary domain. Such an area can be described in terms of certain concepts, that is, thoughts that generalize and distinguish objects of certain classes based on common features. Therefore, a domain can be defined as a hierarchy of classes (concepts) describing the general properties of objects that fall under these concepts. Let's assume that a general, Turing-solvable algorithm for solving the problem is known, and it can be decomposed into a series of repeatedly renegotiated sequential and parallel acyclic processes (methods of objects belonging to classes of the corresponding subject area), the activation sequence of which is determined by the network schedule scheme.

Then the formal description of the process of solving the initial problem will be a network of interconnected objects that are instances of classes in the corresponding domain, interacting, for example, through shared memory. This description can be either limiting, including a single object that exhaustively describes the process of solving the problem, or non-limiting, including more than one object.

It can be assumed that in the most elementary case, the complete solution of the problem is performed by starting the network processes once in the required order. However, it is obvious that in the general case, a controlled multiple restart of the network may be required, for example, as a result of a renegotiation on some special transactional cell. Interesting consequences of the existence of such a mechanism are the following:

a) if transactional memory renegotiation is not required, then the network always shuts down in a finite time.;

b) using renegotiation in conditions of limited partially transactional memory, repeated execution of the same algorithm can be implemented, which is an acceptable alternative to cycles.

Let us now introduce the concept of marginal partially transactional memory. Let it be an associative tuple R _K = (V K, T K), the keys K of which are certain identifiers, and the values Vk can be arbitrary data structures, and each cell can have its own type Tk with values from the set {a, t}. Cells of type a are elementary cells with atomic access, the only cell of type t belongs to transactional memory, the local values of which are actually stored in the vector Vk = (_L1, ..., Ln). Each ith element of such a vector is a deuce (Si, ci), where si is the timestamp of the first modification of the cell in the ith stream, ci is a local copy of the cell for the ith stream (there are N parallel streams in total – parallel execution paths).

Let C be a set of classes. The class S is a triple (NC, F, M), where nc is the class identifier (name), F are fields, and M are methods. Let's define the relation of the parent hierarchy: , set by the function

where e is an empty string. Let each method of the set M be a branching algorithm that does not contain cycles and has full access to all fields of the object node and to all cells of some common marginal partially transactional memory, if any.

Hypothesis. A model that includes a network graph (P, E) containing a set P containing objects of classes C of the current subject area (connected by arcs from the set E), called in the order defined above [taking into account that the methods of objects between which the relationship of succession is not defined (according to the structure of the model) are always executed in parallel], operating according to branching algorithms in conditions of limited partially transactional memory with special matching, is capable of executing an arbitrary Turing-solvable sequential or parallel algorithm.

Let's call such models object-transactional (OTM).

Non-parallel OTM

Let's introduce the concept of a marginal non-parallel object-transactional model. Let such a model be a deuce (R, N), where R is an associative tuple of marginal partially transactional memory, and N is a network of a single node, object A, belonging to a certain class.

We will introduce a special mechanism for matching a single transaction cell. Let it have the RESTART identifier and store a reference to the current executable method of object A (note immediately that in the case of an OTM of several nodes, this will be a list of pairs of the form (A, M[A]), where A is a reference to the node, M[A] is a reference to the method of node A), characterized by What

a) at the beginning of the model execution, this cell stores a reference to a special method, which is always called first.;

b) any assignment of a reference to an arbitrary method to this cell inevitably leads to the need for post-negotiation of the current transaction (the entire network, at the end of its current interpretation) with a call to the specified method.;

c) before post-renegotiating the current transaction, the object methods to be called are determined – these are the methods referenced in RESTART. Next, the RESTART cell is cleared and the post-negotiation of the transaction (of the entire network from the very beginning) begins.

Note that all type a memory cells do not affect the matching process.

Theorem 1. A marginal non-parallel OTM is capable of implementing an arbitrary Turing-solvable algorithm.

Proof. Let's consider an arbitrary program in a high-level algorithmic language C (with an extension that implements the required mechanism for matching the maximum partially transactional memory). If such a program does not contain loops, then it can be implemented by an arbitrary method (implementing an arbitrary branching algorithm) of a single object of marginal non-parallel RTM by definition.

Let the program contain loops. Equivalently, we transform it according to the following rules:

a) we will associate with each operator a certain conditional label;

b) enter the non-transactional CURLABEL variable, which stores the label name of the current operator;

c) at the beginning of the program, the CURLABEL contains the label of the initial operator;

d) each operator with a label is preceded by a construction of the form

[else] if (CURLABEL == label of the flowing operator) {

e) in each operator with a label, we make appropriate assignments to the CURLABEL variable of operator labels performed by the following;

f) at the end of each statement, we put the closing block with a "}" sign, before which (with the exception of the statements executed last) we put a misalignment construct for the current transaction (leading to its subsequent repetition at the end of the current network processing session) by assigning the RESTART variable a reference to the current method;

g) first, convert all the loops to a while loop;

h) each while loop of the form;

Placemark1: while(condition) { Operator_A; … Operator_B; } Operator_C;

replace it with conditional operators:

if (CURLABEL == Placemark1 && condition) { CURLABEL = PLACEMARK_A; RESTART = ...; }

else if (CURLABEL == Placemark1 && !condition) { CURLABEL = PLACEMARK_C; RESTART = ...; }

else if (CURLABEL == PLACEMARK_A) { Operator_A; CURLABEL = …; RESTART = …; }

…

else if (CURLABEL == Label in) { Operator in; CURLABEL = Placemark_1; RESTART = ... }

else if (CURLABEL == PLACEMARK_C) { Operator_C; ... }

i) the entire program consists of a transactional block;

k) we design all program variables as cells of type a of the marginal partially transactional memory.

We have obtained an equivalent program that can be executed using an arbitrary OTM method by definition. So, a marginal non-parallel OTM is capable of implementing an arbitrary program (for example, in a high-level algorithmic language C), which, as is known, can be a program implementing an algorithm for the functioning of a Turing machine (capable of implementing an arbitrary Turing-solvable algorithm), therefore, such an OTM is capable of implementing an arbitrary Turing-solvable algorithm. We also note the undoubted direct structural analogy between the C program obtained after conversion and the code for the Turing machine.

Proven.

Consequence. Since a marginal non-parallel OSM is capable of implementing an arbitrary, Turing-solvable algorithm, therefore, an unintended non-parallel OSM is capable of implementing such an algorithm (for example, using one of its arbitrary nodes).

Parallel OTM

Let's introduce the concept of the ultimate parallel (K-thread) object-transactional model. Let such a model be a deuce (R, N), where R is an associative tuple of marginal partially transactional memory, N is a network including nodes with empty methods (source and drain), as well as K working nodes with non–empty methods, each of which includes an arc from the source and each one contains an arc into the drain. Let the model execute a transactional block according to all the rules described above (possibly with multiple post-negotiation), taking into account that the processes of nodes located in branches for which the sequence relationship is not defined are executed in parallel.

Theorem 2. Limit parallel (K-threading) OTM is capable of implementing an arbitrary Turing-solvable algorithm with K parallel branches.

Proof. It was shown above that a single-node, non-parallel OTM is capable of implementing an arbitrary, Turing-solvable algorithm. Here we have a system of K nodes (which can work in parallel), each of which can be considered as a separate OTM, interacting with other OTMS through shared memory. Thus, the entire system can be considered as K parallel Turing machines exchanging data, for example, through a common tape. Accordingly, this system is capable of executing an arbitrary Turing-solvable algorithm with K parallel branches.

Consequence. Since the limit is parallel (K-threaded) An OTM is capable of implementing an arbitrary parallel K-thread algorithm that is Turing-solvable, hence an unintended parallel OSM with at least K parallel branches is capable of implementing such an algorithm.

The main properties of OTM

In conclusion, we will formulate some basic properties of the object-transactional models proposed in this paper. These properties follow either from the basic structural and functional features of the models, or from the provisions proved above. So, the main properties are:

1. Ultimate uniqueness. Each unique program in some high-level algorithmic language corresponds to at least one equivalent program. This property follows from the potential realizability with the help of an arbitrary Turing-solvable algorithm (Theorem 1). Therefore, the equivalent can be at least a marginal non-parallel OTM that implements a Turing machine in a given high-level language that executes the specified algorithm. In addition, it is possible to build another implementing OTM, for example, similar in structure to the spanning tree of the flowchart graph of this algorithm and containing one or more nodes with methods in a given high-level language.

2. Algorithmic Turing completeness (follows from Theorem 1).

3. Natural description of parallelism (parallel and non-parallel processes are clearly defined by the structure of the model).

4. Atranzational limb. If the mechanism for matching a single transactional memory cell is not activated, then the OTM always completes in a finite time, since it has a network structure, which in this case makes looping fundamentally impossible.

5. The fundamental heterogeneity of the types of memory used with the non-redundant (excluding simple duplication of cycle bodies) implementation of algorithms containing cycles with a counter or inter-turn dependencies. It follows from the fact that the model has a network structure, its methods also have a branching structure, so such cycles can be implemented only by re-matching the model (requires a RESTART cell of the maximum partially transactional memory) while preserving the changing context [counters or other variables common to the turns of the cycle (requires cells of type a partially transactional memory)].

Conclusions

In this paper, we consider the problem of representability of parallel and non-parallel algorithms using object-transactional models based on the idea of marginal partially transactional memory containing a single transactional cell with special matching, in the presence of a single algorithmic construct – branching. The concept of such models is formulated for the first time, the basic principles of their functioning are described, and their basic properties are formulated. Theorems on the solvability of arbitrary sequential algorithms calculated by Turing with such models are proved, as well as on the solvability of arbitrary algorithms with K parallel branches calculated by a system of K parallel Turing machines interacting through a common tape.