Перемножение матриц - конкурс для программистов

[Zealint]

Конкурс завершён, всем спасибо за участие. Здесь подводятся итоги.

[Ajabsandal]

Zealint в сообщении #291296 писал(а):

Конкурс завершён, всем спасибо за участие. Здесь подводятся итоги.

Весьма интересные результаты, хотя я с самого начала сказал, что ассемблер будет доминировать в этих приложениях при прочих равных.
Теперь интересно посмотреть дальше на проблему.
1. Какие же насущные проблемы ускорения имеются и в каких приложениях?
Конечно это не задача о перестановкем ферзей. Матричные вычисления - неотъемлемая часть численных методов решения урматфизов. Основная и самая важная сфера применения суперкомпьютеров (вспомните всякие эмбарго) - моделирование "работы" ОМП.
Высокая размерность задач приводит к огромным размерностям матриц (хотя и довольно сильно разреженных). Все операции проводятся с плавающей точкой и как минимум с двойной точностью (вообще целочисленная арфметика в практических расчетах занимает мизерное место).
Интересно было бы понять как будут работать алгоритмы-победители в случае арифметики с плавающей точкой? Ведь применение много- и спецпроцессорных систем не отвергает теоретических основ. Кроме того, отпадут всякие ограничения конкурса на размерность задачи, что позволит точнее оценить преимущества разных методов ускорения.
А сама идея проведения конкурса несомненно полезна и должна развиваться на этом (где же еще?!) форуме!
Может быть нужно создать совместный денежный фонд с весомым призом для победителей ?

[Zealint]

По поводу плавающей точки: я сомневаюсь, что имеет смысл тягаться с теми, кто уже много времени посвятил написанию такого рода программ: например, тот же MKL с такими данными работает весьма быстро. Даже ускорение на несколько (пусть, 10) процентов кажется весьма сомнительным. Здесь я хотел показать работу именно с целыми числами (это часто требуется в комбинаторных задачах). Мне гораздо больше интересно что будет, если числа окажутся длинными, тысяч по 10 знаков каждое (хотя, это еще мало).

В отличие от физических расчётов, в комбинаторике доминируют именно целые числа и часто они даже больше, чем влезает в 128 бит со знаком. В одной из задач у меня получалось, что нужно хранить 500Гб таких чисел.

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

[venco]

Zealint в сообщении #291429 писал(а):

участники делают небольшой взнос

Так точно не получится привлечь. Я, например, на таких условиях участвовать не буду.

Zealint, вам известен сайт http://www.topcoder.com/tc?
Рекомендую обратить внимание на их Marathon Matches.

[Zealint]

venco в сообщении #291432 писал(а):

Так точно не получится привлечь. Я, например, на таких условиях участвовать не буду.

В том-то и дело! Я как раз этого и ожидаю. Вот если бы такого рода конкурсы были престижными и популярными, то я мог бы получать спонсорскую помощь. У меня есть задачи, за которые не жало и сто тысяч дать, но нету столько... Да и не решит никто, наверное, сильно это узкая область. В общем, это все, конечно, нужно обдумывать.

venco в сообщении #291432 писал(а):

Zealint, вам известен сайт http://www.topcoder.com/tc?
Рекомендую обратить внимание на их Marathon Matches.

Конечно известен : ) Когда-то я там выступал, даже был в верхнем рейтинге среди жёлтых. Потом удалил аккаунт, сделал новый и выступил всего пару раз... написал две статьи и забил вообще на эти игры. Их марафонские матчи меня не устраивают по разным причинам. Там еще ни разу не было тех задач, которые мне хоть сколько-нибудь интересны. Специфика ограничений несколько ограничивает. Например, пользоваться stl я просто не могу (больно медленно, даже если и удобно). Там недавно проходили соревнования по CUDA, но все равно задачи были неинтересными (для меня).

[Dongara]

Ajabsandal писал(а):

Интересно было бы понять как будут работать алгоритмы-победители в случае арифметики с плавающей точкой?

При перемножении 2-х м-ц 5000*5000 с вещественными числами теоретическая скорость перемножения, выраженная в секундах, оценивается следующим образом: 2*5000^3/(4*3000000000)=20.8 с., где 2*5000^3 - число сложений и умножений, 4 - число операций сложения или умножения на 1 период, 3000000000 - частота процессора Duo 8400. Intel MKL приближается на 45 нм. процессоре довольно близко к этому результату. А для целых чисел там лучщий результат 7.52 с., т.е получаем 11 операций на 1 период!
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
Конкурс окончен и как я и предполагал, лохотрон продолжает раскручиваться: Zealint уже предлагает вносить деньги, а venco с гневом отвергает это предложение. Заметьте, что Zealint написал свой пост в 7 ч. 03 мин., а venco ответил в 7 ч. 24 мин.: потрясающая оперативность для такого раннего времени, да еще и в праздник. Сдается мне, что эти 2 товарисча - одно лицо. Во дают: не стесняются уже организовывать фирму "Рога и Копыта" на научном форуме.

