Программа вычисления

Написал консольное приложение (С++), с рекурсивным перебором.
Очень долго вычисляет (при средних запросах, несколько часов)/проц. i7 2.80GHz; ОЗУ 8 Гб./.
Хотел узнать, есть ли какие-нибудь сервера, куда можно загрузить программу, "прогнать" на лучшем железе и получить результат, за меньшее время вычисления?

ps: Сейчас, читаю про Azure, но пока не знаю, на правильном ли я пути )

0

если не секрет, что же это Вы такое считаете, откуда такие вычислительные нагрузки? может быть не вмещаетесь в ОЗУ?
возможно алгоритм крутится на одном ядре? OpenMP задействовано?

в сторону Cuda не смотрели?

1

Сообщение от Unikum с рекурсивным перебором.

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

0

Сообщение от vantfiles если не секрет, что же это Вы такое считаете, откуда такие вычислительные нагрузки?

Не секрет.)
Моделирую набор "круговых" шаговых переключателей, причем у каждого переключателя свой предел кол-во шагов, т.е. есть переключатели, где всего 10 шагов, а есть переключатели, где 1 000 000 шагов. Требуется пройтись по всем вариациям (т.е. перебрать все варианты) при этом определять некий рейтинг варианта (т.е. на каждом варианте требуется некое вычисление).
Еще нюанс, количество переключателей задается только при запуске программы, как и предел кол-ва шагов для каждого переключателя.

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

а насчет cuda где-то слышал, и кажется там на ядра видеокарты "грузить" не простые вычисления противопоказаны. (Но, возможно, я ошибаюсь)

Добавлено через 13 минут

Сообщение от Serg_o_Grey тут вы скорее всего упираетесь в оперативную память и начинаете использовать файл подкачки, но в любом случае сначала лучше узнать в чем именно дело и последить за использованием ресурсов на вашей машине. возможно есть более удачные подходы к решению задачи. Так же есть вероятность что и 32Гб оперативной памяти вам будет мало при использовании данного подхода

Так как кол-во переключателей задается при старте программы, был сделан выбор "рекурсивный перебор". Глубина рекурсии, равна кол-ву переключателей, т.е. в реальных запросах, не более 20-40. Пока тестирую с 10-ью переключателями, и памяти используется, при выполнение, не больше 50%, но тем не менее вычисление идет очень долго.

0

Unikum, судя по тому что вы говорите, то вы упираетесь в трудоёмкость алгоритма (аля 1000 вариантов * 1000 вариантов * ....). Прочитайте про О большое.
Возможно вам не обязательно перебирать все варианты.
Тогда могут помочь: генетические алгоритмы, метод отжига и т.п.

1

покажите исходник, возможно получится избавиться от рекурсии, да и пооптимизировать на скорость с разных сторон...
Сборку в студии делаете или gcc ?

1

Сообщение от vantfiles возможно получится избавиться от рекурсии

Очевидно возможно.

Похожая задача год назад на форуме возникала - и Unikum'у надо просто в алгоритме из этого поста 30 вложенных циклов вместо константы MAX_INDEX_VALUE использовать массив значений верхних границ (в котором значения элементов задаются для каждого переключателя), ну и число переключателей тоже должно задаваться вручную (вместо использования константы INDEX_COUNT).
Т.е. комбинация (вектор) значений индексов будет получаться без всякой рекурсии, вызовом функции Next(), в которой независимо от числа переключателей будет всего 1 цикл.

1

VTsaregorodtsev, а толку ему избавляться от рекурсии если INDEX_COUNT у него десятки, а MAX_INDEX_VALUE может быть

1 000 000 шагов.

Здесь надо отталкиваться от:

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

Для чего он это ищет. Если найти вариант с максимальным рейтингом. То это задача поиска экстремума.
Иначе в худшем случае ему надо перебрать комбинаций!!!

1

Сообщение от AlexVRud Тогда могут помочь: генетические алгоритмы, метод отжига и т.п.

Большое спасибо, за подсказку, кажется то что нужно!
Вчера изучал, метод "отжига". Попробую его реализовать.

Правда, пока не до конца понял, есть варианты, с одним, но медленным "остыванием" и с многократным циклом "остывания" побыстрее, т.е. после "остывания" опять задают высокую температуру и процесс "остывания" повторяется заново.

(А в случае с быстрым остыванием, не будет ли ситуации, когда найденный минимум, будет "хуже", чем в предыдущем цикле остывания (наверное, нужно запоминать минимум "глобального" процесса). Да, еще и сами кол-ва повторений циклов "остывания" нужно регулировать (например, три цикла "глобальный" минимум не падает, то стоп программа)

Добавлено через 2 минуты

Сообщение от vantfiles покажите исходник, возможно получится избавиться от рекурсии

Спасибо, за желания помочь, но кажется нашел направление, возможного решения.

Добавлено через 1 минуту

Сообщение от VTsaregorodtsev Похожая задача год назад на форуме возникала - и Unikum'у надо просто в алгоритме из этого поста 30 вложенных циклов вместо константы MAX_INDEX_VALUE использовать массив значений верхних границ (в котором значения элементов задаются для каждого переключателя), ну и число переключателей тоже должно задаваться вручную (вместо использования константы INDEX_COUNT). Т.е. комбинация (вектор) значений индексов будет получаться без всякой рекурсии, вызовом функции Next(), в которой независимо от числа переключателей будет всего 1 цикл.

Интересный метод. Спасибо, возьму на вооружение, на будущее!

Добавлено через 14 минут

Сообщение от AlexVRud Для чего он это ищет. Если найти вариант с максимальным рейтингом. То это задача поиска экстремума.

Да, задача поиска экстремума. Только не одного, а двух, т.е. в задаче нужно, поймать максимально сильный сигнал и чтобы в этом сигнале было меньше шумов. Т.е. найти лучший вариант с максимальным уровнем "силы" и при этом с минимальным уровнем "шума".
Пока склонялся, отбирать лучший вариант, сравнивая, по одному общему параметру "качество=сила/шум".
(Но кажется, это не совсем правильно, в голове держу мысль, что нужно этот общий параметр вычислять более сложно, через нахождения экстремум дифференциальных уравнений. Но сам пока, даже не представляю как это сделать) )

Возможно, в методе "отжига", общий параметр и не нужно будет вычислять.

0