Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Быстрые матричные сложения 
:(
    Опции темы
Elfet
Дата 17.5.2010, 22:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16
Всем привет! 

Чиркнул на своем блоге о матричных сложениях. Пожалуйста, прокомментируйте!  smile 

Сам пост:
Цитата

В одном проекте на С++ мне понадобилось два типа матриц: разреженные и заполненные.
Для первых выбрали матрицы из библиотеки uBLAS, для вторых выбрать библиотеку сложнее, так как важна была скорость с которой выполняются операции сложения матриц и умножения на скаляр.
Я решил протестировать несколько библиотек: uBLAS, tvmet и AlgLib.

Вот что получилось:

   1. операция: n = m + m;
      uBLAS: 1.357
      tvmet: 0.945
      AlgLib: 0.889
   2. операция: n = 2 * m – m;
      uBLAS: 1.607
      tvmet: 1.512
      AlgLib: 1.404
   3. операция: n = 2 * m + m / 3.3 – 0.1 * -m;
      uBLAS: 2.854
      tvmet: 3.176
      AlgLib: 3.682

В uBLAS хорошо оптимизированы алгоритмы по работе с выражениями и большими матрицами, но хуже работает на простых выражениях и маленьких матрицах чем AlgLib.

Тогда мне в голову пришла гениальная идея о том как можно ускорить простые операции с матрицами до максимума – использовать для этого циклы smile
А для красоты использовать вот такой-вот define:

Код

#define MatrixExp(n, exp) {\
for(int i = 0; i < n.size1(); i++)  \
for(int j = 0; j < n.size2(); j++) \
    n(i, j) = exp; \
}


Этим дефайном очень просто пользоваться: MatrixExp([новая матрица], [выражение с индексами (i,j)] ),
пример:

Код

MatrixExp(new_matrix, 2 * m1(i,j) + m2(i,j) -m3(i,j) / 5 );


Для любых выражений скорость на порядок выше ~ 0.515 (так не создаются временные объекты)

Вот пример из рабочего кода:

Код

Matrix total(varsize, varsize);
MatrixExp(total,  Ck[j] * k(i,j) + Ckx[j] * k_x(i,j) + Cky[j] * k_y(i,j)  );


PS Matrix – это моя обертка над классом ap::real_2d_array из AlgLib. Так как у них уж очень не удобно всё.



--------------------
PHP Чат Скрипт
PM MAIL WWW Skype   Вверх
kemiisto
Дата 17.5.2010, 22:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Дикий Кот. =^.^=
****
Награды: 1



Профиль
Группа: Участник Клуба
Сообщений: 3292
Регистрация: 29.7.2007

Репутация: 2
Всего: 160
Elfet, хотелось бы посмотреть на результаты Eigen.


--------------------
XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile
PM MAIL WWW GTalk Jabber   Вверх
toxx
Дата 17.5.2010, 23:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
Elfet
а какого размера матрицы тестировались?
PM MAIL   Вверх
Elfet
Дата 17.5.2010, 23:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16
kemiisto,  smile 

uBLAS я выбрал так как для неё нашёл реализованный метод GMRES. tvmet же рекомендуется на сайте ublas для маленьких матриц. AlgLib так же взял потому что уже используем её (SVD-разложение).

Добавлено через 1 минуту и 27 секунд
toxx, для 3х3 и 4х4.


--------------------
PHP Чат Скрипт
PM MAIL WWW Skype   Вверх
toxx
Дата 17.5.2010, 23:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
Elfet
я думал побольше =) что-то типа 1000х1000 и побольше =) интересно же как будет вести себя всё это дело...

p.s. спасибо за ответ в блоге.
PM MAIL   Вверх
Elfet
Дата 17.5.2010, 23:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16
toxx, ну 1000 у нас просто редко встречаются smile Если матрица большая и разреженная то лучше конечно же будет справляться специализированные библиотеки такие как uBLAS.

Чаще всего встречаются матрицы 3х3, 4х4 и очень большие 1000000х1000000.


--------------------
PHP Чат Скрипт
PM MAIL WWW Skype   Вверх
toxx
Дата 18.5.2010, 00:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 2
Всего: 13
Elfet
ага, понятно.я просто к тому, что эти измерения очень интересны в плане цифр(даже выступают с докладами на такие темы),
видел вот такие же замеры выполнения для различных видов сортировки(больше 3х разновидностей) 
различных матриц( как раз от 1000х1000 до 5000х5000 элементов,заполненных разными способами) очень интересно было смотреть что и как быстро справляется.
PM MAIL   Вверх
borisbn
Дата 18.5.2010, 06:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Elfet, попробуй Intel Performance Primitives. На своём процессоре они творят чудеса. Правда, платные. Но, если ты не вольный каменьщик, попроси фирму купить. По-моему, не очень дорого. 


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
Alexeis
Дата 18.5.2010, 09:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 12
Всего: 459
Elfet, попробуй еще вспомогательную библиотеку DirectX для работы с матрицами фиксированного размера. Кроме, думаю будет эффективно загружать флоаты/даблы сразу блоками по 128/256 бит и проводить вычисления при помощи инструкций SSE. Например в 256 битный регистр SSE влезет сразу 4 дабла или 8 флоатов. Для матрицы 4х4 это либо одна строка либо пол матрицы за одну инструкцию.


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
GoldFinch
Дата 18.5.2010, 09:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
Цитата(Elfet @  17.5.2010,  23:18 Найти цитируемый пост)
Тогда мне в голову пришла гениальная идея о том как можно ускорить простые операции с матрицами до максимума – использовать для этого циклы 

почитайте про expression templates
PM MAIL ICQ   Вверх
Elfet
Дата 18.5.2010, 10:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16
borisbn, я это, диплом делаю smile


Alexeis, использовать железо для просчётов? нам правда нужна кросс-платформеность. 


Цитата(GoldFinch @  18.5.2010,  10:52 Найти цитируемый пост)
почитайте про expression templates 

Как я понимаю, они реализованы в uBLAS, однако быстрее всё-равно использовать define MatrixExp. smile



--------------------
PHP Чат Скрипт
PM MAIL WWW Skype   Вверх
GoldFinch
Дата 18.5.2010, 10:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
Цитата(Elfet @  18.5.2010,  11:26 Найти цитируемый пост)
однако быстрее всё-равно использовать define MatrixExp

что быстрее? кодить? сомневаюсь.
код работает? скорость та же.
PM MAIL ICQ   Вверх
W4FhLF
Дата 18.5.2010, 11:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


found myself
****


Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121
У меня есть Intel Performance Primitives for Small Matrices. Правда я не юзал эту часть библиотеки, но наверняка она уделает все остальные.

Цитата(Alexeis @  18.5.2010,  09:20 Найти цитируемый пост)
Например в 256 битный регистр SSE влезет сразу 4 дабла или 8 флоатов.


В SSE таких регистров нет. 


--------------------
"Бог умер" © Ницше
"Ницше умер" © Бог
PM ICQ   Вверх
Elfet
Дата 18.5.2010, 11:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Белый и Пушистый
****


Профиль
Группа: Awaiting Authorisation
Сообщений: 3776
Регистрация: 2.4.2003

Репутация: нет
Всего: 16
Цитата(GoldFinch @  18.5.2010,  11:46 Найти цитируемый пост)
что быстрее? кодить? сомневаюсь.
код работает? скорость та же. 

А же провёл тесты. uBLAS проигрывает smile



--------------------
PHP Чат Скрипт
PM MAIL WWW Skype   Вверх
Alexeis
Дата 18.5.2010, 12:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 12
Всего: 459
Цитата(Elfet @  18.5.2010,  09:26 Найти цитируемый пост)
Alexeis, использовать железо для просчётов? нам правда нужна кросс-платформеность. 

  В каком смысле железо? Речь о процессоре. Процессоры выше PIV гарантировано имеют SSE2. Для машин не старше 4х лет можно запросто рассчитывать на SSE3.
  Кросс-платформеность Windows-Linux будет. 

  Если речь про другую архитектуру, то все свои тесты можешь выкрасить и выбросить, потому что на разных архитектурах по разному оптимизируются вычисления и различные операции "стоят" разных ресурсов.

Добавлено @ 12:10
Цитата(W4FhLF @  18.5.2010,  10:04 Найти цитируемый пост)
В SSE таких регистров нет.  

  А что за регистры такие YMM0 — YMM15 ?

Вот например Intel рекомендует использовать их для оптимизации задач линейной алгебры.
http://software.intel.com/ru-ru/articles/o...-dgemm-routine/

Это что-то не то. Значит была речь о том, что можно производить параллельно 2е операции над 128 битными регистрами. В сумме получается 4 дабла или 8 флоатов. 

Это сообщение отредактировал(а) Alexeis - 18.5.2010, 12:18


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0620 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.