Параллельное программирование для ресурсоёмких задач численного моделирования в физике В.О. Милицин, Д.Н. Янышев, И.А. Буткарев Центр компьютерной физики Кафедра общей физики и волновых процессов Международный лазерный центр

2Физический факультет МГУ им М.В.Ломоносова

3 Содержание курса Введение Архитектура высокопроизводительных систем Особенности параллельных вычислений Работа с кластером; операционная система Linux Технология OpenMP Интерфейс передачи сообщений MPI Моделирование физических задач средствами OpenMP и MPI

4 Структура курса лекции практические занятия самостоятельные задания ЗАЧЕТ Физический факультет МГУ им М.В.Ломоносова

5 Развитие инструментов для научного процесса Физический факультет МГУ им М.В.Ломоносова 1. Наблюдение2. Гипотеза 4. Утверждение 3. Прогноз

6 Области применения суперкомпьютеров Научно-исследовательские институты Университеты Геофизика Биология Метеорология Финансовая область Энергетика Наукоемкие отрасли промышленности Медицина Генетика Геологоразведка Контроль за окружающей средой Физический факультет МГУ им М.В.Ломоносова

7 Пример проблемы решаемой с помощью параллельного программирования Car Crash Simulation: Поверхность машины моделируется как считанное количество треугольных элементов. Моделируется позиция каждого элемента во времени с учетом сил действующих на него и его свойств. Каждый элемент взаимодействует только с соседними элементами Физический факультет МГУ им М.В.Ломоносова

8 Сетка конечных элементов Физический факультет МГУ им М.В.Ломоносова

9 Архитектура ЭВМ Архитектура компьютера Организация компьютера Схема компьютера Физический факультет МГУ им М.В.Ломоносова

10 Архитектура фон Неймана Программа хранится в компьютере Программа во время выполнения и необходимые для её работы данные находятся в оперативной памяти Имеется арифметико-логическое устройство, выполняющее арифметические и логические операции с данными Имеется устройство управления, которое интерпретирует команды, выбираемые из памяти, и выполняет их Устройства ввода и вывода используются для ввода программ и данных и для вывода результатов расчетов. Работают под управлением УУ Физический факультет МГУ им М.В.Ломоносова

11Физический факультет МГУ им М.В.Ломоносова Архитектура фон Неймана II ПАМЯТЬ УСТРОЙСТВО УПРАВЛЕНИЯ АРИФМЕТИКО- ЛОГИЧЕСКОЕ УСТРОЙСТВО ВВОДВЫВОД

12 Классификация Флинта Физический факультет МГУ им М.В.Ломоносова

13 SISD-компьютеры Физический факультет МГУ им М.В.Ломоносова

14 SIMD-компьютеры Физический факультет МГУ им М.В.Ломоносова

15 MISD-компьютеры Физический факультет МГУ им М.В.Ломоносова

16 MIMD-компьютеры Физический факультет МГУ им М.В.Ломоносова

17 Компоненты компьютера Центральный процессор и оперативная память ядро системы Внешняя память и устройства ввода/вывода «периферия» Коммуникации между компонентами системы осуществляется посредством шин Физический факультет МГУ им М.В.Ломоносова

18 Схема компьютера Физический факультет МГУ им М.В.Ломоносова

19Физический факультет МГУ им М.В.Ломоносова In June 2010, 2 systems appeared in the TOP500 list.Rank SystemProcsMemory(GB)Rmax (GFlops)Rpeak (GFlops)Vendor 13 LomonosovT-Platforms T-Blade2, Xeon GHz, Infiniband QDR T-Platforms 121 SKIF MSUT-Platforms T60, Intel Quadcore 3Ghz, Infiniband DDR SKIF/T-Platforms

20 Технологии параллельного программирования Все, что начинается хорошо, кончается плохо. Все, что начинается плохо, кончается еще хуже. Из законов Мерфи Физический факультет МГУ им М.В.Ломоносова

21 Особенности программирования параллельных вычислений Физический факультет МГУ им М.В.Ломоносова Модель программирования Алгоритм Информационный граф Вход Выход (n, s) (v, d)

22 Примеры алгоритмов Вход Выход Вход Выход Последовательный Параллельный Физический факультет МГУ им М.В.Ломоносова

23 Основные черты последовательной модели Применение стандартных языков программирования Хорошая переносимость программ Невысокая производительность Физический факультет МГУ им М.В.Ломоносова

24 Основные черты параллельной модели Высокая производительность программ Применение специальных приёмов программирования Более высокая трудоёмкость программирования Проблемы с переносимостью программ Физический факультет МГУ им М.В.Ломоносова

25 Фундаментальные требования к параллельным программам Параллелизм Локальность Масштабируемость Детерминизм Физический факультет МГУ им М.В.Ломоносова

26 Параллелизм Данных Задач Физический факультет МГУ им М.В.Ломоносова

27 Параллелизм данных Основные особенности подхода: Обработкой данных управляет одна программа Пространство имен является глобальным Слабая синхронизация вычислений на параллельных процессорах Параллельные операции над элементами массива выполняются одновременно на всех доступных процессорах Физический факультет МГУ им М.В.Ломоносова

28 Параллелизм задач Повышенная трудоёмкость разработки и отладки программы Программист отвечает за равномерную и сбалансированную загрузку процессоров Минимизация обмена данными между задачами Возникновение конфликтов Физический факультет МГУ им М.В.Ломоносова

29 Модель задача/канал задача асинхронная передача синхронная передача Физический факультет МГУ им М.В.Ломоносова

30 Параллелизм задач Большая гибкостьБольшая свобода Физический факультет МГУ им М.В.Ломоносова Максимальное быстродействие

31 Масштабируемость Независимость результата выполнения параллельной программы от числа процессоров. Физический факультет МГУ им М.В.Ломоносова

32 Детерминизм Физический факультет МГУ им М.В.Ломоносова

33 Закон Амдала - один процессор - N процессоров - коэффициент ускорения выполнения программы Физический факультет МГУ им М.В.Ломоносова

34 Закон Амдала II коэффициент ускорения выполнения программы S - доля последовательной части P - доля параллельной части N - число независимых ветвей/процессоров Физический факультет МГУ им М.В.Ломоносова

35 Две парадигмы параллельного программирования Равномерная загрузка процессоров Эффективная организация обмена информацией между задачами Физический факультет МГУ им М.В.Ломоносова

36 Базовый набор операций Операции управления данными Операции над массивами в целом, а также их фрагментами Условные операции Операции приведения Операции сдвига Операции сканирования Операции, связанные с пересылкой данных Физический факультет МГУ им М.В.Ломоносова

37 Управление данными Физический факультет МГУ им М.В.Ломоносова

38 Операции над массивами Физический факультет МГУ им М.В.Ломоносова

39 Условные операции Физический факультет МГУ им М.В.Ломоносова

40 Операции приведения Физический факультет МГУ им М.В.Ломоносова

41 Операции сдвига Физический факультет МГУ им М.В.Ломоносова

42 Операции сканирования Физический факультет МГУ им М.В.Ломоносова

43 Операции пересылки данных Физический факультет МГУ им М.В.Ломоносова

44 Разработка параллельного алгоритма проблема декомпозиция коммуникации укрупнение планирование вычислений подзадачи процессоры Физический факультет МГУ им М.В.Ломоносова

45 Декомпозиция (сегментирование) Метод декомпозиции данных Метод функциональной декомпозиции Физический факультет МГУ им М.В.Ломоносова

46 Рекомендации по декомпозиции Количество подзадач должно на порядок превосходить количество процессоров Следует избегать лишних вычислений и пересылок данных Подзадачи должны быть примерно одного размера С увеличением объема задачи количество подзадач увеличивалось Физический факультет МГУ им М.В.Ломоносова

47 Зернистость мелкозернистаясреднеблочныйкрупноблочный < 20 ~ 500 независимые программы Через разделяемые переменныеЧерез сообщения Физический факультет МГУ им М.В.Ломоносова

48 Независимость частей программы Независимость по данным Независимость по управлению Независимость по ресурсам do k = 1, m if (a[k] < c) then a[k] = 1 endif enddo do k = 1, m if (a[k-1] < c) then a[k] = 1 endif enddo Физический факультет МГУ им М.В.Ломоносова

49 Проектирование коммуникаций Локальные Глобальные Структурированные Неструктурированные Статические Динамические Синхронные Асинхронные Физический факультет МГУ им М.В.Ломоносова

50 Рекомендации по проектированию коммуникаций Количество коммуникаций у подзадач должно быть примерно одинаковым Желательно использовать локальные коммуникации Коммуникации должны быть, по возможности, параллельными Физический факультет МГУ им М.В.Ломоносова

51 Тупиковые ситуации Физический факультет МГУ им М.В.Ломоносова

52 Реализация обмена сообщениями MPI (Message Passing Interface) PVM (Parallel Virtual Machine) RPC (Remote Procedure Control) CORBA (Common Object Request Broker Architecture) DCOM (Distributed Component Object Model) Физический факультет МГУ им М.В.Ломоносова

53 Укрупнение Физический факультет МГУ им М.В.Ломоносова

54 Укрупнение Снижение затрат на коммуникации При необходимом дублировании вычислений или данных не должно быть потерь в производительности или масштабируемости Результирующие задачи должны иметь примерно одинаковую трудоёмкость Сохранение масштабируемости Сохранение возможности параллельного выполнения Снижение стоимости и трудоёмкости разработки Физический факультет МГУ им М.В.Ломоносова

55 Планирование вычислений Стратегия управления хозяин/работник Физический факультет МГУ им М.В.Ломоносова

56 Характеристики быстродействия Факторы влияющие на производительность Технология выполнения аппаратной части Архитектура вычислительной системы Методы управления ресурсами Эффективность параллельного алгоритма Особенности структуры данных Эффективность языка программирования Квалификация программиста Эффективность транслятора

57 Последовательность действий Разработка алгоритма Предварительный анализ быстродействия программы Оценка трудоёмкости и целесообразности разработки параллельной программы Кодирование Физический факультет МГУ им М.В.Ломоносова

58 Список литературы: Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. -СПб.: Петербург, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. -СПб: BHV, А.С.Антонов "Параллельное программирование с использованием технологии MPI", издательстве Московского университета 2004 А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство ООО «ЦВВР», 2003, 208 с Калиткин Н.Н. Численные методы. - М.: Наука, с В. Д. Корнеев Параллельное программирование в MPI, издательство "Регулярная и хаотическая динамика" 2003 г., стр. Грегори Р. Эндрюс Основы многопоточного, параллельного и распределенного программирования, издательство "Вильямс" 2003 г стр. Богачев К.Ю. Основы параллельного программирования издательство "Бином. Лаборатория знаний" 2003 г стр. Воеводин В.В. Параллельные структуры алгоритмов и программ. - М.: ОВМ АН СССР, с. Физический факультет МГУ им М.В.Ломоносова

59Физический факультет МГУ им М.В.Ломоносова