Разработка программ с использованием MPI для параллельных и распределённых систем. Часть 1

ЛЕКЦИЯ 4 РАЗРАБОТКА ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ MPI ДЛЯ ПАРАЛЛЕЛЬНЫХ И РАСПРЕДЕЛЁННЫХ СИСТЕМ. (Часть 1) Пришло время рассказать о том, что представляют собой пользовательские программы для кластеров и других параллельных и распределѐнных систем, каким образом они создаются и как выполняются. В этой части курса мы рассмотрим создание пользовательских параллельных программ с использованием программного интерфейса MPI. Такие программы могут эффективно выполняться не только на кластерах, но и на многих других многопроцессорных вычислительных системах, в том числе и на завоѐвывающих всѐ большую популярность в мире машинах с многоядерными процессорами. Классические программы, создаваемые для однопроцессорных ЭВМ с одноядерными процессорами и рассчитанные на последовательное выполнение, сильно отличаются от параллельных программ, создаваемых для многопроцессорных систем и ЭВМ с многоядерными процессорами. Последние на много сложнее. Именно параллельные программы позволяют достичь максимального эффекта в производительности при использовании таких систем. Большинство же разработчиков программ, до сих пор ориентируется на последовательное программирование. Последовательное программирование давно и прочно укоренилось в с ознании большинства разработчиков. При этом следует отметить, что создание параллельных программ до сих пор является нетривиальной задачей. Это, в значительной мере, объясняется склонностью человека к планированию последовательных действий и новизной сферы применения. Чем параллельная программа отличается от последовательной, и чем от последовательного программирования отличается параллельное? После трансляции последовательной программы в код, все еѐ команды, выполняются последовательно, одним потоком. Исходя из такого представления о выполнении программы, разработчик планирует единую последовательность действии, которые должна произвести ЭВМ, выполняя его пр ограмму. В отличие от неѐ параллельная программа разрабатывается таким о бразом, чтобы после еѐ трансляции в машинный код, команды могли выполняться параллельно, несколькими потоками. Каждый такой поток можно представить как отдельную последовательную программу. Но, в отличие от просто последовательной программы, которая выполняется самостоятельно, поток команд параллельной программы связан с другими потоками, он зависит от этих потоков по данным, а иногда и по управлению. Таким же образом, от самого этого потока зависят другие потоки. Особенности параллельного программирования, мы будем рассматр ивать на примере конкретной задачи. Пусть у нас имеются четыре одномерных массива A, B, C и D с исходными данными. С элементами массивов необходимо провести арифметиче1 ские операции, а результаты занести в одномерный массив E. Вычисление значения каждого i-го элемента массива E производится по формуле: E[i]=A[i]*B[i]+C[i]*D[i] (1) Необходимо вычислить значения всех элементов массива E. Исследование проведѐм в следующем порядке: 1) Создадим последовательную программу вычисления значений элементов массива E, подробно разберѐм еѐ и проследим этапы еѐ выполнения. 2) Создадим ярусно параллельную форму (см. далее) нашей программы и оценим возможность еѐ распараллеливания. 3) На основе ярусно-параллельной формы нашей последовательной программы создадим алгоритм параллельной программы. 4) Познакомимся со стандартом программирования MPI. 5) Создадим параллельную программу, реализующую вычисления по формуле (1) в стандарте MPI. 6) Разберѐмся с выполнением программы на кластере МЭИ. Материал раздела изложен в ознакомительном стиле. Основная задача – это получить начальное представление о параллельном программировании. Более детальную информацию можно получить в специальной литературе. Последовательная программа Итак, решение нашей задачи начнѐм с создания последовательной программы. Для людей имеющих некоторые навыки в программировании, это сделать не сложно. На рис. 1 показан пример последовательной программы на языке C, которая выполняет арифметические операции согласно формуле (1) над массивами размерностью в 100 элементов каждый. Язык C взят за основу в данном пособии, поскольку является базовым языком, при создании пр ограмм для кластеров. В дальнейшем он нам пригодится и для создания параллельных программ. Последовательную программу, приведѐнную на рис. 1 рассмотрим достаточно подробно, чтобы она, по возможности, была понятна даже людям, не программировавшим на языке C. Перед рассмотрением программы необходимо отметить, что все по дпрограммы, в терминах языка C именуются функциями, независимо от их вида и назначения. Поэтому, когда в тексте учебного пособия речь будет идти о программах, написанных на C и C++, все подпрограммы будут именоваться функциями. В начале программы операторами #include декларируется подключение двух заголовочных файлов stdio.h и fun.h. Заголовочные файлы имеют расширение .h и в них описываются некоторые константы, переменные и функции, которые необходимы для выполнения программы. По существу, каждый 2 заголовочный файл представляет собой библиотеку функций (т.е. подпр ограмм), констант и переменных. Так, файл stdio.h является стандартным заголовочным файлом языка C, в котором, в частности описаны функции стандартного ввода-вывода. Второй подключаемый заголовочный файл fun.h является пользовательским. Он создан автором программы и в нѐм описаны функции fun_in и fun_out, которые далее будут использованы в программе. Отдельно необходимо отметить формат операторов подключения. Формат #include<имя файла> используется для подключения заголовочных файлов стандартных для языка C, а формат #include”имя файла” (“” вместо <>) для подключения прочих файлов. #include // Подключение заголовочного файла stdio.h #include"fun.h" //Подключение заголовочного файла fun.h void main(int argc,char **argv) { //Объявление массивов A,B,C,D и E в формате с плавающей точкой float A[100],B[100],C[100],D[100],E[100]; int i; // Объявление целочисленой переменной i fun_in(A,B,C,D,100); // Ввод исходных даных в массивы for (i=0;i<100;i++) // Оператор цикла E[i]=A[i]*B[i]+C[i]*D[i]; // Непосредственно вычисления fun_out(E,100); // Вывод результата } Рис. 1. Последовательная программа на языке C Во многих языках программирования, программа делится на основную часть и подпрограммы (функции – в терминах C). В отличие от них, любая программа, написанная на языке C, целиком состоит из функций. При этом, одна из функций считается главной и выполнение программы всегда начинается с выполнения именно этой функции. Называется эта функция main. Описание функции main, как и других функций состоит из заголовка и блока операторов. Синтаксис описания функции main такой: <тип возвращаемого значения> main(<аргументы функции>) { <операторы функции>; } Начнѐм с заголовка. В нашей программе тип возвращаемого значения функции main – void (пустой), это означает, что функция во внешнюю среду, по своему окончанию ничего не возвращает. То есть наша функция main – это 3 аналог процедуры в языке Pascal и Subroutine в Фортране. В скобках, после имени функции, через запятую перечислены еѐ аргументы, значение которых она принимает от операционной системы при запуске программы. Перед именем каждого аргумента написан его тип. Поскольку функция main вызывается сразу после начала работы программы, то через аргументы она получает параметры командной строки программы. Так, аргумент argc имеет тип int (от слова integer - целочисленный). Он передаѐт в функцию main число параметров командной строки. Если при вызове программы в командной строке не было параметров, то argc=0. Если в командной строке параметры были, то они передаются в функцию main через аргумент argv. Аргумент argv представляет собой ссылку (знак ссылки - *) на массив ссылок (второй знак *) на параметры. Каждый параметр задаѐтся строкой символов, поэтому аргумент argv имеет символьный тип char (от слова character - символ). После заголовка функции main, следует описание еѐ операторов. Блок операторов функции заключѐн в фигурные скобки {}. Рассмотрим операторы функции main в нашей программе. Сначала идѐт декларация переменных. В первой строке декларируются массивы A, B, C, D и E. В квадратных скобках указывается их размерность (сколько у них элементов). В нашем случае у всех массивов по 100 элементов. Перед перечислением массивов указывается их тип. В нашем случае все массивы имеют тип float, то есть тип с плавающей точкой (float – плавающий). В следующей строке декларируется целочисленная (тип - int) переменная i. Первый выполняемый оператор нашей функции main – это вызов функции fun_in. Функция fun_in загружает исходные данные массивы A, B, C, и D. Эти массивы передаются функции fun_in в качестве аргументов. В качестве последнего аргумента, в функцию передаѐтся размерность массивов равная 100 элементам. Как уже упоминалось ранее, функция fun_in описана разработчиком программы в заголовочном файле fun.h. Сделано это для того, чтобы не описывать действия, выполняемые этой функцией, в тексте main, и таким образом не нагромождать наш пример банальными операциями ввода исходных данных. Поскольку над всеми элементами массивов выполняются одинаковые арифметические операции, то, их целесообразно выполнять в цикле. После вызова функции fun_in, в тексте программы описан оператор цикла. В начале оператора написано ключевое слово for, а затем, в скобках параметры цикла. На языке C, элементы массивов нумеруются с нуля. То есть наши массивы будут иметь по 100 элементов, нумеруемые с 0-го до 99-го. Поэтому, изначально переменная-индекс нашего цикла приравнивается нулю i=0, затем следует условие выполнения очередного шага цикла i<100 (т.е. цикл будет продолжаться пока i≤99), а потом оператор приращения индекса цикла i++. Запись i++ равнозначна записи i=i+1. 4 1-й шаг цикла 2-й шаг цикла .......... Проверка i<100 R1=A[99]*B[99] R2=C[99]*D[99] E[99]=R1+R2 i=i+1 (i=99+1=100) Проверка i<100 Ввод результатов Рис. 2. Диаграмма 1 100-й шаг цикла Последовательность по времени t Ввод исходных данных i=0; Проверка i<100 R1=A[0]*B[0] R2=C[0]*D[0] E[0]=R1+R2 i=i+1 (i=0+1=1) Проверка i<100 R1=A[1]*B[1] R2=C[1]*D[1] E[1]=R1+R2 i=i+1 (i=1+1=2) После оператора цикла следует выполняемый в цикле оператор программы. В нашем случае это арифметическое выражение - формула, вычисляемая на каждом шаге цикла для i-х элементов: E[i]=A[i]*B[i]+C[i]*D[i]. После цикла, следует вызов функции fun_out, которая выводит результаты вычислений, сохранѐнные в массиве E. Функция fun_out описана в файле fun.h. На рис. 2 приведена диаграмма выполнения программы, как это будет происходить в представлении программиста. Сразу необходимо отметить, что данная диаграмма отражает только представление разработчика программы и не учитывает суперскалярный режим выполнения программы процессором и действия оптимизирующего компилятора. Слева, на диаграмме, показана шкала времени. Шкала времени направлена сверху вниз. Большинство современных разработчиков программ мало волнуют конкретные временные параметры различных этапов выполнения программы. Их больше интересует последовательность выполнения этих этапов. Поэтому пока оставим нашу временную шкалу без конкретных значений. В середине диаграммы в столбик показаны сами этапы выполнения программы. Этапы следуют последовательно друг за другом. Этапы выпо лнения цикла сгруппированы по шагам. Шаги цикла показаны справа. В начале выполнения программы осуществляется ввод исходных данных. Потом переменная индекса (i) приравнивается нулю и выполняется первый шаг цикла, затем второй, третий и так далее. Последним, в нашей пр ограмме выполняется сотый шаг (при i=99), после чего осуществляется вывод результатов и завершение программы. Выполнение каждого шага цикла осуществляется, согласно нашей диаграмме, в пять этапов. Сначала осуществляется проверка условия выполнения очередного шага цикла. Если условие выполнения соблюдается, то перемножаются i–e элементы массивов A и B. Результат этого перемножения сохраняется в некотором регистре, который мы условно назовѐм R1. После элементов A и B перемножаются i–e элементы массивов C и D. Результат этого пе5 t 1-й шаг 2-й шаг Ввод исходных данных i=0; Проверка i<100 R1=A[0]*B[0] R2=C[0]*D[0] E[0]=R1+R2 i=i+1 (i=0+1) Проверка i<100 R1=A[1]*B[1] R2=C[1]*D[1] E[1]=R1+R2 i=i+1 (i=1+1) .......... Проверка i<100 R1=A[99]*B[99] R2=C[99]*D[99] E[99]=R1+R2 i=i+1 (i=99+1) Проверка i<100 Ввод результатов 100-й шаг Последовательность по времени ремножения также заносится в регистр, который мы назовѐм R2. Когда оба произведения готовы, они суммируются, а результат сохраняется в i–й ячейке массива E. Потом осуществляется приращение (инкремент) на единицу индексной переменной i и, если выполнится условие, осуществляется переход к следующему шагу. Рис. 3. Диаграмма 2 На рис. 3 показана другая диаграмма. Так, с точки зрения программиста, может выполняться наша программа на процессоре, который имеет два арифметико-логических устройства (АЛУ). Предположим, что каждое АЛУ имеет устройство сложения/вычитания и устройство умножения/деления. Также, чтобы не усложнять диаграмму, в диаграмме не учитывается реальное время выполнения этапов нашей пр ограммы, а показана лишь их последовательность. Кроме этого, как и в первом случае, в диаграмме не учитываются особенности работы конвейеров команд процессора. Как видно из диаграммы, время выполнение каждого шага цикла сократилось. Если ранее, время выполнения шага равнялось времени выполнения всех пяти этапов, то теперь оно сократилось (в идеале) до времени выполнения только трѐх. В реальности, оптимизирующий компилятор может заранее определить число шагов цикла, поскольку все условия цикла в тексте программы заданы явно. В этом случае будет исключена проверка условия продолжения цикла на каждом шаге. 6 Ярусно-параллельная форма программы Рассмотрев последовательную программу, попробуем еѐ распараллелить. В теории параллельного программирования существует понятие ярусно-параллельной формы (ЯПФ) представления программы. В этом случае программа представляется как последовательность ярусов. На каждом ярусе размещаются операторы программы, которые могут выполняться одновр еменно друг с другом, то есть параллельно. На каждом последующем ярусе располагаются операторы, которые могут быть выполнены только после операторов предыдущего яруса. Схематически, ярусно-параллельную форму программы можно представит в виде графа. Операторы программы являются вершинами графа (показаны овалами), а дуги – это зависимости операторов друг от друга. На рис. 4 представлен граф нашей последовательной программы в ярусно-параллельной форме. Комментарии к ним будут даны позднее. Основным критерием при распараллеливании программы, служит завиНачало Ярус 0 симость операторов друг от друга по данным. Кратко сформулируем правило: Правило 1. Любой оператор проВвод исходных граммы, использующий в качестве входi=0 Яр.1 данных ных данных результаты работы другого оператора, может быть выполнен только после окончания выполнения этого опеПроверка i<100 Яр. 2 ратора. Это правило является необходимым, но не достаточным. Выполняясь, E[0]=A[0]*B[0]+C[0]*D[0] Яр. 3 оператор может изменить содержимое ячеек памяти, где хранятся исходные данные для других операторов. Кратко i=i+1 (i=0+1=1) Яр. 4 сформулируем второе правило: Правило 2. Любой оператор программы, который в результате своего Проверка i<100 Яр. 5 выполнения может исказить или уничтожить исходные данные для другого E[1]=A[1]*B[1]+C[1]*D[1] Яр. 6 оператора, может быть выполнен только после окончания выполнения этого оператора. i=i+1 (i=1+1=2) Яр. 7 Остановимся пока на этих двух правилах, поскольку они являются достаточными. Придерживаясь его уже Другие шаги цикла Яр. 8-301 можно начать анализ нашей программы. Однако, на будущее следует заметить, что формулировки Правила 1 и Правила Ввод результата и окончание Ярус 302 Рис. 4. Граф ЯПФ №1 7 2 могут быть заменены более мягкими, при выполнении некоторых допо лнительных условий. Возвратимся к нашей последовательной программе. В ней имеется одна особенность. Наш основной оператор вычисления формулы (6) выполняется в цикле много раз. С точки зрения построения ярусно-параллельной формы, каждое новое выполнение оператора в цикле можно рассматривать как о тдельный оператор. Приведѐнный на рис. 4 граф ЯПФ (граф ЯПФ №1) нашей программы представляет собой удручающую картину. Все шаги цикла выполняются строго последовательно. Дуги зависимостей между операторами по Правилу 1 показаны тонкими чѐрными линиями, а дуги зависимостей между операторами по Правилу 2 показаны толстыми чѐрными линиями. Толстыми белыми линиями показаны зависимости по управлению от условного оператора. Каким образом можно изменить сложившуюся ситуацию? Это можно сделать, если выявить и исключить из программы лишние связи между операторами. Исключить лишние связи можно в два этапа: Во-первых, на начальном этапе можно не замечать связи по управлению (белые толстые дуги). Сами операторы условия выполнения следующего шага цикла временно можно исключить. Это мы вправе сделать по двум причинам. Первая причина заключается в том, что нам заранее известно число шагов цикла. Даже если бы нам число шагов не было известно заранее, то мы всѐ равно могли бы задать его произвольно. Вторая причина заключается в отсутствии выходных данных у условных операторов. Поэтому они не оказ ывают информационного (по данным) влияния на ход вычислений. Это значит, что цикл может быть превращѐн в линейную последовательность без усло вных операторов. Во-вторых, из ЯПФ можно исключить зависимости между операторами приращения переменной индекса цикла i. Кроме индексации шагов цикла, переменная i используется для индексации массивов A, B, C, D и E. Она изменяется строго детерминировано и еѐ значение заранее известно на каждом шаге цикла. Это позволяет нам представить переменную i в виде массива I конкретных еѐ значений. Это же позволяет нам представить оператор ы приращения переменной i как операторы присвоения элементам массива I значеСтарт программы Ярус 0 Ввод исходных данных Ярус 1 I[0]=0 I[1]=1 ... I[99]=99 Ярус 2 E[0]=A[0]*B[0]+C[0]*D[0] E[1]=A[1]*B[1]+C[1]*D[1] ... E[99]=A[99]*B[99]+C[99]*D[99] Ярус 3 8 Ввод результата и конец Рис. 5. Граф ЯПФ №2 Ярус 4 ний переменной i на каждом шаге цикла. Замена операторов приращения индекса на операторы присвоения, приводит к исключению зависимостей между ними по данным (по переменной i) в ЯПФ программы. Граф ЯПФ №2 с исключѐнными связями и исключѐнными условными операторами представлен на рис. 5. Цикл, который имеется в нашей программе, обладает с точки зрения его распараллеливания хорошим свойством – отсутствием зависимостей между шагами цикла. Во первых, отсутствует зависимость по результатам выполнения других шагов. Это происходит потому, что на каждом шаге цикла фо рмируется результат, который сохраняется в своей ячейке массива E и который не используется другими шагами цикла. Во вторых, выполнение каждого шага цикла не приводит к искажению входных данных для других шагов. Отсутствие зависимостей между шагами цикла означает, что все они могут выполняться параллельно, а в ЯПФ нашей программы они помещаются на один ярус. Оператор арифметического выражения можно детализировать, выделив операции умножения и сложения. Как и всякие другие данные, промежуточные результаты арифметических операций должны где-то сохраняться. При реальных вычислениях они сохраняются в регистрах процессора. Поскольку мы пока программу рассматриваем абстрактно, то предположим, что у нас имеются два набора регистров. Первый – набор регистров R1, в котором сохраняются результаты перемножения элементов массивов A и B. Второй – набор регистров R2 в котором сохраняются результаты перемножения элементов массивов C и D. В этом случае граф ЯПФ №3 нашей программы будет выглядеть так (см. рис. 6). Старт программы Ярус 0 Ввод исходных данных Ярус 1 ... I[0]=0 R1[0]=A[0]*B[0] R2[0]=C[0]*D[0] ... I[99]=99 R1[99]=A[99]*B[99] E[0]=R1[0]+R2[0] R2[99]=C[99]*D[99] E[99]=R1[99]+R2[99] Ввод результата и конец Рис. 6. Граф ЯПФ №3 9 Ярус 2 Ярус 3 Ярус 4 Ярус 5 Дадим теперь приблизительную оценку нашей программе, с точки зрения еѐ потенциального параллелизма. Пусть T0 – это оценочное время выполнения нашей программы в последовательном режиме. Оно равно: T0=Tin+Tcl+Tout (2) где - Tin – суммарная продолжительность начального этапа работы программы, включающее время ввода исходных данных в массивы A,B,C и D; - Tcl – продолжительность выполнения цикла; - Tout – суммарная продолжительность этапа завершения программы, включающее время выдачи результатов из массива E. Продолжительность Tcl выполнения цикла, при последовательном выполнении программы будет определяться следующем образом: Tcl=Ti+N*Tst+Tl (3) где - Ti – продолжительность выполнения оператора присвоения значения переменной i=0; - N – число шагов в цикле (в нашей программе N=100); - Tst – продолжительность выполнения одного шага цикла; - Tl – продолжительность оператора условия выполнения шага цикла. Теперь необходимо раскрыть время продолжительности одного шага цикла. Оно будет равно: Tst=Tl+2*Tmul+Tadd+Tink (4) где - Tmul – продолжительность операции перемножения элементов массивов; - Tadd – продолжительность операции сложения элементов массивов; - Tink – продолжительность выполнения оператора приращения переменной i. Две операции перемножения элементов массивов и одна операция сложения, представляют собой арифметический оператор E[i]=A[i]*B[i]+C[i]*D[i]. Раскроем в формуле (2) время выполнения цикла и получим следующее выражение при N=100: T0=Tin+ Ti+100*( Tl+2*Tmul+Tadd+Tink)+Tl+Tout 10 (5) Напоминаем, что T0 – это время последовательного выполнения программы. Определим теперь оценочные времена выполнения программы для ярусно параллельных форм нашей программы. Предположим, что Tin и Tout – не изменяются в зависимости от рассматриваемой нами ЯПФ, и равны временам при последовательном выполнении программы. Также будем считать неизменными от ЯПФ продолжительности выполнения условных операторов, операторов присвоения и арифметических операций. Время T1 – оценочной продолжительности выполнения нашей программы для ЯПФ №1 нас не очень интересует, поскольку отличается от T0 лишь на Ti - время выполнения одного оператора присвоения. Время T2 – оценочной продолжительности выполнения нашей программы для ЯПФ №2 будет рассчитываться по следующей формуле: T2=Tin+Ti+2*Tmul+Tadd+Tout (6) а время T3 – оценочной продолжительности выполнения нашей программы для ЯПФ №3 по формуле: T3=Tin+Ti+Tmul+Tadd+Tout (7) До последнего момента мы не рассматривали конкретные значения времен выполнения операций в нашей программе. Теперь они нам необходимы. В таблице 1 приведены значения времени продолжительности операций в условных временных единицах. Таблица 1 Время Значение Время Значение Tin 100 Tadd 1 Ti 1 Tink 1 Tl 2 Tout 25 Tmul 3 При составлении таблицы, в частности было сделано несколько допущений. Первое, предполагалось, что за одну условную временную единицу задаѐтся значение одного элемента у всех четырѐх массивов, то есть четыре элемента. Также по четыре элемента массива E производится и вывод результата. Второе, при задании значений Tin и Tout не учитывалось возможное время загрузки и завершения программы. Подставив конкретные значения времѐн в формулы (5), (6) и (7), получим значение времени продолжительности выполнения программы в после11 довательном режиме, а также оценочные времена параллельного выполнения программы для ЯПФ №2 и ЯПФ №3: T0=100+1+100*(2+2*3+1+1)+2+25=101+100*10+27=1128 T2=100+1+2*3+1+25=133 T3=100+1+3+1+25=130 Тогда коэффициент ускорения для нашей программы будет равен: K=T0/T3=1128/130≈8.677 Следует отметить, что полученное значение K несколько завышенное. Это объясняется тем, что, составляя ЯПФ №2 и №3, мы не учитывали некоторые операторы, которые учитывали в последовательной программе. Получить более реалистичное значение максимального коэффициента ускорения, мо жно применив закон Амдала. Для этого нам надо выделить последовательную и параллельную части программы. Для рассмотрения возьмѐм ЯПФ №3 (граф ЯПФ №3 смотрите на рис. 6). Операции задания исходных данных, время Tin и вывода результатов, время Tout, выполняются последовательно, а вычисления параллельно. Суммарное время выполнения последовательных операций программы равно: Тпослед3=Tin+Tout=100+25=125 Не трудно подсчитать суммарное время выполнение всех операций программы в ЯПФ №3. Tсумарное3= Tin+100*(Ti+2*Tmul+Tadd)+Tout=125+100*(1+6+1)=925 Таким образом, доля последовательных вычислений в ЯПФ №3 нашей программы равна: b=Tпослед3/Tсуммарное3=125/925≈0.(135) Что, согласно закону Амдала, при неограниченном количестве ресурсов, даѐт максимальный коэффициент ускорения: Kmax1=1/b=7.4 Отсутствие параллелизма операций ввода исходных данных и вывода результатов, резко ограничивает программу в производительности. 12 Теперь на основе закона Амдала получим оценочный коэффициент ускорения нашей программы K, при ограниченном количестве ресурсов. Предположим, что наша вычислительная система имеет четыре скалярных процессорных ядра. Напомним, что ядра скалярные процессоров выпо лняют потоки команд строго последовательно. Скалярному выполнению выражения (1) соответствует ЯПФ №2. Суммарное время выполнения последовательных операций программы равно: Тпослед2= Тпослед3=Tin+Tout=125 Суммарное время выполнение всех операций программы в ЯПФ №2 равно: Tсумарное2= Tсумарное3= Tin+100*(Ti+2*Tmul+Tadd)+Tout=925 Применим закон Амдала для вычисления максимального коэффициента ускорения Kmax2 для этого случая. b= Tпослед2/Tсуммарное2≈0.(135) Kmax2=Pi/(b*Pi+(1-b))=4/(0.54+0.865)=4/1.405≈2.847 Единственный вывод, который можно сделать, это то, что получение ускорения за счѐт введения параллелизма является непростой нетривиальной задачей. В нашем примере, операции ввода исходных данных и вывода р езультатов были не распараллелены преднамеренно. К сожалению, в реальности это часто бывает именно так. Исходные данные либо последовательно считываются из файла, либо последовательно поступают по сети, либо ввод исходных данных и вывод результатов осуществляет только один, специально выделенный процессор. Чтобы как-то скомпенсировать потери из-за этих операций ввода, вычисления начинают производить сразу, по мере поступления исходных данных. Точно так же, по мере готовности сразу выводят р езультаты. Модели параллельного программирования и алгоритм программы На сегодня, наиболее популярны две модели параллельного программирования. Модель с общей памятью и модель с распределѐнной памятью. В обоих случаях речь идѐт о параллельно выполняющихся потоках команд. Ещѐ раз остановимся на понятии потока команд. Известно, что когда процессор выполняет последовательную программу, то он поочерѐдно выбирает из ОЗУ команды программы и выполняет их. Каким образом он их выполняет, последовательно или параллельно, зависит от внутренней организ ации процессора (процессорного ядра). Главное заключается в том, что код последовательной программы рассчитан в первую очередь на строго последо13 вательную выборку из памяти и с точки зрении программиста, на строго последовательное выполнение. Команды кода параллельной программы выбираются из памяти и выполняются несколькими потоками. Если в вычислительной системе имеется один процессор, с одним процессорным ядром, то устройство выборки команд такого процессора выбирает команды попеременно блоками из разных потоков. Выполняет команды ядро процессора также попеременно, блоками. Такой режим выполнения, называется режимом с разделением времени пр оцессора разными потоками. Если у процессора имеется несколько процессорных ядер, и/или в вычислительной системе имеется несколько процессоров, то выполнение потоков параллельной программы распределяется между этими ядрами и/или процессорами. В этом случае программа выполняется действительно параллельно. В модели с общей памятью, в программе имеются переменные, доступные нескольким потокам. В такой программе или все переменные являются доступными разным потокам, или некоторые из них. Каждая такая переменная доступна или всем потокам программы или некоторой группе потоков. Как правило, модель программирования с общей памятью применяется в вычислительных системах, где у процессоров (или процессорных ядер) действительно имеется физически общая, разделяемая ими оперативная память. Но возможны варианты, когда процессоры (ядра) выполняющие потоки параллельной программы не имеют общей физической памяти, но имеют общую логическую. Тогда организуется специальная аппаратная и/или программная система, которая позволяет процессору, выполняющему поток, получить доступ к переменной находящейся физически в памяти другого пр оцессора или к еѐ содержимому. В модели программирования с распределѐнной памятью, каждый поток имеет свой набор переменных, которые при выполнении программы недоступны другим потокам. Нет разницы в том, имеется ли физически общая оперативная память между выполняющими потоки программы процессорами или нет. Каждый поток имеет свой набор переменных и для них в оперативной памяти выделяется своя, недоступная другим потокам область памяти. Чтобы результаты работы одного потока стали доступны другому потоку, необходимо явным образом организовать их пересылку. В этом случае, поток отправитель формирует некий пакет-сообщение, куда записывает содержимое переменной (переменных) которое он собирается передать. После, осуществляется передача сообщения потоку (потокам) приѐмнику. Поток приѐмник, раскрывает сообщение, извлекает из него принимаемые данные и сохраняет их в своей области памяти, в какую либо переменную или переменные. Иногда в модели программирования с распределѐнной памятью, создаѐтся некоторый буфер – почтовый ящик, куда сообщения складываются до востребования. Такой почтовый ящик может задаваться в программе или явно пр ограммистом, или не явно без его участия. 14 Поскольку в настоящем учебном пособии речь идѐт о кластерных системах, которые подразумевают наличие физически распределѐнной памяти, то, далее, речь пойдѐт только о модели программирования с распределѐнной памятью, так как она является наиболее предпочтительной для систем данного класса. Прежде чем приступить к созданию самой параллельной программ, разработаем еѐ алгоритм. Снова предположим, что для выполнения нашей программы будет использовано четыре процессорных ядра нашей вычислительной системы. Процессорные ядра могут быть как скалярными, так и суперскалярными. Поскольку распараллеливание для суперскалярной обрабо тки выполняется внутри ядра, то для параллельного выполнения программы на четырѐх ядрах, программистом должны быть созданы как минимум четыре потока. Именно эти четыре потока мы и создадим. Существуют две разновидности упомянутой ранее модели программирования с распределѐнной памятью, которую мы взяли за основу в настоящем разделе. Это модели программирования с распределѐнной памятью MPMD и SPMD. 1) MPMD (Multiple Program Single Multiple Date – множество программ множество данных). Для каждого потока создаѐтся своя собственная программа. При выполнении потоков, у каждого имеется свой доступный только ему набор данных. Таким образом, параллельная программа представляет собой множество одновременно выполняющихся последовательных программ. Эти программы взаимодействуют друг с другом путѐм передачи сообщений. 2) SPMD (Single Program Multiple Date – одна программа множество данных) – создаѐтся единая для всех потоков программа. При выполнении, одновременно запускается несколько экземпляров этой программы, в количестве равному числу потоков. Каждому запущенному экземпляру программы, операционной системой присваивается индивидуальный номер – ранк. Используя его, на основании заложенного алгоритма программы, каждый поток определяет, что и как он должен делать. Как и в случае MPMD, в SPMD у каждого потока имеется свой доступный только ему набор данных, а запущенные экземпляры программы взаимодействуют друг с другом путѐм передачи сообщений. На сегодняшний день, модель программирования SPMD более популярна для программирования кластеров, чем MPMD. Это, в частности объясняется тем, что модель SPMD более гибкая с точки зрения числа запускаемых потоков по сравнению с MPMD. Часто, параллельную программу в модели SPMD создают таким образом, что она, в зависимости от обстоятельств, может быть выполнена любым (конечно в определѐнных рамках) числом потоков, от одного и более. На рис. 7 показана схема алгоритма параллельной программы в модели 15 SPMD. Программа едина для всех потоков. В начале своей работы, каждый поток должен «узнать» свой номер и сколько их запущено. Чтобы сохранить полученные значения номеров потоков и их количества, необходимо вести соответствующие переменные. Пусть у нас это будут rank и size. Поскольку наша параллельная программа рассчитана на выполнение четырьмя потоками, то, используя переменную size, каждый поток должен удостоверится (выполнив блок 3) в том, что запущены именно четыре потока. Иначе выполнять программу нельзя, можно допустить ошибку в вычислениях. Необходимо отметить, что в модели SPMD, каждый поток имеет свой набор одноименных переменных. Так, объявленная в программе переменная rank будет присутствовать у всех потоков, но у каждого потока она будет свой экземпляр. Присваивая или изменяя значение переменной, поток это делает только для своего экземпляра, не затрагивая экземпляры других потоков. Значение экземпляров переменой size у всех потоков нашей программы будет одинаковое (если только не было системной ошибки). Значение же переменной rank у каждого потока будет своѐ. Как правило, в SPMD номера потокам присваиваются по порядку, начиная с нулевого. То есть, номера наших четырѐх потоков будут следующие, 0, 1, 2 и 3 и у потоков они будут содержаться в переменных rank. 16 1 Начало 2 Получение значения rank и size Нет 3 Получение каждым потоком своего номера в переменную rank и общего числа потоков в переменную size Запущено все четыре потока? size=4 Да 4 rank=0 Нулевой потока выполняет оди блок а для остальные другой Нет Да 5 Ввод исх. данных в массивы A, B, C и D 6 Посылка потокам 1,2 и 3, частей A,B,C,D 7 Исходные данные вводит только нулевой поток 13 Приѐм от потока 0 частей A,B,C,D 14 i=0 Нет 8 Передача/приѐм исходных даных i<25 i=0 Нет 15 i<25 Да 9 E[i]= =A[i]*B[i]+C[i]*D[i] 10 Да 16 E[i]= =A[i]*B[i]+C[i]*D[i] 17 i++ i++ 11 Приѐм частей массива E от потоков 1,2 и 3 18 Посылка частей массива E потоку 0 12 Вывод массива E Каждый поток выполняет по 25 шагов цикла и вычисляет значения своих элементов массива E (смотрите комментарии в тексте главы). Сбор всех результатов нулевым потоком Вывод нулевым потоком результатов вычислений 19 Конец Рис. 7. Схема алгоритма параллельной программы в модели SPMD Вернѐмся к схеме алгоритма. Если число потоков равно четырѐм, тогда все потоки выполняют оператор условия rank=0 (блок 4). Тот поток, у кото17 рого значение переменной rank окажется равной нулю, выполнит блоки 5-12, а остальные потоки выполнят блоки 13-18. Нулевой поток (у которого rank=0), выполняя блок 5, осуществляет ввод в массивы A, B, C и D исходных данных, по 100 элементов в каждый массив. Потом он посылает (блок 6) по 25 элементов из каждого массива первому, второму и третьему потокам для обработки. Сделать он это должен следующим образом: 1) первые 25 элементов (с 0-го по 24-й) каждого массива он «оставляет себе»; 2) другие 25 элементов (с 25-го по 49-й) каждого массива он посылает процессу, у которого rank=1; 3) третьи 25 элементов (с 50-го по 74-й) каждого массива он посылает процессу, у которого rank=2; 4) последние 25 элементов (с 75-го по 99-й) каждого массива он посылает процессу, у которого rank=3. Далее нулевой поток, в цикле (блоки 7-10) вычисляет значения первых 25 элементов с 0-го по 24-й массива E, а потом принимает остальные вычисленные 75 элементов массива E (с 25-го по 99-й) от потоков 1, 2 и 3 (блок 11) и выводит их в качестве результата (блок 12). Теперь рассмотрим функционирование потоков 1, 2 и 3. Выполнив блок 13, каждый поток принимает от нулевого потока свой элементы массивов A, B, c и D, по 25 от каждого. Чтобы создать единый алгоритм функционирования для этих трѐх потоков, был применѐн один приѐм. Каждый поток, принимая очередные 25 элементов, сохраняет их не на своѐм месте в массиве, а в его начале. Так первый поток, принимая с 25-го по 49-й элементы массива A, сохраняет их в ячейках с 0-й по 24-ю в своѐм экземпляре массива. Также поступает и второй поток с элементами 50-74, а третий делает то же самое с элементами 75-99. Это приводит к абсолютной идентичности циклов (блоки 14-17) у всех трѐх потоков, и при этом эти циклы идентичны циклу в нулевом потоке (блоки 7-11). По окончании работы, первый, второй и третий потоки передают свои результаты (блок 18) нулевому потоку. После того как готов алгоритм, можно приступать к созданию самой параллельной программы. Но прежде необходимо познакомится с тем средством, которое нам будет для этого необходимо. 18