OpenMP並列化の一般的なアルゴリズムの使用

OpenMP並列化の一般的なアルゴリズム
Openmpは強力なパラレルコンパイルライブラリで、ダイナミックにマルチスレッドを設定でき、使いやすいです.ここでは検索アルゴリズムを例に、OpenMPで一般的なアルゴリズムを並列化する方法を紹介します.
旅行者問題
旅行業者の問題はもうありふれたことだ.有向帯域重みマップ内で、最短ループを探します(頂点ごとに1回のみ通過し、重み値の合計が最小です).実際,この問題はNPhard問題であり,解決するには指数級の時間的複雑さしかかからない.BFSとDFSを用いてそれを解くことを試みた.問題は各頂点を通過することを要求しているので、ループは現れません.つまり、私たちの検索がすでに通過した頂点を歩かないことを約束すれば、検索の状態は永遠に交差しません.つまり、私たちは解空間ツリーで解く必要があります.検索状態を表す構造体と、次の状態を求めるアルゴリズムを定義します.

/*
           
         ，  order[i]  i      
    ，   order[i] 0，         1
front         ，         。
order[i]==-1       ，           。
*/
struct Node
{
	int order[N];
	int front = -1;
	int cost = 0;
	Node() { fill(order, order + N, -1); }
};

successorsアルゴリズムは簡単で,構造体で頂点が遍歴されたか否かを判別する方法order[i]=−1を定義し,すべての頂点を遍歴し,遍歴されていない頂点を後継頂点として新しい解状態ノードを生成するだけでよい.DFSアルゴリズムを考慮すると,非再帰的な形式,すなわちスタックとサイクルシミュレーションで再帰すれば,自然にサイクル形式のDFSアルゴリズムを実現できる.解空間ツリーを検索している以上,ループの各部分に相関がないのでparallel for文でDFSを直接並列化できるのはかなり簡単である.解空間ツリーの分岐因子は最上位層でn−1であり,下位層毎にforループを単純に分割して並列を実現する場合,最上位層で分割するのが最適解である.nがスレッド数よりはるかに大きい場合は自然に可能であるが,本問題はNPhard問題であり,nが大きい場合は解くことが不可能であり,一般的にnは数十程度であるが,我々のスレッド数は多くなる可能性があり,これにより大きな負荷不均衡をもたらし,我々の従来の並列優位性を失う.このためには並列化されたBFSが必要であり,BFSはキューによって行われる.毎回チームの頭からノードを取り出し、successorsを求めて、新しいノードをチームの尾に入れます.各successors動作間は並列であり,一度のsuccessors動作では線形時間の複雑さしか必要とせず,従来の大規模な問題を粒子化することが容易に分かった.我々のマルチスレッドが毎回キューから要素を要求し,successorsを並列に実行し,新しいノードをキューに入れる限り,良好な負荷等化並列探索アルゴリズムを実現した.注意すべき点は、キューは並列popとpushを許可しないため、操作キューのコードはスレッドロックを設定されるべきである.また,グローバル変数を修正しsolutionを最適に解く場合にもスレッドロックを設計する.もう一つの問題は,単一スレッドでは,キューが空の場合が検索完了の場合であると直接考えている.ただし、マルチスレッドでは、検索が完了していない場合でも、キューが空になる可能性があります.この場合、スレッドがキュー内の要求要素に行くと、エラーが発生します.したがって,検索を完了するには他の論理が必要であり,すべてのリーフノード,すなわちgoalstateが検索されると,検索は本当に終了する.これまで、キューから要素を取得できなくてもループを終了することはできず、待機する必要があるスレッドもありました.bfsのcppコードは以下の通りです.

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define N 4

/*
  ：
                 。
         n           ，      
       ，          “  ”，  
     cost  。        ，     
           ，             
   。

  ：                   ，    
       DFS  。      ，     “   
  ”，       n   ，  m     ，    
 (       )  (n-1)! 。         n-1，   
  ，        for       ，       
   。    comm_sz n   ，              
     ，      ，              

BFS ，     ，           ，  successors 
        。          O(n)，   m=b，  
    。       “  ”  ，           
  。     ，          queue，        
  queue      ，                  。
          (    )，  cost          。

      ， n      ，        n    ，  
    。

*/




struct Node
/*
           
         ，  order[i]  i      
    ，   order[i] 0，         1
front         ，         。
order[i]==-1       ，           。
*/
{
	int order[N];
	int front = -1;
	int cost = 0;
	Node() { fill(order, order + N, -1); }
};

queue<Node> Q;//       
int bestPath[N];//   
int bestCost = 9999999;
int graph[N][N];//    


void showpath(int order[N]) {
	int path[N];
	for (int i = 0;i < N;i++) {
		path[order[i]] = i;
	}
	for (int i = 0;i < N;i++) {
		cout << path[i] << "->";
	}
	cout << 0 << endl;
}


/*
input.txt:
0 1 3 8
5 0 2 6
1 18 0 10
7 4 12 0
*/


int main()
{
	freopen("input.txt", "r", stdin);
	for (int i = 0;i < N;i++)
		for (int j = 0;j < N;j++)
			cin >> graph[i][j];
	Node start;
	start.order[0] = 0;
	start.front = 0;// 0     
	Q.push(start);
	omp_lock_t changeQ, changeSolu;
	omp_init_lock(&changeQ);
	omp_init_lock(&changeSolu);
	int goal_cnt = 0;
	/*     goal    
	                  
	    ，                      
	     ，        ，          ， 
	                   。       
	          ，       ，   goalstate
	        ，        。    ，      
	          ，       ，       */
	int MAX_CNT = 1;
	for (int i = 1;i < N;i++) MAX_CNT *= i;
#	pragma omp parallel num_threads(4)
	{
		while (goal_cnt<MAX_CNT) 
		{
			Node n;
			omp_set_lock(&changeQ);
			if (!Q.empty()) {
				n = Q.front();
				Q.pop();
			}
			omp_unset_lock(&changeQ);
			if (n.front==-1) //     
				continue;
			bool goal = 1;
			for (int i = 0;i < N;i++) {
				if (n.order[i] != -1)
					continue;
				else {
					Node newNode;
					copy(n.order, n.order + N, newNode.order);
					newNode.order[i] = n.order[n.front] + 1;
					newNode.cost = n.cost + graph[n.front][i];
					newNode.front = i;
					omp_set_lock(&changeQ);
					cout << "Process " << omp_get_thread_num() << " push" << endl;
					for (int x : newNode.order)
						cout << x << " ";
					cout << endl;
					Q.push(newNode);
					omp_unset_lock(&changeQ);
					goal = 0;
				}
			}
			if (goal) {//     
				omp_set_lock(&changeSolu);
				int final_cost = n.cost + graph[n.front][0];
				goal_cnt++;
				if (final_cost < bestCost) {
					bestCost = final_cost;
					copy(n.order, n.order + N, bestPath);
				}
				omp_unset_lock(&changeSolu);
			}
		}
	}
	cout << "Best path is: ";
	showpath(bestPath);
	cout << "Cost: " << bestCost << endl;
}