Распределение потоков

[AndryG]

Доброго времени суток.Возникла необходимость повысить производительность системы,так требуется перебор возможных комбинаций чисел,просто создание потоков созданием новых while циклов не дает должных результатов,а напротив уменьшает скорость выполнения задач.Так как не представляю как распределить потоки для разных ядер процессора в LV,прошу помощи,подсказки знающих людей. Заранее благодарю за помощь.

[alerm]

Вообще сама может в распараллеливание:

Но если хотите прям жестко "посадить" цикл на определенное ядро (на самом деле поток), то нужен Timed Loop:

Возможно стоит побольше описать задачу? Может подход к увеличению циклов в корне неправильный?

[IvanLis]

Доброго времени суток.Возникла необходимость повысить производительность системы,так требуется перебор возможных комбинаций чисел,просто создание потоков созданием новых while циклов не дает должных результатов,а напротив уменьшает скорость выполнения задач.Так как не представляю как распределить потоки для разных ядер процессора в LV,прошу помощи,подсказки знающих людей. Заранее благодарю за помощь.

Код выкладывайте, т.к. не "зная броду, не суйся в воду"
Ну а While циклы LabVIEW сама не распараллелит ни как (если это один цикл), For может, но для этого нужно Iteration Parallelism включать.

[AndryG]

Код выкладывайте, т.к. не "зная броду, не суйся в воду"
Ну а While циклы LabVIEW сама не распараллелит ни как (если это один цикл), For может, но для этого нужно Iteration Parallelism включать.

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

[AndryG]

Вообще сама может в распараллеливание: Снимок экрана 2022-07-22 231503.png
Но если хотите прям жестко "посадить" цикл на определенное ядро (на самом деле поток), то нужен Timed Loop: Снимок экрана 2022-07-22 231742.png
Возможно стоит побольше описать задачу? Может подход к увеличению циклов в корне неправильный?

Спасибо,за помощь, первый вариант не подходит,я пробовал и писал про него выше,второй попробую,еще может IvanLis идею с парллелизмом стоит проверить.

[IvanLis]

Дело не в целях, а в конкретной реализации.
Хотя теперь я и с целями запутался
Изначально было озвучено:

... требуется перебор возможных комбинаций чисел ...

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

Потом начали работать с одним числом:

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

но тогда не понятно, что за комбинации из его частей мы ожидаем получить?

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

Открывать свою тайну или нет, решать только Вам.
Решение зависит от понимания задачи и ее реализации.

[AndryG]

Открывать свою тайну или нет, решать только Вам.
Решение зависит от понимания задачи и ее реализации.

IvanLis , никакой тайны пока нет, программа должна проверять полиномы на примитивность.Программа работает,но как только степень полинома становиться выше 17 ,скорость проверки уменьшается до не приличных размеров,вот я и подумал,что может заставить выполняться код на разделенных потоках.Если интересно помоч, я выложу черновую версию своей программы, может найдется интересное решение и кому-то еще поможет)

Запускать нужно PolyPrimeCheck.

Poli.rar

(40.22 КБ) 48 скачиваний

Несколько полиномов разной степени для проверки,степень Order

0b1101; //1+X+X^3 Третьего порядка примитивный
0b1111; //1+X+X^2+X^3 Третьего порядка непримитивный

0b1100001; //1+X+X^6 Шестого порядка примитивный
0b1100101; //1+X+X^2+X^4+X^6 Шестого порядка непримитивный
0b1011011; //1+X^2+X^3+X^5+X^6 Шестого порядка примитивный

0b101110001; //1+X^2+X^3+X^4+X^8 Восьмого порядка примитивный
0b111110001; //1+X+X^2+X^3+X^4+X^8 Восьмого порядка непримитивный

0b1100101000001; //1+X+X^4+X^6+X^12 двенадцатого порядка примитивный

0b111000000000000000000010000000001; //1+X+X^4+X^6+X^12+X^24+X^32 32 порядка примитивный

[IvanLis]

никакой тайны пока нет, программа должна проверять полиномы на примитивность

Какая максимальная степень полинома, который должен проверяться и какое время проверки считаете приемлемым?
Или хотите просто его минимизировать?

