DOI: https://doi.org/10.26089/NumMet.v16r111

An open AlgoWiki encyclopedia of algorithmic features: from mobile to extreme scale

Authors

  • Vl.V. Voevodin

Keywords:

parallel computing
structure of algorithms
sequential properties of algorithms
parallel properties of algorithms
supercomputers
computing platforms
efficient implementation of algorithms
scalability
data locality
encyclopedia of algorithms

Abstract

One of the fundamental problems of high performance computing consists in the necessity of a careful matching between the algorithmic structure of parallel programs and the features of a particular computer architecture. The performance capabilities of modern computers are significant; however, the computer’s efficiency drastically decreases if such a matching is not achieved even in one of the stages during the process of solving a problem. The AlgoWiki project is based on the fact that the features of algorithms by themselves are not dependent on computing systems. In other words, a detailed description of machine-independent properties of an algorithm should be done only once; after that, this description can be used many times when implementing this algorithm on various hardware/software environments. Also of importance of this project is its machine-dependent part devoted to the description of algorithmic implementation peculiarities with consideration of particular hardware/software platforms. The main result of this project is an open AlgoWiki encyclopedia covering the properties of algorithms and the peculiarities of their implementation on various computing systems. The knowledge of how to reveal, describe, analyze, and interpret the properties of algorithms will become of significant importance in a few years. This conclusion is valid for future exaflop supercomputers and for other computing platforms: from server to mobile devices.

New computational technologies

Downloads

Published

2015-03-05

Issue

Vol. 16 (2015): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

Vl.V. Voevodin

Lomonosov Moscow State University,
Research Computing Center
• Deputy Director

References

  1. J. Dongarra, P. Beckman, T. Moore, et al., “The International Exascale Software Project Roadmap,” Int. J. High Perform. Comput. Appl. 25 (1), 3-60 (2011).

  2. http://www.exascale.org . Cited February 22, 2015.

  3. http://www.eesi-project.eu . Cited February 22, 2015.
  4. K. Asanović, R. Bodik, B. C. Catanzaro, et al., The Landscape of Parallel Computing Research: A View from Berkeley , Report UCB/EECS-2006-183 (Univ. California at Berkeley, Berkeley, 2006).
  5. D. E. Knuth, The Art of Computer Programming , 3rd ed. (Addison-Wesley, Reading, 2011), Vols. 1-4.
  6. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes: The Art of Scientific Computing , 3rd ed. (Cambridge Univ. Press, New York, 2007).
  7. J. M. Ortega, Introduction to Parallel and Vector Solution of Linear Systems (Plenum, New York, 1988).
  8. R. Barrett, M. Berry, T. F. Chan, et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods , 2nd ed. (SIAM Press, Philadelphia, 1994).
  9. Y. Saad, Iterative Methods for Sparse Linear Systems , 2nd ed. (SIAM Press, Philadelphia, 2003).
  10. V. V. Voevodin, Mathematical Foundations of Parallel Computing (World Sci. Publ., Singapore, 1992).
  11. V. V. Voevodin, “Information Structure of Sequential Programs,” Russ. J. Numer. Anal. Math. Modelling 10 (3), 279-286 (1995).
  12. V. V. Voevodin and Vl. V. Voevodin, Parallel Computing (BHV-Petersburg, St. Petersburg, 2002), 608 pp.
  13. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods.
    http://www.netlib.org/linalg/html_templates/Templates.html . Cited February 22, 2015.
  14. A Library of Parallel Algorithms.
    http://www.cs.cmu.edu/*| |scandal/nesl/algorithms.html . Cited February 22, 2015.
  15. The Scientific Educational Internet Resource on Numerical Analysis of the Research Computing Center of Moscow State University.
    http://num-anal.srcc.msu.ru . Cited February 22, 2015.
  16. Wikipedia: List of Algorithms.
    https://en.wikipedia.org/wiki/List_of_algorithms . Cited February 22, 2015.
  17. Vl. V. Voevodin and Vad. V. Voevodin, “The Fortunate Locality of Supercomputers,” Otkrytye Sistemy, No. 9, 12-15 (2013).
  18. P. A. Shvets and Vad. V. Voevodin, “The Covering Method for Measuring Locality of Programs Memory Usage,” Vestn. Ufa Aviatsion. Tekh. Univ. 18 (1), 224-229 (2014).
  19. A. S. Antonov and A. M. Teplov, “On Scalability Complexity of Parallel Programs,” in Proc. 14th Int. Conf. on High Performance Computing Using Cluster Systems, Perm, Russia, November 10-12, 2014 (Perm Nat. Res. Univ., Perm, 2014), pp. 20-27.
  20. D. A. Nikitenko, “Overall Supercomputer Performance Analysis Based on System Monitoring Data,” Vychisl. Metody Programm. 15 (1), 85-97 (2014).