Нерекурсивная итерация разбиения массива с помощью tbb :: paralllel_for - PullRequest
Новая
       53

Нерекурсивная итерация разбиения массива с помощью tbb :: paralllel_for

2 голосов
/ 03 июля 2019

Я пытаюсь выполнить вычисление для одномерного массива A[], используя TBB от Intel.Проблема заключается в том, что по умолчанию алгоритм, подобный tbb::parallel_for, рекурсивно разрезает массив пополам, отправляя каждый кусок в пул задач для кражи потоков.

Однако я хочу, чтобы все потоки "сканировали"«массив линейным способом.Например, при использовании 4 потоков они параллельно вычисляют сначала A[0], A[1], A[2] и A[3] в любом порядке.А затем вычислите набор A[4], A[5], A[6] и A[7] в любом порядке.

Прямо сейчас, parallel_for, после пары рекурсивных разбиений вычислили бы сначала A[0], A[2], A[4] и A[6] соответственно.А потом A[1], A[3], A[5] и A[7] (или что-то подобное).

Я использую C ++ 14 и Intel 10101 * Threading Building Blocks .Алгоритмы типа parallel_reduce или parallel_scan работают аналогичным образом в отношении разбиения пространства итераций, поэтому они не очень помогли.

Я предполагаю, что я определил свой собственныйИтерация космического объекта, но я не могу понять, как именно. документы дают это определение: 

class R {
    // True if range is empty
    bool empty() const;
    // True if range can be split into non-empty subranges
    bool is_divisible() const;
    // Splits r into subranges r and *this
    R( R& r, split );
    // Splits r into subranges r and *this in proportion p
    R( R& r, proportional_split p );
    // Allows usage of proportional splitting constructor
    static const bool is_splittable_in_proportion = true;
    ...
};

Все сводится к этому коду: 

#include <mutex>
#include <iostream>
#include <thread>

#include <tbb/parallel_for.h>
#include <tbb/task_scheduler_init.h>

std::mutex cout_mutex;

int main()
{
    auto N = 8;

    tbb::task_scheduler_init init(4);

    tbb::parallel_for(tbb::blocked_range<int>(0, N),
        [&](const tbb::blocked_range<int>& r)
        {
            for (int j = r.begin(); j < r.end(); ++j) {
                // Compute A[j]
                std::this_thread::sleep_for(std::chrono::seconds(1));
                cout_mutex.lock();
                std::cout << std::this_thread::get_id()<< ", " << j << std::endl;
                cout_mutex.unlock();
            }
        }
    );
}

Приведенный выше код дает: 

140455557347136, 0
140455526110976, 4
140455521912576, 2
140455530309376, 6
140455526110976, 5
140455557347136, 1
140455521912576, 3
140455530309376, 7

но я хотел что-то вроде: 

140455557347136, 0
140455526110976, 1
140455521912576, 2
140455530309376, 3
140455526110976, 5
140455557347136, 4
140455521912576, 6
140455530309376, 7

Есть предложения по объекту итерации или есть лучшее решение?

1 Ответ

1 голос
/ 05 июля 2019

Рассмотрите возможность использования внешнего атома, например (// !!! помечает измененные строки) 

#include <mutex>
#include <iostream>
#include <thread>

#include <tbb/parallel_for.h>
#include <tbb/task_scheduler_init.h>

#include <atomic>                                 // !!!

std::mutex cout_mutex;

int main()
{
    auto N = 8;

    tbb::task_scheduler_init init(4);

    std::atomic<int> monotonic_begin{0};           // !!!

    tbb::parallel_for(tbb::blocked_range<int>(0, N),
        [&](const tbb::blocked_range<int>& r)
        {
            int s = static_cast<int>(r.size());    // !!!
            int b = monotonic_begin.fetch_add(s);  // !!!
            int e = b + s;                         // !!!
            for (int j = b; j < e; ++j) {          // !!!       
                // Compute A[j]
                std::this_thread::sleep_for(std::chrono::seconds(1));
                cout_mutex.lock();
                std::cout << std::this_thread::get_id() << ", " << j << std::endl;
                cout_mutex.unlock();
            }
        }
    );
}

Подход дает: 

15084, 0
15040, 3
12400, 2
11308, 1
15084, 4
15040, 5
12400, 6
11308, 7

Почему важно иметь монотонное поведение?Возможно, вы захотите рассмотреть parallel_pipeline или потоковую диаграмму для определения расчетных зависимостей.

...