Home Publications edited volumes Awards Research Teaching Miscellaneous Full CV [pdf] BLOG
Events
Past Events

Publications of Torsten Hoefler
Torsten Hoefler, Grzegorz Kwasniewski:
  Automatic Complexity Analysis of Explicitly Parallel Programs
(In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'14), presented in Prague, Czech Republic, ACM, Jun. 2014)
AbstractThe doubling of cores every two years requires programmers
to expose maximum parallelism. Applications that are developed on today’s machines will often be required to run on
many more cores. Thus, it is necessary to understand how
much parallelism codes can expose. The work and depth
model provides a convenient mental framework to assess the
required work and the maximum parallelism of algorithms
and their parallel efficiency. We propose an automatic analysis to
extract work and depth from a sourcecode. We do
this by statically counting the number of loop iterations depending on the set of input parameters. The resulting ex
pression can be used to assess work and depth with regards
to the program inputs. Our method supports the large class
of practically relevant loops with affine update functions and
generates additional parameters for other expressions. We
demonstrate how this method can be used to determine work
and depth of several realworld applications. Our technique
enables us to prove if the theoretically maximum parallelism
is exposed in a practical implementation of a problem. This
will be most important for futureproof software development.
Documentsdownload article:
  BibTeX  @inproceedings{hoeflerkwasniewskicomplexity, author={Torsten Hoefler and Grzegorz Kwasniewski}, title={{Automatic Complexity Analysis of Explicitly Parallel Programs}}, year={2014}, month={Jun.}, booktitle={Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'14)}, location={Prague, Czech Republic}, publisher={ACM}, source={http://www.unixer.de/~htor/publications/}, } 

