М. Н. Геворкян, А. В. Королькова, Д. С. Кулябов Параллельное программирование
жүктеу/скачать 0,58 Mb. Pdf көрінісі
|
параллель
– if(условие) — выполнение параллельной области по условию;
Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 45
default(private | firstprivate | shared | none) — всем пе- ременным в параллельной области, которым явно не назначен класс, бу- дет назначен класс private ,
или shared
соответствен- но; none означает, что всем переменным в параллельной области класс должен быть назначен явно;
private(список) – задаёт список переменных, для которых порожда- ется локальная копия в каждой нити; начальное значение локальных ко- пий переменных из списка не определено;
firstprivate(список) – задаёт список переменных, для которых по- рождается локальная копия в каждой нити; локальные копии перемен- ных инициализируются значениями этих переменных в нити-мастере;
shared(список) – задаёт список переменных, общих для всех нитей;
copyin(список) – задаёт список переменных, объявленных как thread-
private , которые при входе в параллельную область инициализируют- ся значениями соответствующих переменных в главной нити;
reduction(оператор:список) – задаёт оператор и список общих пе- ременных, для каждой переменной создаются локальные копии в каж- дой нити; над локальными копиями переменных после выполнения всех операторов параллельной области выполняется заданный оператор; опе- ратор — это: –, +, *, .and., .or., .eqv., .neqv., max, min, iand, ior, ieor ; порядок выполнения операторов не определён, по- этому результат может отличаться от запуска к запуску. Иногда бывает необходимо, чтобы какой-то участок кода в параллель- ной области был выполнен только одной нитью. Закрывать параллельную область и открывать вновь было бы слишком ресурсоёмко. Для этой цели следует использовать директиву single
: !$omp single <код> !$omp end single Рассмотрим теперь ещё один пример программы, в котором иллюстри- руется применение директивы single и функции omp_get_thread_num() :
implicit none include "omp_lib.h" integer :: i, n, tn real :: t1, t2 ! Сравнить результаты для переменной объявленной ! как private и public (по умолчанию) write(*,*) "В переменную tn записывается номер нити" write(*,*) "Если эта переменная в параллельной & области не объявлена как private" write(*,*) "То для всех нитей она общая:" !$omp parallel num_threads(4) 46 Глава 3. OpenMP tn = omp_get_thread_num()
tn = omp_get_thread_num() write(*,*) "Нить № ", tn !$omp end parallel ! Следующая часть иллюстрирует применение директивы single, ! которая используется для того, чтобы в параллельной области ! указанные в её рамках команды исполнялись только мастер-нитью t1 = omp_get_wtime() !$omp parallel num_threads(100) private(tn) !$omp single tn = omp_get_thread_num() write(*,*) "Одна нить найдёт для нас число созданных нитей" n = omp_get_num_threads() write(*,*) "Создано нитей:", n write(*,*) "Остальные нити опять распечатают свои номера" !$omp end single tn = omp_get_thread_num() write(*,*) "Нить № ", tn !$omp end parallel t2 = omp_get_wtime() write(*,*) "На создание и закрытие параллельной области & и нитей ушло сек", t2-t1 end program ex4
Следует пояснить использование опции private(tn) во второй парал- лельной области. В OpenMP переменные в параллельных областях разде- ляются на два основных класса:
shared
— общие, все нити видят одну и ту же переменную; – privat
— локальные, каждая нить видит свой экземпляр переменной. По умолчанию все переменные в параллельной области общие, кроме счётчиков итераций. Поэтому в первой параллельной области значение пе- ременной
tn будет одинаковым для всех нитей и её значение после парал- лельной области будет зависеть от того, какая нить последней записала в эту переменную свой номер. В консоль в данном случае будет выдано 4 сообщения типа Нить № n
. Во второй же параллельной области значение переменной tn установлено как private и поэтому оно разное для каждой нити. В консоль в данном случае будут выданы следующие сообщения: Нить №
0 Нить №
1 Нить №
2 Нить №
3 Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 47 Отдельно стоит отметить, что при каждом запуске программы последо- вательность выдаваемых сообщений будет разной, ввиду других фоновых процессов, влияющих на время выполнения нашей программы. 3.4. Параллельные циклы Если в параллельной области встречается оператор цикла do , то он бу- дет выполнен всеми нитями одновременно. Для того чтобы указать на необ- ходимость параллельного выполнения итераций цикла, следует использо- вать директиву !$omp do
!$omp do <код> !$omp end do Теперь итерации цикла в рамках этой директивы будут при возможности разделены между нитями. Отнюдь не каждый цикл может быть распарал- лелен. Например, следующий код:
a(i) = a(i-1) + a(i-2) end do параллельному выполнению не поддаётся, так как каждый шаг вычисления непосредственно зависит от двух предыдущих. Для возможности распараллеливания каждая нить должна иметь воз- можность выполнять свою часть цикла независимо от остальных нитей. В некоторых случаях последовательный алгоритм хорошо поддаётся распа- раллеливанию без дополнительных модификаций. К таким алгоритмам от- носятся многие действия над массивами (матрицами), что иллюстрирует следующий пример:
n = 4000
! Выделяем память allocate(A(1:n,1:n)) allocate(B(1:n,1:n)) allocate(C(1:n,1:n)) ! Заполняем числами от 0 до 1 call random_number(A) call random_number(B) call random_number(C) t1 = omp_get_wtime() ! Итерационные счётчики приватные по умолчанию !$omp parallel shared(A,B,C) private(i,j,tn) num_threads(4) 48 Глава 3. OpenMP tn = omp_get_thread_num()
C(i,j) = A(i,j) + B(i,j) !write(*,*) "Нить ", tn, "сложила элементы", i,j end do end do !$omp end do !$omp end parallel t2 = omp_get_wtime() write(*,*) "На параллельное вычисление ушло сек", t2-t1 ! Заново заполняем числами от 0 до 1 call random_number(A) call random_number(B) call random_number(C) t1 = omp_get_wtime() !$omp do do i = 1,n,1 do j = 1,n,1 C(i,j) = A(i,j) + B(i,j) !write(*,*) "Нить ", tn, "сложила элементы", i,j end do end do t2 = omp_get_wtime() write(*,*) "На последовательное вычисление ушло сек", t2-t1 end program ex4
В данном примере проиллюстрировано лишь сложение матриц. Более ресурсоёмкий процесс перемножения матриц также хорошо поддаётся рас- параллеливанию, что будет предложено показать самостоятельно в первом задании лабораторной работы. В подавляющем большинстве случаев последовательный вариант алго- ритма не поддаётся параллелизации и его приходится модифицировать. В простейших случаях параллельная версия лишь немного отличается от ис- ходной. Например, вычисление суммы или произведения множества чисел (элементов массива) можно разбить на части согласно формулам:
∑
a(i) = m ∑
a(i) + n ∑
a(i), n ∏
a(i) = m ∏
a(i) + n ∏
a(i) Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 49 Однако чаще параллельный вариант алгоритма существенно отлича- ется от последовательного, и при его реализации нарушается идеология Single Program Multiple Data. Это означает, что уже невозможно превра- тить параллельный вариант программы в последовательный, лишь убрав директивы OpenMP. 3.5. Параллельные секции Несмотря на то, что OpenMP реализует идеологию Single Program Multiple Data, все же имеются средства для ручного распараллеливания программы и контроля над тем, какую часть кода будет выполнять та или иная нить. Этой цели служит директива sections
: !$omp sections <блок_секций> !$omp end sections Данная директива определяет набор независимых секций кода, каждая из которых выполняется своей нитью. Для иллюстрации рассмотрим сле- дующий пример:
tn=omp_get_thread_num() !$omp sections !$omp section write(*,*) "Первая секция, процесс ", tn !$omp section write(*,*) "Вторая секция, процесс ", tn !$omp section write(*,*) "Третья секция, процесс ", tn !$omp end sections write(*,*) "Параллельная область, процесс ", tn !$omp end parallel end program ex5
3.6. Задания для лабораторной работы 3.6.1. Задание № 1 В данном задании предлагается написать параллельную версию реше- та Эратосфена — известного алгоритма по нахождению простых чисел. Ниже дан последовательный вариант этого алгоритма, реализованный на 50 Глава 3. OpenMP фортране. Заметим, что переменная n задаёт натуральное число, до кото- рого необходимо производить поиск простых чисел. program Eratosthenes implicit none include "omp_lib.h" integer :: i,j integer :: n integer :: p_num, th_num ! Замер времени real :: t1, t2 logical, allocatable :: A(:) ! Открыли файл open(10,file = "primes.txt") write(*,*), "Введите n =" read(*,*) n write(*,*), "Введите th_num =" read(*,*) th_num ! Выделяем память под массив allocate(A(2:n)) !------------------------------------- A = .true. t1 = omp_get_wtime()
A(i) = .false. end do ! Непосредственно алгоритм do i = 2,nint(sqrt(real(n))),1 if(A(i) .eqv. .true.) then do j = i**2,n,i A(j) = .false. end do end if end do t2 = omp_get_wtime() print *, "Время работы алгоритма: ", t2-t1 !------------------------------------- ! Записываем найденные простые числа в файл p_num = 0 do i = 2,n,1 if(A(i)) then p_num = p_num + 1 write(10,*) i end if end do write(*,*), "Найдено ", p_num, " простых чисел" ! Закрываем файл после того как завершили с ним работу Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 51
end program Eratosthenes 1. С помощью директив OpenMP требуется распараллелить части програм- мы (где это возможно). 2. Необходимо исследовать влияние опции dynamic директивы !$omp do на время выполнения программы. Даёт ли динамическое распределение блоков выигрыш в данном случае? 3. Необходимо исследовать, как зависит время выполнения программы от числа нитей при достаточно большом фиксированном n. Определить оп- тимальное число нитей. 3.6.2. Задание № 2 Реализовать параллельное перемножение квадратных матриц стандарт- ным алгоритмом и алгоритмом Винограда. Замерить выигрыш по време- ни параллельного варианта программ по сравнению с последовательным. Сравнить быстродействие параллельного варианта со встроенной функци- ей matmul . 3.6.3. Задание № 3 Данное задание демонстрирует невозможность непосредственного рас- параллеливания простейшего алгоритма сортировки (сортировка пузырь- ком). Однако можно перестроить алгоритм так, что становится возможным параллельное выполнение его итераций. В приведённом ниже исходном ко- де реализована классическая сортировка пузырьком, модифицированный её вариант (последовательный) и параллельный вариант. Необходимо рас- параллелить параллельный вариант с помощью директив OpenMP и срав- нить быстродействие с двумя последовательными вариантами.
n = 200000 allocate(a(1:n)) allocate(b(1:n)) call random_number(a) b = a
!=========================== ! Оригинальный алгоритм сортировки пузырьком !============================ 52 Глава 3. OpenMP t1 = omp_get_wtime()
t2 = omp_get_wtime() !============================ write(*,*) "Затратили время (последовательно)", t2-t1 ! write(*,'(f8.3)') a !============================ ! Переработанный алгоритм пузырька ! Odd-Even transposition sort !============================ ! t1 = omp_get_wtime() ! sorted = .false. ! do while(.not. sorted) ! Делать пока sorted ложь ! sorted = .true. ! do i = 2,n-1,2 ! if(b(i) .gt. b(i+1)) then ! call swap(b(i),b(i+1)) ! sorted = .false. ! end if ! end do ! do i = 1,n-1,2 ! if(b(i) .gt. b(i+1)) then ! call swap(b(i),b(i+1)) ! sorted = .false. ! end if ! end do ! end do ! t2 = omp_get_wtime() !============================ !============================ ! Переработанный алгоритм пузырька для распараллеливания !============================ t1 = omp_get_wtime() do i = 1,n,1 first = mod(i,2) do j = first,n-1,2 if(b(j) > b(j+1)) then call swap(b(j),b(j+1)) end if end do Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 53
t2 = omp_get_wtime()
bubble
! - Подпрограмма для перестановки элементов массива subroutine swap(a, b) real :: a, b real :: tmp tmp = a
a = b b = tmp
end subroutine swap Последовательный и параллельный алгоритмы иллюстрируются на рис. 3.1 и 3.2:
Отчёт должен включать: 1) титульный лист; 2) формулировку цели работы; 3) описание результатов выполнения задания:
54 Глава 3. OpenMP Рис. 3.2. Параллельный алгоритм сортировки пузырьком – результаты выполнения программ (текст, снимок экрана, таблицы и графики в в зависимости от задания); 4) выводы по каждому заданию лабораторной работы.
1. В чём заключается основное отличие процесса от потока/нити? 2. Какие преимущества даёт технология OpenMP? 3. Оправдано ли использование технологии OpenMP (и вообще многопо- точного программирования) при написании пользовательских программ для персонального компьютера? 4. Как реализуется применение OpenMP при написании программ на языке Fortran? На языках C/C++? 5. Перечислите наиболее используемые директивы OpenMP. 6. Перечислите наиболее используемые функции из библиотеки OpenMP. 7. Какие переменные окружения влияют на число создаваемых потоков? 8. Поясните смысл идеологии Single Program Multiple Data на конкретном примере (можно воспользоваться одной из вышеизложенных программ).
55 4. MPI 4.1. Введение Для компьютеров с раздельной оперативной памятью технология Open- MP уже не применима. В таких системах основным способом параллелиза- ции программ является организация обмена данными между процессами. Одной из технологий, позволяющих организовать взаимодействие парал- лельно выполняемых процессов, является технология обмена сообщения- ми MPI. Аббревиатура MPI расшифровывается как Message Passing Interface — интерфейс передачи сообщений. MPI изначально поддерживается языками C и Fortran , однако существуют библиотеки и для других языков. В отличие от OpenMP основной парадигмой программирования MPI является MIMD (Multiple Instructions Multiple Data), что дословно можно перевести как множество инструкций – множество данных, а на практике означает, что параллельный вариант кода программы существенно отли- чается от последовательного. Напомним, что при программировании с ис- пользованием OpenMP, напротив, код параллельной программы в идеаль- ном случае отличается от кода параллельной программы только наличием директив OpenMP. 4.2. MPI и Fortran MPI является стандартом и не включает в себя конкретные реализации процедур, поэтому для Unix систем существует несколько реализаций MPI, в том числе и коммерческих. Мы будем рассматривать свободно распро- страняемую реализацию под названием mpich. Именно эта версия доступна для использования в дисплейных классах. Для компиляции и запуска Фортран-программы с использованием MPI следует выполнить следующие команды: mpif90 src-file.f90 -o prog-name mpirun -np N prog-name С помощью первой программы исходный файл src-file.f90 програм-
мы компилируется в исполняемый файл prog-name , а с помощью коман- ды mpirun полученный файл запускается с поддержкой MPI. Опция -np
N указывает число N параллельных процессов, которые необходимо поро- дить. Заметим также, что в зависимости от версии mpich
для запуска испол- няемого файла на локальном компьютере может быть необходимо указание дополнительной опции -host localhost , т.е. mpirun -np N -host localhost prog-name 56 Глава 4. MPI Перейдём теперь к рассмотрению основ MPI применительно к языку Фортран. Для использования подпрограмм и функций MPI необходимо под- ключить заголовочный файл: include
'mpif.h' . Для предотвращения конфликтов с другими библиотеками все дополнительные объекты, проце- дуры, константы, типы данных, используемые в MPI, имеют префикс mpi_ .
процессов. Заметим, что, в отличие от OpenMP, это не нити, а полноценные процессы, их порождение и завершение сравнительно ресурсоёмко. Поэто- му фиксированное число процессов порождается единожды, и в ходе рабо- ты нельзя создать дополнительные процессы или же уничтожить работаю- щие (хотя в современных версиях MPI эта возможность есть). У каждого процесса своё адресное пространство и свой набор перемен- ных. Все взаимодействие между ними осуществляется с помощью переда- чи и приёма сообщений. При передаче сообщений от процесса к процессу необходимо иметь возможность однозначно идентифицировать каждый процесс, а также груп- пы процессов. Для этих целей используется два атрибута:
comm_id
) — идентификатор группы процес- сов;
– идентификатор процесса ( proc_id
). Любой процесс однозначно адресуется comm_id и
. По умолчанию создаются три коммуникатора: – mpi_comm_world — все созданные процессы;
mpi_comm_self — только текущий процесс;
mpi_comm_null — ни один процесс. Указанные названия можно использовать непосредственно в программе, так как они определяются при подключении библиотеки. Каждое сообщение имеет следующие атрибуты: – номер процесса отправителя; – номер процесса получателя; – коммуникатор процесса получателя; – идентификатор сообщения (tag, тег). Идентификатор сообщения является неотрицательным числом типа integer и позволяет программисту при необходимости разбить все передаваемые сообщения на классы. 4.3. Основные процедуры MPI Перейдём к рассмотрению основных и некоторых вспомогательных про- цедур MPI. В каждой программе обязательно должны присутствовать вызовы сле- дующих двух подпрограмм:
Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 57 Первая подпрограмма инициализирует параллельную часть програм- мы, а вторая завершает параллельную часть. После mpi_finalise обраще- ние к любой процедуре MPI запрещено, в том числе и к процедуре mpi_init . Из этого следует, что в рамках программы допустима только одна парал- лельная часть. Рассмотрим первый пример: program ex1 implicit none include 'mpif.h' integer :: ierr logical :: flag ! В зависимости от реализации MPI следующее сообщение ! будет напечатано или только одним процессом, или же ! всеми созданными процессами write (*,*),"До параллельной части" call mpi_init(ierr) !------------------------------------- call mpi_initialized(flag, ierr) if(flag) then ! Следующее сообщение обязательно будет распечатано ! всеми процессами write (*,*), "Параллельная часть" end if !------------------------------------- call mpi_finalize(ierr) write (*,*), "После параллельной части" end program ex1 В этом примере используется процедура mpi_initialized(flag, ierr) которая записывает в переменную flag значение
.true. в случае, если процедура вызвана в параллельной области, и .false.
, если процедура вызвана вне параллельной области. Следующие две процедуры используются для получения идентифика- торов процесса ( comm_id ) и коммуникатора ( proc_id ):
call mpi_comm_size(comm_id, comm_size, ierr) call mpi_comm_rank(comm_id, proc_id, ierr) В переменную comm_size записывается число процессов в коммуникато- ре comm_id
. Следующий пример иллюстрирует применение данных про- цедур:
program ex2 implicit none include 'mpif.h' integer :: ierr ! Число процессов в коммуникаторе integer :: comm_size 58 Глава 4. MPI ! Номер процесса integer :: proc_id call mpi_init(ierr) !------------------------------------- call mpi_comm_size(mpi_comm_world, comm_size, ierr) call mpi_comm_rank(mpi_comm_world, proc_id, ierr) write(*,*), "Процесс №", proc_id, ", всего ", comm_size !------------------------------------- call mpi_finalize(ierr) end program ex2 Следующий пример ( ex3 ) показывает использование процедуры mpi_- get_processor_name, которая позволяет получить имя используемого про- цессора (это актуально, например, в случае кластера): integer :: length character(len = mpi_max_processor_name) :: processor_name mpi_get_processor_name(processor_name, length, ierr) Обратите внимание на использование переменной length , благодаря которой имя процессора выводится в консоль без дополнительных знаков пробела:
program ex3 implicit none include 'mpif.h' integer :: ierr ! Количество символов в имени процессора integer :: length ! Имя процессора character(len = mpi_max_processor_name) :: processor_name real(kind = 8) :: time !!! call mpi_init(ierr) !------------------------------------- time = mpi_wtime(ierr) call mpi_get_processor_name(processor_name, length, ierr) write(*,*), "Процессор ", processor_name(1:length), & " Время ", time !------------------------------------- call mpi_finalize(ierr) end program ex3 4.4. Приём и передача сообщений Подновляющее число процедур MPI служит для приёма и отправки со- общений между процессами. Все процедуры по приёму и передаче сооб- щений можно разделить на два класса: Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 59
– приём и передача без блокировки (асинхронные). Здесь мы изучим лишь процедуры с блокировкой. Для дальнейшего изуче- ния следует обратиться к методическому пособию [1]. Две основные процедуры MPI: mpi_send — отправка сообщения и mpi_recv — приём сообщения. Рассмотрим их по порядку. < type> :: msg(*) integer :: count, datatype, proc_id, & msgtag, comm_id, ierr mpi_ssend(msg, count, datatype, proc_id, & msgtag, comm_id, ierr) – count
— число элементов в массиве-сообщении msg
; – datatype
— тип элементов в массиве msg
; – proc_id
— идентификатор процесса-получателя; – msgtag
— тег сообщения (идентификатор сообщения); – comm_id
— идентификатор коммуникатора; – ierr
— служебная переменная для записи кода ошибки. Следует подробнее остановиться на параметре datatype . В MPI для передачи сообщений определены свои типы, эквивалентные стандартным типам Фортрана: Тип данных MPI Расшифровка mpi_integer целые числа mpi_real вещественные числа mpi_double_precision вещественные числа двойной точности mpi_complex комплексные числа mpi_logical логический тип mpi_character текстовой тип Все эти типы данных уже предопределены, и их следует использовать при вызове процедур. Параметр proc_id
может принимать специальное значение
mpi_proc_null , адресующее несуществующий процесс. Операции по пе- ресылке сообщения этому процессу завершаются немедленно с успешным кодом завершения, и выполнение программы продолжается. Следует также иметь в виду модификацию процедуры mpi_send
, про- цедуру
mpi_ssend , которая осуществляет пересылку сообщения с синхро- низацией. Это означает, что передающий процесс не продолжит работу, пока посланное им сообщение не будет принято. Использовать пересылку с синхронизацией следует внимательно, во избежании блокировки. Рассмотрим теперь процедуру по приёму сообщения: < type> :: msg(*) integer :: count, datatype, proc_id, msgtag, comm_id, ierr integer :: status(mpi_status_size) mpi_recv(msg, count, datatype, proc_id, & msgtag, comm_id, status, ierr)
60 Глава 4. MPI Здесь status
— целочисленный массив размера mpi_status_size , в ко- торый записывается информация о переданном сообщении. Перечислим важнейшие его элементы: – mpi_source — номер процесса отправителя;
mpi_tag
— идентификатор сообщения; – mpi_error — код ошибки. Параметр
proc_id может
принимать предопределённое значение mpi_any_source , а параметр mstag
также может принимать значение mpi_any_tag . Приведём теперь пример использования процедур передачи и приёма: program ex4 implicit none include 'mpif.h' integer, parameter :: n = 100 integer :: proc_id, ierr, tag integer, dimension(1:mpi_status_size) :: status character(len = n) :: msg1 character(len = n) :: msg2 msg1 = "Привет параллельному процессу!" tag = 10
tag, mpi_comm_world, ierr) write(*,*),"Процесс №", proc_id, "послал сообщение: ", msg1 else if (proc_id .eq. 1) then call mpi_recv(msg2, n, mpi_character, 0, tag, mpi_comm_world, status, ierr) write(*,*),"Процесс №", proc_id, & "принял сообщение: ", msg2 write(*,*), "status(mpi_source)=", status(mpi_source) write(*,*), "status(mpi_tag)=", status(mpi_tag) write(*,*), "status(mpi_error)=", status(mpi_error) end if !---------------------------------- call mpi_finalize(ierr) end program ex4 Схема, показанная в данном примере, используется в любой программе, написанной с использованием MPI. Вначале параллельной области вызы- вается процедура mpi_comm_rank и в переменную proc_id записывается идентификатор процесса. Так как в MPI нет разделяемых переменных, то значения
proc_id будут различаться для каждого процесса. Это можно ис- пользовать для выделения участков кода, предназначенных для выполне-
Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 61 ния конкретным процессом, что и было сделано в вышеизложенном приме- ре с помощью операторов условия. Следует всегда помнить, что никакого автоматического распараллеливания программы в MPI не предусмотрено и разделить участки кода между процессами необходимо вручную.
mpi_probe(proc_id, msgtag, comm_id, status, ierr) Процедура mpi_probe получает информацию о структуре ожидаемо- го сообщения с идентификатором mstag от процесса с идентификатором proc_id в коммуникаторе comm_id . При этом ожидание сопровождается блокировкой. Важно, что mpi_probe сообщение не принимает и после него надо вызывать mpi_recv . В этом случае будет получено то сообщение, ин- формацию о котором получила процедура mpi_probe . В нижеследующем примере показано применение этой процедуры. program ex5 implicit none include 'mpif.h' integer:: proc_id, ierr integer, dimension(1:mpi_status_size) :: status integer :: im real :: rm call mpi_init(ierr) !---------------------------------- call mpi_comm_rank(mpi_comm_world, proc_id, ierr) ! Две переменные разного типа для отправки im = proc_id rm = 1.0*proc_id
mpi_comm_world, ierr) end if if(proc_id .eq. 2) then call mpi_ssend(rm, 1, mpi_real, 0, 5, mpi_comm_world, ierr) end if ! Прием отправленных сообщений if(proc_id .eq. 0) then call mpi_probe(mpi_any_source, 5, mpi_comm_world, status, ierr) ! Если первым пришло сообщение от первого процесса if(status(mpi_source) .eq. 1) then call mpi_recv(im, 1, mpi_integer, 1, 5, mpi_comm_world, status, ierr) call mpi_recv(rm, 1, mpi_real, 2, 5, mpi_comm_world, status, ierr) 62 Глава 4. MPI ! Если первым пришло сообщение от второго процесса else if(status(mpi_source) .eq. 2) then call mpi_recv(rm, 1, mpi_real, 2, 5, mpi_comm_world, status, ierr) call mpi_recv(im, 1, mpi_integer, 1, 5, mpi_comm_world, status, ierr) end if write(*,*) "Процесс 0 получил", im, " от процесса 1, ", & rm, "от процесса 2" end if !---------------------------------- call mpi_finalize(ierr) end program ex5 В завершение приведём пример по параллельному вычислению суммы массива:
tag = 10
call random_number(array) call mpi_init(ierr) !---------------------------------- call mpi_comm_rank(mpi_comm_world, proc_id, ierr) ! Процесс 0 суммирует половину массива ! и отправляет результат процессу 2 if (proc_id .eq. 0) then a = sum(
array(1:50000000)) call mpi_send(a, 1, mpi_real, 2, tag, mpi_comm_world, ierr) write(*,*), "Процесс 0 закончил суммирование" ! Процесс 1 суммирует вторую половину массива ! и также отправляет результат процессу 2 else if (proc_id .eq. 1) then b = sum(
array(50000001:100000000)) call mpi_send(b, 1, mpi_real, 2, tag, mpi_comm_world, ierr) write(*,*), "Процесс 1 закончил суммирование" ! Процесс 2 складывает полученные от проц 0 и 1 результаты else if (proc_id .eq. 2) then t1 = mpi_wtime(ierr) Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 63
mpi_comm_world, status, ierr)
mpi_comm_world, status, ierr) array_sum = aa + bb t2 = mpi_wtime(ierr) ! Распечатываем затраченное время write(*,*), "t2-t1", t2-t1 ! Для сравнения быстродействия суммируем последовательно t1 = mpi_wtime(ierr) array_sum = sum(
t2 = mpi_wtime(ierr) write(*,*), "t2-t1", t2-t1 end if !---------------------------------- call mpi_finalize(ierr) end program ex6 4.5. Задания для лабораторной работы 4.5.1. Задание № 1 Написать программу по перемножению матриц по стандартному алго- ритму и по алгоритму Винограда. Распараллелить её, используя MPI. Срав- нить быстродействие по сравнению с последовательным вариантом и в за- висимости от числа используемых процессов.
Исследование эффективности реализации двухсторонних передач дан- ных. Постановка задачи. Разработать алгоритм передачи данных между про- цессами по кругу: – второй процесс передаёт данные первому процессу; – третий процесс, получив данные от нулевого, передаёт их второму, – i-й процесс принимает данные от (i-1) процесса и пересылает их (i+1) процессу, последний процесс передаёт данные нулевому и т.д. Требуется:
щих передач программы; – исследовать время решения задачи для длин сообщений: 128, 512, 1024, 2048 и 4096 байт; – число циклов круговой передачи задавать параметром командной стро- ки;
64 Глава 4. MPI – построить графики времени выполнения одного цикла передачи, усред- нённого по числу кругов, для сообщений разной длины и разного числа процессов.
Распараллелить программу, вычисляющую определённый интеграл, с помощью MPI. В качестве примера взять любой вычисляемый в конеч- ном виде (для проверки результата работы программы) определённый ин- теграл.
Отчёт должен включать: 1) титульный лист; 2) формулировку цели работы; 3) описание результатов выполнения задания:
графики в в зависимости от задания); 4) выводы по каждому заданию лабораторной работы.
1. Назовите главные отличия OpenMP и MPI. В каких случаях какую из этих технологий предпочтительнее использовать? 2. Как на практике реализуется парадигма Multiple Instructions Multiple Data (MIMD)? 3. Какие типы данных определены в MPI? Как они соотносятся с типами данных языка Фортран? 4. Кратко опишите суть технологии MPI. 5. Какие разновидности процедуры mpi_send() существуют? В чем их от- личие друг от друга? 6. Укажите основные различия между синхронным (блокирующим) и асин- хронным способами передачи сообщений. 7. На основании чего в MPI можно однозначно идентифицировать тот или иной процесс? 8. Последовательная часть программы (до директивы mpi_init(ierr) ) будет выполняться всеми процессами одновременно или же только од- ним процессом? 65 Литература 1. Антонов А. С. Параллельное программирование с использованием тех- нологии MPI. — Москва : Издательство МГУ, 2004. — 77 с. — ISBN: 5- 211-04907-1. 2. Антонов А. С. Параллельное программирование с использованием тех- нологии OpenMP. — Москва : Издательство МГУ, 2009. — 77 с. — ISBN: 978-5-211-05702-9. 3. Богачев К. Ю. Основы параллельного программирования. — Москва : Бином, 2003. — 342 с. — ISBN: 5-94744-037-0. 4. Макконнелл Д. Анализ алгоритмов. — 3 изд. — Москва : Техносфера, 2009. — 416 с. — ISBN: 978-5-94836-216-8. 5. Старченко А. В., Данилкин Е. А., Лаева В. И., Проханов С. А. Практи- кум по методам параллельных вычислений. — Москва : Издательство Московского университета, 2010. — 200 с. — ISBN: 978-5-211-05976-4. 6. Рыжиков Ю. И. Современный Фортран. — Санкт-Петербург : Корона Принт, 2009. — 288 с. — ISBN: 978-5-7931-0514-9. 7. Якобовский М. В. Введение в параллельные методы решения задач. — Москва : Издательство Московского университета, 2013. — 328 с. — ISBN: 918-5-211-06382-2.
Учебно-методический комплекс дисциплины «Параллельное программирование» Рекомендуется для направления подготовки «Математика и компьютерные науки» и «Прикладная математика и информатика» Квалификация (степень) выпускника: бакалавр 67
68 69 Программа дисциплины Цели и задачи дисциплины Целью дисциплины является введение учащихся в предметную область современных параллельных вычислений. В процессе преподавания дисциплины решаются следующие задачи: – освоение архитектурных принципов реализации параллельной обработ- ки в вычислительных машинах; – изучение методов и языковых механизмов конструирования параллель- ных программ; – овладение параллельными вычислительными методами. Место дисциплины в структуре основной образовательной программы Дисциплина относится к базовой части профессионального цикла. Требования к входным знаниям, умениям и компетенциям студен- та: требуется пройти обучение по дисциплинам «Операционные систе- мы», «Языки и методы программирования», «Численные методы». Требования к результатам освоения дисциплины Процесс изучения дисциплины направлен на формирование следую- щих компетенций (указываются в соответствии с ФГОС ВПО):
ОК-6 — способность применять в научно-исследовательской и профес- сиональной деятельности базовые знания в области фундаментальной и прикладной математики и естественных наук; ОК-7 — обладать значительными навыками самостоятельной научно- исследовательской работы; ОК-10 — умение быстро находить, анализировать и грамотно контекст- но обрабатывать научно-техническую, естественнонаучную и общенауч- ную информацию, приводя ее к проблемно-задачной форме; ОК-11 — обладать фундаментальной подготовкой в области фундамен- тальной математики и компьютерных наук, готовность к использованию полученных знаний в профессиональной деятельности; ОК-12 — владеть значительными навыками самостоятельной работы с компьютером, программирования, использования методов обработки ин- формации и численных методов решения базовых задач;
70 УМК дисциплины ОК-13 — владеть базовыми знаниями в области информатики и совре- менных информационных технологий, навыками использования программ- ных средств и навыками работы в компьютерных сетях, умение создавать базы данных и использовать ресурсы Интернета; ПК-1 — умение определять общие формы, закономерности, инструмен- тальные средства отдельной предметной области; ПК-2 — умение понять поставленную задачу; ПК-3 — умение формулировать результат; ПК-7 — умение грамотно пользоваться языком предметной области; ПК-8 — умение ориентироваться в постановках задач; ПК-9 — знание корректных постановок классических задач; ПК-10 — понимание корректности постановок задач; ПК-11 — владение навыками самостоятельного построения алгоритма и его анализа; ПК-14 — владение навыками контекстной обработки информации; ПК-19 — владение методом алгоритмического моделирования при ана- лизе постановок математических задач; ПК-20 — владение методами математического и алгоритмического мо- делирования при анализе и решении прикладных и инженерно-технических проблем;
ПК-22 — умение увидеть прикладной аспект в решении научной зада- чи, грамотно представить и интерпретировать результат; ПК-23 — умение проанализировать результат и скорректировать мате- матическую модель, лежащую в основе задачи; ПК-24 — владение методами алгоритмического моделирования при ана- лизе управленческих задач в научно-технической сфере, а также в эконо- мике, бизнесе и гуманитарных областях знаний.
ОК-11 — способность владения навыками работы с компьютером как средством управления информацией; ОК-12 — способность работать с информацией в глобальных компью- терных сетях; ОК-14 — способность использовать в научной и познавательной дея- тельности, а также в социальной сфере профессиональные навыки работы с информационными и компьютерными технологиями; ОК-15 — способность работы с информацией из различных источни- ков, включая сетевые ресурсы сети Интернет, для решения профессиональ- ных и социальных задач; ПК-1 — способность демонстрации общенаучных базовых знаний есте- ственных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и ин- форматикой; ПК-2 — способность приобретать новые научные и профессиональные знания, используя современные образовательные и информационные тех- нологии;
Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 71 ПК-3 — способность понимать и применять в исследовательской и при- кладной деятельности современный математический аппарат; ПК-6 — способность осуществлять целенаправленный поиск информа- ции о новейших научных и технологических достижениях в сети Интернет и из других источников; ПК-7 — способность собирать, обрабатывать и интерпретировать дан- ные современных научных исследований, необходимые для формирования выводов по соответствующим научным, профессиональным, социальным и этическим проблемам; ПК-9 — способность решать задачи производственной и технологиче- ской деятельности на профессиональном уровне, включая: разработку ал- горитмических и программных решений в области системного и приклад- ного программирования; ПК-10 — способность применять в профессиональной деятельности со- временные языки программирования и языки баз данных, операционные системы, электронные библиотеки и пакеты программ, сетевые техноло- гии.
В результате изучения дисциплины студент должен: Знать: – общие реализации параллельной обработки в вычислительных маши- нах;
– методы и языковые механизмы конструирования параллельных программ; – параллельные вычислительные методы; – корректные постановки классических задач; – корректность постановок задач. Уметь: – быстро находить, анализировать и грамотно контекстно обрабатывать научно-техническую информацию, приводя ее к проблемно-задачной фор- ме;
отдельной предметной области — операционных систем; – понять поставленную задачу; – формулировать результат; – грамотно пользоваться языком предметной области; – ориентироваться в постановках задач; – увидеть прикладной аспект в решении научной задачи, грамотно пред- ставить и интерпретировать результат; – проанализировать результат и скорректировать математическую модель, лежащую в основе задачи. Владеть: – способностью применять в научно-исследовательской и профессиональ- ной деятельности базовые знания в области фундаментальной и при- кладной математики и естественных наук;
72 УМК дисциплины – значительными навыками самостоятельной научно-исследовательской работы;
– фундаментальной подготовкой в области компьютерных наук; – значительными навыками самостоятельной работы с компьютером, про- граммирования, использования методов обработки информации; – базовыми знаниями в области информатики и современных информа- ционных технологий, навыками использования программных средств и навыками работы в компьютерных сетях;
тематических задач; – методами математического и алгоритмического моделирования при ана- лизе и решении прикладных и инженерно-технических проблем; – методами алгоритмического моделирования при анализе управленческих задач в научно-технической сфере; – параллельными вычислительными методами. Объём дисциплины и виды учебной работы Общая трудоемкость дисциплины составляет 3 зачетные единицы. № Вид учебной работы Всего часов Се- мест- ры 7 1. Аудиторные занятия (всего) 51 51 В том числе: 1.1.
Лекции - - 1.2. Прочие занятия - -
1.2.1. Практические занятия (ПЗ) - - 1.2.2. Семинары (С) - - 1.2.3. Лабораторные работы (ЛР) 51 51 1.2.4. Из них в интерактивной форме (ИФ) 51 51 Геворкян М. Н., Королькова А. В., Кулябов Д. С. Параллельное программирование 73 2. Самостоятельная работа студентов 57 57 В том числе: 2.1.
Курсовой проект (работа) - - 2.2. Расчетно-графические работы - -
Реферат - - 2.4. Подготовка и прохождение промежуточной аттестации 27 27 2.5. Другие виды самостоятельной работы: 2.5.1.
Самостоятельная проработка дополнитель- ных материалов по дисциплине 30 30
Выполнение домашних заданий - - 3. Общая трудоёмкость (ак.часов) 108 108 4.
3 3 Содержание дисциплины Содержание разделов дисциплины № п/п Наимено- вание
раздела дисципли- ны Содержание раздела 1. Язык
Фортран Основные сведения о языке Фортран. История развития. Его преимущества в области научных вычислений по сравнению с другими языками высокого уровня. Структура программы. Типы данных. Встроенные операции и функции. Опе- раторы управления и ветвления. Массивы и рабо- та с ними: описание массивов, задание массивов, динамические массивы, основные функции рабо- ты с массивами как матрицами. Ввод и вывод 74 УМК дисциплины 2. Библиотека LAPACK Основные сведения. Матричные разложения и их использование для численных расчётов. Система наименований подпрограмм LAPACK. Матрич- ные разложения. Процедуры SGESV, SGETRF, SGEEV, SGESVD 3. Технология OpenMP Основные сведения. OpenMP и Fortran. Нити и процессы. Параллельные и последовательные об- ласти. Параллельные циклы и параллельные об- ласти. Автоматическое распараллеливания цик- лов
4. Технология MPI Основные сведения. Способы распараллеливания численных методов. Основные процедуры MPI. Типы данных MPI. Способы передачи сообще- ний. Прием и передача сообщений процессами
1. Язык Фортран - - 15 15 15
2. Библиотека LAPACK - - 12 12 14 26 3. Технология OpenMP - - 12 12 14
4. Технология MPI - - 12 12 14
Итого: - - 51 51 57 108 Описание интерактивных занятий № п/п № р/д жүктеу/скачать 0,58 Mb. Достарыңызбен бөлісу:
|