2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение15.05.2012, 18:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
alexBlack в сообщении #571381 писал(а):
В данном случае не вижу в этом (в распараллеливании) смысла. Это была попытка поиска минимальной константы для квадратов шестого порядка из чисел Смита. Была надежда что удастся проверить ряд констант (точного количества не помню). В таком случае нет разницы - запускать несколько процессов с разными константами или один процесс параллельно для одной константы.

Попытка поиска минимальной константы так и не завершилась!
Все потенциальные константы не проверены.

Сейчас я занимаюсь (вместе с svb, он ведёт поиск по своей программе) поиском всех пандиагональных квадратов с магической константой 5964. И здесь ваша оценка (40-50 часов на всю проверку этой константы), которую вы дали в своей статье, не выдерживает никакой критики.
Дело в том, что проверка даже одного числа (вы понимаете, о чём я говорю) занимает несколько суток! А в массиве первоначально 72 числа (или 76, не помню точно).
Мне не удалось проверить до конца несколько чисел, даже оставляя компьютер работающим на ночь (дважды на вторые сутки отключали электричество). Это притом, что я начала проверку после того, как ряд чисел был проверен svb, в массиве оставалось 66 чисел.
Сейчас продолжается проверка, программа работает вторые сутки (для одного конкретного числа), проверяется число 2902, это 61-ое число массива.

svb сообщил в теме "Магические квадраты", что проверка одного числа (кажется, 2965) для магической константы 5964 у него заняла 44 часа. Это я к тому, что у него компьютер производительнее моего.

Это что касается проверки константы 5964.
Одновременно с этим я проверяю и другие потенциальные константы, пытаясь всё же завершить проверку всех констант. Даже проверка меньших констант выполняется очень долго. Например, проверка константы 4938 по программе svb заняла три дня (с прерываниями на ночь).

[Кстати, о прерываниях... для проверки разных чисел можно делать прерывания и начинать потом с прерванного места. А вот при проверке одного и того же числа такие прерывания делать невозможно. Об этом я тоже здесь написала. Если бы такие прерывания были возможны, жить стало бы намного легче :-) А сделать это совсем несложно, как мне кажется.]

И это притом, что проверяются только числа вида 4(mod 9). А по-хорошему надо проверять все числа, ибо пока так и не доказано (насколько мне известно), что пандиагональные квадраты 6-го порядка составляются только из чисел Смита такого вида.

В программе svb предусмотрена проверка всех чисел Смита (без фильтра), но это в разы увеличивает время выполнения программы.

Одним словом, смысл найти пути убыстрения выполнения программы есть и очень даже большой!
Поиск более эффективного алгоритма - да, это тоже путь. Но вам очень хорошо известно, сколько усилий было потрачено на оптимизацию предложенного в вашей статье алгоритма. Этим занимались четверо: Pavlovsky, вы, svb и я, используя при этом всё лучшее, что придумано другими.
Но увы! Задача так и не решена.

Запуск одновременно двух программ (для проверки разных констант) я делаю. Но всё равно это не даёт большого эффекта.
Я, конечно, мало что понимаю в распараллеливании, но здесь писали, что распараллеливание процесса может дать выигрыш во времени в несколько раз! А не только в 2 раза (например, на моём компьютере с двухядерным процессором).

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение15.05.2012, 19:06 


26/01/10
959
Поскольку я не в теме, хотелось бы узнать, почему выбраны именно числа Смита. И что значит "проверить константу 5964"? И 4(mod 9) желательно тоже пояснить... поскольку я уже выписал систему из 37 уравнений с 15-ю базисными переменными. Но там ещё появилось число S - константа квадрата. Оно тоже считается неизвестным?

От этих ответов зависит, что я буду дальше делать с этой системой. Пока любуюсь...

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение15.05.2012, 19:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Zealint
это очень большой вопрос :-)
На него так сразу не ответишь. Я и мои коллеги svb и alexBlack посвятили проблеме хорошие статьи (ссылки на статьи в начале ветки).
Если возник интерес к задаче, посмотрите статьи.

Подробности найдёте в теме "Магические квадраты". Этой проблеме было посвящено много страниц давно. А совсем недавно я попыталась реанимировать тему. К сожалению, из троих коллег задачей сейчас занимается только один - svb. Остальным, увы, надоело :D

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение15.05.2012, 20:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
alexBlack
специально для вас :wink:
Это работает сейчас ваша программа, проверяется число 2902.

