Блочное умножение матриц

[vitaly333]

Задача: нужно выполнить С = С + A*B, где A,B,C есть MxK, KxN и MxN большие матрицы (не умещаются в кэш L2) с максимальной производительностью при однопоточной реализации. Для этого решил использовать блочный вариант умножения, идея которого состоит в том чтобы загружать блоки матриц в L2 кэш и там их перемножать...т.е. как можно дольше использовать одни и те же загруженные в кэш данные, чтобы минимизировать пересылки между кэшем и ОЗУ. Но у меня удается дочтичь только 50% от пика. Вопрос состоит в том как выбирать оптимальную схему блокирования и размеры блоков, так чтобы достичь пиковой производительности?

[Dongara]

vitaly333 в сообщении #264615 писал(а):

Задача: нужно выполнить С = С + A*B, где A,B,C есть MxK, KxN и MxN большие матрицы (не умещаются в кэш L2) с максимальной производительностью при однопоточной реализации.

Возьмите dgemm из Intel MKL и раскрутите ее, например, IDA Pro. Или возьмите готовый код http://www.cs.utexas.edu/users/flame/goto/

[vitaly333]

Цитата:

Возьмите dgemm из Intel MKL и раскрутите ее, например, IDA Pro.

Что значит раскрутить? Насколько я знаю Intel не предоставляет исходников своей MKL.

Цитата:

Или возьмите готовый код

Там мало что понятно, все сделано на Ассемблере... хотелось бы написать свою реализацию, чтобы было всё понятно, используя подход, который используется в MKL и/или GotoBlas.

[Dongara]

vitaly333 писал(а):

Насколько я знаю Intel не предоставляет исходников своей MKL.

IDA Pro с исходниками не работает.

vitaly333 писал(а):

Там мало что понятно, все сделано на Ассемблере... хотелось бы написать свою реализацию, чтобы было всё понятно, используя подход, который используется в MKL и/или GotoBlas.

Не торопитесь, разберитесь и Ваш труд будет вознагражден. С наскоку ничего не получится: задача нетривиальная. За основу можете взять код из пакета Lapack. Если не секрет, почему Вы хотите взяться за эту задачу?

[vitaly333]

Цитата:

IDA Pro с исходниками не работает.

Думаю что пытаться дизассемблировать MKL не очень хорошая идея. Вряд ли что получится. На это уёдет слишком много времени. Тем более что ассемблер я практически не знаю.

Цитата:

Не торопитесь, разберитесь и Ваш труд будет вознагражден. С наскоку ничего не получится: задача нетривиальная. За основу можете взять код из пакета Lapack.

Понятное дело что нетривиальная. Вы наверное имели ввиду BLAS а не Lapack, поскольку DGEMM вызывается Lapack-ом именно из BLAS. А реализация DGEMM в BLAS далеко не идеальная. Например там отсутствует оптимизация под инструкции процессора.

Цитата:

Если не секрет, почему Вы хотите взяться за эту задачу?

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

[Dongara]

vitaly333 писал(а):

Думаю что пытаться дизассемблировать MKL не очень хорошая идея. Вряд ли что получится. На это уёдет слишком много времени. Тем более что ассемблер я практически не знаю.

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

vitaly333 писал(а):

Понятное дело что нетривиальная. Вы наверное имели ввиду BLAS а не Lapack, поскольку DGEMM вызывается Lapack-ом именно из BLAS. А реализация DGEMM в BLAS далеко не идеальная. Например там отсутствует оптимизация под инструкции процессора.

В пакет Lapack входит и BLAS. И код DGEMM совершенно не учитывает особенности железа: он, так сказать, дает только общее направление.

vitaly333 писал(а):

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

Поверьте, задача умножения матриц имеет множество подводных камней, с которыми не справиться и очень опытному программисту. Мой Вам совет: возьмитесь пока за задачу попроще.

[vitaly333]

Цитата:

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

Здесь вы абсолютно правы. Учитывать осообенности процессоров конечно нужно. Но почти все современные процессоры поддерживают векторизацию вычислений. Это должно быть использовано при написании алгоритма умножения. Самый внутренний цикл матричного умножения должен быть написан на Ассемблере с учетом векторизации (SSE2,SSE3 и.т.д.). При этом нужно использовать все доступные xmm регистры. И использовать многократно данные загруженые в регистры - т.е. минимизировать обмен данными между кэшем и регистрами - блокирование региистров. С этим я разобрался.

Цитата:

Поверьте, задача умножения матриц имеет множество подводных камней, с которыми не справиться и очень опытному программисту. Мой Вам совет: возьмитесь пока за задачу попроще.

Я и так потратил уже много времени на эту задачу. Не хочу отступать на пол пути.
Вопрос остается с блокированием кэша - как выбирать оптимальные размеры блоков. Ещё также нужно учитывать не только кэш данных но и TLB кэш. Т.к промахи в TLB дороже промахов в кэше данных.
Впринципе все ответы на мои вопросы есть в статье K. Goto 'Anatomy of High-Performance Matrix Multiplication'.
Я хочу написать алгоритм, который бы считывал парамерты процессора: размер кешей L1,L2, размер TLB, поддерживаемые инструкции и.т.д. На основе их выбирал из нескольких вариантов умножения наиболее подходящий для этого процессора. В своей статье, Goto подробно описывает как выбирать оптимальные параметры. Именно по этим рекомендациям я написал код. Но достичь производительности которую дает DGEMM из GotoBlas у меня не получается.

[Dongara]

vitaly333 писал(а):

...

Тогда успехов Вам. Хочу только заметить, что K. Goto одно пари уже проиграл. Можете в своих изысканиях опираться на результаты Intel MKL. Хотя существует и более скоростная библиотека. И хочу заметить, что скорость перемножения м-ц в Intel MKL для x64 близка к теоретической, т.е. к 100%.

[vitaly333]

Цитата:

Хотя существует и более скоростная библиотека.

Какая же?

[Dongara]

vitaly333 в сообщении #265027 писал(а):

Цитата:

Хотя существует и более скоростная библиотека.

Какая же?

Есть один умелец: он ее реализовал для поддержки GAUSSIAN: замена библиотеки Intel MKL на его библиотеку приводит к увеличению скорости программы в среднем процентов на 30.

[vitaly333]

Цитата:

Есть один умелец: он ее реализовал для поддержки GAUSSIAN: замена библиотеки Intel MKL на его библиотеку приводит к увеличению скорости программы в среднем процентов на 30

А по подробнее можно? Как называется. Где можно её скачать?

[Dongara]

vitaly333 в сообщении #265107 писал(а):

Цитата:

Есть один умелец: он ее реализовал для поддержки GAUSSIAN: замена библиотеки Intel MKL на его библиотеку приводит к увеличению скорости программы в среднем процентов на 30

А по подробнее можно? Как называется. Где можно её скачать?

Сам бы скачал: сей продукт используется под конкретный экземпляр исходников GAUSSIAN, благо это делать разрешается без распространения GAUSSIAN. Насколько я знаю, сейчас ведутся переговоры по приобретению этой библиотеки GAUSSIAN'ом. Если они завершатся успешно, то покупайте GAUSSIAN вместе с библиотекой.

[Vassil]

Видели это:

http://iwapt.org/2009/pdf/iwapt2009_sawa.pdf

(Auto Tuning Method for Deciding Block Size Parameters in ...)?

Может быть подскажет чего-то в желаемом Вами направлении.

[vitaly333]

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

[vitaly333]

Цитата:

Есть один умелец

Грановский?