ВКР: Предсказание коммуникационных расходов параллельных программ
Описание
Московский государственный университет имени М.В.Ломоносова, факультет Вычислительной математики и кибернетики,
кафедра системного программирования
ДИПЛОМНАЯ РАБОТА
Тема: “Предсказание коммуникационных расходов параллельных программ”
Научный руководитель:
профессор д.ф.-м.н.
Крюков Виктор Алексеевич
Содержание
Параллельное программирование. 3
Новая схема работы Предиктора. 21
Введение
Параллельное программирование
На сегодняшний день параллельные вычислительные системы дают наибольшую производительность в решении задач, требующих большого количества вычислений, часто на больших объемах данных. Это достигается за счет распределения вычислений по большому числу одновременно работающих процессоров, каждый из которых решает свою часть задачи. По архитектуре параллельные вычислительные системы делятся на многопроцессорные системы с общей памятью и системы с распределенной памятью.
Системы с общей памятью обычно выглядят как многопроцессорный вычислительный комплекс, в котором все процессоры обращаются к одному единому для всех блоку оперативной памяти. Такой подход минимизирует время обменов данными между процессорами, но, из-за сложности организации бесконфликтного доступа к общей памяти, ограничивает количество процессоров. Практика показывает, что фактически количество процессоров в такой системе ограничено 32-мя. При большем числе процессоров накладные расходы обеспечения корректной работы с общей памятью сводят на нет увеличение производительности.
Успешной альтернативой такому подходу являются многопроцессорные системы с распределенной памятью, где у каждого процессора есть в распоряжении своя оперативная память, а обмены данными между процессорами осуществляются при помощи коммуникационной системы – обычно специально организованной высокопроизводительной локальной сети. Такой подход позволяет использовать в качестве узлов распределенной системы обычные персональные компьютеры (т.е. не создавать специальную техническую базу), а также легко наращивать число задействованных процессоров. В настоящее время существуют распределенные вычислительные системы с числом процессоров, превышающим 10000.
Программа, решающая задачу на параллельной вычислительной системе, называется параллельной программой. Работа параллельной программы представляет собой одновременную работу копий программы на всех процессорах вычислительной системы (или на заданном подмножестве процессоров). В зависимости от логики работы параллельной программы, их делят на несколько классов:
-SIMD (Single Instruction, Multiple Data) – каждый процессор обрабатывает свою часть данных, но все они действуют по одному алгоритму (один поток выполнения).
-MIMD (Multiple Instruction, Multiple Data) – каждый процессор обрабатывает свою часть данных, но действия могут быть разными для разных процессоров (несколько потоков выполнения).
-MISD (Multiple Instruction, Single Data) – разные потоки выполнения над одними данными. Фактически, никогда не реализовывался.
Существует несколько подходов к созданию параллельных программ. Они различаются используемыми инструментами, а главное - принципами распараллеливания программы, или моделью параллельного программирования.
Модель передачи сообщений. MPI.
В этой модели копии параллельной программы, запускаемые на разных процессорах вычислительной системы, взаимодействуют друг с другом посредством передачи сообщений. При этом определение всей логики работы каждого процесса (т.е. какие данные и как обрабатывать, с какими процессами связываться и какие сообщения посылать) лежит целиком на плечах программиста. Самая распространенная реализация модели передачи сообщений – это стандарт MPI (Message Passing Interface), описывающий ряд функций для обмена данными между отдельными процессами или внутри группы процессов (коллективные операции). Стандарт MPI описывает набор функций, их синтаксис для языков Си и Фортран и общую семантику их работы. В настоящее время существует несколько реализаций этого стандарта в виде библиотек функций для указанных языков на различных платформах. Внутренние алгоритмы их работы (например, способ организации коллективных обменов) могут отличаться. Основные достоинства MPI перед другими коммуникационными библиотеками:
- Общий интерфейс для разных языков (Фортран, Си, Си++);
- Предоставление возможностей для асинхронных обменов (совмещения по времени обменов сообщениями и вычислений);
- Наличие различных режимов передачи сообщений, позволяющих избежать лишнего копирования информации для буферизации. Как следствие – высокая производительность.
- Широкий набор коллективных операций (например, широковещательная рассылка информации, сбор информации с разных процессоров), допускающих гораздо более эффективную реализацию, чем использование соответствующей последовательности пересылок точка-точка;
- Удобная адресация: каждый процесс имеет свой номер (целое число от 0 до N-1, где N - число процессоров). Это делает программу переносимой и независимой от способа адресации в сети.
- Возможность задания типа передаваемой информации, что позволяет обеспечить ее автоматическое преобразование в случае различий в представлении данных на разных узлах системы.
Модель параллелизма по данным. HPF.
В этой модели программист лишь указывает то, каким образом данные должны быть распределены по процессорам, а компилятор, используя эту информацию, преобразует последовательную программу в параллельную либо в модели передачи сообщений, либо в модели с общей памятью. При этом работа распределяется по правилу собственных вычислений: каждый процессор выполняет только те вычисления, которые относятся к данным, распределенным на этот процессор.
Модель параллелизма по данным имеет следующие достоинства.
- Поскольку большинство вычислительных задач характеризуется однотипными вычислениями на больших объемах данных, такие задачи легко распараллеливаются в рамках данной модели.
- Программисту не надо думать об организации взаимодействий и обменов между процессами, он пишет обычную последовательную программу с небольшими пометками для компилятора, который берет всю низкоуровневую работу на себя.
- Улучшение локальности программы – т.к. с ростом числа процессоров на каждый процессор приходится все меньший объем данных, а сами данные расположены компактно, то увеличивается эффективность кэша процессора, что еще больше улучшает производительность.
Пример реализации данной модели – язык HPF (High Performance Fortran).
Модель параллелизма по управлению. OpenMP.
Данная модель представляет собой некоторую автоматизацию создания параллельной программы для систем с общей памятью. Программист не пишет код для отдельных нитей, а лишь указывает компилятору на циклы и секции программы, которые можно распараллелить. Компилятор берет на себя работу по организации параллельных нитей и распределению между ними витков цикла.
Пример реализации такой модели – язык OpenMP. Это интерфейс прикладной программы, расширяющий последовательный язык программирования (Си, Фортран) набором директив компилятора, вызовов функций библиотеки поддержки выполнения и переменных среды.
Модель параллелизма по данным и управлению. DVM.
В данной модели программист также пишет обычную последовательную программу, но теперь он может указать компилятору, какие данные и какие вычисления распределены по процессорам. В рамках данной модели в Институте прикладной математики им М.В. Келдыша РАН была создана система разработки параллельных программ DVM (Distributed Virtual Machine или Distributed Virtual Memory). Она включает в себя расширения языков Си и Фортран C-DVM и Fortran-DVM, где специальные директивы компилятору оформлены в виде макросов, прозрачных для обычных компиляторов. Т.е. программа на языке C-DVM или Fortran-DVM продолжает компилироваться обычным компилятором и работать как простая последовательная программа. Но будучи пропущенной через специальный транслятор, программа с DVM-директивами превращается в программу, использующую функции библиотеки поддержки Lib-DVM, которые используют MPI для обменов данными между процессами. Причем распределение данных и вычислений по процессорам производится функциями runtime-системы динамически. Поэтому скомпилированная DVM-программа может без перекомпиляции работать на произвольном числе процессоров.
Предсказание
Важной задачей в области параллельного программирования является задача предсказания времени выполнения параллельной программы. Имея возможность такого предсказания, можно исследовать характеристики еще не созданных параллельных вычислительных систем и определять их слабые места, оценивать необходимость приобретения той или иной вычислительной системы, изучать поведение и характеристики выполнения задачи на разных конфигурациях (в частности, определить оптимальное число процессоров для данной задачи и т.д.), предсказать эффективность параллельной программы без запуска на реальной параллельной машине и т.д. Однако, не каждая система параллельного программирования, не каждая модель параллельного программирования позволяет осуществить такое предсказание.
Допустим, мы имеем трассу работы параллельной программы на рабочей станции (одном процессоре) или на некоторой параллельной системе и хотим предсказать время выполнения нашей программы на некоторой другой системе.
Модель передачи сообщений. MPI.
В этой модели поведение каждого процесса существенно зависит от общего числа процессов и ранга (номера) данного процесса. Поэтому, не имея информации о внутренней логике программы, предсказать ее поведение не представляется возможным. Подход, который может быть использован – запуск программы на некоторой эмуляции нужной системы – плох тем, что требует произведения вычислений самой программы, т.е. время, необходимое для получения предсказания, будет сопоставимо (или даже больше), чем время выполнения программы на одном процессоре. Если задача достаточно большая (а именно с такими обычно и приходится работать), то это время становится неприемлемо большим.
Модель параллелизма по данным. HPF.
В данной модели поведение каждого процесса зависит от системы поддержки, принимающей решения на основе числа процессов и номера текущего. Поскольку на другом числе процессоров система поддержки HPF примет другие решения, неизвестные заранее, предсказать поведение программы не получится.
Модель параллелизма по управлению. OpenMP.
Поскольку OpenMP применяется на системах с общей памятью, где существуют сложные алгоритмы работы с кэшем и обеспечения консистентности, скорость работы сильно зависит от числа процессоров. Предсказание таких эффектов – слишком сложная и малоизученная задача, поэтому предсказание времени выполнения OpenMP программ также представляется затрудненным.
Модель параллелизма по данным и управлению. DVM.
В отличие от предыдущих моделей, система DVM специально была создана таким образом, чтобы DVM-программы легко могли быть запущены на разных количествах процессоров. Всю работу по распределению данных и вычислений выполняют функции системы поддержки, поэтому обычно в DVM-программе нет разветвлений в зависимости
Файлы условия, демо
Характеристики ВКР
Список файлов
- Предсказание коммуникационных расходов параллельных программ.doc 205 Kb
anhyeuem
zzyxel
