Модели и средства программирования для многопроцессорных вычислительных систем

OpenMP

Разбить на страницы
Показывать лекцию целиком

OpenMP - стандарт программного интерфейса приложений для параллельных систем с общей памятью. Поддерживает языки C, C++, Фортран.

Модель программы в OpenMP

(рис 2.1) Модель параллельной программы в OpenMP

Модель параллельной программы в OpenMP можно сформулировать следующим образом:

  • Программа состоит из последовательных и параллельных секций (рис. 2.1).
  • В начальный момент времени создается главная нить, выполняющая последовательные секции программы.
  • При входе в параллельную секцию выполняется операция fork,порождающая семейство нитей. Каждая нить имеет свой уникальный числовой идентификатор (главной нити соответствует 0). При распараллеливании циклов все параллельные нити исполняют один код. В общем случае нити могут исполнять различные фрагменты кода.
  • При выходе из параллельной секции выполняется операция join.Завершается выполнение всех нитей, кроме главной.
    •

    OpenMP составляют следующие компоненты:

  • Директивы компилятора - используются для создания потоков, распределения работы между потоками и их синхронизации. Директивы включаются в исходный текст программы.
  • Подпрограммы библиотеки времени выполнения - используются для установки и определения атрибутов потоков. Вызовы этих подпрограмм включаются в исходный текст программы.
  • Переменные окружения - используются для управления поведением параллельной программы. Переменные окружения задаются для среды выполнения параллельной программы соответствующими командами (например, командами оболочки в операционных системах UNIX ).
    •

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

    Привязка к языку Fortran

    В программах на языке Fortran директивы компилятора, имена подпрограмм и переменных окружения начинаются с OMP. Формат директивы компилятора:

    {!|C|*}$OMP директива [оператор_1[, оператор_2, ...]]

    Директива начинается в первой (фиксированный формат записи текста языка Fortran 77 ) или произвольной (свободный формат) позиции строки. Допускается продолжение директивы в следующей строке, в этом случае действует стандартное в данной версии языка правило для обозначения строки продолжения (непробельный символ в шестой позиции для фиксированного формата записи и амперсанд для свободного формата).

    Пример программы на языке Fortran с использованием OpenMP

    program omp_example
integer i, k, N
real*4 sum, h, x
print *, "Please, type in N:"
read *, N
h = 1.0 / N
sum = 0.0
C$OMP PARALLEL DO SCHEDULE(STATIC) REDUCTION(+:sum)
do i = 1, N
x = i  * h
sum = sum + 1.e0  * h /   (1.e0 + x**2)
enddo
print *,   4.0  * sum end

    Привязка к языку C

    В программах на языке C прагмы, имена функций и переменных окружения OMP начинаются с omp, omp или OMP. Формат директивы:

    #pragma omp директива [оператор_1[, оператор_2, ...]]

    В OpenMP -программе используется заголовочный файл omp.h.

    Пример программы на языке С с использованием OpenMP

    #include "omp.h" #include <stdio.h> double f(double x) {
return 4.0  / (1 + x * x);
}
main() {
const long N = 100000;
long i;
double h, sum, x; sum = 0;
h = 1.0  / N;
#pragma omp parallel shared(h) {
#pragma omp for private(x) reduction(+:sum) for  (i = 0;  i < N;  i++) 
{ x = h * (i + 0.5); 
sum = sum + f(x);
}
}
printf("PI = %f\n",  sum / N);
}

    Директивы OpenMP

    Далее приводится перечень директив OpenMP. Описания директив OpenMP ориентированы на спецификацию версии 2.5.

    parallel
. . .
end parallel

    Задает границы параллельной секции программы. С данной директивой могут использоваться следующие операторы (их описание дается далее):

  • private;
  • shared;
  • default;
  • firstprivate;
  • reduction;
  • if;
  • copyin;
  • num_threads.
    •  
    do
цикл do end do
#pragma omp for цикл for

    Задает границы цикла, исполняемого в параллельном режиме в языках Fortran и C соответственно. С данной директивой могут использоваться следующие операторы:

  • private;
  • firstprivate;
  • lastprivate;
  • reduction;
  • schedule;
  • ordered;
  • nowait.
    •  
    sections 
...
end sections

    Обрамляет параллельную секцию программы. Вложенные секции программы, задаваемые директивами section, распределяются между нитями. С данной директивой могут использоваться следующие операторы:

  • private;
  • firstprivate;
  • lastprivate;
  • reduction;
  • nowait.
    •

    section

    Определяет часть sections, которая выполняется одной нитью.

    single
...
end single

    Обрамляет блок программы, который должен выполняться одной нитью. С данной директивой могут использоваться следующие операторы:

  • private;
  • firstprivate;
  • copyprivate;
  • nowait.
    •  
    workshare 
...
end workshare

    Делит блок на части, выполнение которых распределяется между нитями таким образом, что каждая часть выполняется один раз. Блок может содержать только следующие конструкции:

  • присваивания массивов;
  • скалярные присваивания;
  • FORALL;
  • WHERE;
  • atomic;
  • critical;
  • parallel.
    •  
    parallel do цикл do
end parallel do

    Объединяет директивы parallel и do.

    parallel sections
...
end parallel sections

    Объединяет директивы parallel и sections.

    parallel workshare
...
end parallel workshare

    Объединяет директивы parallel и workshare.

    master
...
end master

    Обрамляет блок программы, который должен выполняться только главной нитью.

    critical[(блокировка)] 
...
end critical[(блокировка)]

    Обрамляет блок программы, доступ к которому в любой момент времени может получить только одна нить (критическая секция). Блокировка - необязательное имя критической секции. Квадратные скобки указывают, что имя не является обязательным и может быть опущено.

    barrier

    Директива барьерной синхронизации нитей. Каждая нить, выполнение которой достигло данной точки, приостанавливает свое выполнение до тех пор, пока все нити не достигнут данной точки.

    atomic

    Объявляет операцию атомарной (при выполнении атомарной операции одновременный доступ к памяти по записи разных нитей запрещен). Применяется только к оператору, непосредственно следующему после данной директивы. Он может иметь следующий вид:

  • x = x {+|-|*|/|.AND.|.OR.|.EQV.|.NEQV.} скалярное_выражение_не_содержащее_х
  • x = скалярное_выражение_не_содержащее_х {+|-|*|/|.AND.|.OR.|.EQV.|.NEQV.} x
  • x = {MAX|MIN|IAND|IOR|IEOR} (x, скалярное_выражение_не_содержащее_x)
  • x = {MAX|MIN|IAND|IOR|IEOR} (скалярное_выражение_не_содержащее_x, x)
    •

    flush[(список переменных)]

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

    ordered
...

end ordered

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

    threadprivate(список common-блоков)

    Определяет common -блоки, перечисленные в списке, локальными.

    Операторы OpenMP

    Операторы OpenMP используются совместно с директивами.

    private(список переменных)

    Объявляет переменные из списка локальными.

    firstprivate(список переменных)

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

    lastprivate( список переменных)

    Объявляет переменные из списка локальными и назначает им значения из того блока программы, который был выполнен последним.

    copyprivate( список переменных)

    После завершения выполнения блока, заданного директивой single, значения локальных переменных из списка распределяются между остальными нитями.

    nowait

    Отменяет барьерную синхронизацию при завершении выполнения параллельной секции.

    shared( список переменных)

    Объявляет переменные из списка общими для всех нитей.

    default(private|shared|none)

    Данный оператор позволяет изменить правила определения области видимости переменных, действующие по умолчанию. Вариант private используется только в языке Fortran.

    reduction(операция|встроенная функция: список переменных)

    Оператор приведения (редукции) значений локальных переменных из списка с помощью указанной операции или встроенной функции языка. Операция редукции применяется к нескольким значениям и возвращает одно значение.

    if(скалярное логическое выражение)

    Условный оператор.

    num_threads( скалярное целое выражение)

    Задает количество нитей. Альтернативный способ задания количества нитей обеспечивает переменная окружения OMP_NUM_THREADS.

    schedule(характер_распределения_итераций[, количество_итераций_цикла])

    Данный оператор задает способ распределения итераций цикла между нитями:

  • static - количество итераций цикла, передаваемых для выполнения каждой нити фиксировано и распределяется между нитями по принципу кругового планирования. Если количество итераций не указано, оно полагается равным 1;
  • dynamic - количество итераций цикла, передаваемых для выполнения каждой нити фиксировано. Очередная "порция" итераций передается освободившейся нити;
  • guided - количество итераций цикла, передаваемых для выполнения каждой нити постепенно уменьшается. Очередная "порция" итераций передается освободившейся нити;
  • runtime - тип распределения работы определяется во время выполнения программы, например, с помощью переменной окружения OMP_SCHEDULE.
    •

    copyin(список имен common-блоков)

    При выполнении этого оператора данные из главной нити копируются в локальные экземпляры common -блока в начале каждой параллельной секции. Имена задаются между символами "/ ".

    Подпрограммы OpenMP

    Подпрограммы, формирующие среду выполнения параллельной программы

    Здесь и далее вначале приводится интерфейс подпрограмм OpenMP для языка C, затем для языка Fortran.

    void omp_set_num_threads(int threads);

subroutine omp_set_num_threads(threads) integer threads

    Задает количество потоков ( threads ) при выполнении параллельных секций программы.

    int omp_get_num_threads(void);

integer function omp_get_num_threads()

    Возвращает количество потоков, используемых для выполнения параллельной секции.

    int omp_get_max_threads(void); 
integer function omp_get_max_threads()

    Возвращает максимальное количество потоков, которые можно использовать для выполнения параллельных секций программы.

    int omp_get_thread_num(void);

integer function omp_get_thread_num()

    Возвращает идентификатор нити, из которой вызывается данная функция.

    int omp_get_num_procs(void);

integer function omp_get_num_procs()

    Возвращает количество процессоров, доступных в данный момент программе.

    int omp_in_parallel(void);

logical function omp_in_parallel()

    Возвращает значение true при вызове из активной параллельной секции программы.

    void omp_set_dynamic(int threads);

subroutine omp_set_dynamic(threads)

logical threads

    Включает или отключает возможность динамического назначения количества потоков при выполнении параллельной секции. По умолчанию эта возможность отключена.

    int omp_get_dynamic(void);

logical function omp_get_dynamic()

    Возвращает значение true, если динамическое назначение количества потоков разрешено.

    void omp_set_nested(int nested);

subroutine omp_set_nested(nested) integer nested

    Разрешает или запрещает вложенный параллелизм. По умолчанию вложенный параллелизм запрещен.

    int omp_get_nested(void);

logical function omp_get_nested()

    Определяет, разрешен ли вложенный параллелизм.

    Подпрограммы для работы с блокировками

    Блокировки используются для предотвращения эффектов, приводящих к непредсказуемому (недетерминированному) поведению программы. Среди таких эффектов, например, гонки за данными, когда более чем один поток имеет доступ к одной и той же переменной.

    void omp_init_lock(omp_lock_t *lock);

subroutine omp_init_lock(lock) integer(kind = omp_lock_kind) :: lock

    Инициализирует блокировку, связанную с идентификатором lock, для использования в последующих вызовах подпрограмм.

    void omp_destroy_lock(omp_lock_t *lock);

subroutine omp_destroy_lock(lock) integer(kind = omp_lock_kind) :: lock

    Переводит блокировку, связанную с идентификатором lock, в состояние неопределенности.

    void omp_set_lock(omp_lock_t *lock);
subroutine omp_set_lock(lock)
integer(kind = omp_lock_kind) lock

    Переводит потоки из состояния выполнения в состояние ожидания до тех пор, пока блокировка, связанная с идентификатором lock, не окажется доступной. Поток становится владельцем доступной блокировки.

    void omp_unset_lock(omp_lock_t *lock);

subroutine omp_unset_lock(lock) integer(kind = omp_lock_kind) :: lock

    После выполнения данного вызова поток перестает быть владельцем блокировки, связанной с идентификатором lock. Если поток не был владельцем блокировки, результат вызова не определен.

    int omp_test_lock(omp_lock_t *lock);

logical function omp_test_lock(lock) integer(kind = omp_lock_kind) :: lock

    Возвращает значение "истина", если блокировка связана с идентификатором lock.

    void omp_init_nest_lock(omp_nest_lock_t *lock);

subroutine omp_init_nest_lock(lock)
integer(kind = omp_nest_lock_kind) :: lock

    Инициализирует вложенную блокировку, связанную с идентификатором lock.

    void omp_destroy_nest_lock(omp_nest_lock_t *lock);

subroutine omp_destroy_nest_lock(lock) integer(kind = omp_nest_lock_kind) :: lock

    Переводит вложенную блокировку, связанную с идентификатором lock, в состояние неопределенности.

    void omp_set_nest_lock(omp_nest_lock_t *lock);

subroutine omp_set_nest_lock(lock) integer(kind= omp_nest_lock_kind) :: lock

    Переводит выполняющиеся потоки в состояние ожидания до тех пор, пока вложенная блокировка, связанная с идентификатором lock, не станет доступной. Поток становится владельцем блокировки.

    void omp_unset_nest_lock(omp_nest_lock_t *lock);

subroutine omp_unset_nest_lock(lock) integer(kind = omp_nest_lock_kind) ::  lock

    Освобождает выполняющийся поток от владения вложенной блокировкой, связанной с идентификатором lock. Если поток не был владельцем блокировки, результат не определен.

    int omp_test_nest_lock(omp_nest_lock_t *lock);

integer function omp_test_nest_lock(lock) integer(kind = omp_nest_lock_kind) :: lock

    Функция, позволяющая определить, связана ли вложенная блокировка с идентификатором lock . Если связана, возвращается значение счетчика, в противном случае возвращается значение 0.

    Таймеры

    Для профилирования OpenMP программы можно использовать таймеры.

    double omp_get_wtime(void);

double precision function omp_get_wtime()

    Возвращает время в секундах, прошедшее с произвольного момента в прошлом. Точка отсчета остается неизменной в течение всего времени выполнения программы.

    double omp_get_wtick(void);

