Оптимальное распараллеливание задачи по нахождению порождающего полинома CRC32

Question

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

        uint crc_Target = 0x62e2c0d8;

        byte[] data =
        {
            ///
        };

        Stopwatch sw = new Stopwatch();

        sw.Start();

        uint maxValue = 0xf4240;

        for (uint i = 0; i <= maxValue; i++)
        {
            if (crc32(data, i) == crc_Target)
            {
                Console.WriteLine($"Done:{i:X}");
            }
        }            

        sw.Stop();

        Console.WriteLine(sw.ElapsedMilliseconds);

получаем, что время выполнения в одном потоке ~8500 мс на 1000000 вариантов на ноуте с 4 физическими ядрами.

если заменить этот код на этот:

     var result = Parallel.For(0, maxValue, i =>
        {
            if (crc32_2(data, (uint)i) == crc_Target)
            {
                Console.WriteLine($"Done:{i:X}");
            }
        });

То получим ~1200 мс. Что примерно совпадает с моими теоретическими расчётами типа 8 логических ядер, параллельно должно быть примерно в 8 раз быстрее. Так и выходит 8500 мс и 1200 мс примерно...

Процы при этом нагружаются на 100% если поставить количество итерация побольше. Всё хорошо и на ноуте меня всё устраивает. Переношу приложение на Windows Server 2012R2 c 2 процами по 20 ядер. Запускаюсь и получаю на 1 млн итераций 800 мс. но даже если поставить maxValue = 0xffffffff, то процы на сервере полностью не загружаются как на ноуте. Загрузка по процам идёт какая-то рваная, то и дело просадки до 0 по отдельным ядрам. Почему на сервере приложение ведёт себя по другому? Это сама серверная винда там что-то скидывает, либо можно как-то оптимизировать приложение, чтобы дать равномерную нагрузку на все ядра и увеличить скорость расчётов?

Answer 1

В итоге решение для использования всех ядер для конкретно моего случая сработало изменение целевой платформы на x64. Это касается и с++.

Рабочий код на C#:

        var result = Parallel.For(0, maxValue, (i, state) =>
        {
            if (crc32_2(data, (uint)i) == crc_Target)
            {
                Console.WriteLine($"Done:{i:X}");
                state.Break();

            }
        });

время нахождение порождающего полинома 511322 мс.

Рабочий код на С++:

run_with_cancellation_token([minValue, maxValue, data, size, target_CRC, &cts]()
{
    parallel_for(minValue, maxValue, [data, size, target_CRC, &cts](uint value)
    {
        if (crc32(data, size, value) == target_CRC)
        {
            std::cout << "CRC find: " << hex << value << endl;
            cts.cancel();
        }
        
    });

}, cts.get_token());

время нахождение порождающего полинома 141919 мс. Код на с++ оказался почти в 5 раз быстрее.

БЛОГ НА HUSL

Оптимальное распараллеливание задачи по нахождению порождающего полинома CRC32

Ответы (1 шт):