И можно ссылку на алгоритм, который Вы используете при проверке.

[IvanLis]

Смотрите, я не вникая в сам алгоритм, ушел от необходимости "сдвигового регистра" в основной функции (регистр использовался только для подсчета % выполнения) и распараллелил вычисления на 4 потока (в архиве 8 потоков, у меня процессор 4 ядра), сделал функцию реентерабельной.

В результате время вычисления для полинома 12 степени сократилось с 5399ms до 952ms (5,67 раза).
Старайтесь избегать сдвиговых регистров, они не позволяют распарралеливать вычисления.

PolyPrim.zip

(19.4 КБ) 48 скачиваний

Я не силен в теории кодирования, но может существуют рациональные тесты на "примитивность полинома" кроме brute force, типа как тест на простые числа AKS или что-то подобное?

[AndryG]

Смотрите, я не вникая в сам алгоритм, ушел от необходимости "сдвигового регистра" в основной функции (регистр использовался только для подсчета % выполнения) и распараллелил вычисления на 4 потока (в архиве 8 потоков, у меня процессор 4 ядра), сделал функцию реентерабельной.

В результате время вычисления для полинома 12 степени сократилось с 5399ms до 952ms (5,67 раза).
Старайтесь избегать сдвиговых регистров, они не позволяют распарралеливать вычисления.
PolyPrim.zip
Снимок экрана от 2022-07-23 23-59-45.png
Снимок экрана от 2022-07-23 23-58-32.png

Я не силен в теории кодирования, но может существуют рациональные тесты на "примитивность полинома" кроме brute force, типа как тест на простые числа AKS или что-то подобное?

Спасибо большое за помощь, я тоже пока не силен,пользуюсь литературой,по-немногу постигаю упущенное.

[AndryG]

В результате время вычисления для полинома 12 степени сократилось с 5399ms до 952ms (5,67 раза).
Старайтесь избегать сдвиговых регистров, они не позволяют распарралеливать вычисления.

IvanLis , если ввожу Order 31 и более стерень,цикл не выполняется и сразу останавливается,в чем причина?
И вообще как-то странно работает,даже с меньшей степенью.

[IvanLis]

IvanLis , если ввожу Order 31 и более стерень,цикл не выполняется и сразу останавливается,в чем причина?
И вообще как-то странно работает,даже с меньшей степенью.

Я же спрашивал, о степени полинома.
Там Integer32 используется, а функция на вход принимает U64, вот и переполнение буфера получается.

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

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

[IvanLis]

Смотрите, я раскидал на 4 потока. Что бы увеличить их количество, то нужно поправить количество потоков (flow) и значение P на входе цикла.
Ну и переделайте алгоритм вычисления пределов (from ... to), я не стал заморачиваться сильно с этим вопросом. Ну и индикатор % прыгает, т.к. в нескольких потоках считается.

Так к стати побыстрее получилось .

PolyPrimeCheck_IvanLis 2022-07-25.vi

(16.69 КБ) 49 скачиваний

Смотрите, что получается.
У меня компьютер старенький, да и система видимо вмешивается и одно ядро под себя оставляет, т.к. по монитору видно, что 3 ядра нагружены из 4-х.
Время вычисления полинома 16 степени чуть более 3-х минут.

[AndryG]

Смотрите, я раскидал на 4 потока. Что бы увеличить их количество, то нужно поправить количество потоков (flow) и значение P на входе цикла.
Ну и переделайте алгоритм вычисления пределов (from ... to), я не стал заморачиваться сильно с этим вопросом. Ну и индикатор % прыгает, т.к. в нескольких потоках считается.

Да,возможно я пропустил ,степень полинома нужно считать до 41.

[IvanLis]

Да,возможно я пропустил ,степень полинома нужно считать до 41.

Тогда последний вариант должен подойти, там U64 используется.
Но необходимо поискать более рациональный алгоритм.
Я не знаю конечной цели, но может проще использовать какие-то справочные таблицы, наверняка они есть. Или сохранять промежуточные данные и быстрее получится не вычислять, а запрашивать их из СУБД.