Московский государственный университет им.М.В.Ломоносова Институт вычислительной математики РАН www.parallel.ru Воеводин В.В., Воеводин Вл.В. СУПЕРВЫЧИСЛЕНИЯ: - презентация

1 Московский государственный университет им.М.В.Ломоносова Институт вычислительной математики РАН Воеводин В.В., Воеводин Вл.В. СУПЕРВЫЧИСЛЕНИЯ: средства, теория, образование

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

3 Увеличение производительности ЭВМ - за счет чего? EDSAC, 1949 год HP Superdome, 2001 год такт: 2*10 -6 с 1.5* *10 -9 с произв.: 10 2 оп/с 1.9* *10 11 оп/c

4 ASCI White - первое место в Top процессора Power3 (512 * 16) Оперативная память - 4Тбайта Дисковый массив - 160Тбайт Пиковая производительность - более 12Tflops flops - floating operations per second M , G , T

5 Системы параллельного программирования Зарубежные: Linda, PVM, MPI, High Performance Fortran, OpenMP... Отечественные: НОРМА, DVM, Т-система, mpC... Все системы в той или иной мере требуют от пользователя дополнительную информацию

6 Откуда брать дополнительную информацию? Образование и штатное программное обеспечение слабо поддерживают процессы ее получения.

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

8 Результаты оптимизации программы TRFD из пакета PERFECT CLUB BENCHMARK на суперкомпьютерах CRAY Baseline - результаты, полученные с помощью штатного компилятора Manual opt. - результаты, полученные с помощью ручной оптимизации специалистами высокого класса V-Ray opt. - результаты, полученные на основе информации, выданной V-Ray system

9 Пользователь: почему? A ijk = A i-1jk + B jk + B jk, i=1,40; j=1,40; k=1,1000 do k = 1, 1000 do j = 1, 40 do i = 1, 40 A(i,j,k) = A(i-1,j,k)+B(j,k)+B(j,k) Производительность: 20 Mflops на Cray Y-MP C90

10 Пользователь: почему? A ijk = A i-1jk + B jk + B jk, i=1,40; j=1,40; k=1,1000 do i = 1, 40, 2 do j = 1, 40 do k = 1, 1000 A(i,j,k) = A(i-1,j,k)+2*B(j,k) A(i+1,j,k) = A(i,j,k)+2*B(j,k) Производительность: 700 Mflops на Cray Y-MP C90

11 DO i = 1, n DO j = 1, n U( i + j ) = U( 2*n – i – j + 1)*q + p EndDO Простой пример...

12 DO i = 1, n DO j = 1, n – i U( i + j ) = U( 2*n – i – j + 1)*q + p End DO DO j = n – i + 1, n U( i + j ) = U( 2*n – i – j + 1)*q + p End DO Простой пример...

13

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

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

16

17 DO i = 1,n DO j = 1,n-i+1 A(I,J) = … B (I,J) … B(I,J) = … A (I,J) … ENDDO ENDDO Л.Лампорт А.П.Ершов

18 DO i = 1,n DO j = 1,n-i+1 A(I,J) = … B (I,J-1) … B(I,J) = … A (I,J) … ENDDO ENDDO Л.Лампорт А.П.Ершов

19 S = 0 DO i = 1,n S = S + A(I) ENDDO Л.Лампорт А.П.Ершов

20 Базовая математическая задача Для любого вектора I Ω N построить множество векторов J i Ω i N, удовлетворяющих уравнениям: p i N (J i ) = q N (I), и на этих множествах найти вектор J = J(I, N), лексикографически ближайший к I снизу. Все объекты зависят от вектора внешних переменных N, который на момент решения базовой задачи неизвестен. Решение необходимо находить точно и в явном виде.

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

22 Информационная структура алгоритмов Для широкого класса алгоритмов и программ разработаны эффективные методы нахождения всех графов зависимостей. Графы точно описываются конечными наборами простых функций. Используя явное представление графов, разработаны эффективные методы их исследования. Теперь об этих графах можно узнать практически все. Построена первая очередь автономной системы V-Ray system для обнаружения параллелизма в больших программных комплексах. Обнаружены многочисленные междисциплинарные связи.

23 Близкие проблемы Быстрое вычисление градиента и производной Быстрое восстановление линейного функционала Анализ влияния ошибок округления Декомпозиция алгоритмов Восстановление математических формул Обнаружение узких мест алгоритма (по памяти, точности и т.п.) Разработка параллельных численных методов Разработка переносимого программного обеспечения Использование распределенной и иерархической памяти Выбор оптимальной архитектуры компьютера Построение систолических массивов Разработка параллелизующих компиляторов и многое другое

24 Гипотеза Типовых информационных структур алгоритмов в конкретных областях немного Практика подтверждает гипотезу

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

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