Размещено на http://www.allbest.ru/

Министерство науки и высшего образования РФ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Волгоградский государственный технический университет»

Кафедра «Системы автоматизированного проектирования и поискового конструирования»

Контрольная работа по дисциплине: «Параллельные и распределенные вычисления»

На тему: «Технология Open Multi-Processing»

Волгоград 2023



Оглавление

Введение

1. Описание технологии OpenMP

2. Схема программирования в ОреnМР

3. Разделение задач между потоками

3.1 Параллельный цикл

3.2 Параллельные задачи

3.3 Параллельные секции

4. Основные директивы OpenMP

5. Особенности реализации директив ОреnМР

Заключение

Список литературы



Введение

Существуют две основные причины, вызывающие необходимость распараллеливать программы:

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

Ускорение работы программ на современных компьютерах (с 2005 на ПК, с 2001 на серверах) и эффективное использование суперкомпьютеров (с 1960-х).

Весной 2005 года Intel выпустила первый в мире двухъядерный процессор с x86 - Pentium D. А в 2006 все ознакомились со знаменитой линейкой - Intel Core 2. Почти в то же самое время вышел первый аналогичный AMD - Athlon 64 X2. В настоящее время практически невозможно найти компьютер с одноядерным процессором, и даже в бюджетных смартфонах нередко можно встретить четырехядерный процессор.

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

Довольно давно используются системы на базе нескольких компьютеров, они относятся к системам распределённых вычислений. Самый яркий пример распределённых вычислений это MPI(Message Passing Interface(интерфейс для передачи сообщений))

Системы параллельного программирования для работы на одном компьютере, начали свое развитие относительно недавно. Ведь при разработке приложений перед разработчиком стает вопрос, как повысить быстродействие с ресурсами которые имеются под рукой, а именно использованием нескольких ядер компьютера, и к программисту на помощь приходит API OpenMP. Разработанная в 1997 году технология OpenMP позволяет в максимальной степени эффективно реализовать возможности многопроцессорных вычислительных систем с общей памятью, обеспечивая использование общих данных для параллельно выполняемых потоков без каких-либо трудоемких межпроцессорных передач сообщений.



1. Описание технологии OpenMP

OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ на языках Си, Си++ и Фортран. Даёт описание совокупности директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью.

Разработка спецификаций стандарта ведётся некоммерческой организацией OpenMP Architecture Review Board (ARB), в которую входят все основные производители процессоров, а также ряд суперкомпьютерных лабораторий и университетов. Первая версия спецификации вышла в 1997 году, предназначалась только для Фортрана, в следующем году вышла версия для Си и C++.

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

Задачи, выполняемые потоками параллельно, так же, как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка -- «прагм».

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

ОреnМР позволяет легко и быстро создавать многопоточные приложения на алгоритмических языках Fortran и C/C+ +. При этом директивы ОреnМР аналогичны директивам препроцессора для языка C/C++ и являются аналогом комментариев в алгоритмическом языке Fortran. Это позволяет в любой момент разработки параллельной реализации программного продукта при необходимости вернуться к последовательному варианту программы.

В настоящее время ОреnМР поддерживается большинством разработчиков параллельных вычислительных систем: компаниями Intel, Hewlett-Packard, Silicon Graphics, IBM, Fujitsu, Hitachi, Siemens, Bull и другими. Многие известные компании в области разработки системного программного обеспечения также уделяют значительное внимание разработке системного программного обеспечения с ОреnМР. Среди этих компаний отметим Intel, KAI, PGI, PSR, APR, Absoft и некоторые другие.

Основные преимущества и недостатки технологии OpenMp:

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

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

3. Технология OpenMP обеспечивает возможность поэтапной (инкрементной) разработки параллельных программы - директивы OpenMP могут добавляться в последовательную программу постепенно (поэтапно), позволяя уже на ранних этапах разработки получать параллельные программы, готовые к применению; при этом важно отметить, что программный код получаемых последовательного и параллельного вариантов программы является единым и это в значительной степени упрощает проблему сопровождения, развития и совершенствования программ.

4. OpenMP позволяет в значительной степени снизить остроту проблемы переносимости параллельных программ между разными компьютерными системами - параллельная программа, разработанная на языке C или Fortran с использованием технологии OpenMP, как правило, будет работать для разных вычислительных систем с общей памятью.



2. Схема программирования в ОреnМР

