#performance #matrix #transpose #in-place
#Производительность #матрица #транспонировать #на месте
Вопрос:
В Википедии есть обширное краткое изложение методов транспонирования матриц на месте.
Эти методы выглядят сложными в реализации, прежде чем приступить к их реализации, мне интересно, есть ли какие-либо тесты или другие доказательства, которые говорили бы, что эти методы превосходят транспонирование матрицы на месте с точки зрения времени работы на стене (на CPU / GPU / любой архитектуре)?
Все ли они выполняются медленнее по сравнению с использованием транспонирования на месте, когда данные копируются в другое место назначения?
Комментарии:
1. Нет, «Перенос доступа» просто переносит проблему на следующий этап вычисления, делая его потенциально свободным. (например, существуют алгоритмы matmul для обработки случая, когда обе матрицы хранятся одинаково, но это значительно проще, если на одном входе есть последовательные столбцы, а на другом — последовательные строки, в едином порядке памяти.) Помимо этого, я бы посмотрел на некоторые реализации библиотеки, например, у Eigen, вероятно, есть транспонирование SIMD, по крайней мере, для x86. Вы не сказали, какие архитектуры процессора вас интересуют, или какой размер проблемы относительно размера кэша L1d и т.д.
2. @PeterCordes Например, Eigen выполняет неуместное
Ответ №1:
Короче говоря, я не думаю, что когда-либо видел, чтобы обмен на месте выполнялся быстрее, чем не на месте. Просто подумайте о том, «когда вы в последний раз выбирали сортировку на месте вместо неуместной версии».
Но причиной использования транспонирования на месте обычно являются соображения памяти или распределения. В этом случае вы обязаны его использовать.
Для обмена не на месте вам также нужно подумать о кеше, кэшировании и еще раз о кешировании, разделите вашу проблему на более мелкие части, пока и целевой объект, и источник не смогут удобно находиться в кеше одновременно.