Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В.. Программирование для многопроцессорных систем в стандарте MPI -. Организация вычислений в многопроцессорных системах
 Скачать 1.61 Mb.
|
|
Глава 1. ОРГАНИЗАЦИЯ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ В главе 1 приведен обзор методов организации вычислений в со- временных многопроцессорных системах, получивших в последние годы широкое распространение, рассматривается классификация сис- тем, эффективность параллельных вычислений, техническая реализа- ция многопроцессорных систем и систем передачи данных, методы программирования и, наконец, делается переход к основному объекту настоящего издания – системе программирования в стандарте MPI. 1.1. КЛАССИФИКАЦИЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ Наиболее известная классификация параллельных ЭВМ предло- жена Флинном [13] и отражает форму реализуемого ЭВМ паралле- лизма. Основными понятиями классификации являются "поток ко- манд" и "поток данных". Под потоком команд упрощенно понимают последовательность команд одной программы. Поток данных − это последовательность данных, обрабатываемых одной программой. Согласно этой классификации имеется четыре больших класса ЭВМ: 1) ОКОД (одиночный поток команд − одиночный поток данных) или SISD (Single Instruction − Single Data). Это последовательные ЭВМ, в которых выполняется единственная программа, т. е. имеется только один счетчик команд. 2) ОКМД (одиночный поток команд − множественный поток данных) или SIMD (Single Instruction – Multiple Data). В таких ЭВМ выпол- няется единственная программа, но каждая команда обрабатывает массив данных. Это соответствует векторной форме параллелизма. 3) МКОД (множественный поток команд − одиночный поток данных) или MISD (Multiple Instruction − Single Data). Подразумевается, что в данном классе несколько команд одновременно работает с одним элементом данных, однако эта позиция классификации Флинна на практике не нашла применения. 4) МКМД (множественный поток команд − множественный поток данных) или MIMD (Multiple Instruction − Multiple Data). В таких ЭВМ одновременно и независимо друг от друга выполняется не- сколько программных ветвей, в определенные промежутки време- ни обменивающихся данными. Такие системы обычно называют 10 многопроцессорными. Далее будут рассматриваться только много- процессорные системы. Классы многопроцессорных систем. В основе МКМД-ЭВМ ле- жит традиционная последовательная организация программы, расши- ренная добавлением специальных средств для указания независимых фрагментов, которые можно выполнять параллельно. Параллельно- последовательная программа привычна для пользователя и позволяет относительно просто собирать параллельную программу из обычных последовательных программ. МКМД-ЭВМ имеет две разновидности: ЭВМ с разделяемой (об- щей) и распределенной(индивидуальной) памятью. Структура этих ЭВМ представлена на рис. 1.1. а б Рис. 1.1. Структура ЭВМ с разделяемой (а) и индивидуальной (б) памятью. Здесь: П – процессор, ИП − индивидуальная память. Главное различие между МКМД-ЭВМ с общей и индивидуальной памятью состоит в характере адресной системы. В машинах с разде- ляемой памятью адресное пространство всех процессоров является единым, следовательно, если в программах нескольких процессоров встречается одна и та же переменная Х, то эти процессоры будут об- ращаться в одну и ту же физическую ячейку общей памяти. Это вызы- вает как положительные, так и отрицательные последствия. Наличие общей памяти не требует физического перемещения дан- ных между взаимодействующими программами, которые параллельно выполняются в разных процессорах. Это упрощает программирование и исключает затраты времени на межпроцессорный обмен. Однако одновременное обращение нескольких процессоров к об- щим данным может привести к получению неверных результатов. Рассмотрим следующий пример. Пусть имеется система с разделяе- П П П Коммутатор Разделяемая память П П П ИП ИП ИП Коммутатор 11 мой памятью и двумя процессорами, каждый с одним регистром. Пусть в первом процессоре выполняется процесс L1, во втором – L2: L 1: ... X: = X + 1; ... L 2: ... X: = X + 1; ... Процессы выполняются асинхронно, используя общую перемен- ную X. При выполнении процессов возможно различное их взаимо- расположение во времени, например, возможны следующие две си- туации: L1 R1: = X; R1: = R1 + 1; X: = R1; ... (1.1) L2 R2: = X; R2: = R2 + 1; X:= R2; L1 R1: = X; R1: = R1 + 1; X: = R1; (1.2) L2 R2: = Х; R2:=R2+1; X: = R2; Пусть в начальный момент X = V. Тогда в случае (1.1) второй про- цессор производит чтение X до завершения всех операций в первом процессоре, поэтому X = V + 1. В случае (1.2) второй процессор читает X после завершения всех операций первым процессором, поэтому X = V + 2. Таким образом, ре- зультат зависит от взаиморасположения процессов во времени, что для асинхронных процессов определяется случайным образом. Чтобы исключить такие ситуации, необходимо ввести систему синхрониза- ции параллельных процессов (например, семафоры), что усложняет механизмы операционной системы. Поскольку при выполнении каждой команды процессорам необхо- димо обращаться в общую память, то требования к пропускной спо- собности коммутатора этой памяти чрезвычайно высоки, что ограни- чивает число процессоров в системах величиной 10...20. В системах с индивидуальной памятью (с обменом сообщениями) каждый процессор имеет независимое адресное пространство, и нали- чие одной и той же переменной X в программах разных процессоров приводит к обращению в физически разные ячейки памяти. Это вызы- вает физическое перемещение данных между взаимодействующими программами в разных процессорах, однако, поскольку основная часть обращений производится каждым процессором в собственную память, то требования к коммутатору ослабляются, и число процессо- ров в системах с распределенной памятью и коммутатором типа ги- перкуб может достигать нескольких сотен и даже тысяч. 12 1.2. СЕТЕВОЙ ЗАКОН АМДАЛА Закон Амдала. Одной из главных характеристик параллельных систем является ускорение R параллельной системы, которое опреде- ляется выражением: n T T R / 1 = , где T 1 − время решения задачи на однопроцессорной системе, а T n − время решения той же задачи на n − процессорной системе. Пусть W = W ск + W пр , где W − общее число операций в задаче, W пр − число операций, которые можно выполнять параллельно, а W cк − число скалярных (нераспараллеливаемых) операций. Обозначим также через t время выполнения одной операции. То- гда получаем известный закон Амдала [13]: a n n a a t n W W t W R пр ск 1 1 1 ) ( ⎯ ⎯ ⎯ → ⎯ ∞ → − + = ⋅ + ⋅ = (1.3) Здесь a = W ск /W − удельный вес скалярных операций. Закон Амдала определяет принципиально важные для параллель- ных вычислений положения: 1. Ускорение зависит от потенциального параллелизма задачи (вели- чина 1– а) и параметров аппаратуры (числа процессоров n). 2. Предельное ускорение определяется свойствами задачи. Пусть, например, a = 0,2 (что является реальным значением), тогда ускорение не может превосходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным паралле- лизмом задачи. Очевидной является чрезвычайно высокая чувстви- тельность ускорения к изменению величины а. Сетевой закон Амдала . Основной вариант закона Амдала не от- ражает потерь времени на межпроцессорный обмен сообщениями. Эти потери могут не только снизить ускорение вычислений, но и за- медлить вычисления по сравнению с однопроцессорным вариантом. Поэтому необходима некоторая модернизация выражения (1.3). Перепишем (1.3) следующим образом: c n a a t W t W n a a t W t n W W t W R c c c c пр ск c + − + = ⋅ ⋅ + − + = ⋅ + ⋅ + ⋅ = 1 1 1 1 ) ( . (1.4) 13 Здесь W c −количество передач данных, t c −время одной передачи данных. Выражение c n a a c R + − + = 1 1 (1.5) и являетсясетевым законом Амдала. Этот закон определяет следую- щие две особенности многопроцессорных вычислений: 1. Коэффициент сетевой деградации вычислений с: Т А c c c c t W t W c ⋅ = ⋅ ⋅ = , (1.6) определяет объем вычислений, приходящийся на одну передачу данных (по затратам времени). При этом с А определяет алгорит- мическую составляющую коэффициента деградации, обусловлен- ную свойствами алгоритма, а с Т − техническую составляющую, ко- торая зависит от соотношения технического быстродействия про- цессора и аппаратуры сети. Таким образом, для повышения скоро- сти вычислений следует воздействовать на обе составляющие ко- эффициента деградации. Для многих задач и сетей коэффициенты с А и с Т могут быть вычислены аналитически и заранее, хотя они определяются множеством факторов: алгоритмом задачи [14,15], размером данных, реализацией функций обмена библиотеки MPI, использованием разделяемой памяти и, конечно, техническими ха- рактеристиками коммуникационных сред и их протоколов. 2. Даже если задача обладает идеальным параллелизмом, сетевое ус- корение определяется величиной n c n c n c n R c ⎯ ⎯ ⎯ → ⎯ → ⋅ + = + = 0 1 1 1 (1.7) и увеличивается при уменьшении с. Следовательно, сетевой закон Амдала должен быть основой оптимальной разработки алгоритма и программирования задач, предназначенных для решения на мно- гопроцессорных ЭВМ. В некоторых случаях используется еще один параметр для изме- рения эффективности вычислений – коэффициент утилизации z: 1 0 1 1 ⎯ ⎯ ⎯ → ⎯ → ⋅ + = = c n c n R z c . (1.8) 14 Более подробно вопросы эффективности вычислений изложены в главе 12. 1.3. ТЕХНИЧЕСКАЯ РЕАЛИЗАЦИЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ Существующие параллельные вычислительные средства класса MIMD образуют три технических подкласса: симметричные мульти- процессоры (SMP), системы с массовым параллелизмом (МРР) и кла- стеры. В основе этой классификации лежит структурно- функциональный подход. Симметричные мультипроцессоры используют принцип разде- ляемой памяти. В этом случае система состоит из нескольких одно- родных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти с помощью общей шины или коммутатора. Аппаратно поддерживается когерентность кэшей. Наличие общей памяти сильно упрощает взаимодействие процессо- ров между собой, однако накладывает сильные ограничения на их число − не более 32 в реальных системах. Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel- платформ поддерживается Windows NT). Системы с массовым параллелизмом содержат множество про- цессоров (обычно RISC) c индивидуальной памятью в каждом из них (прямой доступ к памяти других узлов невозможен), коммуникацион- ный процессор или сетевой адаптер, иногда − жесткие диски и/или другие устройства ввода–вывода. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.). Общее число процессоров в реальных системах достигает не- скольких тысяч (ASCI Red, Blue Mountain). Полноценная операционная система может располагаться только на управляющей машине (на других узлах работает сильно урезанный вариант ОС), либо на каждом узле работает полноценная UNIX- подобная ОС (вариант, близкий к кластерному подходу). Программи- рование осуществляется в рамках модели передачи сообщений (биб- лиотеки параллельных функций MPI, PVM, BSPlib). Кластерные системы −более дешевый вариантMPP–систем, по- скольку они также используют принцип передачи сообщений, но строятся из компонентов высокой степени готовности [16,2]. 15 Вычислительный кластер − это совокупность компьютеров, объе- диненных в рамках некоторой сети для решения одной задачи. В каче- стве вычислительных узлов обычно используются доступные на рын- ке однопроцессорные компьютеры, двух − или четырехпроцессорные SMP-серверы. Каждый узел работает под управлением своей копии операционной системы, в качестве которой чаще всего используются стандартные операционные системы: Linux, NT, Solaris и т.п. Состав и мощность узлов может меняться даже в рамках одного кластера, давая возможность создавать неоднородные системы. Для кластерных систем в соответствии с сетевым законом Амдала характеристики коммуникационных сетей имеют принципиальное значение. Коммуникационные сети [16]имеют две основныехарактери- стики: латентность − время начальной задержки при посылке сообще- ний и пропускную способность сети, определяющую скорость пере- дачи информации по каналам связи. После вызова пользователем функции посылки сообщения Send() сообщение последовательно про- ходит через целый набор слоев, определяемых особенностями органи- зации программного обеспечения и аппаратуры, прежде чем покинуть процессор. Наличие латентности определяет и тот факт, что макси- мальная скорость передачи по сети не может быть достигнута на со- общениях с небольшой длиной. Чаще всего используется сеть Fast Ethernet, основное достоинство которой − низкая стоимость оборудования. Однако большие наклад- ные расходы на передачу сообщений в рамках Fast Ethernet приводят к серьезным ограничениям на спектр задач, которые можно эффективно решать на таком кластере. Если от кластера требуется большая уни- версальность, то нужно переходить на более производительные ком- муникационные сети, например, SCI, Myrinet, некоторые другие. Ха- рактеристики некоторых сетей представлены в приложении 4. 1.4. ПРОГРАММИРОВАНИЕ ДЛЯ СИСТЕМ С РАЗДЕЛЯЕМОЙ ПАМЯТЬЮ Процессы. В операционной системе UNIX поддерживается воз- можность параллельного выполнения нескольких пользовательских программ. Каждому такому выполнению соответствует процесс опе- рационной системы [17]. Каждый процесс обладает собственными ре- сурсами, то есть выполняется в собственной виртуальной памяти, и тем самым процессы защищены один от другого, т.е. один процесс не 16 в состоянии неконтролируемым образом прочитать что-либо из памя- ти другого процесса или записать в нее. Однако контролируемые взаимодействия процессов допускаются системой, в том числе за счет возможности разделения одного сегмента памяти между виртуальной памятью нескольких процессов. Каждый процесс может образовать полностью идентичный подчиненный процесс выполнением систем- ного вызова FORK() и дожидаться окончания выполнения своих под- чиненных процессов с помощью системного вызова WAIT. После создания процесса предок и потомок могут произвольным образом изменять свой контекст. В частности, и предок, и потомок могут выполнить какой-либо из вариантов системного вызова exec, приводящего к полному изменению контекста процесса. Нити. Понятие нити (thread, light-weight process − легковесный процесс, поток управления) давно известно в области операционных систем. В одной виртуальной памяти может выполняться не один по- ток управления. Если несколько процессов совместно пользуются не- которыми ресурсами (общим адресным пространством, общими пере- менными, аппаратными ресурсами и др.), то при доступе к этим ре- сурсам они должны синхронизовать свои действия. Многолетний опыт программирования с использованием явных примитивов син- хронизации показал, что этот стиль "параллельного" программирова- ния порождает серьезные проблемы при написании, отладке и сопро- вождении программ (наиболее трудно обнаруживаемые ошибки в программах обычно связаны с синхронизацией). Это было главной причиной того, что в традиционных вариантах ОС UNIX понятие процесса жестко связывалось с понятием отдельной и недоступной для других процессов виртуальной памяти. При появлении систем SMP отношение к процессам претерпело существенные изменения. В таких компьютерах физически присутст- вуют несколько процессоров, которые имеют одинаковые по скорости возможности доступа к совместно используемой основной памяти. Появление подобных машин на мировом рынке поставило проблему их эффективного использования. При применении традиционного подхода ОС UNIX к организации процессов наличие общей памяти не давало эффекта. К моменту появления SMP выяснилось, что техно- логия программирования еще не может предложить эффективного и безопасного способа реального параллельного программирования. Поэтому пришлось вернуться к явному параллельному программиро- 17 ванию с использованием параллельных процессов в общей виртуаль- ной (а тем самым и основной) памяти с явной синхронизацией. Нить − это независимый поток управления с собственным счетчи- ком команд, выполняемый в контексте некоторого процесса. Фактиче- ски, понятие контекста процесса изменяется следующим образом. Все, что не относится к потоку управления (виртуальная память, деск- рипторы открытых файлов и т.д.), остается в общем контексте процес- са. Вещи, которые характерны для потока управления (регистровый контекст, стеки разного уровня и т.д.), переходят из контекста процес- са в контекст нити. При этом контексты всех нитей остаются вложен- ными в контекст породившего их процесса. Поскольку нити одного процесса выполняются в общей виртуаль- ной памяти, стек любой нити процесса в принципе не защищен от произвольного (например, по причине ошибки) доступа со стороны других нитей. Семафоры. Чтобы исключить упомянутую выше ситуацию, необ- ходимо ввести систему синхронизации параллельных процессов. Выход заключается в разрешении входить в критическую секцию (КС) только одному из нескольких асинхронных процессов. Под кри- тической секцией понимается участок процесса, в котором процесс нуждается в ресурсе. Решение проблемы критической секции предло- жил Дейкстра [17] в виде семафоров. Семафоромназывается пере- менная S, связанная, например, с некоторым ресурсом и принимаю- щая два состояния: 0 (запрещено обращение) и 1 (разрешено обраще- ние). Над S определены две операции: V и P. Операция V изменяет значение S семафора на значение S + 1. Действие операции P таково: 1. если S ≠ 0, то P уменьшает значение на единицу; 2. если S = 0, то P не изменяет значения S и не завершается до тех пор, пока некоторый другой процесс не изменит значение S с по- мощью операции V. Операции V и P считаются неделимыми, т. е. не могут исполняться одновременно. Приведем пример синхронизации двух процессов, в котором рrocess 1 и process 2 могут выполняться параллельно. Процесс может захватить ресурс только тогда, когда S:=1. После за- хвата процесс закрывает семафор операции P(S) и открывает его вновь после прохождения критической секции V(S). Таким образом, семафор S обеспечивает неделимость процессов Li и, значит, их по- 18 следовательное выполнение. Это и есть решение задачи взаимного ис- ключения для процессов Li. begin semaphore S; S:=1; process 1: begin L1:P(S); Критический участок 1; V(S); Остаток цикла, go to L1 end process 2: begin L2:P(S); Критический участок 2; V(S); Остаток цикла, go to L2 end end OpenMP. Интерфейс OpenMP [18] является стандартом для про- граммирования на масштабируемых SMP-системах с разделяемой па- мятью. В стандарт OpenMP входят описания набора директив компи- лятора, переменных среды и процедур. За счет идеи "инкрементально- го распараллеливания" OpenMP идеально подходит для разработчи- ков, желающих быстро распараллелить свои вычислительные про- граммы с большими параллельными циклами. Разработчик не создает новую параллельную программу, а просто добавляет в текст последо- вательной программы OpenMP-директивы. Предполагается, что OpenMP-программа на однопроцессорной платформе может быть использована вкачестве последовательной программы, т.е. нет необходимости поддерживать последовательную и параллельную версии. Директивы OpenMP просто игнорируются последовательным компилятором, а для вызова процедур OpenMP мо- гут быть подставлены заглушки, текст которых приведен в специфи- кациях. В OpenMP любой процесс состоит из нескольких нитей управления, которые имеют общее адресное пространство, но разные потоки команд и раздельные стеки. В простейшем случае, процесс со- стоит из одной нити. Обычно для демонстрации параллельных вычислений используют простую программу вычисления числа π. Рассмотрим, как можно на- 19 писать такую программу в OpenMP. Число π можно определить сле- дующим образом: = ∫ + dx x 1 0 2 1 1 arctg(1)-arctg(0)= π/4. Вычисление интеграла затем заменяют вычислением суммы : ∫ ∑ + = + = 1 0 1 2 2 1 4 1 1 4 n i i x n dx x , где: x i = (i-0.5)/n . В последовательную программу вставлены две строки, и она ста- новится параллельной. program compute_pi parameter (n = 1000) integer i double precision w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n sum = 0.0d0; !$OMP PARALLEL DO PRIVATE(x), SHARED(w) !$OMP& REDUCTION(+:sum) do i=1,n x = w*(i-0.5d0) sum = sum + f(x) enddo pi = w*sum print *,'pi = ',pi stop end Программа начинается как единственный процесс на головном процессоре. Он исполняет все операторы вплоть до первой конструк- ции типа PARALLEL. В рассматриваемом примере это оператор PARALLEL DO, при исполнении которого порождается множество процессов с соответствующим каждому процессу окружением. В рас- сматриваемом примере окружение состоит из локальной (PRIVATE) переменной х, переменной sum редукции (REDUCTION) и одной раз- деляемой (SHARED) переменной w. Переменные х и sum локальны в каждом процессе без разделения между несколькими процессами. Пе- ременная w располагается в головном процессе. Оператор редукции 20 REDUCTION имеет в качестве атрибута операцию, которая применя- ется к локальным копиям параллельных процессов в конце каждого процесса для вычисления значения переменной в головном процессе. Переменная цикла i является локальной в каждом процессе по своей сути, так как именно с уникальным значением этой переменной поро- ждается каждый процесс. Параллельные процессы завершаются опе- ратором END DO, выступающим как синхронизирующий барьер для порожденных процессов. После завершения всех процессов продол- жается только головной процесс. Директивы. Директивы OpenMP с точки зрения Фортрана явля- ются комментариями и начинаются с комбинации символов "!$OMP". Директивы можно разделить на 3 категории: определение параллель- ной секции, разделение работы, синхронизация. Каждая директива может иметь несколько дополнительных атрибутов − клауз. Отдельно специфицируются клаузы для назначения классов переменных, кото- рые могут быть атрибутами различных директив. Директивы порождения нитей предназначены для генерации и распределения работы между ними, в том числе и для явного распре- деления. PARALLEL ... END PARALLEL определяет параллельную областьпрограммы. При входе в эту область порождается (N–1) но- вых процессов, образуется "команда" из N нитей, а порождающая нить получает номер 0 и становится основной нитью команды (т.н. "master thread"). При выходе из параллельной области основная нить дожида- ется завершения остальных нитей и продолжает выполнение в одном экземпляре. Предполагается, что в SMP-системе нити будут распреде- лены по различным процессорам (однако это, как правило, находится в ведении операционной системы). Директивы разделение работ. Работа распределяется директи- вами DO , SECTIONS и SINGLE . Возможно также явное управление распределением работы с помощью функций, возвращающих номер текущей нити и общее число нитей. По умолчанию код внутри PARALLEL исполняется всеми нитями одинаково. Директива DO ... [ENDDO] определяет параллельный цикл. Директива SECTIONS ... END SECTIONS определяет набор независимых секций кода. Секции отделяются друг от друга директивой SECTION . Директива SINGLE ... END SINGLE определяет блок кода, который будет исполнен толь- ко одной нитью (первой, которая дойдет до этого блока). 21 Директивы синхронизации. Директива MASTER ... END MASTER определяет блок кода, который будет выполнен только master-ом (нулевой нитью). Директива CRITICAL ... END CRITICAL определяет критическую секцию, то есть блок кода, ко- торый не должен выполняться одновременно двумя или более нитями. Директива BARRIER определяет точку барьерной синхронизации, в которой каждая нить дожидается всех остальных. Существуют и дру- гие директивы синхронизации. Классы переменных. OpenMP–переменные в параллельных об- ластях программы разделяются на два основных класса: SHARED (общие − под именем A все нити видят одну переменную) и PRIVATE (приватные − под именем A каждая нить видит свою пере- менную). 1.5. ПРОГРАММИРОВАНИЕ ДЛЯ СИСТЕМ С ПЕРЕДАЧЕЙ СООБЩЕНИЙ Система программирования MPI относится к классу МКМД ЭВМ с индивидуальной памятью, то есть к многопроцессорным системам с обменом сообщениями. MPI имеет следующие особенности: • MPI − библиотека, а не язык. Она определяет имена, вызовы проце- дур и результаты их работы. Программы, которые пишутся на FORTRAN, C, и C++ компилируются обычными компиляторами и связаны с MPI–библиотекой. • MPI − описание, а не реализация. Все поставщики параллельных компьютерных систем предлагают реализации MPI для своих ма- шин как бесплатные, и они могут быть получены из Интернета. Правильная MPI-программа должна выполняться на всех реализа- циях без изменения. • MPI соответствует модели многопроцессорной ЭВМ с передачей сообщений. В модели передачи сообщений процессы, выполняющиеся парал- лельно, имеют раздельные адресные пространства. Связь происходит, когда часть адресного пространства одного процесса скопирована в адресное пространство другого процесса. Эта операция совместная и возможна только когда первый процесс выполняет операцию переда- чи сообщения, а второй процесс − операцию его получения. Процессы в MPI принадлежат группам. Если группа содержит n процессов, то процессы нумеруются внутри группы номерами, кото- 22 рые являются целыми числами от 0 до n-l . Имеется начальная группа, которой принадлежат все процессы в реализации MPI. Понятия контекста и группы объединены в едином объекте, назы- ваемом коммуникатором. Таким образом, отправитель или получа- тель, определенные в операции посылки или получения, всегда обра- щается к номеру процесса в группе, идентифицированной данным коммуникатором. В МPI базисной операцией посылки является операция: MPI_Send (address, count, datatype, destination, tag, comm), где ( address, count, datatype ) − количество ( count) объектов типа datatype , начинающихся с адреса address в буфере посылки; destination – номер получателя в группе, определяемой коммуника- тором comm ; tag − целое число, используемое для описания сообще- ния; comm – идентификатор группы процессов и коммуникационный контекст. Базисной операцией приема является операция: MPI_Recv (address, maxcount, datatype, source, tag, comm, status), где ( address, count, datatype ) описывают буфер приемника, как в случае MPI_Send ; sourse – номер процесса-отправителя сообщения в группе, определяемой коммуникатором comm ; status – содержит ин- формацию относительно фактического размера сообщения, источника и тэга. Sourse, tag, count фактически полученного сообщения восста- навливаются на основе status В MPI используются коллективные операции, которые можно раз- делить на два вида: • операции перемещения данных между процессами. Самый простой из них – широковещание (broadcasting), MPI имеет много и более сложных коллективных операций передачи и сбора сообщений; • операции коллективного вычисления (минимум, максимум, сумма и другие, в том числе и определяемые пользователем операции). В обоих случаях библиотеки функций коллективных операций строятся с использованием знания о преимуществах структуры ма- шины, чтобы увеличить параллелизм выполнения этих операций. Часто предпочтительно описывать процессы в проблемно- ориентированной топологии. В MPI используется описание процессов в топологии графовых структур и решеток. 23 В MPI введены средства, позволяющие определять состояние про- цесса вычислений, которые позволяют отлаживать программы и улучшать их характеристики. В MPI имеются как блокирующие операции send и receive , так и неблокирующий их вариант, благодаря чему окончание этих операций может быть определено явно. MPI также имеет несколько коммуника- ционных режимов. Стандартный режим соответствует общей практи- ке в системах передачи сообщений. Синхронный режим требует бло- кировать send на время приема сообщения в противоположность стандартному режиму, при котором send блокируется до момента за- хвата буфера. Режим по готовности (для send ) – способ, предостав- ленный программисту, чтобы сообщить системе, что этот прием был зафиксирован, следовательно, низлежащая система может использо- вать более быстрый протокол, если он доступен. Буферизованный ре- жим позволяет пользователю управлять буферизацией. Программы MPI могут выполняться на сетях машин, которые имеют различные длины и форматы для одного и того же типа datatype , так что каждая коммуникационная операция определяет структуру и все компоненты datatype . Следовательно, реализация всегда имеет достаточную информацию, чтобы делать преобразования формата данных, если они необходимы. MPI не определяет, как эти преобразования должны выполняться, разрешая реализации произво- дить оптимизацию для конкретных условий. Процесс есть программная единица, у которой имеется собствен- ное адресное пространство и одна или несколько нитей. Процессор − фрагмент аппаратных средств, способный к выполнению программы. Некоторые реализации MPI устанавливают, что в программе MPI все- гда одному процессу соответствует один процессор; другие − позво- ляют размещать много процессов на каждом процессоре. Если в кластере используются SMP–узлы (симметричная много- процессорная система с множественными процессорами), то для орга- низации вычислений возможны два варианта. 1. Для каждого процессора в SMP-узле порождается отдельный MPI- процесс. MPI-процессы внутри этого узла обмениваются сообще- ниями через разделяемую память (необходимо настроить MPICH соответствующим образом). 2. На каждой узле запускается только один MPI-процесс. Внутри ка- ждого MPI-процесса производится распараллеливание в модели "общей памяти", например с помощью директив OpenMP. 24 Чем больше функций содержит библиотека MPI, тем больше воз- можностей представляется пользователю для написания эффективных программ. Однако для написания подавляющего числа программ принципиально достаточно следующих шести функций: MPI_Init Инициализация MPI MPI_Comm_size Определение числа процессов MPI_Comm_rank Определение процессом собственного номера MPI_Send Посылка сообщения MPI_Recv Получение сообщения MPI_Finalize Завершение программы MPI В качестве примера параллельной программы, написанной в стан- дарте MPI для языка С, рассмотрим программу вычисления числа π. Алгоритм вычисления π уже описывался в параграфе 1.4. #include "mpi.h" #include { int n, myid, numprocs, i; double mypi, pi, h, sum, x, t1, t2, PI25DT = 3.141592653589793238462643; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); while (1) { if (myid == 0) { printf ("Enter the number of intervals: (0 quits) "); scanf ("%d", &n); t1 = MPI_Wtime(); } MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); if (n == 0) break; else { h = 1.0/ (double) n; sum = 0.0; for (i = myid +1; i <= n; i+= numprocs) { x = h * ( (double)i - 0.5); sum += (4.0 / (1.0 + x*x)); } mypi = h * sum; MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD); if (myid == 0) { t2 = MPI_Wtime(); 25 printf ("pi is approximately %.16f. Error is %.16f\n",pi, fabs(pi - PI25DT)); printf ("'time is %f seconds \n", t2-t1); } } } MPI_Finalize(); return 0; } В программе после нескольких строк определения переменных следуют три строки, которые есть в каждой MPI–программе: MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); Обращение к MPI_Init должно быть первым обращением в MPI– программе, оно устанавливает "среду" MPI. В каждом выполнении программы может выполняться только один вызов MPI_Init Коммуникатор MPI_COMM_WORLD описывает состав процес- сов и связи между ними. Вызов MPI_Comm_size возвращает в numprocs число процессов, которые пользователь запустил в этой программе. Значение numprocs − размер группы процессов, связан- ной с коммуникатором MPI_COMM_WORLD . Процессы в любой группе нумеруются последовательными целыми числами, начиная с 0. Вызывая MPI_ Comm_rank, каждый процесс выясняет свой номер ( rank) в группе, связанной с коммуникатором. Затем главный процесс (который имеет myid =0) получает от пользователя значение числа прямоугольников n : MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); Первые три параметра соответственно обозначают адрес, количе- ство и тип данных. Четвертый параметр указывает номер источника данных (головной процесс), пятый параметр – название коммуникато- ра группы. Таким образом, после обращения к MPI_Bcast все процес- сы имеют значение n и собственные идентификаторы, что является достаточным для каждого процесса, чтобы вычислить mypi − свой вклад в вычисление π. Для этого каждый процесс вычисляет область каждого прямоугольника, начинающегося с myid + l Затем все значения mypi , вычисленные индивидуальными процес- сами, суммируются с помощью вызова Reduce : 26 MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD); Первые два параметра описывают источник и адрес результата. Третий и четвертый параметр описывают число данных (1) и их тип, пятый параметр – тип арифметико-логической операции, шестой – номер процесса для размещения результата. Затем по метке 10 управление передается на начало цикла. Этим пользователю предоставляется возможность задать новое n и повы- сить точность вычислений. Когда пользователь печатает нуль в ответ на запрос о новом n , цикл завершается, и все процессы выполняют: MPI_Finalize(); после которого любые операции MPI выполняться не будут. Функция MPI_Wtime() используется для измерения времени ис- полнения участка программы, расположенного между двумя включе- ниями в программу этой функции. Ранее говорилось, что для написания большинства программ дос- таточно 6 функции, среди которых основными являются функции об- мена сообщениями типа “точка-точка” (в дальнейшем – функции пар- ного обмена). Программу вычисления можно написать с помощью функций парного обмена, но функции, относящиеся к классу коллек- тивных обменов, как правило, будут эффективнее. Коллективные функции Bcast и Reduce можно выразить через парные операции Send и Recv . Например, для той же программы вычисления числа π операция Bcast для рассылки числа интервалов выражается через цикл следующим образом: for (i=0; i Параллельная MPI программа может содержать различные испол- няемые файлы. Этот стиль параллельного программирования часто называется MPMD (множество программ при множестве данных) в отличие от программ SPMD (одна программа при множестве данных). SPMD не следует путать с SIMD (один поток команд при множестве данных). Вышеприведенная программа вычисления числа π относится к классу программ SPMD. Такие программы значительно легче писать и отлаживать, чем программы MPMD. В общем случае системы SPM и MPI могут имитировать друг друга: 27 1. Посредством организации единого адресного пространства для физически разделенной по разным процессорам памяти. 2. На SMP–машинах вырожденным каналом связи для передачи со- общений служит разделяемая память. 3. Путем использования компьютеров с разделяемой виртуальной памятью. Общая память как таковая отсутствует. Каждый процес- сор имеет собственную локальную память и может обращаться к локальной памяти других процессоров, используя "глобальный ад- рес". Если "глобальный адрес" указывает не на локальную память, то доступ к памяти реализуется с помощью сообщений, пересы- лаемых по коммуникационной сети. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ К ГЛАВЕ 1 Контрольные вопросы к 1.1 1. Какие понятия положены в основу классификации Флинна? 2. Назовите и опишите классы параллельных ЭВМ по Флинну. 3. Что такое многопроцессорные ЭВМ с разделяемой памятью? 4. Что вызывает некорректность вычислений в ЭВМ с разделяемой памятью? 5. Каковы достоинства и недостатки ЭВМ с передачей сообщений? Контрольные вопросы к 1.2 1. Что такое ускорение вычислений? 2. Что определяет закон Амдала? 3. Какую характеристику определяет сетевой закон Амдала? 4. Какие факторы влияют на эффективность сетевых вычислений? Контрольные вопросы к 1.3 1. Определите три класса технической реализации многопроцессорных ЭВМ. 2. Что такое симметричные мультипроцессоры (SMP)? 3. Каковы особенности систем с массовым параллелизмом (MPP)? 4. Дайте определение вычислительного кластера. 5. Опишите виды кластеров, их особенности, дайте примеры кластеров. 6. Что такое коммуникационная сеть, каковы ее основные параметры? Контрольные вопросы к 1.4 1. Определите понятие процесса и нити, в чем их различие? 2. Как в Unix создаются процессы, нити? 3. Что такое семафоры, для чего они необходимы? 4. Что такое стандарт OpenMP? 5. Опишите как выполняется в языке OpenMP программа вычисления числа π. 6. Назовите типы директив стандарта OpenMP. 7. Какие классы переменных используются в OpenMP? 28 Контрольные вопросы к 1.5 1. Что такое стандарт MPI? 2. Назовите основные операции передачи и приема в MPI. 3. Назовите и опишите состав и назначение параметров обменных функций MPI. 4. Что такое процесс и процессор в MPI? 5. Перечислите минимально возможный состав MPI функций. 6. Расскажите, как выполняется программа MPI для вычисления числа π. 7. Какой коммуникатор определен после выполнения функции MPI_Init? 8. Можно ли использовать функции MPI до вызова MPI_Init? 9. Как в MPI определить номер процесса? 10. Как узнать число запущенных процессов приложения? 11. Возможна ли замена в MPI коллективных операций на парные обмены? |