Блог

Главная - Вопросы по программированию - Почему я получаю этот вывод при распараллеливании моего поиска по дереву?

Почему я получаю этот вывод при распараллеливании моего поиска по дереву?

#java #parallel-processing #binary-tree #fork-join

#java #параллельная обработка #двоичное дерево #fork-join

Вопрос:

У меня есть двоичное дерево, где каждый узел равен 0 или 1. Каждый путь от корня до листа представляет собой битовую строку. Мой код последовательно выводит все битовые строки, и он работает нормально. Однако, когда я пытаюсь его распараллелить, я получаю неожиданный результат.

Узел класса

 public class Node{
  int value;
  Node left, right;
  int depth;

  public Node(int v){
    value = v;
    left = right = null;
  }
}

Последовательная версия Tree.java

 import java.util.*;
import java.util.concurrent.*;

public class Tree{
  Node root;
  int levels;
  LinkedList<LinkedList<Integer>> all;

  Tree(int v){
    root = new Node(v);
    levels = 1;
    all = new LinkedList<LinkedList<Integer>>();
  }
  Tree(){
    root = null;
    levels = 0;
  }
  public static void main(String[] args){
    Tree tree = new Tree(0);
    populate(tree, tree.root, tree.levels);
    int processors = Runtime.getRuntime().availableProcessors();
    System.out.println("Available core: " processors);
//    ForkJoinPool pool = new ForkJoinPool(processors);

    tree.printPaths(tree.root);

//    LinkedList<Integer> path = new LinkedList<Integer>();
//    PrintTask task = new PrintTask(tree.root, path, 0, tree.all);
//    pool.invoke(task);
//    for (int i=0; i < tree.all.size(); i  ){
//      System.out.println(tree.all.get(i));
//    }

  }

  public static void populate(Tree t, Node n, int levels){
    levels  ;
    if(levels >6){
      n.left = null;
      n.right = null;
    }
    else{
      t.levels = levels;
      n.left = new Node(0);
      n.right = new Node(1);
      populate(t, n.left, levels);
      populate(t, n.right, levels);
    }
  }

  public void printPaths(Node node)
   {
       LinkedList<Integer> path = new LinkedList<Integer>();
       printPathsRecur(node, path, 0);
//       System.out.println("Inside ForkJoin:  " pool.invoke(new PrintTask(node, path, 0)));
   }

  LinkedList<LinkedList<Integer>> printPathsRecur(Node node, LinkedList<Integer> path, int pathLen)
    {
        if (node == null)
            return null;

        // append this node to the path array
        path.add(node.value);
        path.set(pathLen, node.value);
        pathLen  ;

        // it's a leaf, so print the path that led to here
        if (node.left == null amp;amp; node.right == null){
            printArray(path, pathLen);
            LinkedList<Integer> temp = new LinkedList<Integer>();
            for (int i = 0; i < pathLen; i  ){
                temp.add(path.get(i));
            }
            all.add(temp);
        }
        else
        {
            printPathsRecur(node.left, path, pathLen);
            printPathsRecur(node.right, path, pathLen);
        }
        return all;
    }

    // Utility function that prints out an array on a line.
    void printArray(LinkedList<Integer> l, int len){
        for (int i = 0; i < len; i  ){
            System.out.print(l.get(i)   " ");
        }
        System.out.println("");
    }
}

Это приводит к ожидаемому результату:

 0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 0 1 1
...

Затем я распараллелил Tree.java:

 import java.util.*;
import java.util.concurrent.*;

public class Tree{
  Node root;
  int levels;
  LinkedList<LinkedList<Integer>> all;

  Tree(int v){
    root = new Node(v);
    levels = 1;
    all = new LinkedList<LinkedList<Integer>>();
  }
  Tree(){
    root = null;
    levels = 0;
  }
  public static void main(String[] args){
    Tree tree = new Tree(0);
    populate(tree, tree.root, tree.levels);
    int processors = Runtime.getRuntime().availableProcessors();
    System.out.println("Available core: " processors);
    ForkJoinPool pool = new ForkJoinPool(processors);

//    tree.printPaths(tree.root);

    LinkedList<Integer> path = new LinkedList<Integer>();
    PrintTask task = new PrintTask(tree.root, path, 0, tree.all);
    pool.invoke(task);
    for (int i=0; i < tree.all.size(); i  ){
      System.out.println(tree.all.get(i));
    }

  }

  public static void populate(Tree t, Node n, int levels){
    levels  ;
    if(levels >6){
      n.left = null;
      n.right = null;
    }
    else{
      t.levels = levels;
      n.left = new Node(0);
      n.right = new Node(1);
      populate(t, n.left, levels);
      populate(t, n.right, levels);
    }
  }
}

and added a task class:

 import java.util.concurrent.*;
import java.util.*;

