java - 无向图DFS的并行实现

Question

我一直在尝试在 Java 中为无向图实现并行深度优先搜索。我写了这段代码，但它不能正常工作。它不会加速。

主要方法:

 package dfsearch_v2;

 import java.util.Calendar;
 import java.util.Stack;
 import java.util.Random;

 public class DFSearch_v2 {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {

    long ts_b, ts_e;
    int el_count=100;
    int thread_count = 4;
    int vertices[][]; // graph matrix
    boolean isVisited[] = new boolean[el_count];
    for(int i=0;i<el_count;i++){
        for(int j=0;j<el_count;j++){
            Random boolNumber = new Random();
            boolean edge = boolNumber.nextBoolean(); 
            vertices[i][j]=edge ? 1 : 
        }   
    }


    DFSTest r[] = new DFSTest[thread_count];
    ts_b = Calendar.getInstance().getTimeInMillis();
    for(int i = 0; i < thread_count; i++) {
        r[i] = new DFSTest(el_count,vertices,isVisited);
        r[i].start();
    }

    for(int i = 0; i < thread_count;    
        try {   
            r[i].join();
          } catch (InterruptedException e) {

          }
    }
    ts_e = Calendar.getInstance().getTimeInMillis();
    System.out.println("Time "+(ts_e-ts_b));      
}

线程实现:

package dfsearch_v2;

import java.util.Stack;

public class DFSTest extends Thread {

    int numberOfNodes;
    int adj[][];
    boolean isVisit[];



public DFSTest(int numberOfNodes, int adj[][],boolean isVisit[]){
    this.numberOfNodes = numberOfNodes;
    this.adj=adj;  
    this.isVisit=isVisit;
}

public void run()
{
    int k,i,s=0;
    Stack<Integer> st = new Stack<>();
    for(k=0; k < numberOfNodes; k++) isVisit[k]=false;
    for (k = numberOfNodes - 1; k >= 0; k--) {
        st.push(k);
    }
        DFSearch(st, isVisit);


}

   private void DFSearch(Stack<Integer> st,boolean isVisit[]){
       synchronized(isVisit){
        int i,k;
        while (!st.empty()) { 
        k=st.pop();
        if (!isVisit[k]) {
            isVisit[k] = true;
            System.out.println("Node "+k+" is visit");

            for(i=numberOfNodes-1; i>=0; i--)
                if(adj[k][i]==1) st.push(i);
        }

    }

  }

 }


}

请问有人能帮帮我吗？我真的是并行编程的新手。

谢谢

Answer 1

如果我正确理解您的程序，您将锁定在所有线程之间共享的 isVisit 数组 - 这意味着您不会获得任何加速，因为只有一个线程能够取得进展。尝试使用 ConcurrentHashMap或 ConcurrentSkipListMap相反。

// shared between all threads
ConcurrentMap<Integer, Boolean> map = new ConcurrentHashMap<>();

public boolean isVisit(Integer integer) {
    return map.putIfAbsent(integer, Boolean.TRUE) != null;
}

private void DFSearch(Stack<Integer> st) {
    if(!isVisit(st.pop())) {
       ...
    }
}

并发 map 使用分片来增加并行度。在 isVisit 中使用 putIfAbsent 方法来避免数据竞争(您只希望该方法为一个线程返回 false)。

至于如何在多个线程之间分配工作，请使用工作线程的 ConcurrentLinkedQueue。当一个线程没有更多的工作要执行时，它会将自己添加到工作线程队列中。当一个线程有两条边要遍历时，它会轮询工作线程队列以寻找可用的工作线程，如果有可用的，它会将其中一条边分配给工作线程。当所有线程都在可用线程队列中时，您就遍历了整个列表。