Параллельное программирование: Учебное пособие, страница 59

if (solution(A))

then

score = eval(A)

report solution and score

else

foreach child A(i) of A

seach(A(i))

end for

endif

end

Процедура  search  работает со множеством вершин дерева А. Сначала создается единственная задача для корня дерева (1), которая вычисляет оценку решения для корневой вершины дерева (1). Если оценка не удовлетворяет решению, то создаются новые задачи для вычисления оценок решения в каждой корневой вершине (2, 3, 4) следующих поддеревьев поиска. Канал, создаваемый для каждой новой задачи используется, чтобы возвратить породившей ее задаче любые решения, полученные в вершинах поддеревьев. В результате новые задачи и каналы создают некий волновой фронт исследования оценок решений, распространяющийся вниз по дереву.

Рисунок 3.1.

На рисунке 3.1 показано дерево поиска решения в момент, когда некоторые задачи (например, серые) активно заняты расширением поиска по дереву; а некоторые уже достигли конечных вершин и завершены или ждут, когда будет выполнена передача оценок решения по линиям соподчинения вершин в обратном направлении.

В программе, представленной текстом 3.4, дерево поиска задано условными целыми числами. Каждое число представляет лексикографически упорядоченный номер вершины, с которой связан вызываемый вычислительный процесс, оценивающий значение текущего решения.

Текст 3.4. – Поиск решения на двоичном дереве

globalclassTree     // Создается класс процессорного объекта

{                                                 // Tree  с единственной общей функцией

public:                             // search, являющейся членом этого класса

int search(int);

};

int Tree::search(int A) // Для класса Tree описывается процедура

// поиска концевых вершин на дереве с

// лексикографически упорядоченным

// множеством вершин А (см. рис. 3.1)

intls, rs;

if(leaf(A))         // Если вершина концевая (лист дерева),

{                                             // то проверяется критериальная функция

ifsolution(A)   // решения и устанавливается соответ-

return(1);               // ствующее значение признака 1 или 0

else

return(0);

}

else        // Вершина не концевая, поэтому создаются два новых

{                        // процессорных объекта: поддерево левое и правое

Tree *global lobj = new Tree;

Tree *global robj = new Tree;

par     // Создаются процедуры для рекурсивного

{                // обращения к новым объектам

ls = lobj->search(left_child(A));

rs = robj->search(right_child(A));

}

delete(lobj);         // Удаление процессорных объектов пос-

delete(robj);         // ле завершения запросов на поиск.

return(ls+ rs );            // Возврат значения признаков решения.

}

}

void main(int argc, char *argv[])

{

inttotal;

// Создается новый процессорный объект для исследования решения

Tree *global searcher = new Tree;

// Инициализация исследований с первого узла

total = searcher->search(1);

printf("There were %  /*…etceteras – и прочее …*/);

}

Приведенная программа использует две параллельные конструкции. Ключевое слово global объявляет процессорный объект Tree (дерево), а оператор par объявляет параллельный блок, в котором одновременно выполняются два рекурсивных обращения к процедуре search.

3.5  Организация связи

В языке CC++ нет примитивов нижнего уровня, которые бы непосредственно рассылали и получали данные между потоками. Процессы связываются между собой, используя структуры общих (разделяемых) данных. Один процесс, например, может добавлять в разделяемую структуру элементы, а другой – их удалять, обеспечивая, таким образом, одну из форм канальной связи. Существующие механизмы CC++ позволяют реализовать широкое разнообразие таких структур связи. Так, например, глобальные указатели используются для организации обмена данными между процессорными объектами, а синхронизирующие переменные и неделимые функции обеспечивают синхронизацию и взаимное исключение. Комбинированное их применение позволяет организовать и передавать структуры данных любой сложности.