class PrintTask extends RecursiveAction {
  LinkedList<Integer> path = new LinkedList<Integer>();
  Node node;
  int pathLen;
  LinkedList<LinkedList<Integer>> all = new LinkedList<LinkedList<Integer>>();

  PrintTask(Node node, LinkedList<Integer> path, int pathLen, LinkedList<LinkedList<Integer>> all){
    this.node = node;
    this.path = path;
    this.pathLen = pathLen;
    this.all = all;
  }

  protected void compute(){
    if (node == null){
      return;
    }
    path.add(pathLen, node.value);
    pathLen  ;

    if(node.left == null amp;amp; node.right == null){
      printArray(path, pathLen);
      LinkedList<Integer> temp = new LinkedList<Integer>();
      for (int i = 0; i < pathLen; i  ){
          temp.add(path.get(i));
      }
      all.add(temp);

    }
    else{
      invokeAll(new PrintTask(node.left, path, pathLen, all), new PrintTask(node.right, path, pathLen, all));

    }
  }
  void printArray(LinkedList<Integer> l, int len){
      for (int i = 0; i < len; i  ){
          System.out.print(l.get(i)   " ");
      }
      System.out.println("");
  }

}

И я получаю этот вывод:

 Available core: 8
0 0 1 0 1 1 1 0 0
0 1 1 0 1 1 1 0 1
0 0 1 1 1 0 0
1 1 1 1 0 1
1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1
1 1 1 1 0
0 1
...

[0, 1, 1, 0, 1, 1]
[0, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 0, 1]
[0, 1, 1, 1, 0, 0]
[0, 1, 1, 1, 0, 1]
[0, 1, 1, 1, 0, 1]
[0, 1, 1, 1, 0, 1]
[0, 1, 1, 1, 0, 1]
[0, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 0, 0]
...

Итак, при динамической печати пути он сильно отличается от ожидаемого результата, где каждый путь состоял из 6 бит. В этой версии я сохраняю все пути в списке списков и печатаю список в конце. Он содержит несколько правильно выглядящих битовых строк, но проблема в том, что это не все из них. Он выводит только битовые строки, начинающиеся с 011.

Комментарии:

1. можете ли вы изменить заголовок в форме вопроса с помощью вопросительного знака?

2. Пожалуйста, не разрушайте свой вопрос, удаляя код.

Ответ №1:

Проблема с параллельной реализацией связана с приведенной ниже строкой кода.

 invokeAll(new PrintTask(node.left, path, pathLen, all), new PrintTask(node.right, path, pathLen, all));

invokeAll будет выполнять задачи параллельно. Это приведет к 2 проблемам.

  • Нет гарантии, что левый узел будет выполнен раньше правого
  • Условие гонки может возникать в path pathLen переменных и, которые являются общими для всех задач.

Самый простой вариант исправить это — последовательно вызывать левую и правую задачи. Как показано ниже:

 new PrintTask(node.left, path, pathLen, all).invoke();
new PrintTask(node.right, path, pathLen, all).invoke();

Но при этом вы теряете преимущества параллельной обработки, и это так же хорошо, как выполнять их последовательно.

Чтобы обеспечить корректность и параллелизм, внесем следующие изменения

  • Измените тип all from LinkedList<LinkedList> на LinkedList[] . Мы установим размер массива 2 ^ (levels - 1) таким, чтобы вместить все узлы в дереве.
  • Кроме того, мы введем insertIndex переменную, чтобы конечные узлы вставляли список с правильным индексом в результирующий массив. Мы будем сдвигать влево это insertIndex значение на каждом уровне, а для правого дерева мы также увеличим его на 1.
  • Мы создадим 2 новых связанных списка на каждом уровне, чтобы избежать состояния гонки.

Измененная задача печати:

 class PrintTask extends RecursiveAction {
    LinkedList<Integer> path;
    Node node;
    LinkedList[] all;
    int insertIndex;

    PrintTask(Node node, LinkedList<Integer> path, LinkedList[] all, int insertIndex) {
        this.node = node;
        this.path = path;
        this.all = all;
        this.insertIndex = insertIndex;
    }

    protected void compute() {
        if (node == null)
            return;
        path.add(node.value);
        if (node.left == null amp;amp; node.right == null)
            all[insertIndex] = path;
        else
            invokeAll(new PrintTask(node.left, new LinkedList<>(path), all, insertIndex << 1),
                    new PrintTask(node.right, new LinkedList<>(path), all, (insertIndex << 1)   1));
    }
}

main() Изменения:

 ...
LinkedList[] result = new LinkedList[1 << tree.levels - 1];
PrintTask task = new PrintTask(tree.root, path, result, 0);
pool.invoke(task);
for (LinkedList linkedList : result) 
   System.out.println(linkedList);
...
Метки: