LINUX.ORG.RU

Транспонирование матрицы


0

1

Есть массив uint8_t 1024x1024

Надо его транспонировать как можно быстрее. Хотелось бы узнать, есть ли готовые библиотеки, а так же то, как они работают.

Для этого хотелось бы пояснее разобраться, как работает кэш CPU. Как я понял, при обращении к некоторому элементу массива (a[1], например), в кэш загружаетс сразу некоторый участок памяти, содержащий этот элемент. Программы для транспонирования матриц и подобных операций делают это по маленьким блокам, чтобы весь он влез в кэш, и операции типа m[i,j] = m[j,i] не приводили к загрузки в кеш чего-либо ещё.

Вопросы такие: какой размер блока имеет смысл брать (т.е. сколько кеш обычно сможет вместить в себя)? Как именно происходит деление на блоки? Копированием в отдельный массив, чтобы информация была в нем неразрывна?



Последнее исправление: Zorn (всего исправлений: 1)

Все зависит от модели проца.

Транспонирование лучше всего делает графический процессор.

bk_ ★★
()

Могу посоветовать посмотреть как это было сделано до вас (точно есть в opencv, наверняка в gmp да и вообще в любой мат. библиотеке). А вообще, на «fast matrix transposition» в гугле вторым результатом pdf-ка как раз таки «Cache-Efficient Matrix Transposition».

slovazap ★★★★★
()

Матрицы бывают разные. Бывают разреженные. Для них есть свои алгоритмы. Хотя бы язык укажи.

Если матрицы это обычные массивы в С, то

int buffer;
for(int n=100;n!=0;--n){
    for(int k=n-1;k!=0;--k){
        buffer = a[n][k];
        a[n][k] = a[k][n];
        a[k][n] = buffer;
    }
}

будет вполне оптимально. компилятор сам сообразит как оптимизировать.

soomrack ★★★★
()
Ответ на: комментарий от bk_

Транспонирование лучше всего делает графический процессор.

Пересылка данных займет больше времени, чем транспонирование. мегабайтную матрицу оттранспонировать это около const*10^6 операций. Процессор делает number_of_cores*2.4*10^9 операций в секунду. ИМХО, это оптимизировать не меет смысла.

soomrack ★★★★
()
Ответ на: комментарий от Zorn

Собственно, зачем я это сюда запостил: хотелось бы вот эти 2 обозначенных вопроса уточнить, дополнительно к тому что я уже прочитал (точнее, просмотрел) и нагуглил

Zorn
() автор топика
Ответ на: комментарий от soomrack

Посмотри, например, насколько память медленнее проца.

Zorn
() автор топика
Ответ на: комментарий от Zorn

Вопросы такие: какой размер блока имеет смысл брать (т.е. сколько кеш обычно сможет вместить в себя)? Как именно происходит деление на блоки? Копированием в отдельный массив, чтобы информация была в нем неразрывна?

Собственно, зачем я это сюда запостил: хотелось бы вот эти 2 обозначенных вопроса уточнить, дополнительно к тому что я уже прочитал (точнее, просмотрел) и нагуглил

1. размер кеша в разных процессорах разный. разница даже среди распространненых сегодня процессоров очень сильная, в разы.

2. да, нужно копировать в отдельный массив. Что бы работать с одним массивом: при транспонировании будет два цикла: один +1, второй +n (размер блока n*n).

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

soomrack ★★★★
()
Ответ на: комментарий от bk_

Транспонирование лучше всего делает графический процессор.

Копирование данных из между оперативками убьет всю выгоду.

Проверено: для таких элементарнейших операций нет ничего быстрее вычисления на CPU с распараллеливанием (хоть openmp, хоть pthreads) по количеству ядер.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от soomrack

Спасибо.

Я тут просто делаю простой рендерер ландшафтика (похожий на тот, что у Кена Сильвермана на страничке voxlap). Использую для этого SDL, где экран представляется в виде такого массивчика. Сейчас программа рисует по столбцам, и индекс элемента массива скачет постоянно на ширину экрана. Не меняя сам алгоритм, просто повернул картинку на 90 градусов (теперь индекс изменяется) на 1 и, о чудо! получил 210 fps взамен 180. Вот и думаю, новый алгоритм придумывать, или просто транспонировать этот массив

Zorn
() автор топика

Гы, а ссылки на индексы поменять нельзя, типа, «что у нас сейчас обозначает строки, а что столбцы?». Или тебе обязательно потом этот блок памяти нужно будет скармливать какой-нибудь библиотеке?

anonymous
()
Ответ на: комментарий от Zorn

Я тут просто делаю простой рендерер ландшафтика (похожий на тот, что у Кена Сильвермана на страничке voxlap). Использую для этого SDL, где экран представляется в виде такого массивчика. Сейчас программа рисует по столбцам, и индекс элемента массива скачет постоянно на ширину экрана. Не меняя сам алгоритм, просто повернул картинку на 90 градусов (теперь индекс изменяется) на 1 и, о чудо! получил 210 fps взамен 180. Вот и думаю, новый алгоритм придумывать, или просто транспонировать этот массив

