Эффективность распараллеливания

Естественно, что, используя параллельную систему с p вычислительными уст­ройствами, пользователь ожидает получить ускорение своей программы в p раз по сравнению с последовательным вариантом. Но действительность практически всегда оказывается далека от идеала.

Предположим, что структура информационных зависимостей программы опре­делена (что в общем случае является весьма непростой задачей), и доля опера­ций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по времени выполнения последовательной программы). Крайние случаи в значениях f соот­ветствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из p процессоров при данном значении f, можно воспользоваться законом Амдала:

Например, если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа ис­пользуемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0). Отсюда можно сделать вывод, что не любая программа может быть эффективно распараллелена. Для того чтобы это было возможно, необходимо, чтобы доля информационно независи­мых операций была очень большой. В принципе, это не должно отпугивать от параллельного программирования, потому что, как показывает практика, боль­шинство вычислительных алгоритмов устроено в этом смысле достаточно хо­рошим образом.

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

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

Таким образом, заставить параллельную вычислительную систему или супер­ЭВМ работать с максимальной эффективностью на конкретной программе - это задача не из простых, поскольку необходимо тщательное согласование струк­туры программ и алгоритмов с особенностями архитектуры параллельных вычислительных систем.

Задание 1.

Составить алгоритм решения систем линейных алгебраических уравнений с квадратной невырожденной матрицей методом Гаусса с использованием языков Си++ и MPI

Метод Гаусса решения систем линейных алгебраических уравнений является достаточно простым, и в то же время содержательной с точки зре­ния распараллеливания. На этом примере можно пройти все основные этапы про­цесса разработки параллельных алгоритмов и встретиться со многими подстере­гающими на этом пути трудностями.

Предлагается следующая последовательность действий по написанию и опти­мизации программы (в общем случае, не обязательная при создании параллель­ной программы):

• математическая постановка задачи, запись в формульном виде;

• построение вычислительного алгоритма;

• создание и оптимизация последовательной программы;

• исследование ресурса параллелизма программы и выбор метода распа­раллеливания;

• написание "какой-то" параллельной программы с использованием любых конструкций любых технологий параллельного программирования;

• оптимизация параллельной структуры программы, выбор наиболее под­ходящих конструкций, возможно, принятие другого решения по методу распараллеливания;

• дополнительная оптимизация программы, связанная, например, с эконо­мией памяти или другими требованиями со стороны аппаратуры или про­граммного обеспечения.

Технология MPI

Наиболее распространенной технологией программирования параллельных компьютеров с распределенной памятью в настоящее время является MPI. Ос­новным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии — Message Passing Interface. Стандарт MPI фиксирует интерфейс, который должна соблюдать как система программирования MPI на каждой вы­числительной системе, так и пользователь при создании своих программ. Со­временные реализации, чаще всего, соответствуют стандарту MPI версии 1.1. В 1997—1998 годах появился стандарт MPI-2.0, значительно расширивший функ­циональность предыдущей версии.

MPI поддерживает работу с языками Си и Фортран. В данном пособии все при­меры и описания всех функций будут даны с использованием языка Си. Однако это совершенно не является принципиальным, поскольку основные идеи MPI и правила оформления отдельных конструкций для этих языков во многом схо­жи. Полная версия интерфейса содержит описание более 120 функций. Наша задача — объяснить идею технологии и помочь освоить необходимые на прак­тике компоненты. Более подробно об интерфейсе MPI можно почитать на стра­нице http://parallel.ru/tech/tech_dev/mpi.html.

Стандарт MPI-1.1. включает следующие основные группы функций:

Обмены типа точка-точка

Коллективные обмены

Контексты, группы и коммуникаторы

Топологии процессов

Стандарт MPI-2.0. Данный документ содержит уточнения, привязки к языку C++ и расширения стандарта MPI 1.1, введенные в версиях 1.2 и 2.0.

Стандарт MPI-2: Extensions to the Message-Passing Interface включает следующие основные группы функций:

Динамическое порождение процессов и управление процессами

Односторонние коммуникации

Параллельный Ввод/Вывод

Интерфейс поддерживает создание параллельных программ в стиле MIMD, что подразумевает объединение процессов с различными исходными текстами. Од­нако на практике программисты гораздо чаще используют SPMD-модель, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с нитями.

Обзор MPI

Что такое MPI?

MPI - это библиотека передачи сообщений, собрание функций на C/C++ (или подпрограмм в Фортране, которые, зная MPI для C/C++, легко изучить самостоятельно), облегчающих коммуникацию (обмен данными и синхронизацию задач) между процессами параллельной программы с распределенной памятью . Акроним (сокращение по первым буквам) установлен для Message Passing Interface (интерфейс передачи сообщений). MPI является на данный момент фактическим стандартом и самой развитой переносимой библиотекой параллельного программирования с передачей сообщений.

MPI не является формальным стандартом, подобным тем, что выпускают организации стандартизации, такие как Госкомстандарт РФ, ANSI или ISO. Вместо этого, он является "стандартом по консенсусу", спроектированном на открытом форуме, который включал крупных поставщиков компьютеров, исследователей, разработчиков библиотек программ и пользователей, представляющих более 40 организаций. Такое широкое участие в его развитии гарантировало быстрое превращение MPI в широко используемый стандарт для написания параллельных программ передачи сообщений.

"Стандарт" MPI был введен MPI - форумом в мае 1994 и обновлен в июне 1995. Документ, который определяет его, озаглавлен "MPI: A Message-Passing Standard", опубликован университетом Тэннеси и доступен по World Wide Web в Argonne National Lab. Если вы еще не знакомы с MPI, то, возможно, вы захотите распечатать перевод этого документа на русский язык и использовать его для получения справок о синтаксисе функций MPI, которые данный курс не может охватить полностью за исключением иллюстрации частных случаев.

MPI 2 производит расширения к стандарту MPI передачи сообщений. Эти усилия не изменили MPI; они расширили применение MPI на следующие сферы:

Управление динамичекими процессами

Ассимметричные операции

Параллельный ввод/вывод (I/O)

Привязка к C++ и ФОРТРАН 90

Внешние интерфейсы

Расширенные коллективные коммуникации

Расширения реального времени

Другие сферы

MPI 2 был завершен в июле 1997.

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

Стандартизация

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

Переносимость

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

MPI позволяет вам писать портативные программы, которые все еще используют в своих интересах спецификации аппаратных средств ЭВМ и программного обеспечения, предлагаемого поставщиками. К счастью, эти заботы в основном берут на себя запросы MPI, потому что конструкторы настроили эти вызовы на основные аппаратные средства ЭВМ и окружающую среду программного обеспечения.

Эффективность работы

Множество внешних инструментов, включая PVM, Express и P4, пытались обеспечить стандартизованное окружение для параллельных вычислений. тем не менее, ни одна из этих попыток не показала такой высокой эффективности работы, как MPI.