double precision function omp_get_wtick()

    Возвращает время в секундах, прошедшее между последовательными "тиками". Это время является мерой точности таймера.

    Переменные окружения OpenMP

    Переменные окружения задаются следующим образом:

  • export ПЕРЕМЕННАЯ=значение (в среде UNIX )
  • set ПЕРЕМЕННАЯ=значение (в среде Microsoft Windows )
    •

    OMP_NUM_THREADS

    Задает количество нитей при выполнении параллельных секций программы.

    OMP_SCHEDULE

    Задает способ распределения итераций циклов между нитями. Возможные значения:

  • static ;
  • dynamic ;
  • guided
    •

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

    export OMP_SCHEDULE="static, 10" OMP_DYNAMIC

    Если этой переменной присвоено значение false, динамическое распределение итераций циклов между нитями запрещено, если true - разрешено.

    OMP_NESTED

    Если этой переменной присвоено значение false, вложенный параллелизм запрещен, если true - разрешен.

    Лабораторная работа 1.1 Распараллеливание программы вычисления определенного интеграла с помощью OpenMP

    Распараллеливание программ с помощью OpenMP

    Параллельная OpenMP -программа состоит из последовательных и параллельных секций. Границы параллельных секций обозначаются директивами OpenMP. Процесс разработки OpenMP -программы включает следующие этапы:

  • Разработка последовательной программы.
  • Выявление участков потенциального параллелизма. Чаще всего это циклы.
  • Анализ трудоемкости параллельных секций (профилирование программы). Наибольший выигрыш в производительности дает распараллеливание секций, на которые приходятся наибольшие затраты процессорного времени.
  • Пошаговое распараллеливание программы, начиная с наиболее трудоемких секций.
    •

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

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

    Необходимо правильно определить область видимости переменных в параллельных секциях программы. Параметр цикла, например, должен быть объявлен локальной переменной. Инвариант цикла (величина, не изменяющаяся при выполнении итераций цикла) должен быть глобальным.

    При вычислении суммы, например, к переменной, которая используется для "накопления" суммы, должна быть применена операция приведения (редукции).

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

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

    Трансляция OpenMP-программ

    Трансляция OpenMP -программы выполняется со специальным ключом. В операционной системе Linux транслятор $$Intel\text{\textregistered} Compiler$$ использует ключ - openmp, например:

    #ifort -o my_prog prog_source.f9 0 -openmp

    В операционной системе $$Microsoft\text{\textregistered} Windows$$ командная строка выглядит следующим образом:

    #ifort prog_source.f9 0 /Qopenmp

    Приближенное вычисление определенного интеграла

    Приближенное вычисление интеграла:

    $$I=\int\limits_{x_o}^{x_1}F(x)dx$$

    основано на его замене конечной суммой:

    $$I_n=\sum\limits_{k=0}^n w_kF(x_k)$$

    где $$w_k$$ - числовые коэффициенты, а $$x_k$$ - точки отрезка $$[x_0, x_1]$$. Приближенное равенство:

    $$I\approx I_n$$

    называется квадратурной формулой, точки $$x_k$$ - узлами квадратурной формулы, а числа $$w_k$$ - коэффициентами квадратурной формулы. Разные методы приближенного интегрирования отличаются выбором узлов и коэффициентов. От этого выбора зависит погрешность квадратурной формулы:

    $$R_n=|I-I_n|$$

    Метод трапеций

    Интегрирование методом трапеций - основано на использовании кусочно-линейного приближения для интегрируемой функции. Пусть $$F (x)$$ - гладкая функция на интервале $$[a,b]$$, и этот интервал делится на $$n$$ равных частей, каждая длиной $$h=\frac{b-a}{n}$$.

    Приближение метода трапеций:

    $$I(h)=\frac{h[f_0+2f_1+2f_2+\ldots+2f_{n-1}+f_n]}{2}$$

    где $$f_i = F (a + jh)$$ - значение интегрируемой функции в точке $$a + jh$$.

    Метод Симпсона

    Идея трехточечного метода Симпсона заключается в следующем. Пусть $$x_m$$ - это средняя точка интервала $$[x_0, x_1]$$ и пусть $$Q (x)$$ - единственный полином второй степени, который интерполирует (приближает) подынтегральную функцию $$F(x)$$ по точкам $$x_0,$$ $$x_m$$ и $$x_1$$. Искомый интеграл аппроксимируется интегралом от функции $$Q (x)$$:

    $$I_i\approx \int\limits_{x_i}^{x_{i+1}}Q(x)dx $$

    Эта оценка точна, если $$F (x)$$ является полиномом степени 3.

    Обычно используются составные квадратурные формулы, когда промежуток интегрирования разбивается на $$N$$ подынтервалов и простая формула Симпсона применяется на каждом из этих подынтервалов:

    $$I_i\approx \int\limits_{x_i}^{x_{i+1}}Q(x)dx $$$$I=\sum\limits_{i=1}^N I_i$$

    Недостатком рассмотренного метода является то, что он не дает возможности явно задать точность вычисления интеграла. Точность связана с количеством точек разбиения. От этого недостатка свободны методы интегрирования с адаптивным выбором шага разбиения. Если трехточечный метод Симпсона не дает достаточную точность на заданном интервале, он делится на 3 равные части и метод вновь применяется к каждой из полученных частей.

    Лабораторная работа

    В заданиях лабораторной работы 1.1 предлагается выполнить распараллеливание последовательных программ, предназначенных для вычисления определенных интегралов. В задании 4 распараллеливание производится с помощью MPICH 1.2.7. Цель работы - получить навык анализа простых программ и выявления в них потенциального параллелизма, применить для распараллеливания OpenMP и MPI, сравнить трудоемкость обоих подходов и эффективность полученного результата. Звездочкой отмечено задание повышенной сложности.

    Необходимый для выполнения данной лабораторной работы справочный материал можно найти на стр. 13 - 24 методического пособия "Средства программирования для многопроцессорных вычислительных систем".

    Задания для практической работы

    Задание 1

    Получить у преподавателя файл с исходным текстом программы (примеры 1, 2) и ознакомиться с реализацией квадратурной формулы.

    Задание 2

    Откомпилировать программу, выполнить расчет. Определить процессорное время, потраченное на выполнение расчета.

    Задание 3

    Проанализировать последовательный код и выявить участки потенциального параллелизма. Выполнить распараллеливание с помощью OpenMP. Определить процессорное время, потраченное на выполнение расчета для разного числа потоков (меньшего, равного и большего, чем число процессоров). Сравнить с результатом, полученным в задании 2. Объяснить полученный результат.

    Задание 4*

    Распараллелить программу с помощью MPI. Определить процессорное время, потраченное на выполнение расчета. Сравнить с результатами, полученными в заданиях 2 и 3.

    Задание 5

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

    Пример 1

    В программе на языке Fortran 90 реализован метод трапеций.

    program integral_trapez
integer, parameter :: div_no = 100
real, parameter :: x0 = 0., xl = 1. !3.14159
real, external  :: F
real :: result

result = trapezium(F, x0, x1, div_no) 
print *, result

end

real function trapezium(F, x0, x1, div_no)

real, external ::  F
real, intent(in) :: x0, x1
integer, intent(in) ::  div_no

real :: x, dx, sum integer :: j

  dx = (x1 - x0) / div_no
  sum = F(x0) + F(x1)
  x = x0
  do j = 1, div_no - 1 
    x = x + dx
      sum = sum + 2.0  * F(x)
    end do
    trapezium = dx * sum / 2.0
end

real function F(x) real, intent(in) :: x !F= sin(x)
F = 4./(1.+x**2)
end

    Пример 2

    В программе на языке Fortran 90 реализован метод Симпсона.

    program integral_simps
