0

我一直在尝试在 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);
        }

    }

  }

 }


}

有人可以帮帮我吗？我对并行编程真的很陌生。

谢谢

4

3 回答 3

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())) {
       ...
    }
}

并发映射使用分片来增加并行度。使用putIfAbsentin 方法isVisit避免数据竞争（您只希望该方法为一个线程返回 false）。

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

于 2013-06-04T23:18:24.160 回答
1

您不需要在isVisit上进行同步，这会破坏您的并行性。布尔数组的多个读取器/多个写入器应该是非常安全的。

如果可能的话，您应该避免线程之间的依赖关系。为此，不要使用共享堆栈（如果这是您的代码正在执行的操作 - 尚不清楚）。

在您的情况下，每个顶点完成的工作量很小，因此在每个线程中批处理工作并且仅在达到某个积压阈值时才考虑将工作交给其他线程是有意义的。

于 2013-06-05T00:31:49.717 回答
0

我稍微改变了方法。现在它使用一个由所有线程共享的全局堆栈和 n 个本地堆栈，其中 n 是线程数。每个线程将其子树的节点存储在其本地堆栈中。最初，全局堆栈包含树的根，只有一个线程可以访问它，而其他线程正在等待被工作线程唤醒。工作线程从全局堆栈中检索并处理根，将一个后继线程添加到其本地堆栈，然后将其余后继线程（如果存在）推送到全局堆栈以供其他线程处理，并唤醒所有等待线程。所有其他线程都遵循相同的方法（即

然而，它并没有加速。我会感谢你所有进一步的想法。

主要方法：

package dfsearch_v2;

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




public class DFSearch_v2 {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here
    long ts_b, ts_e;
    //number of nodes
    int el_count=400;
int thread_count = 8;
    int gCounter=0;
    int vertices[][] = new int[el_count][el_count]; // 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 : 0;

        }   
    }
    DFSearch2 r[] = new DFSearch2[thread_count];
          ts_b = Calendar.getInstance().getTimeInMillis();
          for(int i = 0; i < thread_count; i++) {


            r[i] = new DFSearch2(el_count,vertices,isVisited,gCounter);
            r[i].start();

    }      
        for(int i = 0; i < thread_count; i++) {

        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 DFSearch2 extends Thread{

private boolean isVisit[];
private final Stack<Integer> globalStack;
int numberOfNodes;
//traversal is done ?
boolean isDone;
int adj[][];
// count visited nodes
int gCounter;

public DFSearch2(int number_Nodes,int adj[][],boolean isVisit[],int gCounter){
    this.numberOfNodes=number_Nodes;
    this.isVisit = isVisit;
    this.globalStack = new Stack<>();
    this.isDone=false;
    this.adj=adj;
    this.gCounter=gCounter;
    this.globalStack.push(number_Nodes-1);

}

public void run(){

        // local stack
        Stack<Integer> localStack = new Stack<>();
        while (!isDone) { 
            int k;
            synchronized(globalStack){
             k = globalStack.pop();  
             //pop until k is not visited
             while (isVisit[k]) { 
                if(globalStack.empty()) {
                    isDone=true;
                    return;
                }else{
                    k=globalStack.pop();
                }
              }

            } 
            // traverse sub-graph with start node k
            DFSearchNode(localStack,k);
            yield();
            if(globalStack.empty()) {
               isDone = true; 
            }
            // if gCounter is not null unvisited node are pushed in globalStack
            if(isDone&&gCounter<numberOfNodes){ 
                isDone=false;
                //unvisited nodes are pushed in globalStack
                for (int i = 0; i < isVisit.length; i++) {
                    if (!isVisit[i]) {
                      globalStack.push(i);  
                    }  

                }
            }


   }


}    
 synchronized private void DFSearchNode(Stack<Integer> localStack, int k){

            localStack.push(k);

            while (!localStack.empty()) {
               int s=localStack.pop();
               if (!isVisit[s]) {
                    isVisit[s] = true;
                    gCounter++;
                    //System.out.println("Node "+s+" is visit");
                   //first element is pushed into localStack and anothers in   globalStack
                     boolean flag = true; // local or global stack (true -> local; false ->global )
                     for(int i=numberOfNodes-1; i>=0; i--)
                     {
                       //   
                       if(i==s) continue;
                       //push another successors in global stack
                       if(adj[s][i]==1&&!flag&&!isVisit[s]){//visited nodes are not pushed in globalStack
                           globalStack.push(i);
                       }
                       //push first successor  in global stack
                       if(adj[s][i]==1&&flag&&!isVisit[s]) //visited nodes are not pushed in localStack
                       {
                           localStack.push(i);
                           flag=false; //only first element is pushed into localStack
                       } 

                     }                
               }


            }

}

}
于 2013-06-08T20:36:35.717 回答