Газизов Р.К., Лукащук С.Ю., Тулебаев С.Д.
Г 13 Основы параллельного программирования с использованием MPI: Учеб. пособие / Уфимск. гос. авиац. техн. ун-т. – Уфа: УГАТУ, 2004. – 90 с.
ISBN 5-86911-477-2
В пособии излагаются основополагающие моменты разработки параллельных программ для кластерных вычислительных систем с использованием интерфейса передачи сообщений MPI. Рассматриваются вопросы оценки эффективности параллельных программ.
Пособие предназначено для студентов и аспирантов инженерных специальностей технических вузов, а также инженерных и научных работников, интересующихся параллельным программированием для кластерных вычислительных систем.
Табл. 1. Ил. 7. Библиогр. 4 назв.
Научный редактор канд. техн. наук, доц. Р.А. Хисамутдинов
Рецензенты: заведующий отделом вычислительной математики
Института математики УНЦ РАН д-р физ.- мат. наук,
проф. М.Д. Рамазанов,
ст. науч. сотр. Института механики УНЦ РАН
канд. физ.-мат. наук К.И. Михайленко
ББК 32.973.26-018.2(я7)
Публикуется при поддержке Федеральной целевой программы “Интеграция науки и высшего образования России на 2002–2006 годы”, контракт У0011/735
ISBN 5-86911-477-2 Уфимский государственный
авиационный технический
университет, 2004
Р.К. Газизов, С.Ю. Лукащук,
С.Д. Тулебаев, 2004
Содержание
Введение ………………………………………………………..
4
1. ВВЕДЕНИЕ В ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ …………………………………………………………
7
1.1. Простейшая параллельная программа ……………….
7
1.2. Оценка эффективности параллельной программы ….
12
2. ОСНОВЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ
СРЕДСТВАМИ MPI ………………………………………..
19
2.1. Базовые функции MPI …………………………………
19
2.2. Понятие клинча и совмещение приема и передачи
данных ………………………………………………….
28
2.3. Функции коллективного взаимодействия ……………
31
2.3.1. Функции коллективного обмена данными …………
32
2.3.2. Синхронизация процессов ……………………….
48
2.3.3. Функции поддержки распределенных операций .
48
2.4. Определение времени выполнения параллельной
программы ……………………………………………..
52
3. ПРИМЕРЫ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ …………….
55
3.1. Hello MPI ……………………………………………….
55
3.2. Вычисление интеграла …………………………………
57
3.3. Нахождение минимума …..…………………………….
61
3.4. Параллельная сортировка ……………………………...
66
3.5. Решение систем линейных уравнений ………………..
71
Список литературы …………………………………………….
79
ПРИЛОЖЕНИЕ 1. Работа с вычислительным кластером Башкирского регионального центра высокопроизводительных вычислений ………………………………………………..
80
ПРИЛОЖЕНИЕ 2. Некоторые базовые команды операционной системы Linux …………………......……………………….
85
Введение
В последние годы многопроцессорные вычислительные системы (МВС) получают все более широкое распространение в самых различных областях человеческой деятельности. Если пятнадцать-двадцать лет назад такие системы использовались преимущественно в области компьютерного моделирования для изучения сложных физических процессов и для создания высокотехнологичной техники (как правило, военного назначения), то в последние годы наблюдается активное внедрение МВС в производственную сферу, медицину, образование и даже средний бизнес. Причины этого достаточно очевидны: прогресс в области электронной техники и информационных технологий привел к существенному снижению стоимости таких систем. Естественно, что речь в данном случае не идет о так называемых “суперкомпьютерах” – вычислительных системах, обладающих на данный момент максимальными производительностью, оперативной и дисковой памятью. Количество процессоров в таких системах измеряется тысячами, а стоимость достигает нескольких миллионов долларов. Располагаются суперкомпьютеры в ведущих мировых научно-исследовательских центрах, и их основное назначение остается неизменным – компьютерное моделирование сложных объектов и процессов. Однако МВС с относительно небольшим количеством процессоров (от четырех до нескольких десятков) можно встретить все чаще. Как правило, это либо рабочие станции, либо кластерные вычислительные системы. Последние представляют собой объединенные единой коммуникационной средой с относительно небольшой пропускной способностью (100-1000 Мбит в секунду) однотипные персональные компьютеры или рабочие станции, физически собранные в одну или несколько стоек, и работающие как единая вычислительная система. Назначение таких кластеров может быть самым разнообразным: обработка больших потоков информации в режиме реального времени (крупные корпоративные базы данных); проведение расчетов, требующих производительности и объемов памяти, недостигнутых еще на данный момент персональными компьютерами; обработка высококачественного видеоизображения и многое другое. При этом цена кластера может составлять всего 10-20 тысяч долларов.
Однако существуют факторы, сдерживающие повсеместное внедрение МВС кластерного типа. Наиболее существенными из них следует, пожалуй, признать малое количество прикладного программного обеспечения и его высокую стоимость. Дело в том, что программы, выполняющиеся на МВС, являются в большинстве своем программами параллельными, осуществляющими обработку различных данных одновременно на нескольких (часто всех) процессорах системы. Написание таких программ – процесс значительно более трудоемкий, чем программирование для обычных однопроцессорных компьютеров, поэтому и стоимость параллельного программного обеспечения оказывается значительно выше. Но стоимость профессиональных параллельных пакетов определяется не только и не столько стоимостью их разработки, сколько теми целевыми группами, на которые они ориентированы. А именно, основными потребителями такого программного обеспечения являются крупные корпорации, способные заплатить десятки и даже сотни тысяч долларов за одну лицензию. Поэтому и цена параллельных пакетов оказывается соответствующей. Например, если пакет конечно-элементного моделирования ANSYS, широко используемый в промышленности при разработке новой техники, для однопроцессорных систем стоит порядка десяти тысяч долларов, то цена его параллельной версии приближается к ста тысячам. Естественно, что использовать такой пакет может позволить себе только достаточно крупная компания. Поэтому нередко возникает ситуация, когда многопроцессорная система есть, а программного обеспечения для нее очень мало и большую часть времени система простаивает.
Выход из сложившегося положения может быть только один: снижение стоимости параллельного программного обеспечения. А для этого необходимо, чтобы параллельных программных продуктов было много, чтобы была здоровая конкуренция. В свою очередь, это требует как большого количества профессиональных программистов, владеющих навыками параллельного программирования, так и еще большего количества квалифицированных пользователей, способных грамотно использовать параллельный программный продукт. Именно на подготовку таких пользователей и ориентировано, прежде всего, настоящее пособие.
Первая глава данного пособия посвящена основам параллельного программирования. На примере простейшей параллельной программы рассматриваются основные принципы программирования для многопроцессорных вычислительных систем. В этой же главе рассматриваются наиболее важные вопросы, касающиеся оценки эффективности параллельной программы, и приводятся факторы, влияющие на эту эффективность.
Во второй главе пособия излагаются базовые принципы параллельного программирования с использованием технологии передачи сообщений MPI (Message Passing Interface), ставшей в настоящее время стандартом параллельного программирования для кластерных систем. Приводится синтаксис и описание ряда основных функций MPI, а также простейшие примеры их использования.
Третья глава содержит примеры стандартных учебных параллельных программ, написанных с использованием MPI. Программы снабжены необходимыми комментариями и будут, на наш взгляд, весьма полезны для людей, приступающих к изучению параллельного программирования.
Наконец, в приложениях собраны практические рекомендации по работе с конкретной МВС – Alpha-кластером Башкирского регионального центра высокопроизводительных вычислений, установленным в Уфимском государственном авиационном техническом университете, а также приведены некоторые наиболее часто используемые команды операционной системы Linux.
Пособие не требует каких-либо специальных знаний в области многопроцессорной техники или программирования. Однако поскольку при изложении функций MPI за основу был принят язык C, знакомство читателя с этим языком программирования является необходимым условием успешного усвоения материала пособия.
1. ВВЕДЕНИЕ
В ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
1.1. Простейшая параллельная программа
Приступая к изучению основ параллельного программирования, необходимо прежде всего четко понять, в чем же заключается принципиальное отличие программы параллельной от программы последовательной. С этой целью рассмотрим один простейший пример.
Пусть перед нами стоит задача вычисления следующей суммы:
. (1)
Очевидно, что решение этой задачи на обычном однопроцессорном персональном компьютере не представляет никакой сложности и соответствующая программа на языке С имеет следующий вид:
#include
int main(int argc, char **argv)
{
int S=0; /* искомая сумма */
int k; /* переменная цикла */
/* вычисление суммы */
for (k=1; k<=32; k++)
S+=k*k*k;
/* печать результата на экран */
printf(“Sum is equal to %d”,S);
/* нормальное завершение работы программы */
return 0;
}
Теперь предположим, что в нашем распоряжении имеется многопроцессорная вычислительная система (МВС), содержащая 32 процессора. Зададимся вопросом: каким образом можно осуществить вычисление суммы (1) на этой системе так, чтобы были задействованы все 32 процессора? При этом естественно ожидать, что время вычисления на МВС должно быть существенно меньше, чем на обычном персональном компьютере*). Очевидно, что выигрыш во времени вычислений будет получен лишь в том случае, когда процессоры МВС будут работать одновременно, или параллельно. Но для этого каждый процессор должен выполнять свой набор операций, не зависящих от операций, выполняющихся на других процессорах системы. Отсюда естественным образом возникает задача, получившая в практике параллельного программирования название задачи декомпозиции и заключающаяся в разделении исходной задачи на ряд автономных, т.е. независимых друг от друга, подзадач. Решение каждой подзадачи осуществляется на отдельном процессоре МВС.
Для рассматриваемой нами задачи (1) можно легко выделить 32 независимые подзадачи: очевидно, что это возведение в куб первых 32 натуральных чисел:
. (2)
Таким образом, мы можем поручить каждому из имеющихся в нашем распоряжении процессоров решение одной из задач (2). Для получения окончательного ответа нам необходимо просуммировать результаты, полученные на отдельных процессорах. Эту операцию будем выполнять на одном процессоре.
Какие же дополнительные функции нам потребуются, чтобы адаптировать рассмотренную выше программу для МВС? Прежде всего, это функции, позволяющие передавать данные от одного процессора к другому. Введем две такие гипотетические функции: Send и Recv. Применительно к рассматриваемой нами задаче эти функции могут иметь следующие прототипы:
void Send(int sbuf, int dest);
void Recv(int rbuf, int source);
Первая функция (Send) осуществляет передачу данных типа int, связанных с идентификатором sbuf на текущем процессоре, процессору с номером dest. Вторая функция (Recv) принимает данные типа int от процессора с номером source и связывает их с идентификатором rbuf на текущем процессоре. При этом под текущим понимается процессор, вызвавший ту или другую функцию.
При выполнении параллельной программы на МВС необходимо также знать порядковый номер каждого процессора и общее количество процессоров, которые задействованы в решении задачи. Именно через порядковый номер обычно происходит распределение подзадач по процессорам. Нумерация процессоров традиционно начинается с 0. Поэтому помимо уже введенных функций нам потребуются еще две функции:
void Rank(int MyID);
void Size(int NumProc);
Функция Rank(MyID) записывает в MyID номер текущего процессора, а функция Size(NumProc) возвращает в NumProc общее количество активных процессоров.
Теперь с помощью введенных функций мы можем написать параллельную программу для решения задачи (1):
#include
int main(int argc, char **argv)
{
int S=0; /* искомая сумма */
int k; /* переменная цикла */
int SAdd; /* вспомогательная переменная */
int NumProc; /* количество процессоров */
int MyID; /* номер процессора */
/* определение количества
активных процессоров */
Size(NumProc);
/* определение номера текущего процессора */
Rank(MyID);
/* вычисление куба числа
на каждом процессоре */
S=MyID+1;
S=S*S*S;
/* передача результатов со всех процессоров
на процессор с номером 0 и вычисление на
этом процессоре окончательной суммы */
if (MyID!=0) Send(S,0);
else
{
for (k=1; k<=NumProc-1; k++)
{
Recv(SAdd,k);
S+=SAdd;
}
/*печать результата на экран */
printf(“Sum is equal to %d”,S);
}
/* нормальное завершение работы программы */
return 0;
}
Каким же образом будет выполняться данная параллельная программа на МВС? Сразу необходимо понять следующее: в принятой нами модели параллельного программирования (забегая чуть вперед отметим, что именно такая модель лежит в основе MPI) весь программный код выполняется каждым процессором, но со своим набором данных. Другим словами, каждый процессор имеет свою копию программы, которую он и выполняет. Такая технология параллельного программирования носит название технологии разделения по данным. Так, в нашем случае после операции возведения в куб в переменной S на разных процессорах будут храниться разные числа: скажем, на втором процессоре это будет 27, а на девятом – 1000 (напомним, что процессоры нумеруются с 0!). Номер процессора хранится в переменной MyID.
Обратим также внимание на следующий весьма важный момент: если в параллельной программе необходимо выделить участок кода, который должен выполняться не всеми процессорами, а их частью или вообще одним процессором, то для этого используются условные операторы (структуры выбора языка С), в логические условия которых обязательно входит идентификатор номера процессора (в нашем случае MyID). Так, в приведенном примере функция Send будет вызвана всеми процессорами, кроме нулевого, а функция Recv, наоборот, будет вызвана только нулевым процессором, но 31 раз.
Далее отметим, что реализованный в нашей параллельной программе вычислительный алгоритм несколько отличается от алгоритма, по которому написана последовательная программа. А именно: в параллельной программе появилась дополнительная операция сложения – увеличение на единицу номера процессора. Поэтому количество вычислительных операций в последовательной и параллельной программе несколько различаются. Такая ситуация является достаточно типичной: при распараллеливании практически никогда не удается сохранить количество операций исходного последовательного алгоритма – в параллельном алгоритме оно всегда оказывается несколько больше.
В приведенном примере вывод результатов на экран осуществляет только нулевой процессор. Следует отметить, что стандарт MPI не оговаривает правила ввода-вывода и ряд его реализаций (в том числе и MPICH) допускают ввод и вывод данных через любой процессоор. Однако существуют реализации MPI не поддерживающие этот режим. Поэтому в данном пособии мы будем придерживаться следующего правила: ввод-вывод данных и весь диалог с пользователем в параллельной программе осуществляется только через нулевой процессор.
Подводя общий итог отметим, что для написания простейшей параллельной программы нам потребовалось ввести всего четыре гипотетические функции межпроцессорного обмена данными. Теоретически этих функций достаточно для написания любой параллельной программы. Тем не менее библиотека MPI содержит более 120 функций. Нетрудно догадаться, что такое многообразие обусловлено необходимостью создавать не просто параллельные программы, а эффективные параллельные программы. Поэтому прежде чем перейти к изучению самой библиотеки MPI остановимся кратко на вопросах оценки эффективности параллельных программ и факторах, влияющих на эту эффективность.
1.2. Оценка эффективности параллельной программы
Само понятие эффективности параллельного алгоритма или программы всегда необходимо рассматривать в тесной связи с основной целью распараллеливания. Все задачи, решаемые на МВС, условно можно разделить на две группы:
1) задачи, решение которых на однопроцессорных компьютерах в принципе возможно, однако требует больших временных затрат (осредненная оценка здесь примерно такова: задачу целесообразно распараллеливать, если время ее решения на современной однопроцессорной машине превышает 5-7 суток); к этой же группе следует отнести задачи, которые необходимо решать многократно на различных наборах исходных данных;
2) задачи, для решения которых требуются вычислительные ресурсы, существенно превышающие возможности однопроцессорной техники (при этом во внимание принимается не только общий объем вычислений, но и необходимое количество оперативной и дисковой памяти).
Соответственно, с точки зрения конечного пользователя параллельная программа для решения задачи первой группы будет эффективна, если она позволит добиться существенного выигрыша по времени (в пять и более раз). В то же время при решении задач второй группы на первое место выходит оценка равномерности загрузки ресурсов многопроцессорной системы.
Решение задач первой группы осуществляется, как правило, на МВС с небольшим количеством процессоров, и здесь все большее распространение получают вычислительные кластеры, собранные на основе традиционных одно- или двухпроцессорных персональных компьютеров. Для решения задач второй группы применяются мощные суперкомпьютеры, входящие в список самых высокопроизводительных вычислительных систем в мире Top-500 (http://www.top500.org), которые состоят из сотен и тысяч процессоров. В данном пособии мы будем ориентироваться на решение задач первой группы.
Каким же образом можно оценить положительный эффект от перехода с последовательной программы к параллельной?
Вернемся к примеру, рассмотренному в предыдущем параграфе. Проведем оценку общего времени вычислений для последовательной и параллельной программы. Пусть производительность одного процессора в рассматриваемых нами системах равна операций в секунду. Будем считать, что время, затрачиваемое процессором на выполнение операций сложения и умножения, одинаково. В последовательной программе выполняется 64 операции умножения и 32 операции сложения. Таким образом, общее время вычислений (без учета времени вывода результатов на экран) составит
.
Несложно убедиться, что для современных процессоров это время оказывается весьма и весьма малым. В самом деле, для приближенной оценки реальной (не пиковой!) производительности современных процессоров можно использовать величину, равную половине его тактовой частоты*). Так, если в нашем распоряжении имеется процессор класса Pentium 4 с тактовой частотой 3,2 ГГц, то его среднюю производительность можно оценить как GFlops (миллиардов операций с плавающей точкой в секунду). Подставляя данное значение производительности в приведенную выше формулу получим, что с решением нашей последовательной задачи указанный процессор справится за 6010-9 с или 60 нс.
Теперь оценим время, за которое выполнится наш параллельный алгоритм. В этом случае у нас имеется два типа операций: последовательные и параллельные. Параллельно у нас выполняются первая операция суммирования и две операции умножения (всего 96 операций, выполняющиеся параллельно на 32 процессорах), а последовательно (на нулевом процессоре) выполняются последние операции сложения (всего 31 операция). Таким образом, время работы параллельной программы будет складываться из времени работы ее параллельной и последовательной частей:
.
Таким образом, мы ожидаем, что наша параллельная программа будет работать в
раза быстрее, чем ее последовательный аналог.
Отношение времени выполнения последовательной программы ко времени выполнения параллельной программы на процессорах называется ускорением при использовании процессоров:
.
На практике эту величину вычислить можно не всегда, поскольку последовательной программы может просто не быть. Поэтому достаточно часто используется оценка ускорения вида
,
где – время выполнения параллельной программы на одном процессоре (в большинстве случаев оно превышает в силу уже упоминавшегося повышения количества операций в параллельном алгоритме по сравнению с последовательным).
Для рассматриваемого примера получим
Видно, что оценка оказалась более оптимистичной (почти на треть), чем более аккуратная оценка .
Можно получить теоретическую оценку максимально возможного ускорения . Пусть – общее количество операций в параллельной программе (предполагается, что не зависит от числа процессоров ), – доля этих операций, выполняемых последовательно, – как и прежде, производительность отдельного процессора. Тогда справедливы оценки:
.
Данная оценка может оказаться весьма грубой, поскольку не учитывает время, затрачиваемое на передачу данных между процессорами.
Таким образом, в общем случае имеем
.
Это соотношение носит название закона Амдаля.
Из закона Амдаля следует, что для получения больших ускорений доля последовательных операций в параллельной программе должна быть весьма малой. Пусть мы хотим получить ускорение в 50 раз на 100-процессоорной системе. Тогда из закона Амдаля следует, что величина должна быть порядка 0,01, т.е. программа должна быть распараллелена на 99%! Добиться такого уровня распараллеливания в практических задачах бывает достаточно сложно.
Другим важным параметром, с помощью которого оценивается качество параллельной программы, является эффективность использования процессоров:
.
Данный параметр показывает среднюю загруженность процессоров при работе параллельной программы.
Для нашего примера имеем
Таким образом, почти 90 % времени процессоры МВС будут простаивать.
Следует отметить, что оценка (или ) является средней. В нашем примере нулевой процессор будет загружен на 100 %, поскольку он работает постоянно, в то время как время работы остальных процессоров составит порядка 8,8 % этого времени.
Теперь обратимся к другому, возможно, самому важному вопросу, на который необходимо обращать внимание при написании параллельной программы – на организацию обмена данными. Во всех предыдущих оценках мы пренебрегали временем передачи данных. Тем не менее, оно может оказаться весьма значительным. Так, если мы запустим параллельную программу нашего примера, скажем, на Alpha-кластере УГАТУ, то мы не только не получим ожидаемого ускорения, но время работы параллельной программы окажется примерно в 30 000 раз больше, чем последовательного аналога! Причиной этого будут временные задержки при передаче данных.
В общем случае время передачи данных зависит от многих факторов: пропускной способности сети передачи данных, параметров коммутирующего оборудования, принятой схемы маршрутизации, топологии вычислительной системы, количества и типа передаваемых данных, используемых для коммуникации функций и т.д.
Так, уже упоминавшийся Alpha-кластер УГАТУ имеет топологию “звезда”, коммуникационную среду Fast Ethernet 100 Мбит/с и коммутатор со временем латентности равным (100-300)10-6 с. В рассматриваемой нами простейшей параллельной программе у нас имеется 31 передача целочисленного значения от каждого ненулевого процессора нулевому. Соответственно, время собственно передачи данных (без учета времени подготовки сообщения и передачи служебной информации) составит
нс.
В приведенной формуле – размер передаваемого сообщения (количество элементов определенного типа), – битовый размер типа, – пропускная способность сети коммуникации.
Между двумя последовательными передачами коммутатор дает случайную задержку, называемую временем латентности:
мкс.
Таким образом, общее время передачи можно оценить как сумму среднего времени латентности и времени собственно передачи данных:
.
Для нашего примера , поскольку . Всего осуществляется передача, поэтому суммарное время, затрачиваемое на коммуникации в параллельной программе, равно
мкс = с.
Общее время выполнения параллельной программы складывается из времени расчетов и времени коммуникаций :
.
Производительность процессора Alpha-кластера оценивается как GFlops, поэтому время выполнения последовательной программы будет оцениваться величиной с. Следовательно, в рассматриваемом примере время расчетов , поэтому . Обратим внимание на то, что время работы всей последовательной программы оказывается сопоставимо со временем передачи одного числа. Таким образом, для ускорения имеем
,
т.е. получаем уже упоминавшейся ранее результат.
Как же можно повысить эффективность рассмотренной параллельной программы? Очевидно, что необходимо уменьшить количество передач данных, а для этого необходимо ввести новые способы коммуникации. Они будут подробно рассмотрены в последующих главах настоящего пособия, здесь же ограничимся замечанием, что в MPI существуют функции, позволяющие не только выполнять операции сборки данных на одном процессоре, но и сразу производить их суммирование.
Разобранный пример позволяет сформулировать ряд требований, выполнение которых является необходимым для написания любой параллельной программы:
1) объем вычислений, выполняемых на отдельном процессоре МВС, должен существенно превышать время, затрачиваемое на передачу данных с этого процессора; для программы в целом должно выполняться условие
;
2) количество передач данных должно быть сведено к минимуму;
3) доля последовательного кода в параллельной программе должна быть как можно меньше;
4) объем вычислений на каждом процессоре должен быть примерно одинаковым, что обеспечит равномерную загрузку процессоров.
2. ОСНОВЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ
СРЕДСТВАМИ MPI
2.1. Базовые функции MPI
Теперь обратимся к основной части настоящего пособия – рассмотрению интерфейса передачи сообщений MPI (Message Passing Interface). Первый стандарт интерфейса появился в 1994 году и за прошедшие 10 лет MPI стал наиболее распространенным средством разработки параллельных приложений. В немалой степени этому способствовало наличие не только коммерческих, но и свободно распространяемых его реализаций, к которым, в частности, относится MPICH (последние версии доступны для свободной загрузки с сайта www.mpi.org) . Существуют версии MPICH как для операционных систем семейства Unix/Linux, так и для Windows NT/2000/XP.
Физически MPI представляет собой специальную библиотеку функций, которые отвечают за организацию взаимодействия между процессорами системы. Эти функции могут вызываться из обычных программ, написанных на языках С/С++ или Fortran. Стандарт MPI-1.1 [1] предусматривает обязательное наличие в библиотеке 129 функций. Тем не менее, как отмечает в своей книге Ян Фостер [2], для успешного написания практически любого параллельного приложения достаточно 24 функций MPI. Более того, формально любая параллельная программа может быть написана с использованием всего шести (!) функций MPI (вопрос эффективности такой программы, естественно, не обсуждается). Что же это за функции? На самом деле, с четырьмя из них мы уже знакомы (они введены в предыдущей главе): это функции передачи и приема сообщений, а также определения номера процессора и количества процессоров. Как нетрудно догадаться, две другие функции – это функции инициализации и завершения MPI. Таким образом, имеем следующий набор из шести базовых функций MPI:
MPI_Init – инициализация параллельной части приложения;
MPI_Finalize – завершение параллельной части приложения;
MPI_Comm_size – определение числа процессов;
MPI_Comm_rank – определение номера процесса;
MPI_Send – передача сообщения от одного процесса другому;
MPI_Recv – прием сообщения от одного процесса другим.
Читатель, наверное, заметил, что при описании назначения функций вместо слова “процессор” было использовано слово “процесс”. Это не случайно. MPI оперирует понятием именно процесса, а не процессора, и любая параллельная программа рассматривается как совокупность независимых процессов. При этом (и это еще одно важное достоинство MPI) процессы не обязаны выполняться на различных процессорах. Это дает возможность проводить первоначальную отладку параллельных программ на обычных однопроцессорных персональных компьютерах. В этом случае все процессы выполняются на одном доступном процессоре в режиме разделения времени, однако все функции MPI, отвечающие за передачу данных, работают корректно. Таким образом, реализуется режим эмуляции работы многопроцессорной системы. При запуске параллельной MPI-программы на многопроцессорной системе средствами операционной системы происходит распределение процессов по доступным процессорам. Количество процессов, которые выделяются параллельной программе, указывается пользователем в момент запуска программы на выполнение (см. приложение 1).
Прежде чем перейти к рассмотрению синтаксиса названных шести базовых функций MPI, вернемся к рассмотренному в предыдущей главе примеру программы вычисления суммы (1.1) и перепишем программный код в терминах параллельной MPI-программы.
#include
#include “mpi.h”
int main(int argc, char *argv[])
{
int S=0; /* искомая сумма */
int k; /* переменная цикла */
int SAdd; /* вспомогательная переменная */
int NumProc; /* количество процессов */
int MyID; /* номер процесса */
int tag; /* метка сообщения */
MPI_Status status; /* структура, содержащая
информацию о полученном
сообщении */
/* инициализация MPI */
MPI_Init(&argc, &argv);
/* определение количества
активных процессов */
MPI_Comm_size(MPI_COMM_WORLD, &NumProc);
/* определение номера текущего процессора */
MPI_Comm_rank(MPI_COMM_WORLD, &MyID);
/* вычисление куба числа
на каждом процессоре */
S=MyID+1;
S=S*S*S;
/* передача результатов со всех процессоров
на процессор с номером 0 и вычисление на
этом процессоре окончательной суммы */
if (MyID!=0)
tag=MyID+777;
MPI_Send(&S,1,MPI_INT,0,tag,
MPI_COMM_WORLD);
else
{
for (k=1; k<=NumProc-1; k++)
{
tag=k+777;
MPI_Recv(&SAdd,1,MPI_INT,k,tag,
MPI_COMM_WORLD,&status);
S+=SAdd;
}
/* печать результата на экран */
printf(“Sum is equal to %d”,S);
}
/* завершение работы с MPI */
MPI_Finalize();
/* нормальное завершение работы программы */
return 0;
}
Видно, что программный код не претерпел серьезных изменений, увеличилось лишь число аргументов в функциях отправки и приема сообщений, которые мы сейчас и рассмотрим. Но прежде остановимся кратко на принятой в MPI нотации записи.
Имена элементов MPI являются составными и отражают иерархическую структуру интерфейса. Любой элемент, будь то функция, константа или собственный тип данных, начинается с префикса “MPI_”. Затем могут следовать сокращенные названия группы и подгруппы, к которым относится элемент, и, наконец, в конце стоит собственное имя элемента, отражающее его функциональное назначение. Все составляющие полного имени разделяются знаком нижнего подчеркивания. Поскольку язык С чувствителен к регистру, для него принят следующий стандарт записи: предопределенные константы и названия типов данных записываются заглавными буквами, а в именах функций и типов после префикса MPI_ первая буква заглавная, остальные – строчные. Например,
MPI_COMM_WORLD – предопределенный коммуникатор (константа);
MPI_INT – тип данных;
MPI_Comm_size – функция;
MPI_Datatype – специальный тип, который имеют все типы
данных MPI, включая создаваемые
пользователем.
Все имена элементов MPI описаны в заголовочном файле mpi.h, поэтому при написании параллельной MPI-программы этот файл обязательно должен быть подключен соответствующей препроцессорной директивой:
#include “mpi.h”
Перейдем теперь к детальному рассмотрению базовых MPI-функций.
▲ int MPI_Init(int *argc, char **argv[]);
Функция инициализации MPI. Может использоваться в любой параллельной программе только один раз и размещается в начале параллельного участка кода программы. Аргументы функции совпадают с аргументами главной функции программы main, в которой argc – число аргументов командной строки, argv[] – массив строк, содержащих аргументы командной строки. В частности, при запуске параллельной MPI программы с помощью команды mpirun одним из обязательных аргументов командной строки является количество процессов, выделяемых программе (см. приложение). Поэтому указание параметров argc и argv[] в main является обязательным. Возвращаемые функцией MPI_Init значения являются предопределенными константами:
MPI_SUCCESS – возвращается в случае успешного
выполнения,
MPI_ERR_ARG – ошибка неправильного задания аргумента,
MPI_ERR_INTERN – внутренняя ошибка (нехватка памяти),
MPI_ERR_UNKNOWN – неизвестная ошибка.
Только после успешного выполнения функции MPI_Init возможна работа с другими элементами интерфейса MPI.
Во избежание возникновения непредвиденных ошибок рекомендуется вызывать MPI_Init в самом начале программы, до выполнения каких-либо вычислительных операций или операций ввода/вывода.
▲ int MPI_Finalize(void);
Функция завершения работы с MPI, которая помещается в конце параллельного участка кода программы (void, как обычно, указывает на то, что функция не принимает аргументов). После этой функции обращение к любым элементам MPI невозможно.
Во избежание ошибок MPI_Finalize рекомендуется вызывать в самом конце параллельной программы, перед завершением ее работы.
▲ int MPI_Comm_size(MPI_Comm comm, int* size);
Функция определения количества процессов size в коммуникационной группе (communication domain) с коммуникатором comm. Имя коммуникатора comm является входным параметром функции, а целочисленный идентификатор size – выходным параметром.
Здесь кратко остановимся на понятиях коммуникационной группы и коммуникатора. В MPI реализована возможность организации групп процессов, которые называются коммуникационными группами. Подавляющее большинство функций MPI имеет в качестве области действия коммуникационную группу, т.е. организуют взаимодействие лишь между теми процессами, которые входят в одну группу. Каждая коммуникационная группа должна иметь свой уникальный идентификатор, называемый коммуникатором, который является входным параметром большинства функций MPI. Коммуникаторы являются идентификаторами специального типа данных MPI_Comm. Допускается определение нескольких коммуникаторов для одной и той же коммуникационной группы, при этом происходит дублирование исходной группы. Создание новых коммуникационных групп происходит всегда на основе уже существующих. В пределах каждой коммуникационной группы процессы имеют независимую последовательную нумерацию, начинающуюся с 0.
При запуске параллельной программы всегда автоматически создается коммуникационная группа, которая включает в себя все выделенные программе процессы. Эта группа имеет предопределенный коммуникатор MPI_COMM_WORLD. На практике большинство MPI-программ ограничиваются работой только с исходной группой процессов и поэтому используют только этот предопределенный коммуникатор.
▲ int MPI_Comm_rank (MPI_comm comm, int* rank);
Функция, возвращающая номер rank вызвавшего ее процесса, входящего в коммуникационную группу с коммуникатором comm.
▲ int MPI_Send(void* sbuf, int count,
MPI_Datatype datatype, int dest,
int tag, MPI_Comm comm);
Блокирующая функция передачи данных. Все параметры функции являются входными параметрами:
• sbuf – адрес в памяти, начиная с которого размеща-
ются передаваемые данные;
• count – количество передаваемых элементов;
• datatype – тип передаваемых элементов;
• dest – номер процесса-получателя сообщения;
• tag – метка передаваемого сообщения;
• comm – коммуникатор.
Х а р а к т е р н ы е о с о б е н н о с т и ф у н к ц и и.
1. При передаче скалярных данных в качестве sbuf традиционно используется ссылка на передаваемое значение (см. приведенный выше пример).
2. Допускается задание нулевого значения в качестве количества передаваемых элементов count; в этом случае, очевидно, ничего не передается.
3. В качестве datatype может использоваться либо созданный пользователем тип данных типа MPI_Datatype, либо одна из предопределенных констант типа:
4. В качестве значения dest может использоваться любое неотрицательное целое число от 0 до np-1, где np – общее количество процессов в коммуникационной группе с заданным коммуникатором comm. При этом разрешается указывать в качестве dest номер процесса-отправителя сообщения, т.е. процессу разрешается передавать сообщения самому себе.
5. Для того чтобы различать сообщения, с которыми работает процесс, каждому сообщению назначается своя уникальная метка tag. В качестве метки может использоваться любое целое число из диапазона от 0 до 32767, либо целочисленное выражение, принимающее значение в этом диапазоне. Достаточно часто для обеспечения уникальности метки сообщения используется следущее правило ее построения:
номер процесса + произвольная константа
Так, в приведенной выше программе
tag = MyID+777
6. Принадлежность функции MPI_Send к типу блокирующих функций приема-передачи данных означает, что изменение значений в переменных, связанных с sbuf, возможно сразу же после вызова функции. При этом MPI_Send возвращает управление процессу не дожидаясь окончания передачи данных.
▲ int MPI_Recv(void* rbuf, int count,
MPI_Datatype datatype, int source,
int tag, MPI_comm comm,
MPI_Status *status);
Блокирующая функция приема данных. Параметры функции аналогичны описанным выше параметра функции MPI_Send.
Входные параметры функции:
• count – количество получаемых элементов;
• datatype – тип получаемых элементов;
• source – номер процесса-отправителя сообщения;
• tag – метка принимаемого сообщения;
• comm – коммуникатор.
Выходные параметры функции:
• rbuf – адрес в памяти, начиная с которого размещаются
принимаемые данные;
• status – структура, содержащая информацию о принятом сообщении.
Х а р а к т е р н ы е о с о б е н н о с т и ф у н к ц и и.
1. Принадлежность функции MPI_Recv к типу блокирующих функций приема-передачи данных гарантирует, что после успешного ее завершения все элементы сообщения приняты и расположены в буфере rbuf. До тех пор, пока сообщение полностью не принято, процесс-получатель не выполняет дальнейших операций.
2. Число элементов в принимаемом сообщении может быть меньше (но не больше!) заданного значения count. В этом случае стандартом MPI гарантируется, что в буфере приема rbuf будут изменены только те элементы, которые соответствуют принимаемому сообщению.
3. На практике иногда возникают ситуации, когда заранее неизвестен номер процесса-отправителя сообщения или/и метка принимаемого сообщения. В этом случае можно использовать предопределенные константы MPI (так называемые джокеры):
◦ MPI_ANY_SOURCE – указывается на месте номера процесса-отправителя source и означает готовность принять сообщение от любого процесса данной коммуникационной группы;
◦ MPI_ANY_TAG – указывается на месте метки сообщения tag и означает готовность принять сообщение с любым допустимым значением метки.
4. Для определения номера процесса-отправителя и метки сообщения служит структура status. Эта структура имеет три поля:
Status.MPI_SOURCE
Status.MPI_TAG
Status.MPI_ERROR
которые заполняются при приеме сообщения и содержат, соответственно, номер процесса-отправителя сообщения, метку принимаемого сообщения и код завершения приема.
2.2. Понятие клинча и совмещение приема
и передачи данных
В любой параллельной программе последовательность приема и передачи данных должна быть строго определенной, зависящей от используемых средств распараллеливания. Нарушение этого порядка, часто допускаемое начинающими программистами, может привести к так называемому клинчу – зависанию программы вследствие невозможности выполнения операций приема-передачи данных.
Рассмотрим следующую ситуацию. Пусть имеются два процесса, которые должны обменяться данными. Для простоты изложения временно забудем про функции MPI и вновь обратимся к введенным в главе 1 гипотетическим функциям передачи и приема данных Send и Recv. Существует три различных варианта последовательности вызова функций в процессах:
1) Процесс 1 Процесс 2
Recv(r1,2); Recv(r2,1);
Send(s1,2); Send(s2,1);
2) Процесс 1 Процесс 2
Send(s1,2); Send(s2,1);
Recv(r1,2); Recv(r2,1);
3) Процесс 1 Процесс 2
Send(s1,2); Recv(r2,1);
Recv(r1,2); Send(s2,1);
Работоспособность вариантов зависит от того, являются ли функции блокирующими и буферизованными.
В первом варианте если функция Recv является блокирующей (как в случае MPI_Recv), то она не вернет управление процессу до тех пор, пока не получит сообщение, и поэтому функция Send не сможет приступить к отправке данных. В результате оба процесса будут ожидать прихода сообщений друг от друга, но ни один из них не сможет отправить сообщение, поэтому программа зависнет – возникнет клинч. В то же время если функция Recv будет неблокирующей, то прием и передача данных пройдут успешно.
Во втором варианте клинч возникнет в случае, когда функция Send дожидается отправки сообщения процессу-получателю. В MPI функция MPI_Send является хоть и блокирующей, но буферизованной: она не дожидается готовности другого процесса к приему сообщения (т.е. вызова соответствующей функции вида MPI_Recv), а помещает данные во временный системный буфер и возвращает управление процессу немедленно. В результате при вызове MPI_Recv получит данные именно из этого промежуточного системного буфера, а не из пользовательского, и клинч не возникнет.
Третий вариант является самым безопасным и наиболее правильным – он не приводит к клинчу ни в каком случае.
Рассмотренная ситуация является сильноидеализированной. На практике параллельные программы обычно пишутся таким образом, что могут запускаться на различном количестве процессов, при этом функции приема и передачи данных могут оказаться в программном коде сильно разнесенными. Это значительно затрудняет контроль за последовательностью вызова функций и делает клинч вполне реальным событием.
Для предотвращения клинча в MPI существует ряд механизмов. Одним из наиболее простых, но эффективных способов является использование специальной функции совмещенного приема/передачи:
▲ int MPI_Sendrecv(void* sbuf, int scount,
MPI_Datatype sdatatype,
int dest, int stag,
void* rbuf, int rcount,
MPI_Datatype rdatatype,
int source, int rtag,
MPI_comm comm,
MPI_Status *status);
Входные параметры функции:
• sbuf – адрес в памяти, начиная с которого
размещаются передаваемые данные;
• scount – количество передаваемых элементов;
• sdatatype – тип отправляемых элементов;
• dest – номер процесса-получателя сообщения;
• stag – метка отправляемого сообщения;
• rcount – количество получаемых элементов;
• rdatatype – тип получаемых элементов;
• source – номер процесса-отправителя сообщения;
• rtag – метка принимаемого сообщения;
• comm – коммуникатор.
Выходные параметры функции:
• rbuf – адрес в памяти, начиная с которого размещаются
принимаемые данные;
• status – структура, содержащая информацию о принятом
сообщении.
Таким образом, первые пять параметров этой функции соответствуют параметрам отправляемого сообщения и аналогичны параметрам функции MPI_Send, а следующие семь идентичны параметрам функции MPI_Recv.
Х а р а к т е р н ы е о с о б е н н о с т и ф у н к ц и и.
1. Функция MPI_Sendrecv использует для приема и передачи один и тот же коммуникатор.
2. Порядок приема и передачи данных, не приводящих к клинчу, выбирается системой автоматически.
3. Функция MPI_Sendrecv совместима с функциями MPI_Send и MPI_Recv, т.е. сообщение, посланное с помощью MPI_Sendrecv, может быть принято функцией MPI_Recv и, наоборот, сообщение, посланное MPI_Send, может быть принято функцией MPI_Sendrecv.
Другим механизмом MPI, позволяющим избежать клинча, являются неблокирующие функции. Отметим, что грамотное использование таких функций может существенно повысить эффективность работы параллельной программы. Однако их использование требует определенных навыков параллельного программирования, поэтому рассмотрение этих функций не является предметом данного пособия. Заинтересованный читатель может найти полное описание неблокирующих функций в стандарте MPI [1] и монографиях [3, 4].
2.3. Функции коллективного взаимодействия
Рассмотренные ранее функции MPI_Send, MPI_Recv и MPI_Sendrecv относятся к функциям точечного обмена данными, в которых всегда участвуют только два процесса. Между тем в MPI существует достаточно большая группа функций, называемых коллективными, которые организуют взаимодействие одновременно между всеми процессами группы. Все эти функции в соответствии со стандартом делятся на три типа:
1) функции коллективного обмена данными;
2) функции синхронизации – барьеры;
3) функции распределенных операций.
Обязательным аргументом всех коллективных функций является коммуникатор, связанный с коммуникационной группой, включающей в себя все взаимодействующие процессы. Для корректной работы любая коллективная функция должна быть вызвана из всех процессов коммуникационной группы, поэтому ее вызов всегда производится из области программы, доступной всем процессам группы. Если коллективную функцию необходимо вызвать не для всех процессов группы, а лишь для некоторой их части, то для этого необходимо создать новую временную коммуникационную группу со своим коммуникатором, включающую лишь требуемые процессы. Особо отметим, что коллективные функции не совместимы с функциями точечного обмена данными.
2.3.1. Функции коллективного обмена данными
В MPI имеется девять основных функций, предназначенных для обмена данными между всеми процессами группы, которые объединяются в пять категорий по виду коммуникационных операций (см. табл. 2.1).
Коллективные функции обмена данными имеют целый ряд особенностей, отличающих их от функции точечного обмена данными.
1. На прием и/или передачу работают одновременно все процессы коммуникационной группы, коммуникатор которой указан в качестве параметра функции; при этом сообщения передаются не по указанному коммуникатору, а по созданному системой временному коммуникатору-дупликату, что позволяет изолировать потоки данных коллективных функций друг от друга и от потоков, созданных функциями точечного обмена данными.
2. Метки сообщений указываются не пользователем, а назначаются автоматически системой MPI.
3. Коллективная функция может выполнять одновременно и прием, и передачу данных, причем в разных процессах та или иная часть может игнорироваться.
4. Все параметры функции (за исключением адресов буферов и, возможно, размеров сообщений) идентичны во всех процессах группы.
Теперь рассмотрим подробнее каждую из перечисленных в таблице 2.1 функций. Для иллюстрации действий, выполняемых каждой функцией, мы воспользуемся схемой, предложенной в стандарте MPI и имеющей вид, показанный на рис. 2.1. Строки на схеме соответствуют процессам, столбцы – данным, хранящимся на процессах. Слева показывается начальное распределение данных, справа – распределение после выполнения коллективной функции.
Рис. 2.1. Схема действия коллективной функции
Функция MPI_Bcast предназначена для рассылки данных, хранящихся на одном процессе, всем остальным процессам группы (см. схему на рис. 2.2):
▲ int MPI_Bcast(void *buf, int count,
MPI_Datatype datatype, int root,
MPI_Comm comm);
Рис. 2.2. Схема действия функции MPI_Bcast
Входные параметры функции:
• buf – адрес в памяти, начиная с которого
размещаются передаваемые данные;
• count – количество рассылаемых элементов;
• datatype – тип отправляемых данных;
• root – номер процесса-отправителя сообщения;
• comm – коммуникатор.
Таким образом, функция MPI_Bcast рассылает сообщение, хранящееся в буфере buf размером count элементов типа datatype из процесса, имеющего в коммуникационной группе с коммуникатором comm номер root, во все остальные процессы группы.
Функция MPI_Bcast осуществляет рассылку сообщения всем процессам группы, включая и процесс-отправитель.
П р и м е р.
Пусть требуется передать значения целочисленного массива a, состоящего из пяти элементов, из нулевого процесса во все остальные процессы группы. С помощью функции MPI_Bcast это может быть реализовано следующим образом:
int a[5]
…
MPI_Bcast(a, 5, MPI_INT, 0, MPI_COMM_WORLD)
Такого же результата можно добиться и с использованием функций точечного обмена данными, однако в этом случае значительно увеличится объем кода и возрастет количество коммуникационных операций:
int a[5]
int i;
…
if (MyID == 0)
for (i=0; i
MPI_Send(a,5,MPI_INT,i,777+i,
MPI_COMM_WORLD);
MPI_Recv(a,5,MPI_INT,0,777+MyID,
MPI_COMM_WORLD,&status);
Здесь, как и в приведенных ранее примерах, NumProc – количество процессов в основной группе с коммуникатором MPI_COMM_WORLD, MyID – номер процесса. ■
Для сбора данных со всех процессов на одном используется так называемый "совок" – функция MPI_Gather (см. рис. 2.3):
▲ int MPI_Gather(void *sbuf, int scount,
MPI_Datatype stype, void *rbuf,
int rcount, MPI_Datatype rtype,
int root, MPI_Comm comm);
Рис. 2.3. Схема действия функции MPI_Gather
Входные параметры функции:
• sbuf – адрес в памяти на каждом процессе, начиная с
которого размещаются отправляемые данные;
• scount – количество элементов, отправляемых с каждо-
го процесса;
• stype – тип отправляемых данных;
• rcount – количество принимаемых элементов от каж-
дого процесса;
• rtype – тип принимаемых данных;
• root – номер процесса, на котором осуществляется
сборка сообщений;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти на процессе с номером root,
начиная с которого размещаются принимаемые
сообщения.
Таким образом, функция MPI_Gather собирает в буфер rbuf процесса root буферы sbuf со всех процессов.
Х а р а к т е р н ы е о с о б е н н о с т и ф у н к ц и и.
1. Процесс-приемник сообщения root также отправляет данные самому себе.
2. Значение rcount в процессе root представляет собой длину сообщения, получаемого от каждого процесса, а не суммарную длину сообщений от всех процессов.
3. Принимаемые сообщения располагаются в приемном буфере rbuf подряд в порядке возрастания номеров процессов, от которых они получены.
П р и м е р.
Пусть во всех процессах группы, состоящей из 5 процессов (NumProc = 5), имеется вещественный массив AS из 10 элементов. Требуется собрать все массивы в единый общий массив AR в порядке следования номеров процессов на процессе с номером 2. Тогда достаточно одного вызова функции MPI_Gather:
Функция MPI_Gather обладает двумя серьезными недостатками:
1) размер принимаемых сообщений от всех процессов должен быть одинаков;
2) отсутствует механизм позиционного размещения принимаемых сообщений.
Поэтому в MPI введен расширенный (векторный) вариант этой функции, свободный от названных недостатков:
▲ int MPI_Gatherv(void *sbuf, int scount,
MPI_Datatype stype,
void *rbuf, int *rcounts,
int *displs,
MPI_Datatype rtype,
int root, MPI_Comm comm);
Входные параметры функции:
• sbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются отправляемые данные;
• scount – количество элементов, отправляемых
с процесса;
• stype – тип отправляемых данных;
• rcounts – массив длин принимаемых от процессов
сообщений;
• displs – массив позиций в приемном буфере,
по которым размещаются принимаемые
сообщения;
• rtype – тип принимаемых данных;
• root – номер процесса, на котором осуществляется
сборка сообщений;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти на процессе с номером root,
начиная с которого размещаются принимаемые
сообщения.
Функция MPI_Gatherv позволяет отправлять разное количество элементов из различных процессов. Поэтому, в отличие от функции MPI_Gather, в процессе root параметры displs и rcounts являются уже не скалярами, а массивами.
Х а р а к т е р н ы е о с о б е н н о с т и ф у н к ц и и.
1. Массивы displs и rcounts являются целочисленными с размерностью, равной числу процессов в группе.
2. Длины сообщений в массиве rcounts и позиции размещения в массиве displs измеряются в количестве элементов типа rtype.
П р и м е р.
Пусть имеется группа из пяти процессов, в каждом из которых определен двумерный целочисленный массив AS[5][10]. Требуется осуществить выборочную сборку данных со всех процессов на третьем процессе по следующему правилу: с i-го процесса (i = 0,1…,4) выбираются (10–2i) первых значений из i-й строки массива AS и пересылаются в одномерный целочисленный массив AR. При этом расстояние между началами принятых блоков (в стандарте MPI для него используется обозначение stride) должно составлять 12 элементов (см. рис. 2.4).
Рис. 2.4. Схема сбора данных на процессе root
#include “mpi.h”
int main(int argc, char *argv[])
{
int NumProc; /* количество процессов */
int MyID; /* номер процесса */
int AS[5][10]; /* массив исходных данных */
int AR[60]; /* массив для размещения
принимаемых сообщений */
int rcounts[5]; /* массив длин сообщений */
int displs[5]; /* массив позиций,
по которым размещаются
принимаемые сообщения */
int stride=12; /* расстояние между
начальными позициями
размещения принятых
блоков */
int scount; /* количество элементов,
отправляемых с процесса */
int root=3; /* номер процесса,
на котором осуществляется
сборка сообщений */
int i; /* переменная цикла */
/* блок инициализации MPI */
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &NumProc);
MPI_Comm_rank(MPI_COMM_WORLD, &MyID);
. . .
/* определение количества элементов,
отсылаемых с каждого процесса */
scount=10-2*MyID;
/* заполнение массивов displs и rcounts
на процессе-сборщике сообщений */
if (MyID==root)
{
for (i=0; i
{
displs[i]=i*stride;
rcounts[i]=10–2*i;
}
}
/* сборка сообщений */
MPI_Gatherv(&AS[myid][0], scount, MPI_INT,
AR, rcounts, displs, MPI_INT,
root, MPI_COMM_WORLD);
. . .
/* завершение работы с MPI */
MPI_Finalize();
}
■
Обратной к MPI_Gather является функция MPI_Scatter – так называемый "разбрызгиватель" (см. рис. 2.5):
▲ int MPI_Scatter( void *sbuf, int scount,
MPI_Datatype stype, void *rbuf,
int rcount, MPI_Datatype rtype,
int root, MPI_Comm comm);
Рис. 2.5. Схема действия функции MPI_Scatter
Входные параметры функции:
• sbuf – адрес в памяти на процессе-отправителе сооб-
щения, начиная с которого размещаются от-
отправляемые данные;
• scount – количество элементов, отправляемых каждому
процессу;
• stype – тип отправляемых данных;
• rcount – количество элементов, принимаемых каждым
процессом (длина принимаемого сообщения);
• rtype – тип принимаемых данных;
• root – номер процесса-отправителя сообщения;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются принимаемые
сообщения.
Эта функция выполняет операцию, обратную MPI_Gather: сообщение от одного процесса с номером root разбивается на равные части, число которых рано числу процессов в группе, и каждая часть посылается соответствующему процессу.
Необходимо иметь в виду, что в переменную scount записывается длина не всего сообщения, а каждой его части.
П р и м е р.
Пусть необходимо вещественный массив AS, состоящий из 10 элементов и хранящийся на первом процессе, распределить между всеми процессами группы, состоящей из 5 процессов. В результате в каждый процесс пересылается 2 элемента, которые записываются в массив AR.
double AS[10], AR[2]
. . .
MPI_Scatter(AS, 2, MPI_DOUBLE, AR, 2,
MPI_DOUBLE, 1, MPI_COMM_WORLD)
. . .
■
Как и в случае с MPI_Gather, MPI_Scatter имеет векторный аналог, позволяющий разбивать исходное сообщение на части неравной длины, пересылаемые различным процессам:
▲ int MPI_Scatterv(void *sbuf, int *scounts,
int *displs,
MPI_Datatype stype,
void *rbuf, int rcount,
MPI_Datatype rtype,int root,
MPI_Comm comm);
Входные параметры функции:
• sbuf – адрес в памяти на процессе-отправителе
сообщения, начиная с которого размещаются
отправляемые данные;
• scounts – массив, содержащий количество элементов
в каждой части, на которые разбивается
сообщение;
• displs – массив позиций, определяющий начальные
положения каждой части сообщения;
• stype – тип отправляемых данных;
• rcount – количество элементов, принимаемых текущим
процессом (длина принимаемого сообщения);
• rtype – тип принимаемых данных;
• root – номер процесса-отправителя сообщения;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются принимаемые
сообщения.
Функция MPI_Scatterv является обратной для MPI_Gatherv.
П р и м е р.
Рассмотрим операцию, обратную рассмотренной в предыдущем примере. Пусть требуется распределить массив ASN[60] со структурой, аналогичной структуре массива AR[60] предыдущего примера (см. рис. 2.4 на с. 38), по массивам ARN[5][10] по правилу: на процессе с номером i сообщения размещаются с нулевой позиции i-й строки.
#include “mpi.h”
int main(int argc, char *argv[])
{
int NumProc; /* количество процессов */
int MyID; /* номер процесса */
int ASN[60]; /* массив исходных данных */
int ARN[5][10]; /* массив для размещения
принимаемого сообщения */
int scounts[5]; /* массив длин отдельных
сообщений (длин частей
исходного сообщения) */
int displs[5]; /* массив начальных позиций
частей, на которые
разбивается исходное
сообщение */
int stride=12; /* расстояние между
начальными позициями
размещения частей
исходного сообщения */
int rcount; /* количество элементов,
принимаемых процессом */
int root=3; /* номер процесса,
с которого осуществляется
рассылка */
int i; /* переменная цикла */
/* заполнение массивов displs и scounts
на процессе-отправителе сообщений */
if (MyID==root)
{
for (i=0; i
{
displs[i]=i*stride;
scounts[i]=10–2*i;
}
}
Дальнейшим обобщением функции MPI_Gather является функция MPI_Allgather, которая размещает собранные данные не на одном выделенном процессе root, а на всех процессах группы, участвующих в коллективной операции обмена данными (см. рис. 2.6):
▲ int MPI_Allgather(void *sbuf, int scount,
MPI_Datatype stype,
void *rbuf, int rcount,
MPI_Datatype rtype,
MPI_Comm comm);
Входные параметры функции:
• sbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются отправляемые данные;
• scount – количество элементов, отправляемых
с каждого процесса;
• stype – тип отправляемых данных;
• rcount – количество принимаемых элементов
от каждого процесса;
• rtype – тип принимаемых данных;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти, начиная с которого
размещаются принимаемые сообщения.
Как и предыдущие функции, MPI_Allgather имеет векторный аналог:
▲ int MPI_Allgatherv(void *sbuf, int scount,
MPI_Datatype stype,
void *rbuf, int *rcounts,
int *displs,
MPI_Datatype rtype,
MPI_Comm comm);
Входные параметры функции:
• sbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются отправляемые данные;
• scount – количество элементов, отправляемых
с процесса;
• stype – тип отправляемых данных;
• rcounts – массив длин принимаемых от процессов
сообщений;
• displs – массив позиций в приемном буфере,
по которым размещаются принимаемые
сообщения;
• rtype – тип принимаемых данных;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти, начиная с которого
размещаются принимаемые сообщения.
Результат применения MPI_Allgather (MPI_Allgatherv) аналогичен результату n последовательных вызовов функции MPI_Gather (MPI_Gatherv) со значениями root = 0, 1, …, n (n – число процессов в группе).
П р и м е р.
Пусть во всех процессах группы, состоящей из 5 процессов (NumProc = 5), имеется вещественный массив AS из 10 элементов. Требуется собрать все массивы в единый общий массив AR в порядке следования номеров процессов, и этот массив должен находиться на всех процессах группы.
double AS[10], AR[50];
…
MPI_Allgather(AS, 10, MPI_DOUBLE, AR, 10,
MPI_DOUBLE, MPI_COMM_WORLD);
■
Самым общим случаем коллективного обмена данными между процессами является тот, когда передаваемые сообщения в каждом процессе разбиваются на части, которые рассылаются всем процессам; каждый процесс получает части сообщений от всех остальных и формирует принимаемое сообщение в порядке очередности процессов (см. рис. 2.7). В MPI такое коллективное взаимодействие реализуется функцией
▲ int MPI_Alltoall(void *sbuf, int scount,
MPI_Datatype stype,
void *rbuf, int rcount,
MPI_Datatype rtype,
MPI_Comm comm);
Входные параметры функции:
• sbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются отправляемые данные;
• scount – количество элементов, отправляемых
с каждого процесса;
• stype – тип отправляемых данных;
• rcount – количество принимаемых элементов
от каждого процесса;
• rtype – тип принимаемых данных;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти, начиная с которого
размещаются принимаемые сообщения.
Рис. 2.7. Схема действия функции MPI_Alltoall
Векторный аналог этой функции, позволяющий разбивать сообщения на каждом процессе на неравные части с произвольным их взаимным расположением, имеет вид:
▲ int MPI_Alltoallv (void *sbuf, int *scounts,
int *sdispls,
MPI_Datatype stype,
void *rbuf, int *rcounts,
int *rdispls,
MPI_Datatype rtype,
MPI_Comm comm);
Входные параметры функции:
• sbuf – адрес в памяти на каждом процессе, начиная
с которого размещаются отправляемые данные;
• scounts – массив, содержащий количество элементов
в каждой части, на которые разбивается
сообщение на каждом процессе;
• sdispls – массив позиций, определяющий начальные
положения каждой части сообщения на каждом
процессе;
• stype – тип отправляемых данных;
• rcounts – массив длин принимаемых от процессов
сообщений;
• displs – массив позиций в приемном буфере,
по которым размещаются принимаемые
сообщения;
• rtype – тип принимаемых данных;
• comm – коммуникатор.
Выходной параметр функции:
• rbuf – адрес в памяти, начиная с которого
размещаются принимаемые сообщения.
2.3.2. Синхронизация процессов
В параллельных программах часто возникает ситуация, когда к выполнению следующей операции все процессы группы должны приступить одновременно. В этом случае необходимо выполнить выравнивание процессов по времени, т.е. синхронизировать их. Для этих целей в MPI предусмотрена функция
▲ int MPI_Barrier(MPI_Comm comm);
с единственным входным параметром – коммуникатором группы comm. Эта функция приостанавливает выполнение вызвавшего ее процесса до тех пор, пока она не будет вызвана изо всех остальных процессов данной группы. Стандартом MPI гарантируется, что к выполнению следующей за MPI_Barrier операции все процессы группы приступят одновременно.
2.3.3. Функции поддержки распределенных операций
В MPI имеется четыре основные функции, выполняющие распределенные операции, отличающиеся друг от друга размещением результатов:
▲ int MPI_Reduce(void *sbuf, void *rbuf,
int count, MPI_Datatype datatype,
MPI_Op op, int root,
MPI_Comm comm);
▲ int MPI_Allreduce(void *sbuf, void *rbuf,
int count,
MPI_Datatype datatype,
MPI_Op op, MPI_Comm comm);
▲ int MPI_Reduce_scatter(void *sbuf, void *rbuf,
int *rcounts,
MPI_Datatype datatype,
MPI_Op op,
MPI_Comm comm);
▲ int MPI_Scan(void *sbuf, void *rbuf, int count,
MPI_Datatype datatype, MPI_Op op,
MPI_Comm comm);
Входные параметры функций:
• sbuf – адрес в памяти на каждом процессе,
по которому хранятся исходные данные
для распределенной операции;
• count – количество элементов в sbuf;
• rcounts – массив, определяющий количество элементов,
распределяемых каждому процессу;
• datatype – тип данных, над которыми производится
распределенная операция;
• root – номер процесса, на котором осуществляется
размещение результата выполнения операции;
• op – название распределенной операции;
• comm – коммуникатор.
Выходной параметр функций:
• rbuf – адрес в памяти, по которому размещаются
результаты выполнения операции.
Назначение всех приведенных функций одинаково: над данными, хранящимися в sbuf в каждом процессе группы с коммуникатором comm, проделывается операция op, результат которой записывается в rbuf. Например, если в каждом процессе в sbuf хранится вектор размером m, а операция op представляет собой операцию суммирования MPI_SUM, то rbuf также будет вектором из m элементов, представляющий собой сумму векторов, содержащихся во всех процессах. Данные из sbuf и rbuf должны иметь одинаковый размер count и одинаковый тип datatype. Функции различаются способом хранения результатов:
MPI_Reduce – помещает результат в процесс с номером
root;
MPI_Allreduce – рассылает результат всем процессам;
MPI_Reduce_scatter – рассылает каждому процессу не весь
массив-результат, а его часть, длина которой определяется массивом rcounts; при этом размер исходных массивов во всех задачах одинаков и равен сумме длин частей результирующего массива;
MPI_Scan – содержимое массива-результата в i-м
процессе является результатом выполнения операции op над массивами, содержащимися в процесах с номерами от 0 до i включительно; при этом результат рассылается во все процессы.
В функции MPI_Reduce_scatter массив rcounts должен быть идентичен во всех процессах.
Все перечисленные операции являются ассоциативными и коммутативными. Определение операций MPI_MAXLOC и MPI_MINLOC приведено в стандарте MPI [1].
П р и м е р.
Чтобы продемонстрировать эффективность использования функций распределенных операций, обратимся снова к примеру вычисления суммы ряда, приведенному в начале данной главы. Теперь программу можно переписать в следующем виде:
#include
#include “mpi.h”
int main(int argc, char *argv[])
{
int S=0; /* вспомогательная переменная */
int SAdd; /* искомая сумма */
int NumProc; /* количество процессов */
int MyID; /* номер процесса */
/* вычисление куба числа
на каждом процессоре */
S=MyID+1;
S=S*S*S;
/* суммирование результатов на всех
процессах c использованием функции
распределенных операций */
MPI_Reduce(&S, &SAdd, 1,MPI_INT,MPI_SUM, 0,
MPI_COMM_WORLD);
/* печать результата на экран */
if (MyID == 0)
printf(“Sum is equal to %d”,SAdd);
/* завершение работы с MPI */
MPI_Finalize();
/* нормальное завершение работы программы */
return 0;
}
■
Как видно из приведенного программного кода, использование коллективной функции выполнения распределенных операций позволило существенно упростить программу и уменьшить количество переменных.
В заключении данного параграфа отметим, что MPI предоставляет пользователю возможность определять свои собственные операции, используя соответствующие функции-конструкторы. Подробную информацию об этом читатель может найти в стандарте MPI и монографиях [3, 4].
2.4. Определение времени выполнения
параллельной программы
Для определения ускорения и эффективности параллельной программы необходимо уметь определять время ее работы. Кроме того, при анализе загрузки процессов часто бывает полезно определять время работы каждого отдельного процесса. Это можно реализовать с помощью специальной функции MPI, возвращающей значение времени в секундах:
▲ double MPI_Wtime();
Эта функция может быть вызвана из любого отдельно взятого процесса.
Х а р а к т е р н ы е о с о б е н н о с т и ф у н к ц и и.
1. Функция MPI_Wtime работает с астрономическим временем, поэтому она позволяет учесть время, затрачиваемое на передачу данных (в отличие от функций, которые основаны на измерении времени работы процессора).
2. Чтобы значение времени работы процесса, измеренное с помощью функции MPI_Wtime, было адекватно реальному, необходимо, чтобы на каждом процессоре выполнялся только один процесс.
Для определения точности измерения времени функцией MPI_Wtime предусмотрена другая MPI-функция, которая возвращает значение частоты внутреннего таймера:
▲ double MPI_Wtick();
Так, если значением этой функции является число 0,01, то это означает, что счетчик времени изменяется 100 раз в секунду.
П р и м е р.
Для измерения времени выполнения некоторого участка кода программы можно воспользоваться следующей конструкцией:
int main(int argc, char *argv[])
{
int my_rank; /* ранг текущего
процесса */
int numprocs; /* общее число
процессов */
int source; /* ранг отправителя */
int dest; /* ранг получателя */
char message[BUF_LEN];/* буфер для сообщения */
MPI_Status status; /* информация о полученном
сообщении */
/* Начать работу с MPI */
MPI_Init(&argc, &argv);
/* Получить номер текущего процесса
в группе всех процессов */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* Получить общее количество
запущенных процессов */
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
/* Посылаем сообщения процессу 0,
который их выводит на экран */
if (my_rank != 0) {
/* Создаем сообщение */
sprintf(message, "Hello from process %d!",
my_rank);
/* Отправляем его процессу 0 */
dest = 0;
MPI_Send(message, strlen(message) + 1,
MPI_CHAR, dest, MSG_TAG,
MPI_COMM_WORLD);
}
else {
/* В процессе 0: получаем сообщение от
процессов 1,...,numprocs-1 и выводим
его на экран */
for (source = 1; source < numprocs; source++){
MPI_Recv(message, BUF_LEN, MPI_CHAR, source,
MSG_TAG, MPI_COMM_WORLD, &status);
printf("%s\n", message);
}
}
/* Заканчиваем работу с MPI */
MPI_Finalize();
return 0;
}
Компиляция этого файла выполняется командой
$ mpicc MPI_simple.c -o MPI_simple
и запуск
$ mpirun -np 2 MPI_simple .
Здесь символ $ означает приглашение операционной системы к вводу команды (его набирать не нужно!), опция -np задает количество параллельно работающих процессов (в данном случае 2). Попробуйте его изменить, чтобы выяснить, как это отражается на работе программы.
3.2. Вычисление интеграла
Рассмотрим в качестве примера задачу вычисления определенного интеграла от функции по отрезку . Для ускорения работы программы на вычислительной установке с процессорами мы воспользуемся аддитивностью интеграла:
,
где
.
Использовав для приближенного определения каждого из слагаемых
этой суммы составную формулу трапеций и поручив эти вычисления своему процессору, мы получим –кратное ускорение работы. Простейшая программная реализация этой задачи приведена ниже.
Каждый из процессов инициализирует подсистему MPI с помощью вызова MPI_Init, получает свой номер и общее количество процессов посредством MPI_Comm_rank и MPI_Comm_size. Основная работа производится в функции integrate, по окончании которой процесс заканчивает работу с MPI с помощью MPI_Finalize и завершается. Функция integrate вычисляет свою часть интеграла и прибавляет его к ответу total в процессе с номером 0 посредством MPI_Reduce. Процесс с номером 0 перед окончанием своей работы выводит переменную total на экран.
Входные данные (границы отрезка и количество точек разбиения интервала) принимаются от пользователя в процессе с номером 0. Затем эти данные рассылаются всем остальным процессам с помощью MPI_Bcast.
/* Вычислить интеграл по отрезку [a,b] с числом
точек разбиений n по формуле трапеций */
double integrate(double a, double b, int n)
{
double res; /* результат */
double h; /* шаг интегрирования */
double x;
int i;
h = (b-a)/n;
res = 0.5*(f(a)+f(b))*h;
x = a;
for (i=1; i
x += h;
res += f(x)*h;
}
return res;
}
int main(int argc, char *argv[])
{
int my_rank; /* ранг текущего процесса */
int numprocs; /* общее число процессов */
double a; /* левый конец интервала */
double b; /* правый конец интервала */
int n; /* число точек разбиения */
double len; /* длина отрезка интегрирования
для текущего процесса*/
double local_a; /* левый конец интервала для
текущего процесса */
double local_b; /* правый конец интервала для
текущего процесса */
int local_n; /* число точек разбиения для
текущего процесса */
double local_res;/* значение интеграла в текущем
процессе */
double result; /* результат интегрирования */
double wtime; /* время работы программы */
/* Начать работу с MPI */
MPI_Init(&argc, &argv);
/* Получить номер текущего процесса
в группе всех процессов */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* Получить общее количество запущенных
процессов */
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
/* Получить данные */
if (my_rank == 0) {
printf("Input a: ");
scanf("%lf", &a);
printf("Input b: ");
scanf("%lf", &b);
printf("Input n: ");
scanf("%d", &n);
}
/* Рассылаем данные из процесса 0 остальным */
MPI_Bcast(&a, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(&b, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
/* Синхронизация процессов */
MPI_Barrier(MPI_COMM_WORLD);
/* Запускаем таймер */
wtime = MPI_Wtime();
/* Вычисляем отрезок интегрирования
для текущего процесса */
len = (b-a)/numprocs;
local_n = n/numprocs;
local_a = a + my_rank*len;
local_b = local_a + len;
/* Вычислить интеграл на каждом из процессов */
local_res = integrate(local_a, local_b,
local_n);
/* Сложить все ответы и передать процессу 0 */
MPI_Reduce(&local_res, &result, 1, MPI_DOUBLE,
MPI_SUM, 0, MPI_COMM_WORLD);
/* Синхронизация процессов */
MPI_Barrier(MPI_COMM_WORLD);
/* Вычисляем время работы */
wtime = MPI_Wtime() - wtime;
/* Напечатать ответ */
if (my_rank == 0) {
printf("Integral from %.2lf to %.2lf=%.8lf\n",
a, b, result);
printf("Working time: %.2lf seconds\n",
wtime);
}
/* Заканчиваем работу с MPI */
MPI_Finalize();
return 0;
}
Имеет смысл поэкспериментировать с количеством работающих параллельно процессов, чтобы выяснить, как меняется время работы программы.
3.3. Нахождение минимума
Довольно часто в практических задачах встречается проблема оптимизации – поиска экстремума (минимума или максимума) некоторой функции. Одним из методов решения этой задачи является метод сканирования. Рассмотрим работу этого метода для решения задачи нахождения минимума функции двух переменных .
Суть метода заключается в переборе всех значений
с шагом и
с шагом с вычислением значения функции в каждой точке. Решение задачи находится путем выбора наименьшего из всех вычисленных значений функции. Величины определяют погрешность решения, т.е. с какой точностью мы локализуем точку минимума.
К недостаткам метода сканирования относится значительное число повторных вычислений функции , что требует существенных затрат времени. Однако к задаче оптимизации вполне возможно применить концепцию распараллеливания вычислений, "назначив" каждому процессу для обработки свою часть двумерной области изменения параметров.
int main(int argc, char *argv[]) {
int my_rank; /* ранг текущего процесса */
int numprocs; /* общее число процессов */
int source; /* ранг отправителя */
MPI_Status status; /* информация о полученном
сообщении */
double minx, maxx,
miny, maxy; /* границы области поиска */
double hx, hy; /* погрешность поиска */
double global_minf; /* значение глобального
минимума функции */
double global_posx,
global_posy; /* положение глобального
минимума */
double start_x,
end_x, len; /* интервал поиска для
текущего процесса */
double posx, posy; /* положение локального
минимума */
double minf; /* значение минимума функции
в текущем процессе */
double wtime; /* время работы программы */
double x, y, value; /* рабочие переменные */
double exchange_array[6]; /* массив для
рассылки */
/* Начать работу с MPI */
MPI_Init(&argc, &argv);
/* Получить номер текущего процесса
в группе всех процессов */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* Получить общее количество
запущенных процессов */
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
/* Получить данные */
if (my_rank == 0) {
printf("Input the search domain:\n");
printf(" min x: ");
scanf("%lf", &exchange_array[0]);
printf(" max x: ");
scanf("%lf", &exchange_array[1]);
printf(" min y: ");
scanf("%lf", &exchange_array[2]);
printf(" max y: ");
scanf("%lf", &exchange_array[3]);
printf("Input the step of searching:\n");
printf(" hx: ");
scanf("%lf", &exchange_array[4]);
printf(" hy: ");
scanf("%lf", &exchange_array[5]);
}
/* Рассылаем данные из процесса 0 остальным */
MPI_Bcast(exchange_array, 6, MPI_DOUBLE, 0,
MPI_COMM_WORLD);
/* Синхронизация процессов */
MPI_Barrier(MPI_COMM_WORLD);
/* Запускаем таймер */
wtime = MPI_Wtime();
/* Вычисляем интервал поиска
для текущего процесса */
len = (maxx-minx)/numprocs;
start_x = minx + len*my_rank;
end_x = start_x + len;
/* Найти минимум функции в своей подобласти */
minf = +1.0e+38;
x = start_x;
while (x <= end_x) {
y = miny;
while (y <= maxy) {
value = f(x,y);
if (minf > value) {
minf = value; posx = x; posy = y;
}
y += hy;
}
x += hx;
}
/* Передать результаты процессу 0 */
if (my_rank != 0) {
exchange_array[0] = minf;
exchange_array[1] = posx;
exchange_array[2] = posy;
MPI_Send(&exchange_array, 3, MPI_DOUBLE, 0,
MSG_TAG, MPI_COMM_WORLD);
}
/* Синхронизация процессов */
MPI_Barrier(MPI_COMM_WORLD);
/* Вычисляем время работы */
wtime = MPI_Wtime() - wtime;
/* Напечатать ответ */
printf("f(x,y) has a minimum %.5f at
(%.3f,%.3f).\n",global_minf,
global_posx, global_posy);
printf("Working time: %.2lf seconds\n",
wtime);
}
/* Заканчиваем работу с MPI */
MPI_Finalize();
return 0;
}
Командная строка для компиляции этой программы выглядит следующим образом:
$ mpicc MPI_minima.c -o MPI_minima -lm
Ключ -lm указывает компоновщику на необходимость подключения математической библиотеки (так как мы используем функции exp и log).
И вновь, в качестве упражнения, мы предлагаем запустить программу на исполнение с различным количеством параллельно работающих процессов, чтобы выяснить, насколько хорошо масштабируется данная задача.
3.4. Параллельная сортировка
Сортировка является одной из типовых проблем обработки данных и обычно понимается как задача размещения элементов неупорядоченного набора значений в порядке монотонного возрастания или убывания. Вычислительная трудоемкость процедуры упорядочивания является достаточно высокой, однако можно ускорить сортировку, если использовать несколько процессоров. В этом случае исходный упорядочиваемый набор разделяется между процессорами, которые производят локальную сортировку своей части данных при помощи какого-либо быстрого алгоритма. Затем производится объединение уже упорядоченных фрагментов с использованием схемы так называемого P-путевого слияния. Алгоритм слияния имеет следующий вид:
1) рассчитываются начальные элементы оставшихся непустых последовательностей;
2) минимальный элемент записывается в выходной массив;
3) записанный элемент удаляется из соответствующей последовательности;
4) если имеются непустые последовательности, то переходят к пункту 1.
Дополнительно в программе показано, как следует отслеживать ошибки динамического выделения памяти. В случае нехватки памяти на каком-либо вычислительном узле необходимо корректно завершить все процессы.
/* Функция сравнения элементов */
int compare(const void *a, const void *b) {
if (*(int*)a < *(int*)b) return -1;
else return +1;
}
int main(int argc, char* argv[]) {
int my_rank; /* ранг текущего процесса */
int numprocs; /* общее число процессов */
double wtime; /* время работы программы */
int *array = NULL; /* указатель на исходный
массив с данными */
int *array_sorted = NULL;/* указатель на
отсортированные
данные */
int *counts = NULL; /* размеры фрагментов
массива */
int *displacements = NULL; /* смещения
фрагментов
массива */
int *array_local = NULL; /* локальный массив */
int error_flag = 0; /* общий флаг наличия
ошибки */
int local_flag = 0; /* локальный флаг
наличия ошибки */
MPI_Status status;
int i, p, n_div, index;
/* Начать работу с MPI */
MPI_Init(&argc, &argv);
/* Получить номер текущего процесса в группе
всех процессов */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* Получить общее количество запущенных
процессов */
MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
/* Запрашиваем память в корневом процессе */
if (my_rank == 0) {
if (!(array =
(int*)malloc((NUM_ITEMS+1)*sizeof(int))) ||
!(array_sorted =
(int*)malloc(NUM_ITEMS*sizeof(int)))) {
/* Ошибка -- недостаточно памяти */
fprintf(stderr, NO_MEMORY_MSG, 0);
error_flag = 1;
}
}
MPI_Bcast(&error_flag, 1, MPI_INT, 0,
MPI_COMM_WORLD);
/* Если произошла ошибка в корневом процессе,
то досрочно завершаем _все_ процессы */
if (error_flag) goto exit_label;
/* Задаем размеры и смещения фрагментов
массива */
counts = (int*)malloc(numprocs*sizeof(int));
displacements =
(int*)malloc(numprocs*sizeof(int));
n_div = NUM_ITEMS/numprocs;
for (p = 0; p < numprocs; p++) {
counts[p] = n_div;
displacements[p] = p*n_div;
}
/* Корректировка размера последнего фрагмента
в случае, когда число элементов массива не
кратно числу процессов */
counts[numprocs-1] += NUM_ITEMS%numprocs;
/* Запрашиваем память под локальные массивы */
if (!(array_local =
(int*)malloc((counts[my_rank])*sizeof(int))))
local_flag = 1;
/* Сообщаем о результате выделения памяти
корневому процессу */
MPI_Send(&local_flag, 1, MPI_INT, 0,
ERROR_CODE_TAG, MPI_COMM_WORLD);
/* Проверка результатов выделения памяти
под локальные массивы */
if (my_rank == 0) {
for (p = 0; p < numprocs; p++) {
MPI_Recv(&local_flag, 1, MPI_INT, p,
ERROR_CODE_TAG, MPI_COMM_WORLD,
&status);
if (local_flag) {
fprintf(stderr, NO_MEMORY_MSG,
status.MPI_SOURCE);
error_flag = 1;
}
}
}
MPI_Bcast(&error_flag, 1, MPI_INT, 0,
MPI_COMM_WORLD);
/* Была ошибка в каком-либо процессе */
if (error_flag) goto exit_label;
/* Подготовительные операции завершены –
начинаем работу */
/* Получаем последовательность случайных чисел
для сортировки */
if (my_rank == 0) {
randomize();
for (i = 0; i < NUM_ITEMS; i++)
array[i] = get_random(1000);
}
/* Производим сбор данных от всех процессоров */
MPI_Gatherv(array_local, counts[my_rank],
MPI_INT, array, counts,
displacements, MPI_INT,
0, MPI_COMM_WORLD);
/* Производим слияние
упорядоченных фрагментов */
if (my_rank == 0) {
/* ставим как ограничитель число, заведомо
большее любого из массива данных */
array[NUM_ITEMS] = INT_MAX;
for (i = 0; i < NUM_ITEMS; i++) {
index = 0;
for (p = 1; p < numprocs; p++) {
if (array[displacements[p]] <
array[displacements[index]])
index = p;
}
array_sorted[i] =
array[displacements[index]];
displacements[index]++;
counts[index]--;
if (counts[index] == 0)
displacements[index] = NUM_ITEMS;
}
}
/* Вычисляем время работы */
MPI_Barrier(MPI_COMM_WORLD);
wtime = MPI_Wtime() - wtime;
/* Выводим отсортированный массив */
if (my_rank == 0) {
for (i = 0; i < NUM_ITEMS; i++)
printf("%3i ", array_sorted[i]);
printf("\n");
printf("Working time: %.2lf seconds\n",
wtime);
}
exit_label:
/* Освобождаем память и заканчиваем
работу MPI */
free(counts);
free(displacements);
free(array_local);
free(array);
free(array_sorted);
MPI_Finalize();
return(error_flag);
}
3.5. Решение систем линейных уравнений
Рассмотрим систему линейных уравнений с неизвестными :
где коэффициенты – действительные числа.
Запишем приведенную систему в матричной форме:
,
где – матрица размерности , – искомый вектор и – заданный вектор.
Решение систем линейных уравнений является одной из важных вычислительных задач, часто встречающихся в прикладной математике. К решению систем линейных уравнений сводится ряд задач анализа, связанных с приближением функций, решением дифференциальных уравнений и т.д. Весьма распространенными методами решения систем линейных уравнений являются итерационные методы, которые состоят в том, что решение системы находится как предел при последовательных приближений , где – номер итерации.
Мы рассмотрим простейший из таких алгоритмов – метод Якоби. Согласно ему, последовательные приближения начиная с некоторого начального вычисляются с использованием следующих формул:
.
Метод Якоби не является приемлемым для большинства задач, поскольку он сходится не всегда, а только в случае диагонального преобладания матрицы . Однако для учебных целей этот метод представляет собой удобную отправную точку в изучении способов распараллеливания итерационных алгоритмов.
Для решения задачи на параллельной системе исходную матрицу коэффициентов “разрезают” на горизонтальных полос по строкам, где – количество процессоров в системе. Аналогично, горизонтальными полосами, разделяются вектор правых частей и вектор текущего приближения . Полосы распределяются по соответствующим процессорам и реализуется параллельный алгоритм умножения матрицы на вектор.
Качество полученного приближения характеризует норма вектора
– так называемая невязка. Обычно вычисления в итерационном процессе метода Якоби продолжают до тех пор, пока норма невязки не станет достаточно малой:
,
где есть некоторое наперед заданное малое число. Если приведенное условие не выполняется в течении максимального числа итераций, то имеет место расходимость процесса и алгоритм завершает работу с соответствующим диагностическим сообщением.
Текст программы:
/* MPI_Jacobi.c */
/* Решение линейной системы Ax = b
методом Якоби */
#include
#include
#include "mpi.h"
if (my_rank == 0) {
printf("Enter order of system, tolerance,
and max number of iterations:\n");
scanf("%d %f %d", &n, &tol, &max_iter);
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&tol, 1, MPI_FLOAT, 0,
MPI_COMM_WORLD);
MPI_Bcast(&max_iter, 1, MPI_INT, 0,
MPI_COMM_WORLD);
Read_matrix("Enter the matrix:", A_local, n,
my_rank, numprocs);
Read_vector("Enter the right-hand side:",
b_local, n, my_rank, numprocs);
converged = Jacobi(A_local, x_local, b_local, n,
tol, max_iter, numprocs,
my_rank);
if (converged)
Print_vector("The solution is:", x_local, n,
my_rank, numprocs);
else
if (my_rank == 0)
printf("Failed to converge in %d
iterations.\n", max_iter);
MPI_Finalize();
return 0;
} /* main */
/* Возвращает 1, если процесс решения сходится,
0 в противном случае */
int Jacobi(MATRIX_T A_local, float x_local[],
float b_local[], int n, float tol,
int max_iter, int numprocs,
int my_rank)
{
int n_bar, iter_num;
int i_local, i_global, j;
float x_temp1[MAX_DIM];
float x_temp2[MAX_DIM];
float* x_old;
float* x_new;
/* Рассылаем новое решение */
MPI_Allgather(x_local, n_bar, MPI_FLOAT,
x_new, n_bar,MPI_FLOAT,
MPI_COMM_WORLD);
iter_num++;
if (iter_num > max_iter) return 0; /* процесс
расходится */
} while (Distance(x_new,x_old,n) >= tol);
return 1;
} /* Jacobi */
float Distance(float x[], float y[], int n)
{
int i;
float sum = 0.0;
for (i = 0; i < n; i++) {
sum = sum + (x[i] - y[i])*(x[i] - y[i]);
}
return sqrt(sum);
} /* Distance */
void Read_matrix(char* prompt, MATRIX_T A_local,
int n, int my_rank, int numprocs)
{
int n_bar, i, j;
MATRIX_T temp;
n_bar = n/numprocs;
/* Заполняем неиспользуемые столбцы
в temp нулями */
for (i = 0; i < n; i++)
for (j = n; j < MAX_DIM; j++)
temp[i][j] = 0.0;
/* Считываем матрицу */
if (my_rank == 0) {
printf("%s\n", prompt);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%f", &temp[i][j]);
}
/* Рассылаем полосы матрицы по процессам */
MPI_Scatter(temp, n_bar*MAX_DIM, MPI_FLOAT,
A_local, n_bar*MAX_DIM, MPI_FLOAT,
0, MPI_COMM_WORLD);
} /* Read_matrix */
void Read_vector(char* prompt, float x_local[],
int n, int my_rank, int numprocs)
{
int n_bar, i;
float temp[MAX_DIM];
n_bar = n/numprocs;
/* Считываем вектор */
if (my_rank == 0) {
printf("%s\n", prompt);
for (i = 0; i < n; i++)
scanf("%f", &temp[i]);
}
/* и рассылаем по процессам */
MPI_Scatter(temp, n_bar, MPI_FLOAT, x_local,
n_bar, MPI_FLOAT, 0,
MPI_COMM_WORLD);
} /* Read_vector */
void Print_matrix(char* title, MATRIX_T A_local,
int n, int my_rank,
int numprocs)
{
int n_bar, i, j;
MATRIX_T temp;
n_bar = n/numprocs;
/* Собираем матрицу */
MPI_Gather(A_local, n_bar*MAX_DIM, MPI_FLOAT,
temp, n_bar*MAX_DIM, MPI_FLOAT, 0,
MPI_COMM_WORLD);
/* и печатаем */
if (my_rank == 0) {
printf("%s\n", title);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
printf("%4.1f ", temp[i][j]);
printf("\n");
}
}
} /* Print_matrix */
void Print_vector(char* title, float x_local[],
int n, int my_rank,
int numprocs)
{
int n_bar, i;
float temp[MAX_DIM];
n_bar = n/numprocs;
MPI_Gather(x_local, n_bar, MPI_FLOAT, temp,
n_bar, MPI_FLOAT, 0, MPI_COMM_WORLD);
if (my_rank == 0) {
printf("%s\n", title);
for (i = 0; i < n; i++)
printf("%4.1f ", temp[i]);
printf("\n");
}
} /* Print_vector */
При большой размерности матрицы коэффициентов ввод данных с клавиатуры может оказаться весьма утомительным. Чтобы избежать этого и уменьшить вероятность ошибки, можно использовать возможность перенаправления стандартного ввода. При командной строке следующего вида
$ mpirun -np 2 MPI_Jacobi < 4Jacobi.dat
поведение программы будет таким же, как если бы содержимое текстового файла 4Jacobi.dat было набрано на клавиатуре.
Список литературы
1. MPI: A Message-Passing Interface Standard. – University of Tennessee, 1995. – 231 p.
2. Foster I. Designing and Building Parallel Programs. – Addison-Wesley, 1995. – 381 p.
3. Корнеев В.Д. Параллельное программирование в MPI. – Москва-Ижевск: Институт компьютерных исследований, 2003. – 304 с.
4. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002. – 400 с.
Приложение 1
РАБОТА С ВЫЧИСЛИТЕЛЬНЫМ КЛАСТЕРОМ
БАШКИРСКОГО РЕГИОНАЛЬНОГО ЦЕНТРА
ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ
В данном приложении собран необходимый минимум информации, необходимый для начала практической работы на вычислительном кластере Башкирского регионального центра высокопроизводительных вычислений (БРЦ ВВ).
Прежде всего, остановимся кратко на архитектуре рассматриваемой кластерной системы.
Alpha-кластер БРЦ ВВ является учебной многопроцессорной вычислительной системой кластерного типа, функционирующей с 2000 г. Кластер имеет следующую конфигурацию:
• количество узлов – 12 + терминальная машина;
• количество процессоров на узле – 1;
• тип процессора – Alpha 21164EV5 с тактовой частотой 533 МГц;
• оперативная память на узле – 128 Мбайт;
• дисковая память – RAID-массив 625 Гб;
• коммуникационная среда – Fast-Ethernet 100 Мбит/с;
• коммутатор – HP ProСurve 1600M со средним временем латентности 150 мкс;
• топология коммуникационной сети – “звезда”;
• операционная система – Red Hat Linux 6.2 for Alpha.
Для разработки параллельных программ на кластере установлена свободно распространяемая реализация MPI – MPICH 1.2.3.
Продолжение прил. 1
Работа с кластером осуществляется через терминальную машину в режиме удаленного доступа. При этом если при запуске в команде mpirun не указана опция –nolocal, терминальная машина участвует в работе всех запущенных параллельных программ и на ней всегда автоматически запускается процесс с номером 0.
Рассмотрим по шагам процедуру работы с кластерной системой. Предполагается, что параллельная программа пользователем уже написана и предварительно отлажена на однопроцессорной системе.
Шаг 1. Соединение с терминальной машиной кластера.
Соединение с кластером осуществляется в режиме удаленного доступа по защищенному протоколу ssh. Для выхода на кластер необходимо знать его IP адрес вида XXX.XXX.XXX.XXX (X – допустимая цифра), имя зарегистрированного пользователя username и пароль password. Все эти данные можно узнать у администратора БРЦ ВВ или преподавателя. Для соединения с кластером необходимо выполнить команду
$ ssh –l username XXX.XXX.XXX.XXX ,
после чего ввести пароль по соответствующему запросу. Если все данные введены корректно, то вы получаете доступ к терминальной машине с правами пользователя username.
Шаг 2. Проверка свободности кластера.
На учебном Alpha-кластере БРЦ ВВ отсутствует система очередности задач, поэтому пользователь должен убедиться, что в данный момент он является единственным пользователем кластера. Категорически запрещается запускать на выполнение собственные задачи при наличии соединения кластера с другими пользователями, поскольку этим вы существенно затормозите выполнение как собственной, так и чужой программы! Проверить наличие соединений кластера с другими пользователями можно командой
who
или
finger
Продолжение прил. 1
Более опытные пользователи могут воспользоваться командой просмотра активных процессов (см. приложение 2).
Шаг 3. Копирование программы с локального компьютера на кластер.
Для переноса собственной программы на кластер можно воспользоваться ftp-соединением. Если на локальной машине установлена операционная система семейства Linux, то наиболее простой способ установить такое соединение следующий.
Переключитесь на новый терминал локальной машины (Alt+F2, Alt+F3 и т.д.). Войдите в локальную систему под своим пользовательским именем, введите пароль. После этого наберите команду
mc
Загрузится файловый менеджер Midnight Commander (подробнее о работе с MC см. приложение 2). Войдите в меню MC (нажав клавишу F9), выберите left panel или right panel и затем FTP-connection. После этого в качестве имени удаленной машины введите
username@XXX.XXX.XXX.XXX
и затем пароль доступа к терминальной машине кластера. Здесь XXX.XXX.XXX.XXX – IP-адрес терминальной машины кластера, username – имя зарегистрированного на кластере пользователя (см. шаг 1).
После успешного установления ftp-соединения на одной из рабочих панелей MC будет отображаться файловая структура терминальной машины кластера, а на другой рабочей панели – файловая структура Вашей локальной машины. После этого файл можно скопировать на кластер с помощью команды копирования F5.
Копировать файлы на кластер нужно в собственный каталог, который необходимо создать внутри каталога
/mnt/cluster/stud
командой F7 из MC сразу после установления ftp-соединения.
Отметим, что копировать необходимо только исходные файлы программ.
Продолжение прил. 1
После копирования необходимых файлов закройте ftp-соединение и вернитесь на терминал кластера (например, Alt+F1).
Шаг 4. Компиляция и сборка программы.
После того, как исходные файлы скопированы, необходимо выполнить их компиляцию на терминальной машине кластера. Не следует копировать и запускать на кластере исполняемые файлы, созданные на локальных машинах, поскольку вследствие различия компьютерных архитектур эти файлы неработоспособны на кластерной системе.
Компиляция программ на кластере осуществляется традиционным для MPI-программ образом за одним маленьким исключением: скрипты MPI на Alpha-кластере несколько изменены, поэтому для компиляции С-программы следует использовать команду
$ mpiccc program.c –o program –lm ,
а для Fortran-программы – команду
$ mpifort program.for –o program
(здесь program – имя исходного файла, содержащего программу пользователя). Ключ –lm необходим для подключения математической библиотеки языка С.
После успешной компиляции и сборки будет создан исполняемый файл program.
Шаг 5. Запуск программы на выполнение.
Запуск программы на выполнение на кластерной системе осуществляется командой
$ mpirun –np X –machinefile
/mnt/cluster/stud/machines.LINUX_ALPHA program ,
где вместо Х необходимо указать желаемое количество процессоров кластера, которые будут задействованы для выполнения программы. Это число не должно превосходить 13 – общего количества узлов кластерной системы. Отметим, что при указании большего значения ошибки не произойдет, просто какие-то процессоры будут выполнять в этом случае более одного процесса, что существенно замедлит скорость выполнения программы.
Окончание прил. 1
Опция компилятора “-machinefile filename'' позволяет подключать специальный файл machines.LINUX_ALPHA, содержащий список IP-адресов узлов кластера, на которых разрешено выполнение процессов. С помощью этого файла можно, при необходимости, выключать из работы определенные узлы кластера – для этого достаточно закомментировать символом # имя ненужного узла. Иногда может возникнуть ситуация, когда отдельные узлы кластера оказываются неработоспособными. В этом случае их IP-адреса обязательно должны быть закомментированы в machinefile, поскольку процесс распределения процессов по процессорам кластера идет в порядке возрастания IP-адресов и если операционная система наталкивается на неработающий узел, то процесс распределения заданий останавливается и запуска задачи на выполнение не происходит.
Проверить работоспособность узла можно командой
$ ping XXX.XXX.XXX.XXX ,
где XXX.XXX.XXX.XXX представляет собой IP-адрес проверяемого узла. Если отправленные по этому IP-адресу сетевые пакеты не возвращаются, то данный узел следует исключить из списка в machinefile.
Шаг 6. Завершение работы.
Во избежание ошибок ввода/вывода при выполнении на Alpha-кластере параллельная программа должна осуществлять ввод данных и вывод результатов только через нулевой процесс. При этом результаты могут выводиться как на терминал, так и в файл. В случае, если результаты работы записаны в файл, скопировать этот файл на локальную машину можно через ftp-соединение (см. шаг 3). После завершения работы с кластером необходимо разорвать с ним удаленное соединение, выполнив команду
exit
Если выполнение параллельной программы на кластере необходимо по каким-либо причинам прервать, то это можно сделать комбинацией клавиш Ctrl+C.
Приложение 2
НЕКОТОРЫЕ БАЗОВЫЕ КОМАНДЫ
ОПЕРАЦИОННОЙ СИСТЕМЫ LINUX
Alpha-кластер Башкирского регионального центра высокопроизводительных вычислений работает под управлением операционной системы Linux – одной из наиболее известных свободно распространяемых реализаций ОС Unix. Поэтому приведем здесь основные сведения об этой операционной системе, необходимые при работе с Alpha-кластером.
В Linux пользователи должны себя идентифицировать при входе в систему, который состоит из двух шагов: ввода имени (по которому система Вас идентифицирует) и ввода пароля (секретного слова для регистрации в системе). При вводе пароля будьте внимательны, так как пароль на экране не отображается. Каждый пользователь является членом одной или нескольких групп. Принадлежность к группе определяет дополнительные права, которыми обладают все пользователи группы. Список пользователей, работающих в данный момент в системе, можно посмотреть при помощи команды
who
Для завершения сеанса работы нужно набрать команду
exit
Все объекты в Linux делятся на два типа: файлы и процессы. Все данные хранятся в файлах. Доступ к периферийным устройствам осуществляется через специальные файлы. Вся же функциональность операционной системы определяется выполнением различных процессов.
Продолжение прил. 2
В Linux все множество файлов организовано в виде древовидной структуры, называемой файловой системой. Каждый файл имеет имя, определяющее его расположение в файловой системе. Связь между именами файлов и собственно файлами обеспечивается при помощи каталогов. Корнем файловой системы является корневой каталог, имеющий имя “/”. Имена всех остальных файлов содержат путь – список каталогов, которые нужно пройти, чтобы достичь файла.При этом имена каталогов разделяются знаком “/”. Например,
/home/student/myfile.txt
При перемещении по файловой системе текущий каталог называется “.”, а каталог на единицу более высокого уровня “..”. Кроме того, с каждым пользователем ассоциируется его домашний каталог, имеющий псевдоним “~”, в котором по умолчанию хранятся его файлы.
Все операции с файлами удобно производить при помощи файлового менеджера Midnight Commander (MC). MC вызывается командой
mc
Внешне MC похож на Norton Commander или Far Manager и имеет сходный с ними интерфейс. В частности, основные команды работы с файлами связаны с функциональными клавишами:
Команда
Клавиша
Описание
View
F3
Просмотр выбранного файла
Edit
F4
Вызов редактора
Copy
F5
Копирование файла (группы файлов)
Rename/Move
F6
Перенос/переименование файла
MkDir
F7
Создание каталога
Delete
F8
Удаление файла (группы файлов)
Menu
F9
Вызов главного меню
Более подробно о возможностях MC можно узнать из встроенной справки (функциональная клавиша F1). Чтобы закончить работу с MC и выйти из него, необходимо нажать функциональную клавишу F10.
Продолжение прил. 2
Файлы и каталоги в Linux имеют набор атрибутов, среди которых важно отметить владельца и группу. С их использованием организуется гибкое разграничение доступа к файлам и каталогам. Для просмотра всех атрибутов файла можно использовать команду
ls –l
Результат выполнения этой команды для каждого файла будет иметь примерно следующий вид:
1 2 3 4 5 6 7 8
-rwxr-xr-- 1 student group 3422 Feb 28 13:30 test
В первом столбце выдачи приводится список прав доступа к файлу. Первый символ обозначает тип файла (в данном случае “-” означает обычный файл. Другие возможные значения: “d” – каталог, “l” – ссылка и др.). Далее идут три группы по три символа, задающие соответственно права доступа. Первая группа из тpex символов задает права для владельца-пользователя. Следующие три символа определяют права доступа для членов группы, к которой принадлежит файл. Последняя группа из трех символов определяет права для всех остальных пользователей. При этом “-” означает отсутствие права доступа, “r” – право на чтение файла, “w” – право на запись в файл или его удаление, “x” – право на выполнение файла. В нашем примере владелец файла (student) имеет права на чтение, запись и выполнение (“rwx”), члены группы-владельца (group) имеют права на чтение и выполнение файла, но не имеют права на запись в файл (“r-x”), а все остальные пользователи имеют только право на чтение файла (“r--'). Существует также несколько дополнительных атрибутов, а для других типов файлов (например, для каталогов) приведенные атрибуты могут иметь несколько иное значение. Сменить права доступа к файлу можно при помощи команды
chmod
Владельцем-пользователем вновь созданного файла является пользователь, который его создал, а владельцем-группой -- или пер-
Продолжение прил. 2
вичная группа данного пользователя, или наследная группа, приписанная текущему каталогу. Для смены владельца-пользователя и владельца-группы файла существуют команды
chown
и
chgrp
соответственно.
Второй тип объектов в Linux – это процессы. Под процессом упрощенно можно понимать программу в стадии ее выполнения. Одновременно в системе выполняется достаточно большое число процессов, часть из которых является системными, а часть – пользовательскими. Для того чтобы просмотреть список выполняющихся процессов, нужно воспользоваться командой
$ ps –x
Каждый процесс имеет некоторый набор атрибутов, в частности, уникальный идентификатор процесса (PID), который используется для управления его работой, например, посредством посылки сигналов. Для того чтобы завершить выполнение процесса, нужно послать ему соответствующий сигнал командой
$ kill -9 PID
Список процессов, занимающих наибольшее количество процессорного времени или системных ресурсов, можно посмотреть, используя команду
top
Справку по любой команде можно получить следующим образом:
$ man имя_команды
Каждая запущенная программа получает три открытых потока ввода/вывода: стандартный ввод, стандартный вывод и стандартный вывод ошибок. По умолчанию все эти потоки ассоциированы с терминалом, однако могут быть перенаправлены на другое устройство, например, в файл. Для перенаправления стандартного ввода можно
Окончание прил. 2
использовать символ “<”, для стандартного вывода – “>” или “>>” (дозапись), для потока ошибок – “2>”. Например:
program > file.log
Здесь запускается программа program, а ее стандартный вывод перенаправляется в файл file.log.
Последние комментарии
1 день 17 часов назад
1 день 21 часов назад
1 день 23 часов назад
2 дней 38 минут назад
2 дней 1 час назад
2 дней 2 часов назад