[Zealint]

Dongara в сообщении #291442 писал(а):

Ajabsandal писал(а):

Интересно было бы понять как будут работать алгоритмы-победители в случае арифметики с плавающей точкой?

При перемножении 2-х м-ц 5000*5000 с вещественными числами теоретическая скорость перемножения, выраженная в секундах, оценивается следующим образом: 2*5000^3/(4*3000000000)=20.8 с., где 2*5000^3 - число сложений и умножений, 4 - число операций сложения или умножения на 1 период, 3000000000 - частота процессора Duo 8400. Intel MKL приближается на 45 нм. процессоре довольно близко к этому результату. А для целых чисел там лучщий результат 7.52 с., т.е получаем 11 операций на 1 период!

Вы не учли время ввода / вывода данных (это не ноль) и то обстоятельство, что у лидера реализован алгоритм Штрассена.

Dongara в сообщении #291442 писал(а):

Конкурс окончен и как я и предполагал, лохотрон продолжает раскручиваться: Zealint уже предлагает вносить деньги, а venco с гневом отвергает это предложение. Заметьте, что Zealint написал свой пост в 7 ч. 03 мин., а venco ответил в 7 ч. 24 мин.: потрясающая оперативность для такого раннего времени, да еще и в праздник. Сдается мне, что эти 2 товарисча - одно лицо. Во дают: не стесняются уже организовывать фирму "Рога и Копыта" на научном форуме.

Где лохотрон-то? Я ничего не предлагал, а лишь предположил, что там могло было быть. Я же совершенно ясно написал, что лучше бы иметь спонсорскую помощь, но если ее нет, что что поделать? У Вас опять какие-то фобии? Далее, ваши заблуждения продолжаются и не перестают меня удивлять. Мой рабочий день начинается в 5 часов утра и не зависит от каких-либо праздников и выходных - это первое. Второе - вы забыли, что на планете 24 часовых пояса. У тов. venco может быть другое время. Не стыдно для человека, который владеет арифметикой? А если копать еще глубже, что поясните, пожалуйста, где вы увидели гнев venco? Он спокойно выразил свое (правильное в данных условиях) мнение. Надеюсь, это последний раз, когда вы обвиняете меня в том, в чем не разбираетесь и о чем совершенно не имеете представления.

[Dongara]

Zealint писал(а):

Вы не учли время ввода / вывода данных (это не ноль) и то обстоятельство, что у лидера реализован алгоритм Штрассена.

Зачем учитывать время ввода / вывода: я дал фору. При этом учете число операций на 1/4 периода будет не 11/4, а больше. А за 1/4 периода более одной операции не может быть выполнено. Теперь что касается Штрассена: n=5000 - не очень большая м-ца для эффективного использования этого алгоритма, глубокая рекурсия приведет к резкому росту квадратичных операций и мы будем иметь даже не выигрыш, а проигрыш. Впрочем вы можете меня опрвергнуть, выложив экзешник чудо-алгоритма с инструкциями. А так все это сильно смахивает на лохотрон, тем более эти подозрения усиливает присутствие денежных вопросов. Остальной ваш бред комментировать не имеет смысла.

[Zealint]

Dongara в сообщении #291459 писал(а):

Зачем учитывать время ввода / вывода: я дал фору. При этом учете число операций на 1/4 периода будет не 11/4, а больше. А за 1/4 периода более одной операции не может быть выполнено. Теперь что касается Штрассена: n=5000 - не очень большая м-ца для эффективного использования этого алгоритма, глубокая рекурсия приведет к резкому росту квадратичных операций и мы будем иметь даже не выигрыш, а проигрыш. Впрочем вы можете меня опрвергнуть, выложив экзешник чудо-алгоритма с инструкциями. А так все это сильно смахивает на лохотрон, тем более эти подозрения усиливает присутствие денежных вопросов.

Ничего подобного, тов. специалист. Архив конкурса можете скачать сами, там есть все программы участников. Мою можете не смотреть, она не такая быстрая, как у venco. Экзешник лидера можно дизассемблировать и посмотреть. В любом случае, даже у меня алгоритм Штрассена (совершенно безобразно написанный) получился быстрее, чем кубическая версия. Моя кубическая версия давала 14,5 с (из них ввод / вывод - это 3-3,5 с.). Причем Штрассен у меня выигрывает уже на гораздо меньших значениях (при n=160), но спускаться так глубоко нельзя - переполнение слов. Сказать, что кубическая версия у меня плохая тоже нельзя. Поверю только если увижу что-то совсем быстрое.

По поводу денежных вопросов вы опят сильно тормозите: их просто нет. Где вы нашли денежный вопрос? Были только мои сугубо личные предположения и ВСЕ. : ) Извольте отвечать за слова, сударь.

Dongara в сообщении #291459 писал(а):

