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

[Zealint]

Мои научные исследования коснулись одной простой задачи - задачи перемножения квадратных матриц. По этой причине я провожу конкурс на лучшую реализацию любого алгоритма перемножения матриц размером до 5000x5000. Приз за самую быструю программу - 1000 р. Подробные правила - на моем сайте. Это мой первый конкурс такого рода, поэтому и задача выбрана самая простая и приз небольшой.

Главная цель конкурса не в том, чтобы получить в своё распоряжение программу и пользоваться ей, а в том, чтобы понять, чего можно добиться при тех ограничениях, которые я указал. Конечно же, если бы мне нужно было на самом деле любой ценой перемножить матрицы очень быстро, я бы сел за кластер. Здесь же суть в написании максимально быстрой последовательной программы. Сразу хочу предупредить: если вы не сильны в оптимизации программ, то вы точно не выиграете, так как я тоже принимаю участие в конкурсе и буду свою программу оптимизировать дальше. В процессе этого небольшого соревнования я хотел бы выяснить можно ли для данной задачи написать эффективный код. К сожалению, соревнования проводятся только в системе Windows, для тех, кто любит Linux я буду проводить другие конкурсы но чуть позже.

[Ajabsandal]

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

Мои научные исследования коснулись одной простой задачи - задачи перемножения квадратных матриц. По этой причине я провожу конкурс на лучшую реализацию любого алгоритма перемножения матриц размером до 5000x5000. Приз за самую быструю программу - 1000 р. Подробные правила - на моем сайте. Это мой первый конкурс такого рода, поэтому и задача выбрана самая простая и приз небольшой.

Главная цель конкурса не в том, чтобы получить в своё распоряжение программу и пользоваться ей, а в том, чтобы понять, чего можно добиться при тех ограничениях, которые я указал. Конечно же, если бы мне нужно было на самом деле любой ценой перемножить матрицы очень быстро, я бы сел за кластер. Здесь же суть в написании максимально быстрой последовательной программы. Сразу хочу предупредить: если вы не сильны в оптимизации программ, то вы точно не выиграете, так как я тоже принимаю участие в конкурсе и буду свою программу оптимизировать дальше. В процессе этого небольшого соревнования я хотел бы выяснить можно ли для данной задачи написать эффективный код. К сожалению, соревнования проводятся только в системе Windows, для тех, кто любит Linux я буду проводить другие конкурсы но чуть позже.

В серьезных научтехпрограммах (кодах) часто проводят оптимизацию критических мест. Часто повторяющиеся вычисления занимают львиную долю процессорного времени. Сюда относят и операции с матрицами и векторами. Пока не было развито программирование для многопроцессорных и спецпроцессорных систем, выход был один - писать критические части программ на Ассемблерах. После трансляции Ассемблера в машинный код ( получение ЕХЕ-файла) практически невозможно понять что программа написана на Ассемблере а не на какм либо языке программирования. Поскольку алгоритм умножения матрицы давно изъежжен вдоль и поперек, только Ассемблерная прога будет (при прочих равных условиях) непобедима в любой схватке по умножению матриц невысокого (несколько тысяч) порядка на одном процессоре.
Я (да и Вы наверняка) такие программы видел для БЭСМ-6, CDC, IBM-360/370. Полагаю есть они и для Интелевских процессоров. Думаю что для Мотороловских процов Вы уже не рискнете объявлять соревнование (под какой-нибудь МАС/ОS)

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

[Roman Voznyuk]

Думаете сможете получить что нибудь лучше uBLAS-а из boost-а?

[Zealint]

Тов, Ajabsandal, вы в чём-то правы, но далеко не во всём. Алгоритм может и изъезжен вдоль и поперек, но почему-то это обстоятельство программисты часто не принимают во внимание. Они сколько угодно могут говорить, что "есть очень быстрые реализации", но сами при этом либо не умеют ими пользоваться, либо не в состоянии написать что-то подобное (хотя бы медленнее в два-три раза). Вот я и делаю конкурс, чтобы увидеть НЕ абстрактные размышления на эту тему, а реальные возможности простых смертных программистов. У которых нет кластера под рукой, как у меня (я бы мог это задачу решить за полсекунды). Мне нужно понять, что можно выжать из типичной для пользователя архитектуры. Хотя я с Вами полностью согласен, что для решения научной задачи нужны и другие процессоры, и другой подход. Но что делать, если наша научная "лаборатория" имеет в своем распоряжении только то, что я назвал? : )

Это не казино. Я же не заставляю платить деньги. Здесь ситуация простая. Вот если вы пишите программу для заказчика, скажем, вы же не знаете заранее, на каких компьютерах он будет её запускать. И вы будете делать программу под обычные компьютеры с Windows. Так ведь? Здесь у меня похожая ситуация, только я не на заказчика работаю, а на себя. Я вовсе не заставляю кого-то убивать время, просто если есть человек, который в этой задаче разбирается и ему не жалко 10-15 минут, то пусть участвует : )

