Почему не мое матрично-векторное масштабирование?

15

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

Что я хочу

Я реализую параллельную версию методов подпространств Крылова для плотных матриц. В основном GMRES, QMR и CG. Я понял (после профилирования), что моя рутина DGEMV была жалкой. Поэтому я решил сосредоточиться на этом, изолируя его. Я попытался запустить его на 12-ядерном компьютере, но ниже приведены результаты для 4-ядерного ноутбука Intel i3. В тенденции не так много различий.

Мой KMP_AFFINITY=VERBOSEвывод доступен здесь .

Я написал небольшой код:

size_N = 15000
A = randomly_generated_dense_matrix(size_N,size_N); %Condition Number is not bad
b = randomly_generated_dense_vector(size_N);
for it=1:n_times %n_times I kept at 50 
 x = Matrix_Vector_Multi(A,b);
end

Я считаю, что это имитирует поведение CG в течение 50 итераций.

Что я пробовал:

Перевод

Я изначально написал код на Фортране. Я перевел это на C, MATLAB и Python (Numpy). Само собой разумеется, MATLAB и Python были ужасны. Удивительно, но C был лучше, чем FORTRAN на секунду или две для вышеуказанных значений. Последовательно.

Профилирование

Я профилировал свой код для запуска, и он работал в течение 46.075нескольких секунд. Это было, когда MKL_DYNAMIC был установлен вFALSE и все ядра были использованы. Если бы я использовал MKL_DYNAMIC как истину, то в любой момент времени использовалась только (приблизительно) половина количества ядер. Вот несколько деталей:

Address Line    Assembly                CPU Time

0x5cb51c        mulpd %xmm9, %xmm14     36.591s

Наиболее трудоемким процессом представляется:

Call Stack                          LAX16_N4_Loop_M16gas_1
CPU Time by Utilization             157.926s
CPU Time:Total by Utilization       94.1%
Overhead Time                       0us
Overhead Time:Total                 0.0%    
Module                              libmkl_mc3.so   

Вот несколько изображений:введите описание изображения здесь введите описание изображения здесь

Выводы:

Я настоящий новичок в профилировании, но я понимаю, что ускорение все еще не хорошо. Последовательный (1-ядерный) код завершается за 53 секунды. Это скорость меньше, чем 1,1!

Реальный вопрос: что я должен сделать, чтобы улучшить свое ускорение?

Вещи, которые, я думаю, могут помочь, но я не уверен:

  • Реализация Pthreads
  • Реализация MPI (ScaLapack)
  • Ручная настройка (я не знаю, как. Пожалуйста, порекомендуйте ресурс, если вы предлагаете это)

Если кому-то нужно больше (особенно в отношении памяти) деталей, пожалуйста, дайте мне знать, что мне следует запускать и как. У меня никогда не было профилированной памяти раньше.

расследование
источник

Ответы:

20

Размер вашей матрицы 15 000 x 15 000, поэтому в матрице 225 млн элементов. Это составляет примерно 2 ГБ памяти. Это намного больше, чем размер кэша вашего процессора, поэтому он должен загружаться полностью из основной памяти при каждом умножении матриц, что составляет примерно 100 ГБ для передачи данных, плюс то, что вам нужно для векторов источника и назначения.

Максимальная пропускная способность памяти у i3 составляет приблизительно 21 ГБ / с в зависимости от спецификаций Intel, но если вы посмотрите в Интернете, вы обнаружите, что в действительности максимум половина из этого действительно доступна. Таким образом, по крайней мере вы ожидаете, что ваш тест будет длиться 10 секунд, а фактическое измерение 45 секунд не так уж далеко от этой отметки.

В то же время вы также делаете около 10 миллиардов умножений и операций с плавающей запятой. Учитывая, скажем, 10 тактов для комбинации и тактовую частоту 3 ГГц, вы получите ~ 30 секунд. Конечно, они могут работать одновременно со спекулятивной загрузкой памяти, если кеш умен.

В общем, я бы сказал, что вы не слишком далеко от цели. Чего бы вы ожидали?

Вольфганг Бангерт
источник
Разве нет способа получить ускорение как минимум на 2-3?
Дознание
@Nunoxic - вы можете оценить производительность памяти в вашей системе, используя такой инструмент, как SiSoftware Sandra. Анализ Wolfgangs мне кажется очень интересным, если ваше приложение ограничено пропускной способностью памяти, распараллеливание мало что поможет, если вообще поможет. Кроме того, обратите внимание на любые варианты энергосбережения, которые у вас могут быть, они могут снижать производительность памяти. Кроме того, рассмотрите возможность замены вашей памяти более качественной памятью, например, более низкая задержка CAS может существенно повлиять на время вашей стены.
Марк Бут
4

Как дела умножение матрицы на вектор? Двойной цикл вручную? Или звонки в BLAS? Если вы используете MKL, я настоятельно рекомендую использовать подпрограммы BLAS в многопоточной версии.

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

Обновить

После обсуждения в комментариях ниже выясняется, что ваш Intel Core i3-330M имеет только два «настоящих» ядра. Два недостающих ядра эмулируются с гиперпоточностью . Поскольку в многопоточных ядрах и шина памяти, и модули с плавающей запятой являются общими, вы не получите никакого ускорения, если какой-либо из этих двух факторов является ограничивающим фактором. Фактически, использование четырех ядер может даже замедлить работу.

Какие результаты вы получаете на «только» двух ядрах?

Pedro
источник
Я пробовал ATLA, GoTo и Netlib BLAS. Все они слабее, чем MKL в производительности. Это ожидается или я что-то не так делаю? Я составил ATLAS, как указано в справочнике. Далее, я вставил свой (точный) код здесь . Это называется MKL's BLAS.
Дознание
Хорошо, а для масштабирования, вы уверены, что в базовом сценарии код работает только на одном процессоре? Например, если вы сравните его, показывает ли гистограмма использования процессора только одно ядро?
Педро
Да. Гистограмма процессора показывает 1 ядро.
Дознание
Просто из любопытства, что вы получаете за два или три ядра? У вашей машины на самом деле четыре физических ядра или только два ядра с гиперпоточностью ?
Педро
Как мне это узнать? Я включил свой KMP_AFFINITY в основную.
Дознание
0

У меня сложилось впечатление, что упорядочение по основным строкам оптимально для этой проблемы с точки зрения времени доступа к памяти, использования строк кэша и пропусков TLB. Я предполагаю, что ваша версия FORTRAN вместо этого использовала упорядочение по основным столбцам, что могло бы объяснить, почему оно неизменно медленнее, чем версия C.

б

Вы также можете проверить скорость, если вы просто суммируете все элементы матрицы в одном цикле вместо умножения вектора матрицы. (Возможно, вы захотите развернуть цикл в 4 раза, потому что неассоциативность сложения может помешать компилятору выполнить эту оптимизацию за вас.)

Томас Климпел
источник