Любая программа, последовательная или параллельная, состоит из набора областей двух типов: последовательных областей и областей распараллеливания. При выполнении последовательных областей порождается только один главный поток (процесс). В этом же потоке инициируется выполнение программы, а также происходит ее завершение. В последовательной программе в областях распараллеливания порождается также только один, главный поток, и этот поток является единственным на протяжении выполнения всей программы. В параллельной программе в областях распараллеливания порождается целый ряд параллельных потоков. Порожденные параллельные потоки могут выполняться как на разных процессорах, так и на одном процессоре вычислительной системы. В последнем случае параллельные процессы (потоки) конкурируют между собой за доступ к процессору. Управление конкуренцией осуществляется планировщиком операционной системы с помощью специальных алгоритмов. В операционной системе Linux планировщик задач осуществляет обработку процессов с помощью стандартного карусельного (round-robin) алгоритма. При этом только администраторы системы имеют возможность изменить или заменить этот алгоритм системными средствами. Таким образом, в параллельных программах в областях распараллеливания выполняется ряд параллельных потоков.

Рис.1. Принципиальная схема параллельной программы

При выполнении параллельной программы работа начинается с инициализации и выполнения главного потока (процесса), который по мере необходимости создает и выполняет параллельные потоки, передавая им необходимые данные. Параллельные потоки из одной параллельной области программы могут выполняться как независимо друг от друга, так и с пересылкой и получением сообщений от других параллельных потоков. Последнее обстоятельство усложняет разработку программы, поскольку в этом случае программисту приходится заниматься планированием, организацией и синхронизацией посылки сообщений между параллельными потоками. Таким образом, при разработке параллельной программы желательно выделять такие области распараллеливания, в которых можно организовать выполнение независимых параллельных потоков. Для обмена данными между параллельными процессами (потоками) в ОреnМР используются общие переменные. При обращении к общим переменным в различных параллельных потоках возможно возникновение конфликтных ситуаций при доступе к данным. Для предотвращения конфликтов можно воспользоваться процедурой синхронизации (synchronization). При этом надо иметь в виду, что процедура синхронизации - очень дорогая операция по временным затратам и желательно по возможности избегать ее или применять как можно реже. Для этого необходимо очень тщательно продумывать структуру данных программы.

Выполнение параллельных потоков в параллельной области программы начинается с их инициализации. Она заключается в создании дескрипторов порождаемых потоков и копировании всех данных из области данных главного потока в области данных создаваемых параллельных потоков. Эта операция чрезвычайно трудоемка - она эквивалентна примерно трудоемкости 1000 операций. Эта оценка чрезвычайно важна при разработке параллельных программ с помощью ОреnМР, поскольку ее игнорирование ведет к созданию неэффективных параллельных программ, которые оказываются зачастую медленнее их последовательных аналогов. В самом деле: для того чтобы получить выигрыш в быстродействии параллельной программы, необходимо, чтобы трудоемкость параллельных процессов в областях распараллеливания программы существенно превосходила бы трудоемкость порождения параллельных потоков. В противном случае никакого выигрыша по быстродействию получить не удастся, а зачастую можно оказаться даже и в проигрыше.

После завершения выполнения параллельных потоков управление программой вновь передается главному потоку. При этом возникает проблема корректной передачи данных от параллельных потоков главному. Здесь важную роль играет синхронизация завершения работы параллельных потоков, поскольку в силу целого ряда обстоятельств время выполнения даже одинаковых по трудоемкости параллельных потоков непредсказуемо (оно определяется как историей конкуренции параллельных процессов, так и текущим состоянием вычислительной системы). При выполнении операции синхронизации параллельные потоки, уже завершившие свое выполнение, простаивают и ожидают завершения работы самого последнего потока. Естественно, при этом неизбежна потеря эффективности работы параллельной программы. Кроме того, операция синхронизации имеет трудоемкость, сравнимую с трудоемкостью 11 инициализации параллельных потоков, т. е. эквивалентна примерно трудоемкости выполнения 1000 операций.

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



3. Разделение задач между потоками

3.1 Параллельный цикл

Самый популярный способ распределения задач в OpenMP -- параллельный цикл. Не секрет, что программы почти всю свою жизнь проводят выполняя циклы, при этом если между итерациями цикла нет зависимостей -- то цикл называется векторизуемым (его итерации можно поделить между потоками и выполнить независимо друг от друга).

Параллельный цикл позволяет задать опцию schedule, изменяющую алгоритм распределения итераций между потоками. Всего поддерживается 3 таких алгоритма. Далее полагаем, что у нас p потоков выполняют n итераций:

Опции планирования:

