Можно ли распараллелить с OpenMP список, который может добавлять новые элементы на каждой итерации? - PullRequest
Новая
       18

Можно ли распараллелить с OpenMP список, который может добавлять новые элементы на каждой итерации?

2 голосов
/ 06 ноября 2019

Можно ли как-нибудь использовать openMP для распараллеливания цикла со списком, в который может добавляться больше элементов на каждой итерации? Насколько я понимаю, openMP может распараллелить цикл for путем погружения диапазона в порции для каждого потока, но в этом случае диапазон изменяется, для одного случая цикл может иметь 10 итераций, а для другого 100, дело в том, что вlist Обычно у меня будет около 10-20 элементов.

Вот пример того, что я хотел бы распараллелить (обратите внимание, что порядок, в котором вещи вставляются в vectorOfResults, не имеет значения) 

while(!list.empty()) {
 vectorOfResults.push_back(performExpensiveFunction());
 if (conditions) {
   add new elements to the list;
 }
}

Я думал о том, чтобы сделать что-то вроде, внутри цикла while, иметь цикл for с текущим «пакетом» элементов в списке (скопировать их во временный список), а затем следующий, пока итерация будетиспользовать недавно добавленные элементы, но я подумал, есть ли способ сделать это, используя другие конструкции openmp. (Я только сейчас немного о openmp).

Спасибо за вашу помощь.

1 Ответ

1 голос
/ 06 ноября 2019

Я не думаю, что возможно увеличить размер параллельного цикла for после его запуска.

Вы можете запускать несколько параллельных циклов for один за другим, пока все данные не будут обработаны какпредложенный в этот ответ . Что-то вроде: 

Data proccessInParallel(Data d) {
    Data newData
    #pragma omp parellel for
    for (int i = 0; i < d.size i++) {
        // Do some processing
        if (create_new) {
            #pragma omp critical
            {
                newData.push_back(data)
            }
        }
    }
    return newData;
}

int main() {
   Data data;
   // Process data in batches until no new data is created
   do {
       data = proccessInParallel(data);
   } while (!data.empty());

Недостатком является то, что некоторые потоки могут быть неиспользованы во время обработки "пакетов".

Вы также можете попробовать использовать tasks анализировать новые элементы списка, не дожидаясь запуска другого цикла for.

Может быть что-то вроде: 


#pragma omp parallel for
for (int i = 0; i < N; i++) {
    process(data[i]);
    if (new_data) {
        #pragma omp task
        {
        process(new_data);
        }
    }
}

Задача будет выполнена, как только поток станет доступен для ее выполнения.

...