Просто транспонировать. Это со всех точек зрения правильно.

soomrack ★★★★
()

А нафига? Работай с ним переставив индексы.

r2d2
()
Ответ на: комментарий от soomrack

Пересылка данных займет больше времени, чем транспонирование

Подумай головой. 1024х1024х1байт = 1 МБ.

Даже если это 4МБ - это обычная текстура с разрешением 1024х1024. На айфоне такие текстуры грузятся со скоростью 10-20 штук в секунду (зависит от фоновых задач).

Учти, что это айфон. А на десктопе с можщными видяхами - куда быстрее.

И ты говоришь пересылка будет долгой? Ты не прав.

bk_ ★★
()
Ответ на: комментарий от Eddy_Em

Копирование данных из между оперативками убьет всю выгоду.

см. коммент выше

bk_ ★★
()
Ответ на: комментарий от Eddy_Em

а параллелить то зачем??? все равно все в пропускную способность памяти упирается, тут параллель не параллель все едино...

AIv ★★★★★
()
Ответ на: комментарий от bk_

Он прав, самое долгое будет именно пересылка. Вопрос не в том, сколько это будет мс, а в том что будет быстрее, ЦПУ или ЖПУ.

AIv ★★★★★
()
Ответ на: комментарий от AIv

Проверял: на таких элементарных операциях распараллеливание на 4 потока дает прирост производительности раза 2..2.5.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от bk_

Там память общая, хотя копировать в отведенную под vram область все равно нужно.

note173 ★★★★★
()
Ответ на: комментарий от Eddy_Em

Как говорил Станиславский - не верю! Точнее, верю - если матрица маленькая и влезает в кэш;-)

AIv ★★★★★
()
Ответ на: комментарий от AIv

Ладно. Врать не буду: столь элементарнийшую операцию я на распараллеливание не проверял. Самое простое, что параллелил - математические функции над элементами матриц.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от AIv

а параллелить то зачем??? все равно все в пропускную способность памяти упирается, тут параллель не параллель все едино...

На NUMA контроллеров памяти много может быть.

mv ★★★★★
()
Ответ на: комментарий от mv

На NUMA контроллеров памяти много может быть.

Разве что... но на айфоне наврядли;-)

Да и ТС игрульку пишет, думаете он ее на нуме пущать будет?;-)

AIv ★★★★★
()
Ответ на: комментарий от Eddy_Em

Самое простое, что параллелил - математические функции над элементами матриц.

Ну дак всякие синуса-шинуса сам Б-г параллелил и нам велел;-)

AIv ★★★★★
()
Ответ на: комментарий от AIv

Да и ТС игрульку пишет, думаете он ее на нуме пущать будет?;-)

Нет, конечно, но по моим наблюдениям скоро ширпотреб для дома будет NUMA, иначе всё разстаяющееся количество ядер будет не прокормить. Дешёвые сервера за $3k уже NUMA, и там поход процессора не в свою память прям хорошо так заметен.

mv ★★★★★
()
Ответ на: комментарий от anonymous

нужно будет скармливать какой-нибудь библиотеке?

Так и есть

Zorn
() автор топика
Ответ на: комментарий от mv

Ну и на код смотреть надо

Раз так просишь, то вот он:

http://pastebin.com/wKrZGhUr

/100 и /200, ясное дело, потом уберу из внутреннего цикла.

Вот медленный вариант, но легче читаемый (и ешё с билинейной фильтрацией):

http://pastebin.com/CLLYxM19

Текстурки размером 512x512 8-битный grayscale, если захочешь запустить)

Zorn
() автор топика
Ответ на: комментарий от Zorn
    if (!text) printf ("Error\n");
    Uint8 *col = text->pixels;

Тебе от сообщения «Error» перед сегфолтом легче? ;) И результат TTF_OpenFont не проверяешь.

mv ★★★★★
()
Ответ на: комментарий от mv

Именно. Передовая технология )

Тебе от сообщения «Error» перед сегфолтом легче? ;) И результат TTF_OpenFont не проверяешь.

Да пока плевать на них. Пруф оф концепт эдакий.

Zorn
() автор топика
Ответ на: комментарий от mv

Тебе от сообщения «Error» перед сегфолтом легче? ;)

Да, этот «быстрый» вариант часто так падает. Я его сделал, чтобы проверить, не ошибся ли в математических выкладках

Zorn
() автор топика

Предлагаю такую фичу:

1) держать в памяти ещё одну переменную типа bool и менять её значение на противоположное при каждом транспонировании.

2) При операциях с матрицей писать вместо

C[i,k] = A[i,k] + B[i,k]
что-то вроде
if(A_trans == true) C[i,k] = A[k,i]+B[i,k];
else C[i,k] = A[i,k] + B[i,k];

yura_ts ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.