Спасибо,но долго считает,я уже попробовал несколько вариантов алгоритмов,но увы все долгоиграющие,по этому поводу вообще мало информации,так как полиномы используются в алготитмах проверки и никто ими делиться не хочет,все ,что выше 32 степени-табу Задача не тривиальна,но проста,только вот способы ,которые я нахожу,для проверки (примитивный или не примитивный полином) требуют перебора большого количества чисел,может у Вас, IvanLis ,будут какие-то идеи,был бы признателен) Вообще я занимаюсь интересными проэктами и мне талантливые люди нужны,с удовольствием поработал с Вами.Но это на перспективу)Полиномы для проверки есть 32,38 и 39 степени,но это в личку.IvanLis писал(а): ↑26 июл 2022, 09:55 Тогда последний вариант должен подойти, там U64 используется.
Но необходимо поискать более рациональный алгоритм.
Я не знаю конечной цели, но может проще использовать какие-то справочные таблицы, наверняка они есть. Или сохранять промежуточные данные и быстрее получится не вычислять, а запрашивать их из СУБД.
Распределение потоков
-
- assistant
- Сообщения: 111
- Зарегистрирован: 24 апр 2017, 22:27
- Версия LabVIEW: 2016
- Благодарил (а): 1 раз
- Поблагодарили: 1 раз
- Контактная информация:
Re: Распределение потоков
-
IvanLis
- guru
- Сообщения: 5464
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 87 раз
Re: Распределение потоков
Я с самого начала написал,. что имею лишь поверхностные знания (представления) в данной области, по этому как то даже не интересно погружаться в эту проблематику.AndryG писал(а): ↑26 июл 2022, 10:13 Спасибо,но долго считает,я уже попробовал несколько вариантов алгоритмов,но увы все долгоиграющие,по этому поводу вообще мало информации,так как полиномы используются в алготитмах проверки и никто ими делиться не хочет,все ,что выше 32 степени-табу Задача не тривиальна,но проста,только вот способы ,которые я нахожу,для проверки (примитивный или не примитивный полином) требуют перебора большого количества чисел,может у Вас, IvanLis ,будут какие-то идеи,был бы признателен) Вообще я занимаюсь интересными проэктами и мне талантливые люди нужны,с удовольствием поработал с Вами.Но это на перспективу)Полиномы для проверки есть 32,38 и 39 степени,но это в личку.
Что касается ускорения....
Необходимо разделить на 2 задачи:
1. Ускорение проверки конкретного полинома на примитивность.
Если нет других алгоритмов, то использовать то, что есть. Возможно получится адаптировать код для CUDA и вычисления вести на GPU. И при необходимости построить нечто подобное... Да и задача с майнингом схожа. 2. Сокращение количества самих проверяемых комбинаций, я бы упор сделал на эту задачу.
Одно дело, когда проверяешь одну комбинацию и тратишь 1 час на это. Другое дело, когда тебе необходимо проверить все комбинации для полинома 32 степени, а это 2^32=4294967296 часов (490293 с небольшим лет )
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
- assistant
- Сообщения: 111
- Зарегистрирован: 24 апр 2017, 22:27
- Версия LabVIEW: 2016
- Благодарил (а): 1 раз
- Поблагодарили: 1 раз
- Контактная информация:
Re: Распределение потоков
Да уж,не позавидуешь мне)IvanLis писал(а): ↑26 июл 2022, 11:50 Я с самого начала написал,. что имею лишь поверхностные знания (представления) в данной области, по этому как то даже не интересно погружаться в эту проблематику.
Что касается ускорения....
Необходимо разделить на 2 задачи:
1. Ускорение проверки конкретного полинома на примитивность.
Если нет других алгоритмов, то использовать то, что есть. Возможно получится адаптировать код для CUDA и вычисления вести на GPU. И при необходимости построить нечто подобное... Да и задача с майнингом схожа.
farm.jpg
2. Сокращение количества самих проверяемых комбинаций, я бы упор сделал на эту задачу.
Одно дело, когда проверяешь одну комбинацию и тратишь 1 час на это. Другое дело, когда тебе необходимо проверить все комбинации для полинома 32 степени, а это 2^32=4294967296 часов (490293 с небольшим лет )
-
alerm
- leader
- Сообщения: 683
- Зарегистрирован: 02 май 2012, 21:28
- Награды: 1
- Версия LabVIEW: 20
- Благодарил (а): 59 раз
- Поблагодарили: 9 раз
- Контактная информация:
Re: Распределение потоков
Что я делаю не так?
Разобрался, необходимо ещё и в самом цикле задать число потоков (на вход P не реагирует?) От нечего делать:
-
IvanLis
- guru
- Сообщения: 5464
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 87 раз
Re: Распределение потоков
В Linux работает, но я так понимаю, что больше чем доступно ядер, оно не запустит.
Я вчера погонял тоже, и пришел к выводу, что количество потоков нужно ставить больше чем количество процессоров, т.к. например первый интервал обрабатывается во много раз быстрее, чем остальные. Остальные по затратам времени примерно равны.
По этому количество ядер желательно ставить реальное, а количество интервалов побольше, но в разумных пределах.
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
- adviser
- Сообщения: 231
- Зарегистрирован: 06 ноя 2020, 15:37
- Версия LabVIEW: 19
- Благодарил (а): 18 раз
- Поблагодарили: 37 раз
- Контактная информация:
Re: Распределение потоков
Если речь идет о таких сроках можно посмотреть и в сторону FPGA.
Что-то типа такой платы приобрести. Раза в 3-4 дешевле топовых видеокарт. А зачем нужны эти полиномы?
-
- VIP
- Сообщения: 1337
- Зарегистрирован: 03 фев 2010, 00:42
- Награды: 6
- Версия LabVIEW: 6.1 - 2024
- Откуда: Германия
- Благодарил (а): 1 раз
- Поблагодарили: 44 раза
- Контактная информация:
Re: Распределение потоков
Тут ещё проблема в том, что компилятор в LabVIEW выдаёт не так чтобы самый эффективный код. Это делается обычно на чистом Си и поключается библиотекой, будет значительно быстрее (навскидку сложно сказать насколько, но в некоторых случаях и десятикратное увеличение можно выжать). Если вы посмотрите на мат библиотеку LabVIEW, то увидите, что там так и сделано, и это не случайно. Параллелить можно и средствами LabVIEW. У вас есть реализация этого алгоритма на нормальном языке программирования?
-
alerm
- leader
- Сообщения: 683
- Зарегистрирован: 02 май 2012, 21:28
- Награды: 1
- Версия LabVIEW: 20
- Благодарил (а): 59 раз
- Поблагодарили: 9 раз
- Контактная информация:
Re: Распределение потоков
Разве не потоков? И даже если и ядер, то всё равно ерунда: Вход P цикла задает максимально возможное из "Number of generated parallel loop instances"? То есть P может ограничивать введенное в цикл количество параллельных циклов, но не может задать больше этого количества параллельных циклов? Как же косноязычно я пишу
Последний раз редактировалось alerm 27 июл 2022, 19:23, всего редактировалось 1 раз.
-
dadreamer
- professor
- Сообщения: 3926
- Зарегистрирован: 17 фев 2013, 16:33
- Награды: 4
- Версия LabVIEW: 2.5 — 2022
- Благодарил (а): 11 раз
- Поблагодарили: 127 раз
- Контактная информация:
Re: Распределение потоков
Мне кажется, такое было актуально где-то года до 2017, потом уже компилятор лучше стал работать. По крайней мере я примерно с этого времени не создавал библиотек специально для , меня его производительность устраивала.
-
IvanLis
- guru
- Сообщения: 5464
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 87 раз
Re: Распределение потоков
Я сильно не вникал, но распараллеливание потоков в Linux и Windows несколько по разному реализовано. Так сказать, более по честному
Вот видео записал, четко видно как процессоры нагружаются.
Достаточно хорошо видно как и как перебрасывается с одного ядра на другое, видимо для более равномерного прогрева (охлаждения), в случае когда не все ядра нагружены.
Ну и правда комп немного поднагружен, работает виртуалка (2 ядра задействует) и запись экрана 1920*1080 и сжатие, нагружают.
Вот видео записал, четко видно как процессоры нагружаются.
Достаточно хорошо видно как и как перебрасывается с одного ядра на другое, видимо для более равномерного прогрева (охлаждения), в случае когда не все ядра нагружены.
Ну и правда комп немного поднагружен, работает виртуалка (2 ядра задействует) и запись экрана 1920*1080 и сжатие, нагружают.
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
alerm
- leader
- Сообщения: 683
- Зарегистрирован: 02 май 2012, 21:28
- Награды: 1
- Версия LabVIEW: 20
- Благодарил (а): 59 раз
- Поблагодарили: 9 раз
- Контактная информация:
Re: Распределение потоков
Я не совсем про это имел в виду. Понимаю, что возможно всех достал, но объясню
Итак в окне For Loop Iteration Parallelism ставим галочку на разрешение параллельных циклов и вписываем число (пусть будет 2), а на вход P подаем число 1 (смысла в этом конечно же нет, чисто для проверки): Затем на вход P подаем число 2 (имеем одинаковые значения и на P и в окне For Loop Iteration Parallelism): Теперь на вход P подаем число 3 (логично думать, что создаст 3 параллельных цикла, но этого не происходит): Процент загрузки немного прыгает, так что можно не обращать внимания на то, что при числе 3 загрузка меньше, чем при числе 2 на входе P (может там частота сыграла роль).
То есть если подать на вход P число большее, чем число в окне For Loop Iteration Parallelism, то это игнорирует (?).
А теперь пропишем в окне For Loop Iteration Parallelism максимально возможное (в данном случае это число 16). Если сравнить с предыдущим рисунком, то тут видно, что работает 3 ядра (нагрузка перебрасывается между потоками в ядре). То есть сейчас (как и в первом случае, когда подавали 1 на вход P) вполне понимает, что мы хотим от программы, и ограничивает количество параллельных циклов.
Увеличение числа на входе P в таком случае работает корректно: Также видно, что работают 4 ядра (с "переброской" нагрузки, но теперь уже видно, что это происходит не в пределах конкретных ядер, но это не имеет отношения к вопросу).
Вот за что уцепился глаз: получается, что значение, подаваемое из программы на вход P, должно быть меньше или равно значению Number of generated parallel loop instances в окне For Loop Iteration Parallelism, иначе просто игнорирует это?
Итак в окне For Loop Iteration Parallelism ставим галочку на разрешение параллельных циклов и вписываем число (пусть будет 2), а на вход P подаем число 1 (смысла в этом конечно же нет, чисто для проверки): Затем на вход P подаем число 2 (имеем одинаковые значения и на P и в окне For Loop Iteration Parallelism): Теперь на вход P подаем число 3 (логично думать, что создаст 3 параллельных цикла, но этого не происходит): Процент загрузки немного прыгает, так что можно не обращать внимания на то, что при числе 3 загрузка меньше, чем при числе 2 на входе P (может там частота сыграла роль).
То есть если подать на вход P число большее, чем число в окне For Loop Iteration Parallelism, то это игнорирует (?).
А теперь пропишем в окне For Loop Iteration Parallelism максимально возможное (в данном случае это число 16). Если сравнить с предыдущим рисунком, то тут видно, что работает 3 ядра (нагрузка перебрасывается между потоками в ядре). То есть сейчас (как и в первом случае, когда подавали 1 на вход P) вполне понимает, что мы хотим от программы, и ограничивает количество параллельных циклов.
Увеличение числа на входе P в таком случае работает корректно: Также видно, что работают 4 ядра (с "переброской" нагрузки, но теперь уже видно, что это происходит не в пределах конкретных ядер, но это не имеет отношения к вопросу).
Вот за что уцепился глаз: получается, что значение, подаваемое из программы на вход P, должно быть меньше или равно значению Number of generated parallel loop instances в окне For Loop Iteration Parallelism, иначе просто игнорирует это?
-
- VIP
- Сообщения: 1337
- Зарегистрирован: 03 фев 2010, 00:42
- Награды: 6
- Версия LabVIEW: 6.1 - 2024
- Откуда: Германия
- Благодарил (а): 1 раз
- Поблагодарили: 44 раза
- Контактная информация:
Re: Распределение потоков
Ну как вы понимаете, если у вас есть два значения, то одно из них таки должно иметь приоритет над другим. Это примерно как круиз контроль в автомобиле - нажимая на педаль газа можно ускорить машину, но есть и другой режим - лимита скорости, там сколько бы не давили на газ, быстрее чем установлено машина ехать не будет.Вот за что уцепился глаз: получается, что значение, подаваемое из программы на вход P, должно быть меньше или равно значению Number of generated parallel loop instances в окне For Loop Iteration Parallelism, иначе просто игнорирует это?
Справка говорит мне что "If the number of loop instances LabVIEW determines is larger than the number you specify in Number of generated parallel loop instances, LabVIEW uses only the number of loop instances you specify in Number of generated parallel loop instances". Довольно расплычато, но оно работает как работает.
Кстати, проверить сколько потоков задействуется можно и проще, примерно вот так: Ну и до кучи - там есть внутренний лимит на 64 потока, если надо больше, скажем 256, то в LabVIEW.ini надо добавить ParallelLoop.MaxNumLoopInstances=256
-
- VIP
- Сообщения: 1337
- Зарегистрирован: 03 фев 2010, 00:42
- Награды: 6
- Версия LabVIEW: 6.1 - 2024
- Откуда: Германия
- Благодарил (а): 1 раз
- Поблагодарили: 44 раза
- Контактная информация:
Re: Распределение потоков
Ну конкуренты-то тоже не дремлют. Интеловский компилятор работает неплохо, может раскручивать циклы, кроме того. я могу сделать двухпроходную компиляцию - вначале запустить с профилировкой, он сам найдёт "горячие точки" и учтёт это, когда я буду компилировать второй раз с данными профилировки. Ну а LabVIEW гонит всё вначале в LLVM, ну а потом уже генерит машинный код и немного теряет на этом.
В данном примере код довольно "рыхлый", два вложенных цикла с набором несложных логических операций - там много теряется на итерациях, так что я думаю, что в данном случае компиляция в Си выиграет. Я, кстати, сейчас Раст изучаю, он иногда показывает чудеса производительности, может там ещё лучше получится, а может и нет. Тут сложно заранее оценить выигрыш, надо просто попробовать, но мне, право слово, лень перегонять это спагетти в Си, тут где-то полдня положить придётся, а навскидку я ничего похожего не нашёл, есть только в Матлабе встроенная функция вроде бы.
-
- VIP
- Сообщения: 1337
- Зарегистрирован: 03 фев 2010, 00:42
- Награды: 6
- Версия LabVIEW: 6.1 - 2024
- Откуда: Германия
- Благодарил (а): 1 раз
- Поблагодарили: 44 раза
- Контактная информация:
Re: Распределение потоков
Да он не ненемного поднагружен, у меня в простое вот так: Отличия распараллеливания между Linux и Windows и правда любопытны. В принципе планировщики там совершенно разные, но при уверенной загрузке всех ядер общее время выполнения на одном и том же железе должно быть сравнимо.
-
- VIP
- Сообщения: 1337
- Зарегистрирован: 03 фев 2010, 00:42
- Награды: 6
- Версия LabVIEW: 6.1 - 2024
- Откуда: Германия
- Благодарил (а): 1 раз
- Поблагодарили: 44 раза
- Контактная информация:
Re: Распределение потоков
Слушайте, а это, часом не NP полная задача ли?
Вот я навскидку вижу, что увеличение степени на единицу увеличивает время счёта примерно вчетверо, на моём компе вот так:
14 - 12 s
15 - 49 s
16 - 196 s
17 - 799 s
Если эта тенденция продолжится и дальше (а с чего бы ей не продолжиться), то несложно подчитать, что время счёта для 41 степени составит приблизительно семь миллиардов лет.
Тут либо алгоритм менять, либо какие-то частные случаи использовать.