Как писать быстрые программы

[wrest]

Dmitriy40 в сообщении #1718237 писал(а):

Товарищ согласен поделиться кодом, но мне его даже проверить не на чем. Прям хоть беги покупать видюху ...

Dmitriy40 в сообщении #1718237 писал(а):

Прям хоть беги покупать видюху ...

Можно арендовать облачный сервер с ней, будет где-то 10-15% от стоимости видеокарты в месяц.
Ну арендовать наверное можно и на более короткий срок.

[Yadryara]

Dmitriy40 в сообщении #1718237 писал(а):

И очевидно код можно переделать под любую нашу задачу.
Товарищ согласен поделиться кодом, но мне его даже проверить не на чем.

Может надо наоборот, попробовать переделать код под простейшую задачу и попросить его запустить? Типа кода на 1-й странице этой темы.

Ему-то есть на на чём проверить?

[Dmitriy40]

Yadryara в сообщении #1718250 писал(а):

Может надо наоборот, попробовать переделать код под простейшую задачу и попросить его запустить?

Зачем? Я же выше уже привёл сравнение скорости поиска по паттерну.
Кроме того, оптимизировать код под GPU намного сложнее и делать это без проверки на реальном железе неразумно. А без оптимизации код может работать в сотни и тысячи раз медленнее.

wrest
Не вижу смысла: потратить десятки тысяч ради лишь знаний и умений ... Проще уж купить скажем RTX5060 с 4608 потоками за 41тр и разбираться сколь угодно долго и основательно. По идее должна быть хотя бы в 40 раз быстрее ...
Вот если бы код был готовым и вся задача укладывалась бы в дни (ну неделю) счёта, то вариант аренды был бы интересен. Но пока что не выполнены оба условия.

[Yadryara]

Dmitriy40 в сообщении #1718252 писал(а):

Зачем? Я же выше уже привёл сравнение скорости поиска по паттерну.

Никакой конкретики я пока не увидел. Какого поиска? По какому паттерну?

Воздух-то обсуждать не хочется.

Dmitriy40 в сообщении #1718252 писал(а):

Кроме того, оптимизировать код под GPU намного сложнее и делать это без проверки на реальном железе неразумно.

Ну так я и говорю о проверке на реальном железе. У этого человека есть реальное железо в распоряжении? Или может он на форум придёт и можно будет прямо спросить.

[Dmitriy40]

Yadryara в сообщении #1718254 писал(а):

Какого поиска? По какому паттерну?

По такому: v=[0..21]*19#;. Все 22 числа должны быть простыми. Я за полгода проверил до 3e22, не нашёл. А RTX4090 считает 2e22 в день.
Но очевидно паттерн может быть любым, ведь и моя программа практически одинакова (внутри) для любых паттернов и здешних цепочек, ведь в основе всё равно проверка на простоту чисел цепочки.
Надо было наверное в тему о кортежах, а не сюда.

[Yadryara]

Или сюда: «Арифметические прогрессии из простых чисел»

[Dmitriy40]

Посмотрел я на предыдущие версии этого кода, пока не для GPU, только для CPU. Нашлась и скомпилированная версия под SSE/AVX, сравнил её скорость со своей программой, AVX2 вариант быстрее моей проги в 15 раз.
Оказалось там используется та моя прошлогодняя идея по ускорению, с некоторыми упрощениями, но всё же, уже лет почти 20 назад её применили, в том числе и для SSE/AVX/GPU (минимум лет 5 назад).
Код заточен под паттерны с постоянной разницей, типа v=[0..n]*d. И строго под числа <2^64. Влёгкую это не переделывается ...
И есть пара пока непонятных тонкостей.
Код для GPU ещё не изучал, так, мельком глянул, но так как он на OpenCL, то должен запускаться на любой видюхе, даже относительно новых встроенных (во всяком случае у меня встроенное видео 10+ летней давности OpenCL поддерживает, хотя от 20 потоков на 1ГГц толку чуть, да и архитектура Intel GPU сильно отличается от Nvidia/AMD). И да, код для GPU намного более замороченный.
Теперь думаю как бы упростить свой код чтобы получить не 6х ускорение как вроде бы есть, а все 15х, что-то я переусложнил и переоптимизировал, а тут похоже кэш важнее быстрых вычислений.

[Yadryara]

На таком уровне непонятно что обсуждать. Примеров кода нет.

Единственное что вроде понятно, это то, что такие ускорения хорошо применимы именно для поиска конструкций с большим количеством простых чисел. То есть, например для кортежей. Или для цепочек с 12-ю делителями.

