Уважаемые программисты, предлагаю принять участие в моём алгоритмическом конкурсе. Требуется написать программу, которая перемножает две квадратные матрицы за минимальное время. Максимальный размер матриц - 5000x5000. Конкурс пока бесплатный, поэтому и приз не сильно большой - 1000 р. Описание правил приводится на моём сайте. http://zealint.ru/fast-matrix-multiplication-comp.html

В будущем я предполагаю проводить и другие конкурсы, сложнее и интереснее!

Удачи!

Что-то условие какое-то нежизнеспособное.   Windows XP у меня под руками нет, да и машины с соответствующим процессором - тоже. Однако под Linux (конкретно openSuSE 11.2 x86-64) на одном ядре от Athlon X2 5200+ (в принципе, не мощнее, чем Ваш Intel Core 2 Duo 8400) вот эта вот тупейшая программа на Фортране

отработала за 145-150 секунд (плюс-минус пара секунд для разных запусков и матриц), в отличие от Ваших 800.   Если что - компилятор Intel'овский, вызывался ifort -fast cross.f90 -o cross, подсчет времени выполнялся с помощью банального time ./cross. Замена компилятора на Sun'овский привела к тому, что время счета увеличилось секунд на 20.

Это, собственно, к тому, что задача неудачная - такие вещи "убиваются" не алгоритмическими изысками, а просто правильным выбором инструмента. При этом попытки написать что-то более сложное, скорее всего, приведут в лучшем случае к повторению того же результата.

Это сообщение отредактировал(а) Фантом - 9.2.2010, 01:08

Тов. Фантом, спасибо, что уделили внимание моему конкурсу. Дело в том, что создавая этот конкурс я, разумеется, подумал тех вещах, о которых вы говорите. Я бы не стал делать конкурс, если бы считал себя чайником : ). Я поставил в условиях Winsows XP, значит на то была определённая причина - это эксперимент, результаты которого мне интересны. Моя (та же самая) программа под Linux Enterprise с компилятором Intel C++ работает всего 108 секунд против ваших 145 (на процессоре, с частотой 2,67GHz). Да и то, программу я еще даже не начинал оптимизировать. Понимаете? В этом конкурсе я хочу, чтобы был именно Windows и хочу посмотреть, кто способен написать быструю программу под эту систему. Кстати, вы не написали, сколько ваша программа кушает памяти.

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

Если процессор Intel, то это нормально. На моем AMD из icc можно будет выжать дополнительный десяток секунд, не больше. 


А смысл? Ни для каких практических целей программы такого рода под Windows никто писать не будет. Т.е. сама по себе задача, конечно, имеет право на существование, но в такой постановке ее результаты показывают непонятно что.

И, кстати, это в любом случае будет в основном соревнование компиляторов и библиотечных кодов.


Так ведь очевидно. Три матрицы 5000*5000 c 4-байтовыми элементами, все остальное - мелочь, не стоящая внимания. Получается что-то в районе 300 мегабайт (точнее, матрицам надо 286, по "честным" измерениям получается 288).


Нет. В таких условиях все, что может дать реальный выигрыш - это блочные методы и аккуратное использование векторных возможностей процессоров. В тот же matmul оно уже заложено, так что удастся разве что немного подкорректировать параметры блоков, поиграв с укладкой их в кэш. Однако это имеет смысл для матриц фиксированного размера, т.е. именно 5000*5000 таким способом немного оптимизировать, возможно, и получится, а для произвольного размера больше времени уйдет на написание программы. 


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

Можно выжать больше, если вмешаться туда руками. Более того, я претендую на то, что моя программа под Windows скоро станет работать быстрее, чем ваша - под Linux. Этим вообще хочу показать, что ОС не играет сильной роли, если, конечно, не проводить какую-то совершенно жуткую оптимизацию.


Результат будет показывать то, что мы можем выжать из Windows и Intel. Если проводить конкурсы для всех архитектур и ОС, то для этого у меня не хватит сил. На универсальном компьютере (архитектуры Intel, AMD или Mac) все равно результаты будут не слишком объективными, и вообще, если мне нужна будет совсем оптимальная программа, я задействую видеокарту, в которой будут вычисляться небольшие блоки, а большие будут считаться на обоих ядрах. Или вообще буду считать на кластере. То есть мне важна не сама скорость, с которой мы можем решать эту задачу, а скорость, которую можно выжать именно при моих ограничениях. Конечно, я могу такое же конкурс устроить и на Linux. Только мне сильно надоело наблюдать за тем, как программа скомпилированная на одном Линуксе соврешенно не хочет работать на другом. А в Windows XP хотя бы есть универсальность, которая нужна.