integer, parameter :: div_no = 100
real, parameter :: x0 = 0., x1 = 1. !3.14159
real, external :: F
real :: result

result = simpson(F, x0, x1, div_no) print *, result

end

real function simpson(F, x0, x1, div_no)
real, external :: F
real, intent(in) :: x0, x1
integer, intent(in) :: div_no

real :: x, dx, sum integer :: j

  dx = (x1 - x0) / (2.0 * div_no) 
  sum = F(x0) + F(x1)
  x = x0
  do j = 1, 2 * div_no - 1 
    x = x + dx
    if (mod(j, 2) /= 0) then 
    sum = sum + 4.0 * F(x) 
  else
      sum = sum + 2.0 * F(x) 
  end if 
  end do
  simpson = dx * sum / 3.0
end

real function F(x) real, intent(in) :: x !F= sin(x)
F  =  4./(1.+x**2)
End

    Лабораторная работа 2.1 Распараллеливание программы решения систем линейных алгебраических уравнений методом Гаусса с помощью OpenMPи MPI

    Распараллеливание программ с помощью OpenMP

    Параллельная OpenMP -программа состоит из последовательных и параллельных секций. Границы параллельных секций обозначаются директивами OpenMP. Процесс разработки OpenMP -программы включает следующие этапы:

  • Разработка последовательной программы.
  • Выявление участков потенциального параллелизма. Чаще всего это циклы.
  • Анализ трудоемкости параллельных секций (профилирование программы). Наибольший выигрыш в производительности дает распараллеливание секций, на которые приходятся наибольшие затраты процессорного времени.
  • Пошаговое распараллеливание программы, начиная с наиболее трудоемких секций.
    •

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

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

    Необходимо правильно определить область видимости переменных в параллельных секциях программы. Параметр цикла, например, должен быть объявлен локальной переменной. Инвариант цикла (величина, не изменяющаяся при выполнении итераций цикла) должен быть глобальным.

    При вычислении суммы, например, к переменной, которая используется для "накопления" суммы, должна быть применена операция приведения (редукции).

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

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

    Трансляция OpenMP-программ

    Трансляция OpenMP -программы выполняется со специальным ключом. В операционной системе Linux транслятор $$Intel\text{\textregistered} Compiler$$ использует ключ - openmp, например:

    #ifort -o my_prog prog_source.f9 0 -openmp

    В операционной системе $$Microsoft\text{\textregistered} Windows$$ командная строка выглядит следующим образом:

    #ifort prog_source.f9 0 /Qopenmp

    Решение систем линейных алгебраических уравнений методом Гаусса

    Классическим численным методом решения систем линейных алгебраических уравнений:

    $$Ax=b$$

    где $$A=\|a_{ij}\|_{i,j=1,\ldots n}$$ - квадратная матрица коэффициентов, $$x$$ - вектор неизвестных, а $$b$$ - вектор правой части, является метод Гаусса. Он относится к числу "точных" методов, то есть погрешность метода Гаусса определяется только погрешностью машинной арифметики. "Точные" методы решения систем линейных алгебраических уравнений основаны, как правило, на преобразовании исходной задачи к такой эквивалентной (имеющей то же решение), которая допускала бы простое вычисление компонентов вектора неизвестных. Это может быть система с диагональной или, как в методе Гаусса, треугольной матрицей коэффициентов. Переход к системе с верхней треугольной матрицей производится путем линейного комбинирования строк. Решение системы при этом не изменяется.

    Приведем описание алгоритма для метода Гаусса.

    Прямой ход

  • Найти наибольший по абсолютной величине элемент первого столбца и поменять соответствующую строку местами с первой.
  • Выбирая подходящим образом множители для элементов первой строки и складывая полученные произведения с элементами строк со 2-й по n-ю,обратить в ноль все элементы первого столбца, находящиеся ниже главной диагонали. При вычислении комбинаций следует учитывать и вектор правой части.
  • Повторить данную процедуру для второй строки и второго столбца и т. д.
    •

    Обратный ход (обратная подстановка)

  • Вычислить $$x_n=\frac{b_n^\prime}{a_{nn}^\prime}$$
  • Для $$i = n-1,\ldots ,1$$ вычислить $$x_i=\frac{1}{a_{ii}^\prime} \left(b_i^\prime - \sum\limits_{j=i+1}^n a_{ij}^\prime x_j \right)$$
    •

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

    Лабораторная работа

    В заданиях лабораторной работы 2.1 предлагается выполнить распараллеливание последовательной программы, предназначенной для решения систем линейных алгебраических уравнений. В задании 4 распараллеливание производится с помощью MPICH 1.2.7. Цель работы - получить навык анализа программ, выявления в них участков потенциального параллелизма с наибольшей трудоемкостью, применить для распараллеливания OpenMP и MPI, сравнить трудоемкость обоих подходов и эффективность полученного результата. Звездочкой отмечено задание повышенной сложности.

    Необходимый для выполнения данной лабораторной работы справочный материал можно найти на стр. 13 - 24 методического пособия "Средства программирования для многопроцессорных вычислительных систем".

    Задания для практической работы

    Задание 1

    Получить у преподавателя файл с исходным текстом программы (пример 1) и ознакомиться с реализацией простого метода Гаусса.

    Задание 2

    Откомпилировать программу, выполнить расчет. Определить процессорное время, потраченное на выполнение расчета.

    Задание 3

    Проанализировать последовательный код. Выявить участки потенциального параллелизма с наибольшей трудоемкостью. Для этого следует подсчитать количество операций для прямого хода метода Гаусса и хода обратной подстановки. Выполнить распараллеливание с помощью OpenMP. Определить процессорное время, потраченное на выполнение расчета для разного числа потоков (меньшего, равного и большего, чем число процессоров). Сравнить с результатом, полученным в задании 2. Объяснить полученный результат.

    Задание 4*

    Распараллелить программу с помощью MPI. Определить процессорное время, потраченное на выполнение расчета. Сравнить с результатами, полученными в заданиях 2 и 3.

    Задание 5

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

    Пример 1

    В программе на языке Fortran 90 реализован простой метод Гаусса без выбора ведущего элемента.

    program linear_algebra_gauss

integer, parameter :: n = 3
real, dimension(1:n, 1:n) :: a, left
real, dimension(1:n) :: x, b

data left/9 * 0./
data a/.471, 4.27, .012, 3.21, -.513, 1.273, -1.307, 1.102, -
4.175 /
data b/ 2.425, -.176, 1.423  /
!  Решение:   0.07535443  0.6915624 -0.1297573

! Прямой ход метода Гаусса

do k = 1,  n - 1 
  do i = k + 1,  n
    left(i, k) = a(i, k) / a(k, k) 
    b(i) = b(i) - left(i, k) * b(k)
  end do

  do j = k + 1,  n 
    do i = k + 1,  n
    a(j, i) = a(j, i) - left(j, k) * a(k, i)
    end do

  end do 
end do
!  Обратная подстановка x(n) = b(n) / a(n,  n) 
do i = n - 1, 1, -1
  x(i) = b(i)
  do j = i + 1, n
    x(i) = x(i) - a(i, j) * x(j)
  end do
  x(i) = x(i) / a(i, i)
end do

