Конструкция Parallel.Invoke

Семинарское занятие № 4. Рекурсия и параллелизм (часть 1)

При изучении применения рекурсии в программировании, одним из наиболее типичных примеров является обработка структур данных, представленных в виде дерева. При этом, при обработке деревьев используются различные способы прохождения по их вершинам. Однако, при попытках параллельной (многопоточной) обработки деревьев возникают проблемы, которые отсутствуют при обычной, последовательной обработке.

Рассмотрим простую структуру данных - бинарное дерево ( Tree ):

class Tree<T>
{
    public Tree<T> Left, Right; // потомки
    public T Data; // данные для этого узла 
}

Предположим, что нам необходимо обработать каждую вершину дерева с помощью действия Action<T>, не заботясь о порядке в котором обрабатываются вершины. В последовательном, рекурсивном варианте это сделать очень легко:

public static void Process<T> (Tree<T> tree, Action<T> action)
{
    if (tree == null) return;

    // Обработать текущую вершину, затем левое поддерево,
    // а потом правое
 
    action(tree.Data);
    Process(tree.Left, action);
    Process(tree.Right, action);
}

Задача 1.

Реализуйте класс Tree, представляющий дерево с произвольной степенью ветвления (т.е., не только со степенью 2). Переделайте соответственно процедуру Process.

Нерекурсивный вариант с явным использованием стека (объекта класса Stack ) может выглядеть следующим образом:

public static void Process<T> (Tree<T> tree, Action<T> action)
{
    if (tree == null) return;
    var toExplore = new Stack<Tree<T> > ();

    // Начало обработки с корневой вершины
    toExplore.Push(tree);
    while (toExplore.Count > 0)
    {
        // Извлечь очередную вершину, обработать ее, поместить в 
        // стек ее потомков

        var current = toExplore.Pop();
        action(current.Data);
        if (current.Left != null) 
            toExplore.Push(current.Left);
        if (current.Right != null) 
            toExplore.Push(current.Right);
    }
}

Задача 2.

Переписать приведенный выше метод Process с использованием класса Queue вместо Stack.

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

С использованием средств .NET Framework, имеются различные возможности для реализации такого параллельного варианта. Ниже приведена реализация, следующая оригинальному рекурсивному алгоритму и использующая класс ThreadPool:

public static void Process<T> (Tree<T> tree, Action<T> action)
{
    if (tree == null) return;

    // Событие mre используется, чтобы реализовать возврат из
    // данного метода только после того, как будет закончена
      // обработка вершин-потомков

    using (var mre = new ManualResetEvent(false))
    {
        // Обработать левого потомка асинхронно

        ThreadPool.QueueUserWorkItem(delegate
        {
            Process(tree.Left, action);
            mre.Set();
        });

        // Обработать текущую вершину и правого потомка синхронно

        action(tree.Data);
        Process(tree.Right, action);

        // Ожидание окончания обработки левого потомка

        mre.WaitOne();
    }
}

Задача 3.

Показать, как аналогичный параллельный вариант можно реализовать, используя класс Thread.

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

public static void Process<T> (Tree<T> tree, Action<T> action)
{
    if (tree == null) return;

    // Необходимо воспользоваться конструкцией события
    // для ожидания завершения обработки потомков

    using (var mre = new ManualResetEvent(false))
    {
        int count = 2;

        // Обработать левого потомка асинхронно

        ThreadPool.QueueUserWorkItem(delegate
        {
            Process(tree.Left, action);
            if (Interlocked.Decrement(ref count) == 0) 
                mre.Set();
        });

        // Обработать правого потомка асинхронно

        ThreadPool.QueueUserWorkItem(delegate
        {
            Process(tree.Right, action);
            if (Interlocked.Decrement(ref count) == 0) 
                mre.Set();
        });

        // Обработать текущую вершину синхронно

        action(tree.Data);

        // Ожидание завершения обработки потомков

        mre.WaitOne();
    }
}

Задача 4.

Переписать приведенный выше метод Process в предположении, что класс Tree определен так, как в Задаче 1. Подготовьте несколько объектов класса Tree с количеством вершин, соответственно, 100, 200, 500, 1000, и протестируйте метод Process на данных деревьях.