Automatic Permutation for Arbitrary Static Access Patterns
2012 (English)In: Parallel and Distributed Processing with Applications (ISPA), 2012, IEEE , 2012, 215-222 p.Conference paper (Refereed)
A significant portion of the execution time on current SIMD and VLIW processors is spent on data access rather than instructions that perform actual computations. The ePUMA architecture provides features that allow arbitrary data elements to be accessed in parallel as long as the elements reside in different memory banks. Using permutation to move data elements that are accessed in parallel, the overhead from memory access can be greatly reduced; and, in many cases completely removed. This paper presents a practical method for automatic permutation based on Integer Linear Programming (ILP). No assumptions are made about the structure of the access patterns other than their static nature. Methods for speeding up the solution time for periodic access patterns and reusing existing solutions are also presented. Benchmarks for e.g. FFTs show speedups of up to 3.4 when using permutation compared to regular implementations.
Place, publisher, year, edition, pages
IEEE , 2012. 215-222 p.
integer programming;linear programming;multiprocessing systems;parallel architectures;storage management;ILP;SIMD processor;VLIW processor;arbitrary data element;arbitrary static access pattern;automatic permutation;data access;ePUMA architecture;execution time;integer linear programming;memory access;memory banks;periodic access pattern;Discrete cosine transforms;Equations;Hardware;Mathematical model;Memory management;Program processors;Vectors;integer linear programming;multi-bank memories;parallel data access;permutation
IdentifiersURN: urn:nbn:se:liu:diva-100377DOI: 10.1109/ISPA.2012.36ISBN: 978-1-4673-1631-6OAI: oai:DiVA.org:liu-100377DiVA: diva2:661698
2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications (ISPA), 10-13 July 2012, Madrid, Spain
FunderSwedish Foundation for Strategic Research