AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features

Vladimir V. Voevodin; Alexander S. Antonov; Jack Dongarra

doi:10.14529/jsfi150101

Authors

Vladimir V. Voevodin Moscow State University, Moscow
Alexander S. Antonov Moscow State University, Moscow
Jack Dongarra University of Tennessee, Knoxville

DOI:

https://doi.org/10.14529/jsfi150101

Abstract

The main goal of this project is to formalize the mapping of algorithms onto the architecture of parallel computing systems. The basic idea is that features of algorithms are independent of any computing system. A detailed description of a given algorithm with a special emphasis on its parallel properties is made once, and after that it can be used repeatedly for various implementations of the algorithm on different computing platforms. Machine-dependent, part of this work is devoted to describing features of algorithms implementation for different parallel architectures. The proposed description of algorithms includes many non-trivial features such as: parallel algorithm complexity, resource of parallelism and its properties, features of the informational graph, computational cost of algorithms, data locality analysis as well as analysis of scalability potential, and many others. Descriptions of algorithms form the basis of AlgoWiki, which allows for collaboration with the computing community in order to produce different implementations and achieve improvement. Project website: http://algowiki-project.org/en/

References

Dongarra, J., Beckman, P., Moore, T., Aerts, P., Aloisio, G., Andre, J.C., Barkai, D., Berthou, J.Y., Boku, T., Braunschweig, B. and others: The International Exascale Software Project roadmap // International Journal of High Performance Computing Applications, Vol. 25, No. 1, p.3-60 (2011)

Big Data and Extreme-scale Computing (BDEC), http://www.exascale.org

EESI project - The European Exascale Software Initiative, http://www.eesi-project.eu

Asanović, K., Bodik R., Demmel J., Keaveny T., Keutzer K., Kubiatowicz J. D., et al.: The Parallel Computing Laboratory at U.C. Berkeley: A Research Agenda Based on the Berkeley View (2008)

Asanović, K., Bodik R., Catanzaro B., Gebis J. J., Husbands P., Keutzer K., et al.: The Landscape of Parallel Computing Research: A View from Berkeley (2006)

Christesen C.: Mantevo Views. A Flexible System for Gathering and Analyzing Data for the Mantevo Project. Thesis, College of St. Benedict/St. John's University (2007)

Heroux, M.A., Doerfler, D.W., Crozier, P.S., Willenbring, J.M., Edwards, H.C., Williams, A., Rajan, M., Keiter, E.R., Thornquist, H.K., Numrich, R.W.: Improving Performance via Mini-applications. Sandia National Laboratories, Report SAND2009-5574 (2009)

Kaiser, A., Williams, S., Madduri, K., Ibrahim, K., Bailey, D., Demmel, J., Strohmaier, E.: TORCH Computational Reference Kernels: A Testbed for Computer Science Research, Lawrence Berkeley National Laboratory, Paper LBNL-4172E (2010)

Kaiser, A., Williams, S., Madduri, K., Ibrahim, K., Bailey, D., Demmel, J., Strohmaier, E.: A Principled Kernel Testbed for Hardware/Software Co-Design Research, Proceedings of the 2nd USENIX Workshop on Hot Topics in Parallelism (HotPar) (2010)

Strohmaier, E., Williams, S., Kaiser, A., Madduri, K., Ibrahim, K., Bailey, D., Demmel, J.: A Kernel Testbed for Parallel Architecture, Language, and Performance Research, International Conference of Numerical Analysis and Applied Mathematics (ICNAAM) (2010)

Knuth, D.: The Art of Computer Programming, Volumes 1-4A Boxed Set 3rd Edition (Reading, Massachusetts: Addison-Wesley (2011)

Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes 3rd Edition: The Art of Scientific Computing. WH Press. Cambridge university press (2007)

Ortega, J.M.: Introduction to Parallel and Vector Solution of Linear Systems, Plenum Press, New York, USA (1988)

Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J., Dongarra, J, Eijkhout, V., Pozo, R., Romine, C., Van der Vorst, H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition, SIAM, Philadelphia (1994)

Saad, Y.: Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia (2003)

Polychronopoulos, C.D.: Compiler optimizations for enhancing parallelism and their impact on architecture design. IEEE Trans. on Computers, Vol.37, N.8 (1988)

Voevodin, V.V.: Mathematical foundations of parallel computing, World Scientific Publishing Co., Series in computer science. Vol.33. 343 p. (1992)

Voevodin, V.V.: Information structure of sequential programs. Russ. J of Num. An. and Math Modelling. Vol.10, N3. 279-286 (1995)

Voevodin, V.V., Voevodin, Vl.V.: Parallel computing. BHV-St.Petersburg, 608 p. (in Russian) (2002)

Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, http://www.netlib.org/linalg/html_templates/Templates.html

A Library of Parallel Algorithms, http://www.cs.cmu.edu/~scandal/nesl/algorithms.html

Scientific and educational Internet site of RCC on numerical analysis, http://num-anal.srcc.msu.ru/ (in Russian)

Wikipedia, List of algorithms, https://en.wikipedia.org/wiki/List_of_algorithms

Adinets A.V., Bryzgalov P.A., Voevodin Vad.V., Zhumatii S.A., Nikitenko D.A., Stefanov K.S.: Job Digest: an approach to dynamic analysis of job characteristics on supercomputers, Numerical methods and programming: Advanced Computing, Vol.13, Section 2, Pp. 160-166 (2012)