Изображение

Программа запущена вчера утром, в 4:40 (время московское). В исходном массиве 61 число.

Сейчас думаю о том, что придётся опять прерывать программу, не хочется оставлять компьютер на вторую ночь, тем более что у нас очень часто отключают электричество. Завтра утром проснусь, а программа уже не работает, т.к. и компьютер уже не работает из-за отключения электричества.

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

Вот исходный массив (61 число), который сейчас проверяется программой:

Код:
4 22 58 85 94 121 166 202 265 274 319 346 355 382 391 454 517 526 535 562 634 706 778 895 913 922 958 985 1111 1165 1219 1255 1282 1507 1633 1642 1678 1795 1822 1858 1894 1903 1921 1966 2038 2155 2173 2182 2218 2227 2326 2362 2434 2461 2515 2578 2605 2614 2722 2785 2902

Даже если предположить, что производительность вашего компьютера в 3 раза больше производительности моего компьютера, то и тогда проверка только одного числа 2902 займёт у вас не менее 14 часов.
Я прервала программу после почти 42 часов работы (в 22:40 было бы ровно 42 часа).

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 03:58 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Пока оппонент не отвечает, продолжу :D

Цитата:
Заключение.
Реализация этого алгоритма проверена на константе 5964 для чисел Смита = 4 (mod 9).Время работы на массиве из 36-ти чисел менее 10-ти секунд. Для константы 3912 полная проверка 39-ти чисел заняла 10 минут. К сожалению время проверки очень быстро растет с увеличением количества чисел в массиве. На полном массиве могу пока дать только грубую оценку времени выполнения - 40-50 часов для константы 5964.
Проверил константу 4884 (88 чисел Смита = 4 (mod 9)). Проверка заняла около 40 часов.

alexBlack
это цитата из вашей статьи.
По высказанному вами выше замечанию для вас нет никакой разницы будет выполняться программа 40 часов или 4 часа. Так?
Ну, запускаю я одновременно две программы, скажем, для проверки констант 4992 и 5046.
Обе программы нормально работают, загрузка процессора 100%. И какой же эффект? А никакого! Потому что обе программы будут работать 40 или более часов.

Ещё позволю себе немного пояснить ту поразительную разницу, которая наблюдается при проверке разных магических констант. Это хорошо понимают те, кто писал программу по данному алгоритму, но всё равно поясню (для других, кто пока не в теме).
Например, проверка магической константы 4884 (для массива из 88 чисел) заняла около 40 часов. Всего!
Что мы имеем при проверке магической константы 5964 (с массивом из 76 чисел)? А имеем мы удручающую картину: на проверку этой константы потребуется не менее 10 суток (при очень хорошей производительности компьютера).
Почему такая разница? Всё очень просто. В программе работает "перебор с возвратом". Чем лучше складываются нужные суммы (по критериям отсечения негодных комбинаций), тем глубже каждый раз забираются вложенные циклы. Чем хуже складываются нужные суммы, тем чаще и быстрее происхдят "возвраты". Вот и всё объяснение.

Ещё пример. Поверялись массивы из 36 чисел (из последовательных простых чисел). Проверка первого массива (для магической константы 1454) заняла у svb около 5 часов. Проверка следующих массивов занимала около 20 минут! В программе svb хорошо наблюдать, как складываются нужные суммы. Для константы 1454 очень часто на местах оказывались 34 числа, это значит, что вложенные циклы проходили почти до конца. Для других магических констант на месте оказывались 31-32 чисел, очень редко 33 числа.
Я проверила уже много массивов из 36 последовательных простых чисел (по программе svb), все они проверялись от 2 до 15 минут.
(вот тут нужна программа для обработки большого количества массивов из 36 чисел; это не предусмотрено ни в одной из программ, всё делаю вручную для каждого нового массива)

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 06:24 


26/01/10
959
Nataly-Mak в сообщении #571403 писал(а):
Zealint
это очень большой вопрос :-)
На него так сразу не ответишь. Я и мои коллеги svb и alexBlack посвятили проблеме хорошие статьи (ссылки на статьи в начале ветки).
Если возник интерес к задаче, посмотрите статьи.

Подробности найдёте в теме "Магические квадраты". Этой проблеме было посвящено много страниц давно. А совсем недавно я попыталась реанимировать тему. К сожалению, из троих коллег задачей сейчас занимается только один - svb. Остальным, увы, надоело :D

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

Прочитал только те куски статей, где не обсуждается сам алгоритм. Ответов на свои вопросы там не нашёл. Читать тему про магические квадраты из более чем 100 страниц я не могу. Сами понимаете.

Что я понял: квадратов с указанным свойством шестого порядка из чисел от 1 до 36 не существует. Вы пытаетесь создать такой квадрат и чисел Смита, выбирая из нескольких заранее подобранных чисел ровно 36 полным перебором с отсечениями. Так что же всё-таки значит "проверить константу"? Значит константа квадрата S задана заранее? А какие числа Смита брать? Это не очень сложные вопросы, но искать на них ответ в стостраничной теме мне некогда. Не обязательно объяснять мне, зачем именно вы так делаете. Мне нужно знать, ЧТО вы делаете.

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 06:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Zealint в сообщении #571548 писал(а):
Что я понял: квадратов с указанным свойством шестого порядка из чисел от 1 до 36 не существует. Вы пытаетесь создать такой квадрат и чисел Смита, выбирая из нескольких заранее подобранных чисел ровно 36 полным перебором с отсечениями. Так что же всё-таки значит "проверить константу"? Значит константа квадрата S задана заранее? А какие числа Смита брать? Это не очень сложные вопросы, но искать на них ответ в стостраничной теме мне некогда. Не обязательно объяснять мне, зачем именно вы так делаете. Мне нужно знать, ЧТО вы делаете.

Проверить магическую константу (из нескольких известных нам потенциальных констант) значит: ввести значение этой магической константы S в программу, то есть считать её заданной. Далее по этой константе подобрать соответствующий массив чисел Смита и проверить этот массив на предмет составления из чисел этого массива пандиагонального квадрата 6-го порядка.
Числа Смита мы пока берём только вида 4(mod 9). Экспериментально установлено, что ни в одном найденном нами ("во все времена") пандиагональном квадрате 6-го порядка из чисел Смита не встречаются числа другого вида, отличного от указанного. Однако сей факт строго не доказан.

Я всё объяснила?
Собственно, данная ветка посвящена не самому алгоритму, а вопросу распараллеливания готового кода.
Постановка задачи и описание алгоритмов её решения в теме "Магические квадраты".
Если вам некогда или просто лень читать тему, дело ваше.

P.S. Забыла важный момент: надо не просто найти пандиагональный квадрат 6-го порядка из чисел Смита, а найти квадрат с минимальной магической константой. На сегодня наименьшей константой является S = 5100.
Да, и совсем не обязательно задавать в программе значение магической константы. Одна из моих первых версий программы делалась как раз так - без задания значения магической константы, я задавала только верхнюю границу для магической константы, например, не более 5964. В этом случае в программе будет на 1 больше свободных переменных и выполняться она, понятно, будет дольше, чем при заданном значении магической константы.

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 10:57 


26/01/10
959
Понятно.

А хоть один квадрат порядка 6 с числами Смита существует? В смысле до S=5100 показано, что квадрата точно нет, а для бОльших значений пока неизвестно?

Почему следующее число 5964?

В принципе, я понял задачу, пошёл чесать репу.

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 11:19 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Всё наоборот: идём от бОльших магических констант к меньшим :-)

Доказано, что пандиагональный квадрат с магической константой S = 5100 существует.
svb и alexBlack независимо друг от друга и почти одновременно получили такие квадраты:

Код:
S = 5100 (квадрат alexBlack, выложен на ПЕН)
355,1633,1642, 958, 166, 346,
1255, 85, 535, 778,2182, 265,
1822,1858, 58, 562, 526, 274,
121, 319, 517,1966,1282, 895,
1165,1111,1894, 202, 22, 706,
382, 94, 454, 634, 922,2614

S = 5100 (квадрат svb, выложен на ПЕН)
2362 895 121 166 1165 391
85 706 2155 454 778 922
94 913 1255 526 634 1678
355 382 985 517 958 1903
1642 1858 319 1219 58 4
562 346 265 2218 1507 202

Квадратов с меньшей магической константой пока получить не удалось. Однако не доказано, что такие квадраты не существуют.

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 11:34 


