Объектно-транзакционное расширение Cilk++

Синтаксис

Предложим расширенный синтаксис динамического запуска транзакции:

[идентификатор_переменной «=»] [идентификатор_объекта («.»|«‑>»|«.*»)] «cilk_spawn» [«(» количество_предусловий «,» идентификатор_массива_предусловий «)»] «идентификатор_функции_или_метода» «(» аргументы «)» «;»

аргументы = [аргумент {«,» аргумент}]

аргумент = константа | переменная | «=» переменная

Здесь идентификатор_объекта – идентификатор объекта класса TObj<класс> или TQueuedObj<класс> или их наследника (если запуск конструкции производится внутри какого-либо метода одного из перечисленных классов, то идентификатор объекта можно не указывать, тогда будет использован текущий объект).

Данная конструкция возвращает ненулевой целочисленный идентификатор запущенной транзакции или ноль, если транзакцию запустить временно не удалось (это возможно только для объектов TObj<класс> и их потомков). Массив_предусловий, если он указан, содержит идентификаторы предусловий, то есть тех транзакций, которые должны быть завершены до старта данной. Что же касается аргументов, то следует обратить особое внимание на случай передачи локальной переменной – если есть опасность, что транзакция завершится позже текущего локального блока, то декларированные в нем переменные следует передавать с префиксом «=», который создаст внутренние копии таких переменных.

Теперь рассмотрим расширенный синтаксис конструкции ожидания завершения всех запущенных объектом транзакций:

[идентификатор_объекта («.»|«‑>»|«.*»)] «cilk_sync» «;»;

Здесь идентификатор_объекта – также идентификатор объекта класса TObj<класс> или TQueuedObj<класс> или их наследника.

Апробация

Предложенные синтаксические нововведения были реализованы с применением средств построения языковых расширений Planning C. Были разработаны соответствующие дедуктивные макросы cilk_spawn и cilk_sync, а также написана библиотека транзакционных классов и переменных.

В качестве простого примера применения рассмотрим построение гистограммы. Здесь основным рабочим классом является Histogrammer, метод process которого выполняет полезную работу по обработке одного элемента исходного массива (для которого строится гистограмма). Согласуемой переменной является поле – виртуальный массив F, представляющий массив частот.

Транзакционным классом является, соответственно, TQueuedObj<класс_Histogrammer>, на котором запускаются транзакции, в рамках каждой из которых выполняется метод process со специфическими параметрами. Этот же класс выполняет и ожидание завершения всех транзакций при вызове 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;

}

Данная программа успешно исполняется, выдавая в качестве результата число «10000».

Также, с применением предложенных средств были успешно решены: а) задача параллельного обучения искусственной нейронной сети прямого распространения (модификация весов и расчет отклика каждого отдельного нейрона являлись отдельными транзакциями; транзакции имели предусловия, отражающие необходимую последовательность из выполнения) и б) задача целочисленной линейной оптимизации методом ветвей и границ (с порождением транзакций-вариантов решения).

Выводы

Итак, в данной работе впервые предложено и реализовано объектно-транзакционное расширение Cilk++, позволяющее работать с динамической транзакционной памятью. Разработанные средства отличаются минимализмом набора конструкций, а также возможностью определения порядка обработки транзакций с помощью предусловий запуска (в результате можно, например, выстроить сетевой график транзакций). Реализация построена на базе средств расширения, характерных для языка Planning C. Разработанные средства успешно апробированы как при решении простых задач (построение гистограммы), так и при решении более сложных проблем обучения искусственной нейронной сети и решения задачи целочисленной линейной оптимизации методом ветвей и границ.