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

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

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

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

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

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

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;
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Спасибо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Типа

время обработки ЦПУ в ОЗУ < время пересылки в ГПУ + время обработки ГПУ

?

+ время пересылки обратно

Завтра по возможности напишу тест для айфона и сравню.

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

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

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

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

Сейчас программа рисует по столбцам

What Every Programmer Should Know About Memory.

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

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

Ну и на код смотреть надо, а то, может, до забивания канала и не доходит :)

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

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

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

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

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

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

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

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

Так и есть

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

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

http://pastebin.com/wKrZGhUr

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

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

http://pastebin.com/CLLYxM19

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

    if (!text) printf ("Error\n");
    Uint8 *col = text->pixels;

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

Это ты так воксели, что ли, рисуешь?

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

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

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

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

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

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

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];