print *, (x(i), i = 1,  n)

end
    Страницы:

    OpenMP - стандарт программного интерфейса приложений для параллельных систем с общей памятью. Поддерживает языки C, C++, Фортран.

    Модель программы в OpenMP

    (рис 2.1) Модель параллельной программы в OpenMP

    Модель параллельной программы в OpenMP можно сформулировать следующим образом:

  • Программа состоит из последовательных и параллельных секций (рис. 2.1).
  • В начальный момент времени создается главная нить, выполняющая последовательные секции программы.
  • При входе в параллельную секцию выполняется операция fork,порождающая семейство нитей. Каждая нить имеет свой уникальный числовой идентификатор (главной нити соответствует 0). При распараллеливании циклов все параллельные нити исполняют один код. В общем случае нити могут исполнять различные фрагменты кода.
  • При выходе из параллельной секции выполняется операция join.Завершается выполнение всех нитей, кроме главной.
    •

    OpenMP составляют следующие компоненты:

  • Директивы компилятора - используются для создания потоков, распределения работы между потоками и их синхронизации. Директивы включаются в исходный текст программы.
  • Подпрограммы библиотеки времени выполнения - используются для установки и определения атрибутов потоков. Вызовы этих подпрограмм включаются в исходный текст программы.
  • Переменные окружения - используются для управления поведением параллельной программы. Переменные окружения задаются для среды выполнения параллельной программы соответствующими командами (например, командами оболочки в операционных системах UNIX ).
    •

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

    Привязка к языку Fortran

    В программах на языке Fortran директивы компилятора, имена подпрограмм и переменных окружения начинаются с OMP. Формат директивы компилятора:

    {!|C|*}$OMP директива [оператор_1[, оператор_2, ...]]

    Директива начинается в первой (фиксированный формат записи текста языка Fortran 77 ) или произвольной (свободный формат) позиции строки. Допускается продолжение директивы в следующей строке, в этом случае действует стандартное в данной версии языка правило для обозначения строки продолжения (непробельный символ в шестой позиции для фиксированного формата записи и амперсанд для свободного формата).

    Пример программы на языке Fortran с использованием OpenMP

    program omp_example
integer i, k, N
real*4 sum, h, x
print *, "Please, type in N:"
read *, N
h = 1.0 / N
sum = 0.0
C$OMP PARALLEL DO SCHEDULE(STATIC) REDUCTION(+:sum)
do i = 1, N
x = i  * h
sum = sum + 1.e0  * h /   (1.e0 + x**2)
enddo
print *,   4.0  * sum end

    Привязка к языку C

    В программах на языке C прагмы, имена функций и переменных окружения OMP начинаются с omp, omp или OMP. Формат директивы:

    #pragma omp директива [оператор_1[, оператор_2, ...]]

    В OpenMP -программе используется заголовочный файл omp.h.

    Пример программы на языке С с использованием OpenMP

    #include "omp.h" #include <stdio.h> double f(double x) {
return 4.0  / (1 + x * x);
}
main() {
const long N = 100000;
long i;
double h, sum, x; sum = 0;
h = 1.0  / N;
#pragma omp parallel shared(h) {
#pragma omp for private(x) reduction(+:sum) for  (i = 0;  i < N;  i++) 
{ x = h * (i + 0.5); 
sum = sum + f(x);
}
}
printf("PI = %f\n",  sum / N);
}

    Директивы OpenMP

    Далее приводится перечень директив OpenMP. Описания директив OpenMP ориентированы на спецификацию версии 2.5.

    parallel
. . .
end parallel

    Задает границы параллельной секции программы. С данной директивой могут использоваться следующие операторы (их описание дается далее):

  • private;
  • shared;
  • default;
  • firstprivate;
  • reduction;
  • if;
  • copyin;
  • num_threads.
    •  
    do
цикл do end do
#pragma omp for цикл for

    Задает границы цикла, исполняемого в параллельном режиме в языках Fortran и C соответственно. С данной директивой могут использоваться следующие операторы:

  • private;
  • firstprivate;
  • lastprivate;
  • reduction;
  • schedule;
  • ordered;
  • nowait.
    •  
    sections 
...
end sections

    Обрамляет параллельную секцию программы. Вложенные секции программы, задаваемые директивами section, распределяются между нитями. С данной директивой могут использоваться следующие операторы:

  • private;
  • firstprivate;
  • lastprivate;
  • reduction;
  • nowait.
    •

    section

    Определяет часть sections, которая выполняется одной нитью.

    single
...
end single

    Обрамляет блок программы, который должен выполняться одной нитью. С данной директивой могут использоваться следующие операторы:

  • private;
  • firstprivate;
  • copyprivate;
  • nowait.
    •  
    workshare 
...
end workshare

    Делит блок на части, выполнение которых распределяется между нитями таким образом, что каждая часть выполняется один раз. Блок может содержать только следующие конструкции:

  • присваивания массивов;
  • скалярные присваивания;
  • FORALL;
  • WHERE;
  • atomic;
  • critical;
  • parallel.
    •  
    parallel do цикл do
end parallel do

    Объединяет директивы parallel и do.

    parallel sections
...
end parallel sections

    Объединяет директивы parallel и sections.

    parallel workshare
...
end parallel workshare

    Объединяет директивы parallel и workshare.

    master
...
end master

    Обрамляет блок программы, который должен выполняться только главной нитью.

    critical[(блокировка)] 
...
end critical[(блокировка)]

    Обрамляет блок программы, доступ к которому в любой момент времени может получить только одна нить (критическая секция). Блокировка - необязательное имя критической секции. Квадратные скобки указывают, что имя не является обязательным и может быть опущено.

    barrier

    Директива барьерной синхронизации нитей. Каждая нить, выполнение которой достигло данной точки, приостанавливает свое выполнение до тех пор, пока все нити не достигнут данной точки.

    atomic

    Объявляет операцию атомарной (при выполнении атомарной операции одновременный доступ к памяти по записи разных нитей запрещен). Применяется только к оператору, непосредственно следующему после данной директивы. Он может иметь следующий вид:

  • x = x {+|-|*|/|.AND.|.OR.|.EQV.|.NEQV.} скалярное_выражение_не_содержащее_х
  • x = скалярное_выражение_не_содержащее_х {+|-|*|/|.AND.|.OR.|.EQV.|.NEQV.} x
  • x = {MAX|MIN|IAND|IOR|IEOR} (x, скалярное_выражение_не_содержащее_x)
  • x = {MAX|MIN|IAND|IOR|IEOR} (скалярное_выражение_не_содержащее_x, x)
    •

    flush[(список переменных)]

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

    ordered
...