26/01/10
959
Что-то я никак не могу в толк взять, зачем Вам тогда 5964? Надо наоборот, число поменьше брать.

Цитата:
Квадратов с меньшей магической константой пока получить не удалось. Однако не доказано, что такие квадраты не существуют.

Моя задача - перебрать все константы до 5100?

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 11:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
Сейчас я занимаюсь (вместе с svb, он ведёт поиск по своей программе) поиском всех пандиагональных квадратов с магической константой 5964.

Для магической константы 5964, которая служит у нас некоторым эталоном (тестовая константа), я решила найти все пандиагональные квадраты 6-го порядка.
Понимаете, что значит "все"?
А вообще надо построить пандиагональный квадрат 6-го порядка из чисел Смита с минимальной магической константой. Пока известен квадрат с константой 5100.

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

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 14:43 
Аватара пользователя


31/10/08
1244
Цитата:
Понимаете, что значит "все"?

Нет. А можно услышит четкое определение почему мы берем набор констант Шмита?

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 16:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavia в сообщении #571766 писал(а):
Цитата:
Понимаете, что значит "все"?

Нет.

Давно-давно американцы захотели построить все классические магические квадраты 5-го порядка. Для этого, как говорит история, им понадобилось всего 100 часов.
Ну, что значит "все"? Все - это значит все :D
Оказалось, что из чисел натурального ряда от 1 до 25 можно составить более 25 миллионов магических квадратов (неизоморфных) 5-го порядка.

А вот нетрадиционных магических пандиагональных квадратов 6-го порядка с магической константой 5964 (неизоморфных), составленных из чисел Смита, значительно меньше. Сколько точно, пока не могу сказать, потому что мы с svb пока их все не нашли.

Цитата:
А можно услышит четкое определение почему мы берем набор констант Шмита?

Нет, чёткое нельзя :D

Классических пандиагональных квадратов 6-го порядка не существует, что является фактом, доказанным в науке о магических квадратах (доказал Россер в 1937 г.).
Ну, раз не существует классических, будем строить нетрадиционные. Нетрадиционные магические квадраты можно строить:
а) из произвольных натуральных чисел;
б) из простых чисел;
в) из чисел какой-либо другой известной последовательности чисел; я взяла для этого последовательность чисел Смита A006753, интересная последовательность, и магические квадраты из этих чисел составляются неплохо, правда, гораздо хуже, чем из простых чисел.

Из всех трёх видов чисел я и строю нетрадиционные магические квадраты.

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

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение16.05.2012, 22:14 
Аватара пользователя


31/10/08
1244
Nataly-Mak
Цитата:
Давно-давно американцы захотели построить все классические магические квадраты 5-го порядка. Для этого, как говорит история, им понадобилось всего 100 часов.
Ну, что значит "все"? Все - это значит все
Оказалось, что из чисел натурального ряда от 1 до 25 можно составить более 25 миллионов магических квадратов (неизоморфных) 5-го порядка.

Это ещё реально. 25!*135
А для квадрата 6 порядка 36! для одной константы. Так что не меньше 10 000 часов надо на перебор.

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение17.05.2012, 03:18 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavia в сообщении #572053 писал(а):
А для квадрата 6 порядка 36! для одной константы. Так что не меньше 10 000 часов надо на перебор.

Как и американцы, мы не делаем тупой полный перебор.
Есть алгоритмы построения различных типов магических квадратов, которые позволяют строить их довольно быстро.

Например, строим нетрадиционные пандиагональные квадраты 6-го порядка из чисел Смита. Если мы берём массив ровно из 36 чисел, то программа в большинстве случаев отрабатывает очень быстро (за редкими исключениями) и находится (почти всегда) всего один (!) квадрат (с точностью до изоморфизма). В некоторых случаях программа отрабатывает за 10-20 сек.
Но массив чисел, из которых можно получить заданную магическую константу, в большинстве случаев содержит не 36 чисел, а гораздо больше. Вот тут и начинаются проблемы со временем.

Я пробовала действовать так: пусть полный массив содержит 76 чисел. Попробовать сформировать все возможные массивы из 36 чисел и проверять каждый такой массив отдельно. Нет, плохо получается, потому что нереально сформировать все такие массивы по 36 чисел, их получается очень и очень много.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3  След.

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



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

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


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

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