Efficient way to transpose matrix?

Clemens Eisserer

Hi,

I would like to transpose (exchange columns and rows) a 64x64 matrix, which contains 1-byte elements (so 8x8 registers).

All solutions I have come up so far are horrible inefficient, and require a huge amount of instructions - so maybe there are some special tricks which would make it more efficient.

Thank you in advance, Clemens

over 13 years ago

0 Chad Courtney over 13 years ago

TI__Mastermind 30825 points

Clemens,

This is simply memory location manipulation, I'd suggest doing this with the EDMA instead of using the DSP. It's going to be fairly inefficient doing it with the DSP, but should be able to set up an EDMA transfer to do it in a single shot.

Best Regards,
Chad

0 Victor Kazmirenko over 13 years ago in reply to Chad Courtney

Guru 13202 points

As Chad suggested, EDMA engine can do this work while DSP is doing more intelligent jobs.

I'd like to suggest think further and define, why actual transposition is required. If your matrix participate in some calculation, then you may substitute A^T[i,j] === A[j,i], i.e. get elements of transposed matrix without actual transposing. Many linear algebra algorithms like Cholesky decomposition use this way.

0 Clemens Eisserer over 13 years ago in reply to Victor Kazmirenko

Expert 2430 points

Thanks a lot for the EDMA suggestions, I will have a look at it.

Also thanks for the suggestion about just adapting the algorithm to work with the non-transposed matrix, however as its part of a larger library (with many different existing implmentations) I am not in control of data managemenbt.

Thanks again, Clemens

Processors

Processors forum

Efficient way to transpose matrix?