schedule(static) -- статическое планирование. При использовании такой опции итерации цикла будут поровну (приблизительно) поделены между потоками. Нулевой поток получит первые \(\frac{n}{p}\) итераций, первый -- вторые и т.д.;

schedule(static, 10) -- блочно-циклическое распределение итераций. Каждый поток получает заданное число итераций в начале цикла, затем (если остались итерации) процедура распределения продолжается. Планирование выполняется один раз, при этом каждый поток «узнает» итерации которые должен выполнить;

schedule(dinamic), schedule(dynamic, 10) -- динамическое планирование. По умолчанию параметр опции равен 1. Каждый поток получает заданное число итераций, выполняет их и запрашивает новую порцию. В отличии от статического планирования, выполняется многократно (во время выполнения программы). Конкретное распределение итераций между потоками зависит от темпов работы потоков и трудоемкости итераций;

schedule(guided), schedule(guided, 10) -- разновидность динамического планирования с изменяемым при каждом последующем распределении числе итераций. Распределение начинается с некоторого начального размера, зависящего от реализации библиотеки до значения, задаваемого в опции (по умолчанию 1). Размер выделяемой порции зависит от количества еще нераспределенных итераций

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

3.2 Параллельные задачи

Параллельные задачи -- это более гибкий механизм, чем параллельный цикл. Параллельный цикл описывается внутри параллельной области, при этом могут возникнуть проблемы. Например, мы написали параллельную функцию вычисления суммы элементов одномерного массива, и нашу функцию решили применить для вычисления суммы элементов матрицы, но сделать это также параллельно. Получится вложенный параллелизм. Если (теоретически) наш код запущен на 8 ядрах -- то фактически будет создано 64 потока.

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

Параллельные задачи были предложены в стандарте OpenMP 3.0 (в 2008 году) поэтому их поддержка отсутствует в Microsoft C++. Кроме того, в стандарте OpenMP 4.5 была предложена конструкция taskloop, за счет которой использовать параллельные задачи для распараллеливания циклов теперь также удобно как и параллельный цикл.

3.3 Параллельные секции

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

for (int i = 1; i < n; ++i)

a[i] = a[i-1]+1;

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

#pragma omp parallel

{

#pragma omp sections

{

#pragma omp section

{

for (int i = 1; i < n; ++i)

a[i] = a[i-1]+1;

}

#pragma omp section

{

for (int i = 1; i < n; ++i)

b[i] = b[i-1]+1;

}

}

}



4. Основные директивы OpenMP

Любые дополнительные директивы вызываются с помощью стандартной директивы #pragma, и OpenMP не исключение. Следовательно, для того, чтобы обратиться к директиве нужно написать #pragma omp, и назвать искомую директиву. Справедлива следующая конструкция вызова.

#pragma omp директива [опция1, опция2, ...]

Где «директива» -- имя директивы, а опции являются необязательным для вызова, их у разных директив может быть разное количество.

Директива parallel

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

Если написать вложенную директиву parallel, то каждая из созданных нитей, встретив директиву, создаст еще такое же количество дополнительных нитей.

#pragma omp parallel [опция1, опция2, ...]

{

//блок

}

Опции директивы parallel

shared(переменные) -- в скобочках можно явно перечислить список переменных, которые будут общими для всех нитей, хотя по умолчанию все переменные, объявленные до блока таковыми являются.

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

if(условие) -- проверка условия, если true, то выполняется директива, если false, то код исполняется в прежнем режиме, без создания нитей. Может быть только одна такая опция на директиву.

Пример использования

omp_set_num_threads(4); //Установить количество нитей

#pragma omp parallel shared(num) //В этот момент создается 4 нити, переменная num у них будет общей

{

cout << omp_get_thread_num() << endl; //Вывести номер нити

someFunc(num); //Функцию кинутся выполнять все нити параллельно

}

omp_set_num_threads(4); //Установить количество нитей

#pragma omp parallel //В этот момент создается 4 нити

{

//А в этот момент каждая из 4 нитей создаст еще 4,

// итого 16 нитей буду выполнять следующий блок

#pragma omp parallel

{

//блок

}

}

Директива for

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

#pragma omp for [опция1, опция2]

for(int i = 0; i < 100; i++)

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

Пример использования

omp_set_num_threads(4);

#pragma omp for

//в этот момент каждая из нитей возьмет себе по индексу и начнет исполнение цикла

for(int i = 0; i < 8; i++) {

//блок

}

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

Директива single

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

#pragma omp single

Пример использования

omp_set_num_threads(4);

#pragma omp for

for(int i = 0; i < 8; i++) {

#pragma omp single

cout << " i = " << i << endl;

}

