liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Automatic Permutation for Arbitrary Static Access Patterns
Linköping University, Department of Electrical Engineering, Computer Engineering. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Computer Engineering. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Computer Engineering. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Computer Engineering. Linköping University, The Institute of Technology.
2012 (English)In: Parallel and Distributed Processing with Applications (ISPA), 2012, IEEE , 2012, 215-222 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.
Keyword [en]
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
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:liu:diva-100377DOI: 10.1109/ISPA.2012.36ISBN: 978-1-4673-1631-6 (print)OAI: oai:DiVA.org:liu-100377DiVA: diva2:661698
Conference
2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications (ISPA), 10-13 July 2012, Madrid, Spain
Projects
ePUMAHiPEC
Funder
Swedish Foundation for Strategic Research
Available from: 2013-11-04 Created: 2013-11-04 Last updated: 2013-11-18

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Sohl, JoarWang, JianKarlsson, AndréasLiu, Dake

Search in DiVA

By author/editor
Sohl, JoarWang, JianKarlsson, AndréasLiu, Dake
By organisation
Computer EngineeringThe Institute of Technology
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 242 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf