分區的並行生成

Question

我正在使用生成一組分區的算法（用C實現）。 （代碼在這裏：http://www.martinbroadhurst.com/combinatorial-algorithms.html#partitions）。

我在想，如果有修改這個算法並行，而不是直線狀的方式？

我有我的CPU在多個內核，並想分區的生成分成多個正在運行的線程。

Answer 1

初始化包含第一k個元素的每一個分區共享集合。直到集合爲空時，每個線程反覆從集合中刪除一個分區，並使用您鏈接的算法爲剩餘的n-k個元素生成所有可能性（當增加當前n元素分區時，將獲得另一個k元素前綴前k個元素之一）。

Answer 2

正如你可以看到你提到的算法在基地n創建計數器每次把物品與相同數量的一組，在這種方式分區輸入。

從0 to (0,1,2,...,n-1)每個計數器的計數，這意味着A= N-1 +（N-2）* N + ... + 1 * N ^n-1個 0號。所以你可以在k個不同的線程上運行你的算法，在第一個線程中你應該從0到A/k，然後你應該從（A/k）+1到2 * A/k等等。意味着只是你應該添加long變量並使用上限檢查（在for循環的條件）同樣計算基礎n格式的值和相關號碼r*A/k for 0 <= r <= k。

Answer 3

首先，考慮串行算法的以下變化。取元素a，並將其分配給子集＃0（這總是有效的，因爲分區內子集的順序無關緊要）。下一個元素b可能屬於與a相同的子集或屬於不同的子集，即屬於子集＃1。然後，將元件c屬於任一＃0（與a一起）或＃1（具有b一起，如果它是獨立的從a），或它自己的子集（這將是＃1，如果＃0 = {a，b}或＃2（如果＃0 = {a}和＃1 = {b}）。等等。因此，您可以逐個添加新元素以部分構建分區，爲每個輸入生成幾個可能的輸出 - 直到您放入所有元素。並行化的關鍵是每個不完整的分區可以獨立地附加新元素，即與所有其他變體並行。

該算法可以用不同的方式實現。我將使用一種遞歸方法，其中一個函數被賦予一個部分填充的數組和一個當前的長度，並且複製數組的次數爲下一個元素的可能值（比數組當前的最後一個值多一個） ），將下一個元素設置爲每個可能的值，併爲每個新數組遞歸調用自身，並增加長度。這種方法對於盜用並行引擎的工作似乎特別有用，例如cilk或tbb。類似於@swen建議的實現也是可能的：您使用所有不完整分區和一個線程池的集合，並且每個線程從集合中獲取一個分區，生成所有可能的擴展並將它們放回集合;添加所有元素的分區顯然應該進入不同的集合。

Answer 4

這是我獲得的使用SWEN的建議C++實現。線程的數量取決於r的值。對於r = 6，分區數是第六個鍾號，它等於203.對於r = 0，我們只得到一個正常的非並行程序。

#include "omp.h" 
#include <bits/stdc++.h> 
using namespace std; 
typedef long long lli; 

const int MAX=10010; 
const int MX=100; 
int N,r=6; 

int F[MAX]; // partitions first r 
int Fa[MAX][MX]; // complete partitions 
int P[MAX]; // first appearances first r 
int Pa[MAX][MX]; // first appearances complete 

int next(){// iterates to next partition of first r 
    for(int i=r-1;i>=0;i--){ 
     P[F[i]]=i; 
    } 
    for(int i=r-1;i>=0;i--){ 
     if(P[F[i]]!=i){ 
      F[i]++; 
      for(int j=i+1;j<r;j++){ 
       F[j]=0; 
      } 
      return(1); 
     } 
    } 
    return(0); 
} 

int sig(int ID){// iterates to next partition in thread 
    for(int i=N-1;i>=0;i--){ 
     Pa[ID][Fa[ID][i]]=i; 
    } 
    for(int i=N-1;i>=r;i--){ 
     if(Pa[ID][Fa[ID][i]]!=i){ 
      Fa[ID][i]++; 
      for(int j=i+1;j<N;j++){ 
       Fa[ID][j]=0; 
      } 
      return(1); 
     } 
    } 
    return(0); 
} 

int main(){ 
    int N; 
    scanf("%d",&N); 
    int t=1,partitions=0; 
    while(t || next()){// save the current partition so we can use it for a thread later 
     t=0; 
     for(int i=0;i<r;i++){ 
      Fa[partitions][i]=F[i]; 
     } 
     partitions++; 
    } 
    omp_set_num_threads(partitions); 
     #pragma omp parallel 
    { 
     int ID = omp_get_thread_num(); 
     int t=1; 
     while(t || sig(ID)){// iterate through each partition in the thread 
      // the current partition in the thread is found in Fa[ID] 
     } 
    } 
}