Цитата:

Думаете сможете получить что нибудь лучше uBLAS-а из boost-а?

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

[Zealint]

Roman Voznyuk в сообщении #286842 писал(а):

Думаете сможете получить что нибудь лучше uBLAS-а из boost-а?

Можете посмотреть, чего стоит BLAS на самом деле. Один из участников использовал его и попал в мой рейтинг. Причем далеко не на первое место. А uBLAS еще хуже по той причине, что он как раз создавался с расчетом не на скорость, а на точность, да еще и с шаблонами C++ - это не меньше чем 5% чисто программного замедления (по моим оценкам).

[Dongara]

Zealint писал(а):

Можете посмотреть, чего стоит BLAS на самом деле. Один из участников использовал его и попал в мой рейтинг. Причем далеко не на первое место

Да что вы говорите? Очень интересно. А Вы хорошо знакомы с алгоритмами профессора Донгарры и соответствующими реализациями его алгоритмов в пакете Intel MKL?

[Андрей АK]

Спрашиваю просто для интереса: у вас все числа не должны превышать 600? Т.е. произведения производятся по модулю 600?
Или это только начальные коэффициенты матриц маленькие, а результаты могут быть любого размера? (теоретически 600^N).

... а это что прикол?:
"8.Максимальный порядок матрицы в тесте n = 5000"
Вы хоть представляете сколько лет такие монстры должны перемножаться?
А тут читаем:
"Время работы программы на каждом тесте не должно превышать 900 секунд."
Да ... смешно.

[Xaositect]

Не $600^N$, а $600^2\cdot N$, при тамошних ограничениях влезает в 32-битный int, но почти на грани.

[Андрей АK]

Xaositect в сообщении #287069 писал(а):

Не $600^N$, а $600^2\cdot N$, при тамошних ограничениях влезает в 32-битный int, но почти на грани.

А , ну да, у меня почему-то рефлекс - если матрицы перемножаются, то и детерминант их придется вычислять ... а это M^N.

[Ajabsandal]

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

Цитата:

Тов, Ajabsandal, вы в чём-то правы, но далеко не во всём. Алгоритм может и изъезжен вдоль и поперек, но почему-то это обстоятельство программисты часто не принимают во внимание. Они сколько угодно могут говорить, что "есть очень быстрые реализации", но сами при этом либо не умеют ими пользоваться, либо не в состоянии написать что-то подобное (хотя бы медленнее в два-три раза). Вот я и делаю конкурс, чтобы увидеть НЕ абстрактные размышления на эту тему, а реальные возможности простых смертных программистов. У которых нет кластера под рукой, как у меня (я бы мог это задачу решить за полсекунды). Мне нужно понять, что можно выжать из типичной для пользователя архитектуры. Хотя я с Вами полностью согласен, что для решения научной задачи нужны и другие процессоры, и другой подход. Но что делать, если наша научная "лаборатория" имеет в своем распоряжении только то, что я назвал? : )

Я не хотел Вас обидеть или упрекнуть в нечестности. Моя мысль следующая.
На сегодня есть последние версии трансляторов с С и Фортрана (с очень хорошими опциями оптимизации выполняемого кода) от ряда известных компаний (Напр. от Intel 11-ой версии). Стоят они хороших денег, которых у многих здесь нет. Таким образом средний программист с деньгами может оказаться (по вашим критериям) лучше чем умелый, но бедный!
Поэтому условия соревнования должны иметь единый критерий. Я не выговариваю себе осоых условий и денег мне не надо, но я бы принял участие только на равноправных условиях (хотя готов и на Radeon-5ХXX серии, под OPEN CL посоревноваться).

[Dongara]

Ajabsandal
Хороший программист достанет хороший транслятор бесплатно. Но дело не в этом: мало для кого эта задача подъемная, в том числе и для автора этой темы. Хороший алгоритм должен содержать не одну тысячу строк ассемблерного кода.

[Roman Voznyuk]

Ajabsandal в сообщении #287073 писал(а):

На сегодня есть последние версии трансляторов с С и Фортрана (с очень хорошими опциями оптимизации выполняемого кода) от ряда известных компаний (Напр. от Intel 11-ой версии). Стоят они хороших денег, которых у многих здесь нет.

Чем плоха оптимизация в Sun Studio, который распространяется бесплатно?

[Circiter]

2Ajabsandal

Цитата:

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

Кажется, это не совсем так... По крайней мере поток публикаций на эту тему еще долго не иссякнет.

2Zealint

Цитата:

да еще и с шаблонами C++ - это не меньше чем 5% чисто программного замедления

Шаблоны не дают оверхеда по времени (при адекватном использовании).

[Ajabsandal]

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

Ajabsandal
Хороший программист достанет хороший транслятор бесплатно. Но дело не в этом: мало для кого эта задача подъемная, в том числе и для автора этой темы. Хороший алгоритм должен содержать не одну тысячу строк ассемблерного кода.

достанет = украдет?
Джек Dongarra Вас бы не одобрил, а он для многих программистов авторитет!
У меня есть его фортрановские программы - весьма качественно написаны!
Насчет тысяч строк ассемблера думаю он тоже, как и я, не согласился бы. Это ведь нужно только для критических фрагментов всей программы, а отладка ассемблера требует куда больше сил и времени, чем языковая (С, Фортран, Паскаль ets.).

-- Чт фев 11, 2010 08:49:04 --

Circiter в сообщении #287087 писал(а):

2Ajabsandal

Цитата:

Поскольку алгоритм умножения матрицы давно изъежжен вдоль и поперек]

Цитата:

Кажется, это не совсем так... По крайней мере поток публикаций на эту тему еще долго не иссякнет.

Если так, то математическое словосочетание: 2х2=? (дважды два) встречается в интернете существенно больше чем умножение матриц.
Но может ли это говорить о нерешенности проблемы?

[Zealint]

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

Да что вы говорите? Очень интересно. А Вы хорошо знакомы с алгоритмами профессора Донгарры и соответствующими реализациями его алгоритмов в пакете Intel MKL?

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

Цитата:

Я не хотел Вас обидеть или упрекнуть в нечестности. Моя мысль следующая.
На сегодня есть последние версии трансляторов с С и Фортрана (с очень хорошими опциями оптимизации выполняемого кода) от ряда известных компаний (Напр. от Intel 11-ой версии). Стоят они хороших денег, которых у многих здесь нет. Таким образом средний программист с деньгами может оказаться (по вашим критериям) лучше чем умелый, но бедный!
Поэтому условия соревнования должны иметь единый критерий. Я не выговариваю себе осоых условий и денег мне не надо, но я бы принял участие только на равноправных условиях (хотя готов и на Radeon-5ХXX серии, под OPEN CL посоревноваться).

Нет, все в равных условиях. Смотрите, если говорить о том, что у всех разная возможность доступа к компиляторам, то также можно сказать - у всех разные возможности доступа к научной литературе (например, у меня есть оригинал статьи Штрассена, а у вас (ну или у многих), скорее всего - нет). Далее, у всех разное воспитание в университете, поэтому у одного знаний больше, а у другого - меньше. У одного IQ 90, а у другого 180 (хотя это не показатель). Понимаете? Точно так же и с инструментами. Компилятор Intel можно отыскать при желании. Например, в университете у нас есть лицензионная версия. У кого нет, наверняка есть знакомый-программист из какой-нибудь фирмы и т. д. Каждый человек находится в своих условиях, а если хотите чтобы все было полностью одинаково - то это выглядит несколько утопично. Да и кроме того, программист, который съел собаку на оптимизации (не я, конечно) должен иметь этот компилятор под рукой всегда. Конечно, это ИМХО, но согласитесь, я привожу разумные доводы. Кстати, обидеть меня не получится : ) так что не извиняйтесь вы так зря : )

Цитата:

Хороший программист достанет хороший транслятор бесплатно. Но дело не в этом: мало для кого эта задача подъемная, в том числе и для автора этой темы. Хороший алгоритм должен содержать не одну тысячу строк ассемблерного кода.

Я уже отвечал на этот вопрос про ассемблер в своем FAQ, вопрос номер 3.

Цитата:

Чем плоха оптимизация в Sun Studio, который распространяется бесплатно?

Понятия не имею что это такое. Был бы вам признателен, если бы вы поучаствовали как раз с этой реализацией. Если знакомы с ней, это отнимет у вас минут 10 да? Зато вы получите полную оценку этой реализации на практике.

Цитата:

Шаблоны не дают оверхеда по времени (при адекватном использовании).

Ключевое слово - "адекватном". Где гарантия, что в uBLAS использование адекватное? Вот мне как раз один товарищ еще прислала программу gotoBLAS2 (понятия не имею о том, что это), но работает все равно не слишком шустро... проигрывает реализации "в лоб", написанной кем-то на Delphi.

Цитата:

... а это что прикол?:
"8.Максимальный порядок матрицы в тесте n = 5000"
Вы хоть представляете сколько лет такие монстры должны перемножаться?
А тут читаем:
"Время работы программы на каждом тесте не должно превышать 900 секунд."
Да ... смешно.

Тов. Андрей АK. Прежде чем смеяться, надо подумать. Во-первых, если в таблице рейтинга уже есть реальные записи с указанным временем работы программ, то вы что-то поняли неправильно (да, я видел, что вы ошиблись, спутав умножение и определитель, ничего страшного). Во-вторых, даже если бы я попросил считать определитель матрицы 5000 на 5000, то это примерно 30 секунд счета.
Например, Maple 13 решает эту задачу примерно за такое время, ответ типа 600 в степени N - это ерунда. У меня есть задачи, где надо считать харполином для матрицы размером в несколько тысяч, и числа в ней по 15 000 знаков каждое. Вот это уже я понимаю - задача. Кстати, это была реальная задача, которая возникла в процессе моих исследований.