[PR] Tensor permutation in-place on linearized data [systemds]

["dogakarakas (via GitHub)" <gi...@apache.org>]

dogakarakas opened a new pull request, #2412:
URL: https://github.com/apache/systemds/pull/2412

   This PR implements the transposeInPlaceTensor() functionality, facilitating in-place permutations for tensors linearized within a MatrixBlock. The implementation is inspired by the EITHOT algorithm (Efficient In-Place Transposition for High-Order Tensors) and focuses on minimizing memory overhead by avoiding full-copy allocations.
   
   **Implementation Details**:
   The implementation handles permutations by identifying and applying fundamental primitive patterns:
   
   Primitive 21 (Matrix Transpose): When the permutation allows for a split index where both sub-permutations maintain their internal order, the logic leverages the highly optimized LibMatrixReorg.transposeInPlaceDenseBrenner() method. This ensures peak performance for standard matrix-style transpositions.
   
   Primitive 1324 (General Permutation): For more complex high-order permutations, the algorithm resolves the transposition by swapping neighboring data blocks and applying a cycle-following algorithm.
   
   Cycle Tracking: To maximize generalizability and reduce implementation complexity, a robust cycle-tracking strategy was utilized. While the EITHOT paper suggests Catanzaro's algorithm for certain index calculations, this implementation utilizes a simplified conversion strategy to ensure better integration with existing SystemDS data structures.
   
   Parallelization Potential: As noted in the EITHOT literature, the block-based nature of this algorithm is highly amenable in GPU settings.
   
   **Testing Framework**:
   Test Location: src/test/java/org/apache/sysds/test/component/matrix/libMatrixReorg/TransposeInPlaceBrennerTest.java.
   
   Validation Logic: A helper method, compareTensorValues(), was implemented within the test component src/test/java/org/apache/sysds/test/TestUtils.java, to compare each cell value.
   
   Link for the article: https://www.semanticscholar.org/paper/EITHOT%3A-Efficient-In-place-Transposition-of-High-on-Wu-Tu/cf4c177a64e1e271ccf1b742b5cc2efdb77fda9b 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Tensor permutation in-place on linearized data [systemds]

["mboehm7 (via GitHub)" <gi...@apache.org>]

mboehm7 commented on PR #2412:
URL: https://github.com/apache/systemds/pull/2412#issuecomment-4161628698

   Thanks for the contribution @dogakarakas. During the merge I fixed the redundant test-utils, formatting (tabs over spaces), warnings, and method name violations. 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] Tensor permutation in-place on linearized data [systemds]

["mboehm7 (via GitHub)" <gi...@apache.org>]

mboehm7 closed pull request #2412: Tensor permutation in-place on linearized data
URL: https://github.com/apache/systemds/pull/2412


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: dev-unsubscribe@systemds.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org