Структура алгоритмов - глобальный вызов для вычислительных наук

Общеизвестно, что компьютерный мир меняется очень быстро и все устройства, от мобильных телефонов и персональных компьютеров до суперкомпьютеров высшего диапазона производительности, становятся параллельными. В то же время полное использование всех тех возможностей, которые предоставляет современная компьютерная техника, является глобальным вызовом, серьезно влияющим на всю вычислительную практику. Использование потенциала современных вычислительных систем и распределенных вычислительных сред требует новых знаний, умений и навыков, где одно из самых существенных мест занимает глубокое понимание ключевых свойств параллельных алгоритмов. Какие это свойства? Что нужно уметь находить в существующих алгоритмах при появлении новой архитектуры компьютеров? Как обеспечить эффективную реализацию алгоритмов для конкретной платформы? Как упростить разработку параллельной программы для компьютеров с новой архитектурой? По- добные вопросы и будут рассматриваться в докладе.

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

Первая часть описывает собственно алгоритмы и их свойства. Вторая часть посвящена множеству вопросов их реализации на различных платформах. Если первая часть обращает внимание на ключевые теоретические свойства алгоритмов, то вторая делает акцент на практических нюансах. Такое разделение сделано осознанно, чтобы отделить машинно-независимые свойства алгоритмов, определяющие потенциал и качество их реализации на параллельных вычислительных платформах, от большого числа тонких моментов, возникающих как в процессе программной реализации, так и в процессе выполнения программ.

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

Подобный подход успешно опробован в рамках открытой энциклопедии свойств алгоритмов и программ AlgoWiki:

Structure of algorithms as a global challenge for computational sciences

V. V. Voevodin

Lomonosov Moscow State University; 1, Leninskie Gory, Moscow, 119991, Russia

The computing world is changing and all devices – from mobile phones and personal computers to high-performance supercomputers – are becoming parallel. At the same time, the efficient usage of all the opportunities offered by modern computing systems represents a global challenge. Using full potential of parallel computing systems and distributed computing resources requires new knowledge, skills and abilities, where one of the main roles belongs to understanding of key properties of parallel algorithms. What are these properties? What should be discovered and expressed explicitly in existing algorithms when a new parallel architecture appears? How to ensure efficient implementation of an algorithm on a particular parallel computing platform? All these as well as many other issues will be addressed in the talk.

The idea that we use in educational practice at the university is to split a description of an algorithm into two parts. This helps us to explain what a good parallel algorithm is and what is important for its efficient implementation. The first part describes algorithms and their properties.

The second part is dedicated to describing particular aspects of their implementation on various computing platforms. The first part draws attention to the key theoretical properties, and the second part puts emphasis on the aspects fundamentally important on practice. This division is made intentionally to highlight the machineindependent properties of algorithms which determine their potential and the quality of their implementations on parallel computing systems, and to describe them separately from a number of issues related to the subsequent stages of programming and executing the resulting programs. In addition to the classical algorithm properties such as serial complexity, we have to explain concepts such as parallel complexity, parallel structure, determinacy, data locality, performance and scalability estimates, communication profiles for specific implementations, and many others aspects.

This approach was successfully implemented as an open encyclopedia AlgoWiki, which is available for the computational community at