Помогите с распараллеливанием потоков.

[Alexu007]

Вещь для меня новая, прошу помощи более опытных.

Есть вложенный цикл, например решето Эрастофена:

Код

C++ (Qt)
    const uint N = 1000000000;     //миллиард
 
    QBitArray bbuf(N, false);
 
    bbuf[0] = 1;
    bbuf[1] = 1;
 
    for(uint s = 2; s < N; s++)
    {
        if(bbuf.at(s) == false)
        {
           for(uint j = s * 2; j < N; j += s) bbuf[j] = true;
        }
    }

Ну где-то так. На моём компе работает  6 минут, хотелось бы ускорить, и заодно потоки выучить. Поэтому идея: допустим имеем 2 потока, каждый из которых может вычислять внутренний цикл. Внешний цикл проверяет, свободен ли поток, и если свободен - запускает его на выполнение. При этом ставится флаг занятости потока. После окончания вычислений поток сбрасывает флаг занятости. И так далее.

Вопросы: реализуемо ли это в принципе, и будет ли выигрышь во времени, т.е. будут ли при этом работать 2 ядра процессора?

[gil9red]

Посмотрите в сторону OpenMP

[m_ax]

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

У вас алгоритм не оптимально реализован.
И от распараллеливания здесь врят ли будет существенный выйгрыш..

[vizir.vs]

Решето Эратосфена не самый лучшей способ поиска простых чисел. Этот метод можно ускорить

[Igors]

[off]
выигрышь/выйгрыш - вспоминается классика

...на котором красовалась надпись: ВАСТОК-2. Я подошел и исправил обе ошибки: ВОСТОГ-2

[/off]

Что касается распараллеливания - то надо сначала для него переделать алгоритм (так бывает часто). Здесь хорошо на atomic. Главная нитка ищет след простое число, а в это время др нитки занимаются "вычеркиванием". Надо только не пускать главную дальше "уже вычеркнутого"

Внешний цикл проверяет, свободен ли поток, и если свободен ...

На эти грабли наступают абсолютно все - и много раз  

[Alexu007]

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

У вас алгоритм не оптимально реализован.
И от распараллеливания здесь врят ли будет существенный выйгрыш..

Дело не в алгоритме. Я не пишу никакую программу и эти простые числа мне не нужны. Просто, когда я запускаю эту прогу, комп показывает загрузку 25% - это одно ядро процессора. Интересно было бы попробовать загрузить 2 ядра или 4.

Ну так, к слову, эрастофена я оптимизировал. Во первых, внешний цикл достаточно тянуть до кв. корня. Во вторых, я выкинул чётные числа - в 2 раза расход памяти уменьшился и в 2 раза шустрей работать стал:

Код

C++ (Qt)
    const uint N = 1000000000/2;
 
    QBitArray bbuf(N, false);
 
    QTime t1 = QTime::currentTime();
 
    uint k;
 
    for(uint i = 0; i < sqrt(N)+1; i++)
    {
        if(!bbuf.at(i))
        {
            k = 2*i+3;
            for(uint j = k*(i+1)+i; j < N; j += k) bbuf[j] = true;
        }
    }

[m_ax]

Дело не в алгоритме. Я не пишу никакую программу и эти простые числа мне не нужны. Просто, когда я запускаю эту прогу, комп показывает загрузку 25% - это одно ядро процессора. Интересно было бы попробовать загрузить 2 ядра или 4.

Так я о том и говорю.. Вы выбрали пример, где распараллеливание не даст заметного выйгрыша, поскольку операция итерирования примерно совпадает по порядку с операцией во внутреннем цикле:

Код

C++ (Qt)
bbuf[j] = true;
 

+ Надо ещё учитывать затраты на создание потоков и т.п.. Короче, ваша задача едва ли раскроет тот потенциал, который можно извлечь от распараллеливания..
Я бы не стал именно здесь на этом замарачиваться, имхо.. Но, как уже здесь упоминалось, вы можете это легко проверить с помощью OpenMP)

Но есть, например, другие задачи, когда это существенно может ускорить время вычислений. Сам сейчас этим занимаюсь (особенно после того, как прикупил себе AMD FX 8350))
В частности, мне часто приходиться использовать распараллеленную версию std алгоритма transform. О реализации можно почитать, например здесь: http://www.prog.org.ru/topic_25963_15.html 

 

[Igors]

Вы выбрали пример, где распараллеливание не даст заметного выйгрыша, поскольку операция итерирования примерно совпадает по порядку с операцией во внутреннем цикле:

Основное время уходит на "вычеркивание" и эти операции независимы - поэтому даст. Другое дело что задача достаточно трудная. Да еще и учебная - поэтому заморачиваться и не хочется.

Код

C++ (Qt)
#pragma omp parallel for
for (int thread = 0; thread < num_thread; ++thread)
 for (uint i = 0; i < N; ++i)
    if (!bbuf.at(i))
 

Вот здесь надо каким-то образом проверить было ли значение в буфере уже "пройдено" всеми остальными нитками или еще нет.

По ходу дела

   for(uint i = 0; i < sqrt(N)+1; i++)

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

[Igors]

Да, есть прозаичный, хотя  и громоздкий, способ:

- находим все простые числа напр в диапазоне от 0 до 100
- запускаем "вычеркивание" всеми нитками для полного диапазона
- находим простые в след диапазоне - напр от 100 до 1000
и.т.д

Можно и по-другому, с LRU или даже с std::set ...

[Bepec]

А разве openmp не забирает на себя полностью эти проблемы? Насколько мне объясняли, openmp просто бьёт цикл на N частей и каждый отдаёт потоку. Собственно этим и достигается распараллеливание.

[Igors]

А разве openmp не забирает на себя полностью эти проблемы? Насколько мне объясняли, openmp просто бьёт цикл на N частей и каждый отдаёт потоку. Собственно этим и достигается распараллеливание.

Он может бить всяко-разно и диспатчить, напр

Код

C++ (Qt)
#pragma omp parallel for schedule(dynamic, 3)

Но он не отвечает за зависимость одного вычисления (тела цикла) от другого, а здесь она есть. Откройте в вике "решето Эрастофена"

[Alexu007]

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

Я проверял, по времени работает одинаково. Но если так неграмотно - поменяю.