Matrix Reorganization - Matrix Flattening and Transposing optimizations
Reviewer: Diego Novillo.
The layout of data in memory can have a significant affect on the performance of applications. Matrix flattening and matrix transposing are two data layout optimizations which reorganize matrices layout in memory. The purpose of matrix flattening is replacing a m-dimensional matrix with its equivalent n-dimensional matrix, where n<m. The frequent case is when a multidimensional matrix is flattened to its equivalent one dimensional matrix. This reduces the level of indirection needed for accessing the elements of the matrix. The second optimization is matrix transposing, which swaps rows and columns, and by doing so improves cache locality.
Both optimizations are interprocedural, and use the TREE-SSA based interprocedural framework, currently on ipa branch
Personnel
- Razya Ladelsky
Delivery Date
- Matrix Flattening patch - Mid November
- Matrix Transposing patch - Mid December
Benefits
- The performance measured on Linux PowerPC for matrix flattening on art benchmark is 35% improvement, and 9% for equake benchmark.
If profiling is enabled, matrix transposing optimization can be additionally performed. In this case, we get 2x improvement on art.
Furthermore, when measured together with another data layout optimization, struct reorg, there is 5x improvement on art.
Dependencies
Modifications Required
Adding an ipa pass