end ordered

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

    threadprivate(список common-блоков)

    Определяет common -блоки, перечисленные в списке, локальными.

    Операторы OpenMP

    Операторы OpenMP используются совместно с директивами.

    private(список переменных)

    Объявляет переменные из списка локальными.

    firstprivate(список переменных)

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

    lastprivate( список переменных)

    Объявляет переменные из списка локальными и назначает им значения из того блока программы, который был выполнен последним.

    copyprivate( список переменных)

    После завершения выполнения блока, заданного директивой single, значения локальных переменных из списка распределяются между остальными нитями.

    nowait

    Отменяет барьерную синхронизацию при завершении выполнения параллельной секции.

    shared( список переменных)

    Объявляет переменные из списка общими для всех нитей.

    default(private|shared|none)

    Данный оператор позволяет изменить правила определения области видимости переменных, действующие по умолчанию. Вариант private используется только в языке Fortran.

    reduction(операция|встроенная функция: список переменных)

    Оператор приведения (редукции) значений локальных переменных из списка с помощью указанной операции или встроенной функции языка. Операция редукции применяется к нескольким значениям и возвращает одно значение.

    if(скалярное логическое выражение)

    Условный оператор.

    num_threads( скалярное целое выражение)

    Задает количество нитей. Альтернативный способ задания количества нитей обеспечивает переменная окружения OMP_NUM_THREADS.

    schedule(характер_распределения_итераций[, количество_итераций_цикла])

    Данный оператор задает способ распределения итераций цикла между нитями:

  • static - количество итераций цикла, передаваемых для выполнения каждой нити фиксировано и распределяется между нитями по принципу кругового планирования. Если количество итераций не указано, оно полагается равным 1;
  • dynamic - количество итераций цикла, передаваемых для выполнения каждой нити фиксировано. Очередная "порция" итераций передается освободившейся нити;
  • guided - количество итераций цикла, передаваемых для выполнения каждой нити постепенно уменьшается. Очередная "порция" итераций передается освободившейся нити;
  • runtime - тип распределения работы определяется во время выполнения программы, например, с помощью переменной окружения OMP_SCHEDULE.
    •

    copyin(список имен common-блоков)

    При выполнении этого оператора данные из главной нити копируются в локальные экземпляры common -блока в начале каждой параллельной секции. Имена задаются между символами "/ ".

    Подпрограммы OpenMP

    Подпрограммы, формирующие среду выполнения параллельной программы

    Здесь и далее вначале приводится интерфейс подпрограмм OpenMP для языка C, затем для языка Fortran.

    void omp_set_num_threads(int threads);

subroutine omp_set_num_threads(threads) integer threads

    Задает количество потоков ( threads ) при выполнении параллельных секций программы.

    int omp_get_num_threads(void);

integer function omp_get_num_threads()

    Возвращает количество потоков, используемых для выполнения параллельной секции.

    int omp_get_max_threads(void); 
integer function omp_get_max_threads()

    Возвращает максимальное количество потоков, которые можно использовать для выполнения параллельных секций программы.

    int omp_get_thread_num(void);

integer function omp_get_thread_num()

    Возвращает идентификатор нити, из которой вызывается данная функция.

    int omp_get_num_procs(void);

integer function omp_get_num_procs()

    Возвращает количество процессоров, доступных в данный момент программе.

    int omp_in_parallel(void);

logical function omp_in_parallel()

    Возвращает значение true при вызове из активной параллельной секции программы.

    void omp_set_dynamic(int threads);

subroutine omp_set_dynamic(threads)

logical threads

    Включает или отключает возможность динамического назначения количества потоков при выполнении параллельной секции. По умолчанию эта возможность отключена.

    int omp_get_dynamic(void);

logical function omp_get_dynamic()

    Возвращает значение true, если динамическое назначение количества потоков разрешено.

    void omp_set_nested(int nested);

subroutine omp_set_nested(nested) integer nested

    Разрешает или запрещает вложенный параллелизм. По умолчанию вложенный параллелизм запрещен.

    int omp_get_nested(void);

logical function omp_get_nested()

    Определяет, разрешен ли вложенный параллелизм.

    Подпрограммы для работы с блокировками

    Блокировки используются для предотвращения эффектов, приводящих к непредсказуемому (недетерминированному) поведению программы. Среди таких эффектов, например, гонки за данными, когда более чем один поток имеет доступ к одной и той же переменной.

    void omp_init_lock(omp_lock_t *lock);

subroutine omp_init_lock(lock) integer(kind = omp_lock_kind) :: lock

    Инициализирует блокировку, связанную с идентификатором lock, для использования в последующих вызовах подпрограмм.

    void omp_destroy_lock(omp_lock_t *lock);

subroutine omp_destroy_lock(lock) integer(kind = omp_lock_kind) :: lock

    Переводит блокировку, связанную с идентификатором lock, в состояние неопределенности.

    void omp_set_lock(omp_lock_t *lock);
subroutine omp_set_lock(lock)
integer(kind = omp_lock_kind) lock

    Переводит потоки из состояния выполнения в состояние ожидания до тех пор, пока блокировка, связанная с идентификатором lock, не окажется доступной. Поток становится владельцем доступной блокировки.

    void omp_unset_lock(omp_lock_t *lock);

subroutine omp_unset_lock(lock) integer(kind = omp_lock_kind) :: lock

    После выполнения данного вызова поток перестает быть владельцем блокировки, связанной с идентификатором lock. Если поток не был владельцем блокировки, результат вызова не определен.

    int omp_test_lock(omp_lock_t *lock);

logical function omp_test_lock(lock) integer(kind = omp_lock_kind) :: lock

    Возвращает значение "истина", если блокировка связана с идентификатором lock.

    void omp_init_nest_lock(omp_nest_lock_t *lock);

subroutine omp_init_nest_lock(lock)
integer(kind = omp_nest_lock_kind) :: lock

    Инициализирует вложенную блокировку, связанную с идентификатором lock.

    void omp_destroy_nest_lock(omp_nest_lock_t *lock);

subroutine omp_destroy_nest_lock(lock) integer(kind = omp_nest_lock_kind) :: lock

    Переводит вложенную блокировку, связанную с идентификатором lock, в состояние неопределенности.

    void omp_set_nest_lock(omp_nest_lock_t *lock);

subroutine omp_set_nest_lock(lock) integer(kind= omp_nest_lock_kind) :: lock

    Переводит выполняющиеся потоки в состояние ожидания до тех пор, пока вложенная блокировка, связанная с идентификатором lock, не станет доступной. Поток становится владельцем блокировки.

    void omp_unset_nest_lock(omp_nest_lock_t *lock);

subroutine omp_unset_nest_lock(lock) integer(kind = omp_nest_lock_kind) ::  lock

    Освобождает выполняющийся поток от владения вложенной блокировкой, связанной с идентификатором lock. Если поток не был владельцем блокировки, результат не определен.

    int omp_test_nest_lock(omp_nest_lock_t *lock);

integer function omp_test_nest_lock(lock) integer(kind = omp_nest_lock_kind) :: lock

    Функция, позволяющая определить, связана ли вложенная блокировка с идентификатором lock . Если связана, возвращается значение счетчика, в противном случае возвращается значение 0.

    Таймеры

    Для профилирования OpenMP программы можно использовать таймеры.

    double omp_get_wtime(void);

double precision function omp_get_wtime()

    Возвращает время в секундах, прошедшее с произвольного момента в прошлом. Точка отсчета остается неизменной в течение всего времени выполнения программы.

    double omp_get_wtick(void);

