Максимальное количество ядер в рекурсивном дереве поиска с Open MP - PullRequest
Новая
       25

Максимальное количество ядер в рекурсивном дереве поиска с Open MP

0 голосов
/ 15 октября 2019

Я хочу реализовать дерево поиска, используя рекурсивную функцию. В каждом узле я оцениваю функцию Pass_or_Die. Если Pass, то узел расширяется на n больше ветвей, в противном случае он умирает. Предположим, что узел проходит с определенной фиксированной вероятностью.

Предположим, у меня есть машина с M > n ядрами. Я хотел бы использовать все свои ядра в дереве поиска. Приведенный ниже код демонстрирует простой пример дерева поиска.

Мои проблемы с этим примером использования openMP: 1) Программа использует только n ядер. Таким образом, он не использует все доступные ядра.

2) По выводу кажется, что дерево поиска просеивается постепенно. Это означает, что сначала проверяются все узлы на уровне 1, затем все узлы на уровне 2 и т. Д. Я хотел бы вместо этого сосредоточить внимание на прохождении через первые узлы и их поддеревья, пока они не умрут или не достигнут конца, а затем сосредоточиться на другомузлы.

Я также открыт для решения с использованием альтернатив openMP. 

#include <stdio.h> 
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "omp.h"

int n = 3;

// Pass with probability prob/100
int Pass_or_Die(int prob)
{
    int max = 100;
    if ((rand()%max)>(max-prob))
        return 1;
    else
        return 0;
}

// extend the node if Pass, kill it if Die. Print current thread in use, current node and PASS or DIE
void extend_node(int base_node, int extension)
{
    // extend the node
    base_node = base_node*10+extension;

    // get thread id number
    int th_id = omp_get_thread_num();

    // just some noise
    sleep(1);

    // if true, then the tree reaches the end, so do not extend
    if (base_node > 100000)
        return;

    // if Pass, then extend the tree. Pass with probability 0.2
    if (Pass_or_Die(20))
    {
        printf("th_id %d - %d PASS\n ", th_id, base_node);
#pragma omp target teams distribute parallel for
        for (int i = 1; i <= n; ++i)
        {
            extend_node(base_node, i);
        }
    }
    else
        printf("th_id %d - %d DIE\n ", th_id, base_node);
    return;
}


int main (int argc, char *argv[]) {

#pragma omp target teams distribute parallel for
    for (int i = 1; i <= n; ++i)
    {
        extend_node(0, i);
    }

    return 0;
}
...