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

[abc_qmost]

В 1969 году Штрассен опубликовал, а затем Виноград косметически подкорректировал алгоритм быстрого умножения м-ц. Вот что по этому поводу пишет Дж. Деммель: "Недостатками данного метода являются большие затраты памяти и несколько худшая численная устойчивость". Возможно ли бороться с эти недостатками (см. ответ на моей странице в интернете, посвященной Core 2 Duo под IA32)?

[abc_qmost]

На первый взгляд, элементарная, но очень важная для многих приложений задача умножения матриц, получила дальнейшее развитие в пакете Inel MKL.16 февраля сего года в последнем Update Intel MKL (Intel® MKL 10.0 Update 2:
http://softwarecommunity.intel.com/isn/ ... 49675.aspx ) появилась быстрая версия dgemm под IA32 (их так расперло от гордости, что они сначала написали, что скорость увеличилась на 80%, потом эту цифру снизили до 25% - на самом деле прирост скорости составил примерно 38%). История вопроса примерно такова: несколько лет назад я на своей странице говорил о низкой скорости современных алгоритмов умножения матриц (и не только) под IA32. Мне мало кто поверил. В числе них оказался и Грановский (создатель квантовохимической программы PC GAMESS). В конце прошлого года он на своей странице сообщил о реализации новой версии программы умножения матриц, скорость которой для лучших результатов достигает 83% от теоретически возможной. Сравнительный анализ алгоритмов Intel и Грановского говорит о том, что в основе алгоритма Intel MKL лежит алгоритм Грановского. Опять показали мы эти буржуям ...(шутка).

[maxal]

abc_qmost, не плодите однообразные темы. Присоединяю к вашей старой теме про алгоритмы умножения матриц.

[abc_qmost]

maxal писал(а):

abc_qmost, не плодите однообразные темы. Присоединяю к вашей старой теме про алгоритмы умножения матриц.

Вообще говоря, алгоритмы быстрого умножения и,собственно говоря, просто умножения м-ц - две совершенно разные песни.

[abc_qmost]

На новых 45 нм. процессорах (конкретно: q9450) при грамотном подходе к реализации алгоритма перемножения матриц практически исчезает грань в скоростях перемножения матриц для IA32 и EM64T. Максимальные скорости перемножения для квадратных матриц на одном ядре: 96.2% для IA32 и 97.7% для EM64T (100% - это теоретически достижимая скорость). Интересно отметить, что на 45 нм. процессорах скорость умножения матриц на IA32 выше, чем на предыдущих 65 нм. процессорах для EM64T! Если кто-либо пользуется пакетом Intekl MKL, имеет 45 нм. процессор и использует ОС IA32, следите за появлением версии 10.1. Как я понимаю, скорость многих функций для IA32 в этом пакете должна значительно возрасти (на сколько - не знаю, во всяком случае разработчики Intel интересовались моей реализацией под IA32: http://softwarecommunity-rus.intel.com/ ... 21215.aspx ), да и функции, реализованные под EM64T, немного должны подтянуться.

[abc_qmost]

Доработан алгоритм быстрого умножения м-ц, описанный на моей странице, посвященной Core 2 Duo для IA32. Он требует относительно небольшого объема дополнительной оперативной памяти и позволяет перемножать м-цы вплоть до размера 11500*11500 при 4 GB оперативной памяти. Для EM64T на процессоре q9450 для одного ядра получены интересные результаты: например, для м-ц 480*480 скорость равна 4.21 ops/cycle (dgemm Interl MKL - 3.70 ops/cycle), для м-ц 960*960 скорость равна 4.25 ops/cycle (dgemm Interl MKL - 3.75 ops/cycle), а для м-ц 11264*11264 скорость равна 5.98 ops/cycle (dgemm Interl MKL - 3.80 ops/cycle). Особенно хочется отметить результаты для малых матриц - даже близких к ним результатов я еще не встречал и в помине, а м-цы такого размера важны в некоторых приложениях. Алгоритм получился очень сложным (ведь кроме значительного увеличения скорости был минимизирован и объем используемой дополнительной памяти, что позволяет перемножать м-цы очень большого порядка, т.е. я убил сразу двух зайцев !) и я им горжусь. К распараллеливанию пока не приступал, а получил оценку сверху, пропустив один экземпляр программы одновременно на 4-х ядрах (например, для м-ц 480*480 я получил 3.65 ops/cycle), что является очень грубой оценкой для неканонических dgemm, т.к. на время расчета велико влияние квадратичных операций. При распараллеливании моего алгоритма результаты должны быть значительно лучше. Появится свободное время - займусь распараллеливанием.