double precision function omp_get_wtick()

    Возвращает время в секундах, прошедшее между последовательными "тиками". Это время является мерой точности таймера.

    Переменные окружения OpenMP

    Переменные окружения задаются следующим образом:

  • export ПЕРЕМЕННАЯ=значение (в среде UNIX )
  • set ПЕРЕМЕННАЯ=значение (в среде Microsoft Windows )
    •

    OMP_NUM_THREADS

    Задает количество нитей при выполнении параллельных секций программы.

    OMP_SCHEDULE

    Задает способ распределения итераций циклов между нитями. Возможные значения:

  • static ;
  • dynamic ;
  • guided
    •

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

    export OMP_SCHEDULE="static, 10" OMP_DYNAMIC

    Если этой переменной присвоено значение false, динамическое распределение итераций циклов между нитями запрещено, если true - разрешено.

    OMP_NESTED

    Если этой переменной присвоено значение false, вложенный параллелизм запрещен, если true - разрешен.

    Лабораторная работа 1.1 Распараллеливание программы вычисления определенного интеграла с помощью OpenMP

    Распараллеливание программ с помощью OpenMP

    Параллельная OpenMP -программа состоит из последовательных и параллельных секций. Границы параллельных секций обозначаются директивами OpenMP. Процесс разработки OpenMP -программы включает следующие этапы:

  • Разработка последовательной программы.
  • Выявление участков потенциального параллелизма. Чаще всего это циклы.
  • Анализ трудоемкости параллельных секций (профилирование программы). Наибольший выигрыш в производительности дает распараллеливание секций, на которые приходятся наибольшие затраты процессорного времени.
  • Пошаговое распараллеливание программы, начиная с наиболее трудоемких секций.
    •

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

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

    Необходимо правильно определить область видимости переменных в параллельных секциях программы. Параметр цикла, например, должен быть объявлен локальной переменной. Инвариант цикла (величина, не изменяющаяся при выполнении итераций цикла) должен быть глобальным.

    При вычислении суммы, например, к переменной, которая используется для "накопления" суммы, должна быть применена операция приведения (редукции).

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

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

    Трансляция OpenMP-программ

    Трансляция OpenMP -программы выполняется со специальным ключом. В операционной системе Linux транслятор $$Intel\text{\textregistered} Compiler$$ использует ключ - openmp, например:

    #ifort -o my_prog prog_source.f9 0 -openmp

    В операционной системе $$Microsoft\text{\textregistered} Windows$$ командная строка выглядит следующим образом:

    #ifort prog_source.f9 0 /Qopenmp

    Приближенное вычисление определенного интеграла

    Приближенное вычисление интеграла:

    $$I=\int\limits_{x_o}^{x_1}F(x)dx$$

    основано на его замене конечной суммой:

    $$I_n=\sum\limits_{k=0}^n w_kF(x_k)$$

    где $$w_k$$ - числовые коэффициенты, а $$x_k$$ - точки отрезка $$[x_0, x_1]$$. Приближенное равенство:

    $$I\approx I_n$$

    называется квадратурной формулой, точки $$x_k$$ - узлами квадратурной формулы, а числа $$w_k$$ - коэффициентами квадратурной формулы. Разные методы приближенного интегрирования отличаются выбором узлов и коэффициентов. От этого выбора зависит погрешность квадратурной формулы:

    $$R_n=|I-I_n|$$

    Метод трапеций

    Интегрирование методом трапеций - основано на использовании кусочно-линейного приближения для интегрируемой функции. Пусть $$F (x)$$ - гладкая функция на интервале $$[a,b]$$, и этот интервал делится на $$n$$ равных частей, каждая длиной $$h=\frac{b-a}{n}$$.

    Приближение метода трапеций:

    $$I(h)=\frac{h[f_0+2f_1+2f_2+\ldots+2f_{n-1}+f_n]}{2}$$

    где $$f_i = F (a + jh)$$ - значение интегрируемой функции в точке $$a + jh$$.

    Метод Симпсона

    Идея трехточечного метода Симпсона заключается в следующем. Пусть $$x_m$$ - это средняя точка интервала $$[x_0, x_1]$$ и пусть $$Q (x)$$ - единственный полином второй степени, который интерполирует (приближает) подынтегральную функцию $$F(x)$$ по точкам $$x_0,$$ $$x_m$$ и $$x_1$$. Искомый интеграл аппроксимируется интегралом от функции $$Q (x)$$:

    $$I_i\approx \int\limits_{x_i}^{x_{i+1}}Q(x)dx $$

    Эта оценка точна, если $$F (x)$$ является полиномом степени 3.

    Обычно используются составные квадратурные формулы, когда промежуток интегрирования разбивается на $$N$$ подынтервалов и простая формула Симпсона применяется на каждом из этих подынтервалов:

    $$I_i\approx \int\limits_{x_i}^{x_{i+1}}Q(x)dx $$$$I=\sum\limits_{i=1}^N I_i$$

    Недостатком рассмотренного метода является то, что он не дает возможности явно задать точность вычисления интеграла. Точность связана с количеством точек разбиения. От этого недостатка свободны методы интегрирования с адаптивным выбором шага разбиения. Если трехточечный метод Симпсона не дает достаточную точность на заданном интервале, он делится на 3 равные части и метод вновь применяется к каждой из полученных частей.

    Лабораторная работа

    В заданиях лабораторной работы 1.1 предлагается выполнить распараллеливание последовательных программ, предназначенных для вычисления определенных интегралов. В задании 4 распараллеливание производится с помощью MPICH 1.2.7. Цель работы - получить навык анализа простых программ и выявления в них потенциального параллелизма, применить для распараллеливания OpenMP и MPI, сравнить трудоемкость обоих подходов и эффективность полученного результата. Звездочкой отмечено задание повышенной сложности.

    Необходимый для выполнения данной лабораторной работы справочный материал можно найти на стр. 13 - 24 методического пособия "Средства программирования для многопроцессорных вычислительных систем".

    Задания для практической работы

    Задание 1

    Получить у преподавателя файл с исходным текстом программы (примеры 1, 2) и ознакомиться с реализацией квадратурной формулы.

    Задание 2

    Откомпилировать программу, выполнить расчет. Определить процессорное время, потраченное на выполнение расчета.

    Задание 3

    Проанализировать последовательный код и выявить участки потенциального параллелизма. Выполнить распараллеливание с помощью OpenMP. Определить процессорное время, потраченное на выполнение расчета для разного числа потоков (меньшего, равного и большего, чем число процессоров). Сравнить с результатом, полученным в задании 2. Объяснить полученный результат.

    Задание 4*

    Распараллелить программу с помощью MPI. Определить процессорное время, потраченное на выполнение расчета. Сравнить с результатами, полученными в заданиях 2 и 3.

    Задание 5

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

    Пример 1

    В программе на языке Fortran 90 реализован метод трапеций.

    program integral_trapez
integer, parameter :: div_no = 100
real, parameter :: x0 = 0., xl = 1. !3.14159
real, external  :: F
real :: result

result = trapezium(F, x0, x1, div_no) 
print *, result

end

real function trapezium(F, x0, x1, div_no)

real, external ::  F
real, intent(in) :: x0, x1
integer, intent(in) ::  div_no

real :: x, dx, sum integer :: j

  dx = (x1 - x0) / div_no
  sum = F(x0) + F(x1)
  x = x0
  do j = 1, div_no - 1 
    x = x + dx
      sum = sum + 2.0  * F(x)
    end do
    trapezium = dx * sum / 2.0
end

real function F(x) real, intent(in) :: x !F= sin(x)
F = 4./(1.+x**2)
end

    Пример 2

    В программе на языке Fortran 90 реализован метод Симпсона.

    program integral_simps