Не очевидно, я же не знаю что за алгоритм скрыт в матричном умножении. Если тупой тройной цикл, то понятно. У меня так же. Но у меня еще есть реализация одного из билинейных алгоритмов, которая требует еще около 10 матриц и в память не влезает. А мне нужно, чтобы влезала, поэтому я и провожу конкурс. 


Так вот я вам обещаю, что ваш matmul будет повержен к концу конкурса. При одном условии - что люди начнут участвовать и начнётся конкуренция. Если конкуренции не будет, то, конечно, грустно. Значит народ не умеет программировать руками совсем, считая, что все уже есть в стандартных библиотеках. Это плохо. Еще раз: конкурс нужен для того, чтобы посмотреть, кто умеет программировать алгоритмы эффективно. Эффективность всегда достигается, когда учтена специфика задачи. В этом случае пасуют все встроенные алгоритмы, расчитанные на универсальный подход. 

Ну хорошо. Когда кто-нибудь повергнет, напишите. Мне тоже интересно.   

Ну, господа, что-то слабенько.  

Intel Core 2 Duo P8400 2.2 Ггц:

Компилятор MSVC++ 2008:



Компилятор Intel C++ 11 даёт такие же результаты с отличием в 1-2 секунды. 

Алгоритм Штрассена требует много памяти. Поэтому для матриц 5120х5120 используемая память достигает 900Мб. Но в рамках условий конкурса.  Однако можно перемножать матрицы только кратные 2^n. Универсальный алгоритм работает в среднем в три раза хуже, однако его можно оптимизировать, чтобы он раза в два быстрее был.

Если бы можно было использовать GPU, то цифры были бы гораздо меньше. Перемножение 5000х5000 в рамках 8 секунд на обычной NVIDIA 9600GT реальная задача. 

Оптимизированное умножение (на у Фантома на фортране) у меня выполняется 187 сек.


Это сообщение отредактировал(а) W4FhLF - 9.2.2010, 13:42

М-да, похоже, я ошибся, посчитав, что Штрассен в память не влезет. А код универсального варианта можно посмотреть? Хочется посмотреть на него в тех же условиях.

Я погорячился)



Второй вариант не использует дополнительной памяти, но идёт более грамотная работа с память. Данные делятся на блоки относительно размера кеша и кеш-лайна. 

Не понял немного. В каких тех же? 

На той же машине, чтобы сравнить с тривиальным вариантом.

Тривиальный алгоритм с тремя циклами у меня работал больше 15 минут на матрицах 5120, я даже не дождался конца. 
Слегка подправленный (скорее всего такой же как в фортране) с транспонированной второй матрицей работал 187 секунд. 

В аттчае вариант с двумя алгоритмами, которые я приводил в первом своём посте этой темы. 

Матрицы заполняются так:



запускать так:



где N - размер матрицы. 

Чтобы выложить целиком, надо его доработать. 



Присоединённый файл ( Кол-во скачиваний: 18 )
 matmul_vc.rar 7,82 Kb

Ну да, только exe-шник под Linux и запускать.  Я исходники хочу (точнее, второй исходник - то, что метод Штрассена должен давать такие результаты, и так понятно).

Тов. W4FhLF, что вы меряетесь тут? Присылайте мне программу и я протестирую все на своей машине (по условию, я должен получить прогу на почту и чтобы она с файлами работала). Все сравнения будут объективными, и с кубической реализаций сравним, и со Штрассеном и с ним же в моем скромном исполнении, если кубический алгоритм я не смогу довести до победы. Кстати, у E8400 вы неправильно написали скорость, там 3000MHz. Давайте, участвуйте, посоревнуемся! Ваши "21s" меня приятно удивили, мне видимо придется долго думать, чтобы это переплюнуть. Еще дело в компиляторе...

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

Это сообщение отредактировал(а) Zealint - 9.2.2010, 14:24

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