Object-transactional Extension of Cilk++

Let's propose an extended syntax for dynamically starting a transaction:

[variable id "="] [object id ("."|"?>"|".*")] "cilk_spawn" ["(" number of conditionals"," identifier of conditionals ")"] "identifier of function_or_ method" "(" arguments")" ";"

arguments = [argument {"," argument}]

argument = constant | variable | "=" variable

Here, the object identifier is the identifier of an object of the TObj<class> or TQueuedObj<class> class or their successor (if the construction is launched inside a method of one of the listed classes, then the object identifier can be omitted, then the current object will be used).

This construct returns a non-zero integer identifier of the running transaction or zero if the transaction could not be started temporarily (this is only possible for TObj<class> objects and their descendants). The precondition array, if specified, contains the identifiers of the preconditions, that is, those transactions that must be completed before the start of this one. As for the arguments, special attention should be paid to the case of passing a local variable – if there is a danger that the transaction will end later than the current local block, then the variables declared in it should be passed with the prefix "=", which will create internal copies of such variables.

Now let's look at the extended syntax of the construction of waiting for the completion of all transactions started by the object:

[object_id ("."|"?>"|".*")] «cilk_sync» «;»;

Here, the object_id is also the identifier of an object of the TObj<class> or TQueuedObj<class> class or their successor.

ApprobationThe proposed syntactic innovations were implemented using the tools for building language extensions of Planning C. The corresponding deductive macros cilk_spawn and cilk_sync were developed, and a library of transactional classes and variables was written.

As a simple example of application, consider the construction of a histogram. Here, the main working class is Histogrammer, the process method of which performs useful work on processing one element of the source array (for which a histogram is being built). The matched variable is a field – a virtual array F representing an array of frequencies.

The transactional class is, respectively, TQueuedObj<class_Histogrammer>, on which transactions are started, within each of which the process method with specific parameters is executed. The same class also waits for the completion of all transactions when calling cilk_sync.

#include <stdlib.h>

#include < iostream >

#include <omp.h>

using namespace std;

#include "transacted.h"

const int N = 10000;

const int M = 600;

const int NF = 20;

class Histogrammer {

public:

         TArray< int > * F;

         Histogrammer(int nthreads) {

                   F = new TArray< int >(NF);

                   *F = 0;

         }

         void process(int * A, double grain, int i) {

                   int k = A[i] / grain;

                   if (k >= NF) k = NF - 1;

                   ++((*F)[k]);

         }

         ~Histogrammer() {

                   delete F;

         }

};

int main() {

        int * A = new int[N];

         srand(184415);

         for (int i = 0; i < N; i++)

             A[i] = rand() % M;

         double grain = 1.0 * M / NF;

         TQueuedObj< Histogrammer > obj(omp_get_num_procs());

         for (int i = 0; i < N; i++)

                   obj.cilk_spawn obj.process(A, grain, =i);

         obj.cilk_sync;

         int SF = 0;

         for (int i = 0; i < NF; i++)

                   SF += (*obj.F)[i];

         cout << SF;

         delete[] A;

         return 0;

}

This program is successfully executed, giving as a result the number "10000".

Also, using the proposed tools, the following were successfully solved: a) the problem of parallel training of an artificial neural network of direct propagation (modification of weights and calculation of the response of each individual neuron were separate transactions; transactions had preconditions reflecting the necessary sequence from execution) and b) the problem of integer linear optimization by the method of branches and boundaries (with the generation of transaction variants solutions).

Conclusions

So, in this paper, for the first time, an object-transactional extension of Cilk++ was proposed and implemented, which allows working with dynamic transactional memory. The developed tools are distinguished by the minimalism of the set of designs, as well as the ability to determine the order of transaction processing using launch preconditions (as a result, you can, for example, build a network transaction schedule). The implementation is based on extension tools specific to the Planning C language. The developed tools have been successfully tested both in solving simple problems (building a histogram) and in solving more complex problems of training an artificial neural network and solving the problem of integer linear optimization by the method of branches and boundaries.