integer, parameter :: div_no = 100
real, parameter :: x0 = 0., x1 = 1. !3.14159
real, external :: F
real :: result

result = simpson(F, x0, x1, div_no) print *, result

end

real function simpson(F, x0, x1, div_no)
real, external :: F
real, intent(in) :: x0, x1
integer, intent(in) :: div_no

real :: x, dx, sum integer :: j

  dx = (x1 - x0) / (2.0 * div_no) 
  sum = F(x0) + F(x1)
  x = x0
  do j = 1, 2 * div_no - 1 
    x = x + dx
    if (mod(j, 2) /= 0) then 
    sum = sum + 4.0 * F(x) 
  else
      sum = sum + 2.0 * F(x) 
  end if 
  end do
  simpson = dx * sum / 3.0
end

real function F(x) real, intent(in) :: x !F= sin(x)
F  =  4./(1.+x**2)
End

    Лабораторная работа 2.1 Распараллеливание программы решения систем линейных алгебраических уравнений методом Гаусса с помощью OpenMPи MPI

    Распараллеливание программ с помощью OpenMP

    Параллельная OpenMP -программа состоит из последовательных и параллельных секций. Границы параллельных секций обозначаются директивами OpenMP. Процесс разработки OpenMP -программы включает следующие этапы:

  • Разработка последовательной программы.
  • Выявление участков потенциального параллелизма. Чаще всего это циклы.
  • Анализ трудоемкости параллельных секций (профилирование программы). Наибольший выигрыш в производительности дает распараллеливание секций, на которые приходятся наибольшие затраты процессорного времени.
  • Пошаговое распараллеливание программы, начиная с наиболее трудоемких секций.
    •

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

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

    Необходимо правильно определить область видимости переменных в параллельных секциях программы. Параметр цикла, например, должен быть объявлен локальной переменной. Инвариант цикла (величина, не изменяющаяся при выполнении итераций цикла) должен быть глобальным.

    При вычислении суммы, например, к переменной, которая используется для "накопления" суммы, должна быть применена операция приведения (редукции).

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

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

    Трансляция OpenMP-программ

    Трансляция OpenMP -программы выполняется со специальным ключом. В операционной системе Linux транслятор $$Intel\text{\textregistered} Compiler$$ использует ключ - openmp, например:

    #ifort -o my_prog prog_source.f9 0 -openmp

    В операционной системе $$Microsoft\text{\textregistered} Windows$$ командная строка выглядит следующим образом:

    #ifort prog_source.f9 0 /Qopenmp

    Решение систем линейных алгебраических уравнений методом Гаусса

    Классическим численным методом решения систем линейных алгебраических уравнений:

    $$Ax=b$$

    где $$A=\|a_{ij}\|_{i,j=1,\ldots n}$$ - квадратная матрица коэффициентов, $$x$$ - вектор неизвестных, а $$b$$ - вектор правой части, является метод Гаусса. Он относится к числу "точных" методов, то есть погрешность метода Гаусса определяется только погрешностью машинной арифметики. "Точные" методы решения систем линейных алгебраических уравнений основаны, как правило, на преобразовании исходной задачи к такой эквивалентной (имеющей то же решение), которая допускала бы простое вычисление компонентов вектора неизвестных. Это может быть система с диагональной или, как в методе Гаусса, треугольной матрицей коэффициентов. Переход к системе с верхней треугольной матрицей производится путем линейного комбинирования строк. Решение системы при этом не изменяется.

    Приведем описание алгоритма для метода Гаусса.

    Прямой ход

  • Найти наибольший по абсолютной величине элемент первого столбца и поменять соответствующую строку местами с первой.
  • Выбирая подходящим образом множители для элементов первой строки и складывая полученные произведения с элементами строк со 2-й по n-ю,обратить в ноль все элементы первого столбца, находящиеся ниже главной диагонали. При вычислении комбинаций следует учитывать и вектор правой части.
  • Повторить данную процедуру для второй строки и второго столбца и т. д.
    •

    Обратный ход (обратная подстановка)

  • Вычислить $$x_n=\frac{b_n^\prime}{a_{nn}^\prime}$$
  • Для $$i = n-1,\ldots ,1$$ вычислить $$x_i=\frac{1}{a_{ii}^\prime} \left(b_i^\prime - \sum\limits_{j=i+1}^n a_{ij}^\prime x_j \right)$$
    •

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

    Лабораторная работа

    В заданиях лабораторной работы 2.1 предлагается выполнить распараллеливание последовательной программы, предназначенной для решения систем линейных алгебраических уравнений. В задании 4 распараллеливание производится с помощью MPICH 1.2.7. Цель работы - получить навык анализа программ, выявления в них участков потенциального параллелизма с наибольшей трудоемкостью, применить для распараллеливания OpenMP и MPI, сравнить трудоемкость обоих подходов и эффективность полученного результата. Звездочкой отмечено задание повышенной сложности.

    Необходимый для выполнения данной лабораторной работы справочный материал можно найти на стр. 13 - 24 методического пособия "Средства программирования для многопроцессорных вычислительных систем".

    Задания для практической работы

    Задание 1

    Получить у преподавателя файл с исходным текстом программы (пример 1) и ознакомиться с реализацией простого метода Гаусса.

    Задание 2

    Откомпилировать программу, выполнить расчет. Определить процессорное время, потраченное на выполнение расчета.

    Задание 3

    Проанализировать последовательный код. Выявить участки потенциального параллелизма с наибольшей трудоемкостью. Для этого следует подсчитать количество операций для прямого хода метода Гаусса и хода обратной подстановки. Выполнить распараллеливание с помощью OpenMP. Определить процессорное время, потраченное на выполнение расчета для разного числа потоков (меньшего, равного и большего, чем число процессоров). Сравнить с результатом, полученным в задании 2. Объяснить полученный результат.

    Задание 4*

    Распараллелить программу с помощью MPI. Определить процессорное время, потраченное на выполнение расчета. Сравнить с результатами, полученными в заданиях 2 и 3.

    Задание 5

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

    Пример 1

    В программе на языке Fortran 90 реализован простой метод Гаусса без выбора ведущего элемента.

    program linear_algebra_gauss

integer, parameter :: n = 3
real, dimension(1:n, 1:n) :: a, left
real, dimension(1:n) :: x, b

data left/9 * 0./
data a/.471, 4.27, .012, 3.21, -.513, 1.273, -1.307, 1.102, -
4.175 /
data b/ 2.425, -.176, 1.423  /
!  Решение:   0.07535443  0.6915624 -0.1297573

! Прямой ход метода Гаусса

do k = 1,  n - 1 
  do i = k + 1,  n
    left(i, k) = a(i, k) / a(k, k) 
    b(i) = b(i) - left(i, k) * b(k)
  end do

  do j = k + 1,  n 
    do i = k + 1,  n
    a(j, i) = a(j, i) - left(j, k) * a(k, i)
    end do

  end do 
end do
!  Обратная подстановка x(n) = b(n) / a(n,  n) 
do i = n - 1, 1, -1
  x(i) = b(i)
  do j = i + 1, n
    x(i) = x(i) - a(i, j) * x(j)
  end do
  x(i) = x(i) / a(i, i)
end do

print *, (x(i), i = 1,  n)

end
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^