Открытая энциклопедия свойств алгоритмов AlgoWiki: от мобильных платформ до экзафлопсных суперкомпьютерных систем

Авторы

DOI:

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

Ключевые слова:

параллельные вычисления, структура алгоритмов, последовательные свойства алгоритмов, параллельные свойства алгоритмов, суперкомпьютеры, компьютерные платформы, эффективная реализация алгоритмов, масштабируемость, локальность данных, энциклопедия алгоритмов

Аннотация

Фундаментальная проблема высокопроизводительных вычислений — это необходимость аккуратного согласования структуры алгоритмов и программ с особенностями архитектуры компьютеров. Возможности современных компьютеров велики, но если хотя бы на одном из этапов процесса решения задачи согласования не будет, то и эффективность работы компьютера будет близка к нулю. Основная идея данного проекта состоит в том, что свойства самих алгоритмов никак не зависят от вычислительных систем, существующих сейчас или будущих. Иными словами, детальное описание машинно-независимых свойств алгоритма нужно сделать лишь один раз, после чего оно может быть многократно использовано при реализации данного алгоритма в различных программно-аппаратных средах. Не менее важна и вторая, машинно-зависимая часть данного исследования, которая посвящена описанию особенностей программной реализации алгоритмов с учетом конкретных программно-аппаратных компьютерных платформ. Результатом проекта, которому посвящена данная статья, является открытая энциклопедия AlgoWiki по свойствам алгоритмов и особенностям их реализации для различных компьютерных систем. Умение эффективно работать со свойствами алгоритмов (выделять, описывать, анализировать, интерпретировать) станет широко востребованным уже через несколько лет, что будет верно как для экзафлопсных суперкомпьютерных систем высшего диапазона производительности, так и для всех других компьютерных платформ: от серверных до мобильных.

Автор

Вл.В. Воеводин

Библиографические ссылки

  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).

Загрузки

Опубликован

05-03-2015

Как цитировать

Воеводин В. Открытая энциклопедия свойств алгоритмов AlgoWiki: от мобильных платформ до экзафлопсных суперкомпьютерных систем // Вычислительные методы и программирование. 2015. 16. 99-111. doi 10.26089/NumMet.v16r111

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения