Параллельное сито Эратосфена

Впервые я попытался использовать потоки самостоятельно, чтобы реализовать параллельное сито Эратосфена . Фокус в том, что каждый раз, когда найдено простое число, создается поток, чтобы исключить все кратные этого простого числа из булева вектора (той, которая указывает, является ли число простым или нет). Вот мой код:

#include <cmath>
#include <functional>
#include <thread>
#include <vector>

// Invalidates the multiples of the given integer
// in a given boolen vector
template<typename Integer>
void apply_prime(Integer prime, std::vector<bool>& vec)
{
    for (Integer i = prime*2u ; i < vec.size() ; i += prime)
    {
        vec[i] = false;
    }
}

template<typename Integer>
auto sieve_eratosthenes(Integer n)
    -> std::vector<Integer>
{
    std::vector<bool> is_prime(n, true);
    std::vector<std::thread> threads;
    std::vector<Integer> res;

    auto end = static_cast<Integer>(std::sqrt(n));
    for (Integer i = 2u ; i <= end ; ++i)
    {
        // When a prime is found,
        // * add it to the res vector
        // * spawn a thread to invalidate multiples
        if (is_prime[i])
        {
            res.push_back(i);
            threads.emplace_back(apply_prime<Integer>,
                                 i, std::ref(is_prime));
        }
    }

    for (auto& thr: threads)
    {
        thr.join();
    }

    // Add the remaining primes to the res vector
    for (Integer i = end+1u ; i < is_prime.size() ; ++i)
    {
        if (is_prime[i])
        {
            res.push_back(i);
        }
    }
    return res;
}

Простые числа добавляются в два этапа к вектору res: каждый prime \ $ p \ $, такой как \ $ p <\ sqrt {n} \ $ добавляется при обнаружении простого числа до того, как будет получен соответствующий поток. Остальные простые числа добавляются в конце функции. Вот пример main:

int main()
{
    auto primes = sieve_eratosthenes(1000u);

    for (auto prime: primes)
    {
        std::cout << prime << " ";
    }
}

Я был уверен, что у меня возникнут проблемы из-за параллелизма, но по какой-то причине он работает. Я получил ожидаемые результаты в правильном порядке. Чтобы быть уверенным, я хотел бы знать, является ли моя программа правильной или имеет некоторые проблемы с потоками, которые я не мог видеть.

Примечание. Я использовал многие идеи из ответа, чтобы улучшить код и написал последующий вопрос .

36 голосов | спросил Morwenn 12 PMpSat, 12 Apr 2014 23:33:35 +040033Saturday 2014, 23:33:35

5 ответов


22

Как вы правильно предполагаете, с вашим кодом связаны несколько связанных с потоками вопросов, но позволяет дразнить вас и начинать с обычных подозреваемых.

Нейминг

Имя apply_prime вводит в заблуждение и невыразительно. Кроме того, функция действительно не требует простого и не применяется, справедливо ли это. Вы должны называть его чем-то вроде строк: strike_out_multiples или что-то подобное.

Эффективность

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

И теперь для основного действия:

Безопасность резьбы

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

Сортировка:

Ничто не мешает системе «отдать предпочтение» вашему основному потоку и позволить всем остальным работать после того, как основной поток попадет в цикл join. Это приводит к неправильным результатам, поскольку mainthread распахивается через полностью true, прежде чем кто-либо сможет сказать, что, например, 4 не является простым.

Параллельная запись:

Это может быть немного, а не проблема, но по крайней мере в старом стандарте std::vector<bool> была специализация, которая использовала только один бит на значение. В то время как это экономит вам некоторое пространство, оно поставляется со стоимостью фактического доступа к 8 бит при работе только с одним. Это означает, что два потока могут хорошо работать с разными битами, но в том же байте. Рассмотрим это:

В потоке 1 записывается ложь в бит 4, а поток 2 записывает ложь в бит 6. Оба они расположены в байте 0. Теперь оба начинаются с чтения начального значения байта, скажем (true, true, true, false, true , true, true, true) и сохраняет их! Теперь один из двух потоков напишет свое значение позже другого и перезапишет ложное значение другого -> потерянное обновление.

Возможно, это может произойти даже с байтовыми байлевыми размерами, поскольку некоторые архитектуры не допускают только байт-мудрый доступ, а только мудрый (что приводит к той же проблеме, только с более широкими размерами).

ответил Nobody 12 PMpSat, 12 Apr 2014 23:49:19 +040049Saturday 2014, 23:49:19
20

Как правило, это хороший, хорошо структурированный код, но он полагается на обещание, которое может не сохраниться.

В частности, одновременный доступ к различным элементам в std::vector<bool> не гарантируется как потокобезопасный , поскольку байты хранения могут совместно использоваться несколькими битами в vector.

Рассмотрим альтернативный способ срезания вещей. Каждый поток может отвечать за собственный раздел булевого массива. По мере того, как становятся известны простые числа, они могут быть отправлены на каждый из потоков для одновременного устранения из соответствующего раздела.

Также неплохо бы иметь параметр настройки, в котором размер подмашины сбалансирован относительно стоимости нереста другого потока.

Edit: Я изменил main следующим образом:

int main()
{
    auto primes = sieve_eratosthenes(20000000u);

    long long s=0;    
    for (auto prime: primes)
        s += prime;
    std::cout << s << '\t' << primes.size() << std::endl;
}

Затем я запустил код четыре раза и получил этот результат:

12273796368896  1270814
12273126258541  1270843
12273106282821  1270780
12272824476679  1270794

Таким образом, либо число простых чисел действительно меняется с итерации на итерацию (что математики обычно считают маловероятной возможностью!), либо проблема с конфликтом потоков проявляется. Правильные цифры:

12272577818052  1270607

Изменить 2: Я столкнулся с этой статьей , которая прекрасно объясняет число возможных подходов к распараллеливанию алгоритма решета Эратосфена.

ответил Edward 13 AMpSun, 13 Apr 2014 00:25:08 +040025Sunday 2014, 00:25:08
14

Игнорирование проблем с памятью с использованием недействительности кэша (что замедлит работу кода).

Создание потока относительно дорого (как вам нужно выделить стек и сохранить его). Поэтому вместо создания и уничтожения потоков лучше поддерживать пул потоков и повторно использовать потоки.

Количество потоков для пула в пуле должно быть немного больше, чем общее количество ядер, которые вы имеете (как правило, * 1.x (где x находится в диапазоне 2 => 5) - это число потоков, которые вы должны положить в пул).

ответил Martin York 13 AMpSun, 13 Apr 2014 00:44:38 +040044Sunday 2014, 00:44:38
11

Собственно, потоки просто совершенно неправильны. Во всем мире есть условия гонки. Из-за проблемы, она не имеет много видимых эффектов, но она по-прежнему неправа.

Выходной цикл в sieve_eratosthenes перебирает индексы от 2 до конца и проверяет, отмечены ли элементы массива как «простые». В этом цикле он запускает потоки, которые изменяют элементы массива от «prime» до «non-prime». Нет гарантии того, насколько продвинулись эти потоки. Поэтому, когда внешний цикл проверяет, являются ли 4, 6, 8, 9, 10, 12 и т. Д., Нет гарантии, что они действительно были помечены как нестандартные. В худшем случае внешний цикл запускает поток для каждого i от 2 до конца, пока ни один из этих потоков не запущен. В случае простого сита, который не изменяет правильность, но в целом эта программа не делает то, что она должна делать.

В потоках установлены логические значения в false. Они, как правило, устанавливают одинаковые значения в false несколько раз. Например, потоки для 2 и 3 оба устанавливают каждый кратный 6 на false. Два потока, записывающие одну и ту же переменную, называются «условием гонки», и это больше, чем просто плохо. В этом случае это не влияет, потому что оба потока устанавливают одно и то же значение boolean в false. В общем, это вызовет серьезные ошибки.

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

ответил gnasher729 13 PMpSun, 13 Apr 2014 12:46:56 +040046Sunday 2014, 12:46:56
5

Ни один из других ответов не упоминал, что на самом деле существует проблема, когда значение, переданное в сито, является простым числом. Например, sieve_eratosthenes(7u) возвращает вектор, содержащий 2 3 5. Это связано с тем, что вектор is_prime слишком короткий одним элементом: он рассматривает элементы между \ $ 0 \ $ и \ $ n-1 \ $, в то время как он должен учитывать элементы между \ $ 0 \ $ и \ $ n \ $. Он должен был быть объявлен как:

std::vector<bool> is_prime(n+1u, true);

Кроме того, как упоминалось в одном из комментариев, я могу заменить apply_prime на lambda. Взятие is_prime по ссылке в захвате лямбда также позволяет отбросить std::ref и соответствующий #include <functional>. Вот измененный threads.emplace_back:

threads.emplace_back([&is_prime](Integer prime)
{
    for (Integer i = prime*2u ; i < is_prime.size() ; i += prime)
    {
        is_prime[i] = false;
    }
}, i);
ответил Morwenn 13 PMpSun, 13 Apr 2014 14:30:15 +040030Sunday 2014, 14:30:15

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132