2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Куда обратиться с ПО?
Сообщение25.12.2017, 13:25 


31/08/06
17
Здравствуйте! Я написал программу, которая на шахматной доске, размером 28х28 клеток, расставляет 28 ферзей так, чтобы ни одна фигура не находилась под боем. Делает это НЕВЕРОЯТНО БЫСТРО!!! Находит 1 миллион вариантов в среднем за 46 секунд + 1 секунда на сохранение результатов в файл (55,3Мб).
Ссылка на демо версию: http://www.znanie-soft.com/soft/28_queens_demo.rar (19Кб).
Куда обратиться, чтобы полную версию запустили на мощном компьютере?

Программа написана в редакторе «Visual Studio 2017» (Basic). Характеристика моего компьютера:
ОС: Windows 7 Professional
Процессор: Pentium(R) Dual-Core CPU E5200 @ 2,50GHz 2,50GHz
ОЗУ: 2ГБ
Тип системы: 32 разрядная операционная система

Задача 27х27 уже решена. Она имеет 234,907,967,154,122,528 вариантов. Ссылка: https://en.wikipedia.org/wiki/Eight_queens_puzzle
Работа длилась как минимум с 11 января 2016 г. по 19 сентября 2016 г. Ссылка: https://github.com/preusser/q27

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение25.12.2017, 13:39 
Супермодератор
Аватара пользователя


09/05/12
17952
Кронштадт
Star Cat в сообщении #1278563 писал(а):
Куда обратиться, чтобы полную версию запустили на мощном компьютере?
Боюсь, это нереально, причем сразу по двум причинам. Во-первых, никто не решится запускать неизвестный код (вдруг Вы туда что-нибудь вредоносное заложили? :wink: ), а тратить время на дизассемблирование и т.п. по такому поводу всем лень, во-вторых, найти существенно более мощный компьютер, ресурсы которого Ваша программа сможет использовать, нереально (не думаю, что Вы на VB предусмотрели кластерные вычисления).

Впрочем, даже при подъеме производительности порядка на три (больше маловероятно - вычислительные ресурсы дороги, а задача прикладного значения не имеет) то количество вариантов, которое получается для $27\times 27$, будет считаться десятки тысяч лет, а тут их очевидно больше.

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение25.12.2017, 13:50 
Заслуженный участник
Аватара пользователя


16/07/14
3096
Москва
$10^6$ вариантов за $46$ секунд в этой задаче - это очень медленно. Вычислительные мощности сейчас принято брать в облаках (возможно в Azure даже есть какая-то поддержка visual basic).

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение25.12.2017, 13:56 


05/09/16
6300
Star Cat в сообщении #1278563 писал(а):
Куда обратиться, чтобы полную версию запустили на мощном компьютере?

Можно купить виртуальные компьютеры напрокат:
Amazon: https://aws.amazon.com/ru/ec2/?hp=tile&so-exp=below
Microsoft: https://azure.microsoft.com/ru-ru/servi ... -machines/

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение25.12.2017, 14:03 


31/08/06
17
Pphantom в сообщении #1278569 писал(а):
Star Cat в сообщении #1278563 писал(а):
Куда обратиться, чтобы полную версию запустили на мощном компьютере?
Боюсь, это нереально, причем сразу по двум причинам. Во-первых, никто не решится запускать неизвестный код (вдруг Вы туда что-нибудь вредоносное заложили? :wink: )

Впрочем, даже при подъеме производительности порядка на три (больше маловероятно - вычислительные ресурсы дороги, а задача прикладного значения не имеет) то количество вариантов, которое получается для $27\times 27$, будет считаться десятки тысяч лет, а тут их очевидно больше.

1) Я же не прячусь, меня легко найти. Какой смысл мне подставляться?
2) 27х27 уже решили за как минимум с 11 января 2016 г. по 19 сентября 2016 г. Ссылка: https://github.com/preusser/q27.

 Профиль  
                  
 
 Posted automatically
Сообщение25.12.2017, 14:05 
Супермодератор
Аватара пользователя


09/05/12
17952
Кронштадт
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Computer Science»
Причина переноса: трудно сказать, к какому подразделу это следует отнести, но это все же не математика.


-- 25.12.2017, 14:07 --

Star Cat в сообщении #1278575 писал(а):
1) Я же не прячусь, меня легко найти. Какой смысл мне подставляться?
Возможно, что никакого, но в чем смысл для владельца компьютера вообще об этом думать?
Star Cat в сообщении #1278575 писал(а):
2) 27х27 уже решили за как минимум с 11 января 2016 г. по 19 сентября 2016 г.
Стало быть, там все работало существенно быстрее.

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение25.12.2017, 19:11 
Заслуженный участник


20/08/14
5743
Россия, Москва
Star Cat в сообщении #1278563 писал(а):
Находит 1 миллион вариантов в среднем за 46 секунд
Star Cat в сообщении #1278563 писал(а):
Процессор: Pentium(R) Dual-Core CPU E5200 @ 2,50GHz 2,50GHz
Star Cat в сообщении #1278563 писал(а):
Задача 27х27 уже решена. Она имеет 234,907,967,154,122,528 вариантов.
Star Cat в сообщении #1278563 писал(а):
Работа длилась как минимум с 11 января 2016 г. по 19 сентября 2016 г.
Из комбинации процитированных сообщений видно, что задача 28х28 минимум в 500 тысяч раз медленнее, это при том же количестве вариантов -- что понятно невозможно, их больше более чем на порядок. Т.е. компьютер нужен в десятки и сотни миллионов раз более быстрый. Это попросту нереально. Даже если Вы вдруг напишите реально много-много-задачную программу (что на VB само по себе нетривиально) для запуска на большом кластере, то найти кластер из миллиона машин и занять его вычислениями на годы ... Это стоит очень немалых денег. Это минусы.

Но есть и плюсы. Переписывайте программу на VC++ под кластерные вычисления, обязательно задействуйте CUDA -- и попытайтесь заинтересовать своей задачей например BOINC (или аналогичное) сообщество, найти там ресурсы в виде тысячи компьютеров с парой тысяч CUDA потоков на каждом в принципе реально, хотя и весьма непросто (заинтересовать людей вам помочь). Зато бесплатно.

Вообще, неплохо бы хоть примерно оценить сложность задачи, требуемое количество вычислений, моя оценка выше слишком грубая. Одно дело если просите неделю на 40-ка потоковом компьютере (для задачи 27х27), другое дело если просите год на нём же. Ну а просить десяток лет и более просто бессмысленно.

-- 25.12.2017, 19:30 --

Star Cat в сообщении #1278563 писал(а):
Хм, по этой ссылке (как и для предыдущей задачи 26х26) используется FPGA для ускорения расчётов. В обычных компьютерах FPGA не встречаются вообще. Вы уверены что вообще разумно считать на обычном компьютере? Судя по диаграмме сравнительной скорости (для задачи 26х26, внизу страницы) FPGA почти на два порядка быстрее. Т.е. даже для задачи 27х27 Вам понадобится не 8 месяцев, а лет 30.

Или я что-то недопонял, или Вы очень сильно недооценили, если вообще оценивали, сложность задачи.
Даже чтобы повторить расчёт для 27х27 Вам при скорости миллион решений за 46 секунд потребуется 340 тысяч лет! А Вы замахиваетесь на более крупную задачу. :facepalm:
В общем тут по моему даже обсуждать нечего, поставленная задача при всей её "НЕВЕРОЯТНО БЫСТРОй" скорости, абсолютно нереальна.

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение25.12.2017, 20:17 
Заслуженный участник


20/08/14
5743
Россия, Москва
Что-то чем дальше вникаешь, тем бредовее выглядит затея ТС. Три с лишним миллиона лет вычислений (если оценить количество решений как вдесятеро больше решений 27х27, как это соблюдается уже с 22х22, см. A000170) на "невероятно большой" скорости ... Мрак. Тем более что эта скорость вовсе не большая, в OEIS указана скорость для 25х25, 53 года счёта CPU, значит для 28х28 потребуется порядка 53 тысячи лет, а не 3 с половиной миллиона, т.е. эта скорость в 60 раз медленнее чем реально возможно.
Нет, на BOINC лет за 20 посчитать наверное можно, если переписать под C++/CUDA, но это потребует немалых трудов по переписыванию программы и по организации и сопровождению добровольных вычислений.

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение07.01.2018, 01:59 
Аватара пользователя


07/02/12
1252
Питер
Программа ТС может быть не совсем оптимальной по той причине, что на самом деле будет параллельно майнить биткоины ))

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

В первую очередь стоит задать очевидные вопросы:
- насколько легко вашу программу можно адаптировать, что б она параллелилась в рамках одной машины на все имеющиеся ядра?
- насколько легко вашу программу можно адаптировать, что б она параллелилась на кластер компьютеров с использованием облачных технологий или без оных.
Тогда можно будет дать хоть какие-то конструктивные ответы, т.к. если вы считаете, что суперкомпьютер или кластер - это что-то, на чем можно выполнить любую программу, и она будет работать в 100,000 раз быстрее, чем на рабочей станции, согласно заявленным мощностям, то это совсм не так.

 Профиль  
                  
 
 Re: Куда обратиться с ПО?
Сообщение07.01.2018, 10:23 
Заслуженный участник


20/08/14
5743
Россия, Москва
Да задача параллелится элементарно, даже по постановке видно, обычный полный перебор всех вариантов, можно несколько верхних циклов развернуть и каждую комбинацию счётчиков раскидать по процессам. Лично мне непонятно насколько ТС "в теме", а не просто "услышал звон" о годе счёта и решил по быстрому нахаляву всех переплюнуть. Если тот год счёта был на FPGA, то возвращаться на обычные компы - это мягко говоря глупость.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group