Но уже для полупростых и тем более для pqr, pqrs и так далее, такие методы уже не дают ускорения в разы?

Ну вот, допустим мне не жалко отдать 40-50 тысяч рублей за новое железо. И, как понимаю, при нормальном, то бишь круглосуточном поиске, за электричество в год нужно будет дополнительно отдать по меньшей мере ещё столько же.

Это уже на фанатизм похоже. И в чём же профит? Найдётся то, что раньше не находилось? А оно того стоит?

[wrest]

Yadryara в сообщении #1718504 писал(а):

Это уже на фанатизм похоже. И в чём же профит? Найдётся то, что раньше не находилось? А оно того стоит?

Капвложения в хобби обычно делаются для морального профита: наслаждение/удовольствие. Например, суть этой темы, как я её понимаю, состоит в том, что какое-то вычисление ускоряется. Это ускорение и есть ожидаемый профит в материальном выражении, который "того стоит". А уж найдётся что-то в процессе ускоренных вычислений или нет - дело десятое (для этой темы).

А сколько "стоит" найти D(48,24) или D(24,20)?

[Yadryara]

wrest в сообщении #1718505 писал(а):

А сколько "стоит" найти D(48,24) или D(24,20)?

В буквальном смысле, то есть в деньгах, примерную стоимость D(24,20) посчитать можно. Но здесь это вроде бы будет оффтоп.

[wrest]

Yadryara в сообщении #1718507 писал(а):

В буквальном смысле, то есть в деньгах, примерную стоимость D(24,20) посчитать можно.

Я имел в виду в том же смысле в котором вы писали тут:

Yadryara в сообщении #1718504 писал(а):

Найдётся то, что раньше не находилось? А оно того стоит?

Как раз и хотел понять что значит "стоит" по-вашему.

[Yadryara]

wrest в сообщении #1718527 писал(а):

Как раз и хотел понять что значит "стоит" по-вашему.

Это весьма трудно формализовать.

Ну вот кстати, D(24,20), легка на помине — сегодня нашлась. Ясно же что её искать стоило — затраты сравнительно невелики, зато столько кайфа А вот почти два года искать 19-252, на мой взгляд, не стоило. Но у Дмитрия может быть другое мнение.

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

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

[Dmitriy40]

Найденный пример кода: https://github.com/ibethune/ap26 (там есть и готовые приложения).
Там же есть ссылка на исходную программу AP26 и доки Ярослава Врублевского http://www.math.uni.wroc.pl/~jwr/AP26, которая от 2008 без всяких SSE/AVX (по моему тесту в сотни раз медленнее первого кода и похоже не из-за SSE/AVX, а из-за делений).
Только оба они на C, плюс первый ещё и с интриксами SSE/AVX и плюс версия под GPU на OpenCL.

Но меня интересовало не сам готовый код, а методы в нём использованные. Они неплохо описаны в доке AP26v3.pdf Врублевского: перебор только разрешённых делителей внутри периода 59#*30/23# с КТО (её кстати не упоминает, догадался лишь по использованной формуле) и линейный перебор периодов (без перебора, по маскам допустимости).

Товарищ про RTX4090 и код с длинными числами пока не ответил, но я и не настаивал.

За ~40тр можно купить RTX3060Ti с 4864 потоками или RTX5060(Ti) с 3840(4608) потоками, это конечно не 16384 потоков RTX4090, но тоже очень неплохо. Вопрос как под неё код написать или модифицировать.

Выигрыш GPU 130 раз уменьшится до 130/15=8.7 раза если сравнивать с avx(2) версией кода выше. А на поток - CPU быстрее в 30 раз. т.е. чтобы обогнать 64 потока CPU надо GPU с 2000 потоками минимум. Хотя это сравнение несколько разных кодов не слишком адекватно.

[wrest]

Dmitriy40 в сообщении #1718536 писал(а):

Вопрос как под неё код написать или модифицировать.

Я подозреваю что если не всё, то хотя бы что-то хорошее украдено до нас и надо гуглить примерно на тему OpenCL CUDA multiprecision library и около

[Dmitriy40]

wrest в сообщении #1718539 писал(а):

OpenCL CUDA multiprecision library

Это будет медленно. Лучше по максимуму перейти от чисел к их остаткам по разным модулям, а работу с самими числами оставить CPU (как я из асма оставляю допроверку кандидатов для PARI/GP) благо интерфейс GPU-CPU достаточно быстр.