Параллельная генерация перегородок

Question

Я использую алгоритм (реализованный в C), который генерирует разделы набора. (Код здесь: http://www.martinbroadhurst.com/combinatorial-algorithms.html#partitions).

Мне было интересно, есть ли способ изменить этот алгоритм для параллельного выполнения вместо линейного?

У меня есть несколько ядер на моем процессоре, и я хотел бы разделить генерацию разделов на несколько работающих потоков.

Answer 1

Вот реализация C ++, которую я получил, используя предложение swen. Количество потоков зависит от значения 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]
        }
    }
}

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 и проверить ее с верхней границей (в ваших условиях цикла). Также вычисляется значение A и соответствующее число в базовом формате 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

Инициализирует общую коллекцию, содержащую каждый раздел первых k элементов.Каждый поток, пока коллекция не пуста, многократно удаляет раздел из коллекции и генерирует все возможности для оставшихся n - k элементов, используя алгоритм, к которому вы привязаны (получите другой префикс k-элемента, если приращение текущего раздела n-элемента изменитсяодин из первых k элементов).