При этом какая именно нить выполнит участок кода, заранее мы никак не узнаем.

Директива master

Аналогична директиве single, но мы точно знаем, что блок выполнится мастер-нитью. Мастером является та нить, которая породила все остальные, ее порядковый номер равен 0.

Директива critical

Похожа на две предыдущие. Разница заключается в том, что блок после директивы critical выполнится всеми нитями, но по очереди. Если блок уже исполняется любой нитью, то все остальные блокируются на входе и ждут завершения. После завершения работы, случайным образом из списка заблокированных выбирается новая. Таким образом в один момент блок будет исполняться только одной нитью.

Пример использования

omp_set_num_threads(4);

#pragma omp parallel

{

int n = 1;

#pragma omp critical //Тут образуется очередь на вход

{

n++;

cout << "n = " << n << endl;

}

}

Директива barrier

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

Пример использования

omp_set_num_threads(4);

#pragma omp parallel

{

int n = 1000;

for(int i = 0; i < n; i++) {

someFunc();

}

//Исполнение кода заблокируется до тех пор, пока все нити не пройдут цикл

#pragma omp barrier

someFunc2();

}



5. Особенности реализации директив ОреnМР

Количество потоков в параллельной программе определяется либо значением переменной окружения omp_num_threads, либо специальными функциями, вызываемыми внутри самой программы. Задание переменной окружения omp_num_threads в операционной системе Linux осуществляется следующим образом с помощью команды

export OMP_NUM_THREADS=256

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

export | grep OMP_NUM_THREADS

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

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

В ОреnМР существуют различные режимы выполнения (Execution Mode) параллельных структурных блоков. Возможны следующие режимы:

* Динамический режим (Dynam ic Mode). Этот режим установлен по умолчанию и определяется заданием переменной окружения OMP_DYNAMIC в операционной системе Linux. Задать эту переменную можно, например, с помощью следующей команды операционной системы Linux: export omp_dynamic Кроме того, существует возможность задать этот режим и саму переменную внутри программы, вызвав функцию omp_set_dynamic() Отметим, что на компьютерах Silicon Graphics S350 и Kraftway G-Scale S350 вторая возможность отсутствует. В динамическом режиме количество потоков определяется самой операционной системой в соответствии со значением переменной окружения omp_num_threads. В процессе выполнения параллельной программы при переходе от одной области распараллеливания к другой эта переменная может изменять свое значение; параллельный программирование директива

* Статический режим (Static Mode). Этот режим определяется заданием переменной окружения omp_static в операционной системе Linux. В этом случае количество потоков определяется программистом. Задать переменную окружения omp_static можно, например, с помощью следующей команды операционной системы Linux: export omp_static Кроме того, существует возможность задать этот режим и саму переменную внутри программы, вызвав функцию omp_set_static() Однако на компьютерах Silicon Graphics S350 и Kraftway G-Scale S350 вторая возможность отсутствует;

Параллельные структурные блоки могут быть вложенными, но компилятор иногда по ряду причин может выполнять их и последовательно в рамках одного потока. Вложенный режим выполнения параллельных структурных блоков определяется заданием переменной окружения omp_nested=[false |true] (п о умолчанию задается false) в операционной системе Linux. Задать эту переменную можно, например, с помощью следующей команды операционной системы Linux: setenv omp_nestedtrue Кроме того, существует возможность задать этот режим и саму переменную внутри программы, вызвав функцию omp_set_nested(TRUE|FALSE) Однако на компьютерах Silicon Graphics S350 и Kraftway G-Scale S350 вторая возможность отсутствует.

Заключение

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

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

Разработка параллельных программ (ПП) состоит из трех основных этапов:

1. Декомпозиция задачи на подзадачи. Идеально, чтобы эти подзадачи работали независимо друг от друга (принцип локальности данных). Обмен данными между подзадачами является дорогой операцией, особенно, если это обмен по сети.

2. Распределение задачи по процессорам (виртуальным процессорам). В некоторых случаях решение этого вопроса можно оставить на усмотрение среды выполнения ПП.

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

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

Список литературы

1. Л.В. Городняя «ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ Часть 4 - Параллельное программирование» - 2015г.

2. А.С. Антонов, «Параллельное программирование с использованием технологии OpenMP», - издательство Московского Университета, 2009.

3. С. Б. Попов «Стандарт ОреnМР» Учебное пособие - 2011г.

4. https://ru.wikipedia.org/

5. https://intuit.ru/

6. https://learn.microsoft.com/

Размещено на Allbest.ru

...