Остальной ваш бред комментировать не имеет смысла.

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

[Dongara]

Zealint писал(а):

не умеете мыслить на уровне более-менее разумного человека.

Вам и до неандертальца далеко, но не в этом суть: я не нашел архива, о котором вы писали. После того, как посмотрю, отвечу на остальное. Только на что смотреть? А пока это только одна демагогия. И сивушный бред про штрассена пишете и не только.

[Zealint]

Dongara в сообщении #291483 писал(а):

Zealint писал(а):

не умеете мыслить на уровне более-менее разумного человека.

Вам и до неандертальца далеко, но не в этом суть: я не нашел архива, о котором вы писали. После того, как посмотрю, отвечу на остальное. Только на что смотреть? А пока это только одна демагогия. И сивушный бред про штрассена пишете и не только.

Так, хватит игр. Конкретно: где написан бред? Четко и по пунктам. По поводу архива с решениями: на моей странице с итогами конкурса чуть ниже таблицы есть раздел "Архив конкурса". Там ссылка. Там же пояснения к тому, как запускать систему. Посмотрите экзешники участников и сделайте правильные выводы. Итак, жду конкретного объяснения от Вас: где я написал бред? Хоть одно место. Чётко и с обоснованием: как в школе учили : ) [ уже понятно, что Вы не сможете ответить ]

[Dongara]

Zealint писал(а):

...

Так вы ничего и не поняли: а я писал про 3 с., ну, и еще время ввода матриц.
И если вам трудно 2.98 с умножить на 3.47 и разделить на 3.0, то это ваши проблемы. И только командовать не надо: почему ваш бред я должен комментировать? Потерпите: всему свое время. И еще я ранее рассказал, как грамотно реализовать алгоритм.

[Zealint]

Dongara в сообщении #291516 писал(а):

Так вы ничего и не поняли: а я писал про 3 с., ну, и еще время ввода матриц.
И если вам трудно 2.98 с умножить на 3.47 и разделить на 3.0, то это ваши проблемы. И только командовать не надо: почему ваш бред я должен комментировать? Потерпите: всему свое время.

Хорошо, может я чего-то не понимаю, но ситуация такая. Вы сказали, что можете решить задачу за 3 секунды, но на другом процессоре. Допустим. Что дальше? Я не видел реально работающей программы и не замерял время её работы. Я не видел, чтобы на моем компьютере что-то работало бы 3,5 секунды (ну плюс ввод/вывод). Этого не было. А слова ни к чему не обязывают. Так? Вы согласны? А если вам конкурс не нравится, но не надо было начинать демагогию. Все, что я писал выше относилось именно к тем программам участников, которые я видел. В том числе, и к моей. Правильно ли я понял, что Ваша программа не ускоряется методом Штрассена?

Я не командую Вами, а просто призываю к элементарному соблюдению правил приличия. Вы надоели уже сыпать в меня обвинениями, не объяснив НИ ОДНО ИЗ НИХ. Если не хотите объяснять, то и не надо было начинать. Перечитайте дискуссию с самого начала и увидите, что Вы неправильно выбрали тональность общения. Последний вопрос: что Вы хотите показать в этой полемике?

[venco]

Если кому интересно, вот разбивка времени на разные операции в моём решении на моём Core2Duo 2.4GHz.
Матрицы 5000х5000, увеличены до 5120x5120 для делимости на 16x16.

Полное время: 9.22
{
  Инициализация CygWin  : 0.26 
  Ввод (16 бит)         : 0.46
  Вывод (32 бит)        : 0.83
  4-х уровневый Штрассен: 7.67
  {
    Сложение операндов (16 бит) : 1.03
    Умножение (16->32 бит)      : 6.01
    Сложение результата (32 бит): 0.59
  }
}

[Zealint]

Dongara в сообщении #291516 писал(а):

И еще я ранее рассказал, как грамотно реализовать алгоритм.

Вы имеете в виду вот это:

Цитата:

Intel MKL - Это всего лишь профессиональная рализация (правда, расширенная) свободно распространяемого пакета LAPACK (туда входит и BLAS). Но она не ориентиравана на работу с целыми числами. А процессор здесь Интеловский. Кто знаком с эффективными методами реализации перемножения матриц (т.е. 95% от теоретически возможной скорости), состоящей из вещественных чисел, без труда, используя SSE4, реализует качественный алгоритм и для целых чисел. А если программер еще разбирается и в быстрых алгоритмах перемножения матриц, основным недостатком которых является потеря точности, то ему и карты в руки: здесь целые числа и точность никуда не убежит. Вот постарается - и на бомжовую похлебку заработает.

??? Или я что-то недопонял?

Ответе на такой вопрос: на каких размерностях алгоритм Штрассена, по-Вашему, быстрее кубической реализации? Имеется в виду, что мы в условиях конкурса, где входные данные 16 бит (целые), а выходные - 32 (целые).