Разработка лабораторного практикума по курсу «Методы параллельной обработки»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

" Национальный исследовательский ядерный университет «МИФИ»

ФАКУЛЬТЕТ КИБЕРНЕТИКИ И ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ КАФЕДРА УПРАВЛЯЮЩИХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ

Дипломный проект

Тема:

Разработка лабораторного практикума по курсу

" Методы параллельной обработки"

Студент-дипломник Малкин Д.Ю.

Руководитель Шувалов В. Б., доцент, к. т. н.

• Введение
• 1. Теоретическая часть
• 1.1 Технология MPI
• Сообщения
• Разновидности обменов сообщениями
• Привязка к языку C
• Основные понятия MPI
• Различные подпрограммы MPI
• Двухточечный обмен
• Коллективный обмен
• 1.2 Технология OpenMP
• Принципиальная схема программирования в OpenMP
• Синтаксис директив в OpenMP
• Особенности реализации директив OpenMP
• Директивы OpenMP
• 1.3Технология Posix Threads
• Создание и завершение нитей
• Атрибуты нитей и управление нитями
• 1.4 Выводы
• 2. Практическая часть
• 2.1 Выбор инструментальных средств
• 2.2 Проведение лабораторных работ
• Учебные задания
• Подготовка к выполнению
• Выполнение лабораторных работ
• 2.3 Алгоритмическое обеспечение
• 2.4 Функциональная структура программы лабораторного практикума
• 2.5 Интерфейс разработанной программы
• Работа с программой (преподаватель)
• Работа с программой (студент)
• 2.6 Тестирование и отладка
• 2.7 Выводы
• Заключение
• Список литературы
• Приложения

Потребность решения сложных прикладных задач с большим объемом вычислений и принципиальная ограниченность максимального быстродействия «классических» — по схеме фон Неймана — ЭВМ привели к появлению многопроцессорных вычислительных систем (МВС). Особую значимость параллельные вычисления приобрели с переходом компьютерной индустрии на массовый выпуск многоядерных процессоров. Суперкомпьютерные технологии и высокопроизводительные вычисления с использованием параллельных вычислительных систем становятся важным фактором научно-технического прогресса; их применение принимает всеобщий характер.

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

К основным моделям параллельных вычислений относятся [2]:

1. POSIX Threads — стандарт POSIX для потоков. Стандарт определяет интерфейс программирования приложений для создания и манипуляции потоками, существуют как закрытые, так и открытые реализации. Используется в основном в UNIX-подобных ОС, хотя есть реализации и для MS Windows. Предназначен для использования преимущественно в системах с разделяемой памятью.

2. Parallel Virtual Machine (PVM) — свободная реализация платформы для параллельных вычислений в гетерогенных сетях. Объединяет несколько физических компьютеров в один логический. Существуют реализации для самых различных типов ЭВМ.

3. Message Passing Interface (MPI) — языко-независимый протокол, используемый для программирования параллельных (допускающих одновременное выполнение различных инструкций) компьютеров. Является открытым, считается сложным для разработчика, но в настоящее время полноценных альтернатив MPI нет.

4. OpenMP — открытый интерфейс программирования приложений, поддерживающий программирование мультипроцессорных ЭВМ с разделяемой памятью. Является открытым, в использовании намного проще MPI, однако имеет целый набор архитектурных ограничений, не свойственных MPI.

5. Прочие технологии, а именно: TBB, Charm++, Cilk, Global Arrays, Star-P от Interactive Supercomputing, Graphical System Design, HPF, Intel Ct, ProActive, SHMEM и т. д.

Таким образом, существуют модели параллельных вычислений как для симметричных мультипроцессорных систем (OpenMP, Posix Threads), так и для массивно-параллельных систем (MPI, PVM). В кластерных системах чаще всего используется технология MPI, в системах с неоднородным доступом к памяти (NUMA) используются те же технологии, что и в симметричных мультипроцессорных системах.

Цель данной работы — разработка лабораторного практикума по курсу «Методы параллельной обработки». Задача данного практикума — дать студентам знания об основных директивах и функциях, применяемых в наиболее распространенных технологиях параллельного программирования, а также научить студента выбирать наиболее подходящую технологию для решения конкретных задач и использовать выбранную технологию оптимальным образом. Выше было выделено четыре основных технологии параллельного программирования, использующиеся в настоящее время. В лабораторный практикум включены три из этих технологий — MPI, OpenMP и Posix Threads. Выбор в пользу MPI перед PVM был сделан по причине того, что при решении этими технологиями сходных задач MPI имеет единый стандарт, поддерживаемый многими производителями (Microsoft, Hewlett-Packard, Intel и др.). Технология OpenMP разрабатывается несколькими крупными производителями вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB). Технология поддерживается многими современными компиляторами, такими как Sun Studio, Visual C++ 2005 и младше, GCC, Intel C++ Compiler и др. Для повышения производительности программ OpenMP может использоваться в сочетании с MPI. Технология Posix Threads нашла широкое применение в Unix — подобных операционных системах, таких как Unix и Solaris. Библиотека является частью нового единого стандарта спецификаций UNIX (Single UNIX Specifications Standard) и включена в набор стандартов IEEE, описывающих интерфейсы ОС для UNIX (IEEE Std.1003.1−2001). Таким образом, технологии, выбранные для изучения в рамках лабораторного практикума, охватывают основные классы существующих архитектур ЭВМ (массивно-параллельные системы, симметричные мультипроцессорные системы, системы с неоднородным доступом к памяти, кластерные системы) и основные операционные системы (Windows и Unix — подобные операционные системы). Студенту, изучившему эти технологии, в дальнейшем в большинстве случаев будет достаточно какой-либо из указанных технологий или их сочетаний без необходимости изучения иных средств параллельной разработки.

Лабораторные практикумы по курсу «Параллельная обработка» используются во многих отечественных вузах: МГТУ им. Баумана, СПбГУ и др., однако там отсутствует специализированное ПО для проведения лабораторных работ и исследования результатов выполнения параллельных программ, создаваемых в ходе выполнения этих лабораторных работ. В настоящей работе предлагается заложить в разрабатываемую программу, реализующую лабораторный практикум, функции проведения предварительного тестирования, выдачи условий заданий, справочных материалов, исполнения программ, разработанных студентами и обработки результатов исполнения разработанных программ.

Разрабатываемый лабораторный практикум представляет собой набор из трех лабораторных работ, объединенных общей целью — определить оптимальную параллельную технологию и количество параллельных процессов (потоков) для решения конкретной задачи. Также исследуется влияние объема вычислений на выбор оптимальной параллельной технологии. Каждая лабораторная работа охватывает одну из технологий параллельного программирования (MPI, OpenMP, Posix Threads). На протяжении лабораторных работ студенты решают одну и ту же задачу с применением различных технологий в соответствии с полученным вариантом задания. По каждой лабораторной работе практикума студенты составляют отчет, содержащий разработанную параллельную программу и зависимости, о которых сказано ниже. По выполнении всех лабораторных работ студент пишет заключительный отчет, содержащий вывод об оптимальной параллельной технологии для решения поставленной задачи.

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

Таким образом, разработка лабораторного практикума сводится к следующим этапам:

· Разработать методику проведения лабораторных работ.

· Разработать варианты заданий.

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

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

· Разработать алгоритмическое обеспечение лабораторных работ.

· Разработать программу, реализующую лабораторный практикум.

· Протестировать и отладить программу, реализующую лабораторный практикум.

1. Теоретическая часть

Рассматриваемые технологии MPI, OpenMP и Posix Threads используются в различных областях программирования и охватывают большую часть спектра параллельных вычислительных систем. Технология MPI применяется в массивно-параллельных и кластерных системах. Кластерные системы можно использовать там, где требуется ЭВМ с производительностью порядка десятков и сотен триллионов операций с плавающей запятой в секунду (TFlops). Кластеры находят применение при решении задач моделирования климата, генной инженерии, проектировании интегральных схем, анализа загрязнения окружающей среды, создании лекарственных препаратов и др. Технологии Posix Threads и OpenMP применяются в симметричных мультипроцессорных системах (SMP) и системах с неоднородным доступом к памяти (Numa). SMP часто применяется в науке, промышленности, бизнесе, где программное обеспечение специально разрабатывается для многопоточного выполнения. В некоторых приложениях, в частности, программных компиляторах и некоторых проектах распределённых вычислений, повышение производительности будет почти прямо пропорционально числу дополнительных процессоров.

1.1 Технология MPI

Message Passing Interface (MPI, интерфейс передачи сообщений) — программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу.

MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для большого числа компьютерных платформ. Используется при разработке программ для кластеров и суперкомпьютеров. Основным средством коммуникации между процессами в MPI является передача сообщений друг другу. Стандартизацией MPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который должен поддерживаться как на платформе, так и в приложениях пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.

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

Далее будут рассмотрены те аспекты технологии MPI, которые были приняты во внимание и использованы в настоящей работе, а именно:

Основные понятия MPI (сообщения, ранга, коммуникатора и др.) и типы данных

Основные функции MPI (MPI_Init, MPI_Finalize, MPI_Comm_size, MPI_Comm_rank и др.)

Блокирующая разновидность двухточечного обмена

Широковещательная рассылка как вариант коллективного обмена

Полное описание всех принятых стандартов доступно в источнике.

Сообщения

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

ранг процесса-отправителя сообщения;

адрес, по которому размещаются пересылаемые данные процесса-отправителя;

тип пересылаемых данных;

количество данных;

ранг процесса, который должен получить сообщение;

адрес, по которому должны быть размещены данные процессом-получателем.

тег сообщения;

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

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

Разновидности обменов сообщениями

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

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

Блокирующие прием/передача — приостанавливают выполнение процесса на время приема сообщения.

Неблокирующие прием/передача — выполнение процесса продолжается в фоновом режиме, а программа в нужный момент может запросить подтверждение завершения

приема сообщения.

Cинхронный обмен — сопровождается уведомлением об окончании приема сообщения.

Асинхронный обмен — уведомлением не сопровождается.

лабораторный практикум программа

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

В программах на языке C имена подпрограмм имеют вид: Класс_действие_подмножество или Класс_действие. В C++ подпрограмма

является методом для определенного класса, имя имеет в этом случае вид

MPI: Класс: действие_подмножество. Для некоторых действий введены стандартные наименования: Create — создание нового объекта, Get — получение информации об объекте, Set — установка параметров объекта, Delete — удаление информации, Is — запрос о том, имеет ли объект указанное свойство.

Имена констант MPI записываются в верхнем регистре. Их описания находятся в заголовочном файле mpi. h.

Входные параметры функций передаются по значению, а выходные (и INOUT) — по ссылке.

Соответствие типов MPI стандартным типам языка C приведено в табл.1.

Таблица 1. Типы данных MPI для языка C

Основные понятия MPI

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

MPI_COMM_WORLD — включает все процессы параллельной программы;

MPI_COMM_SELF — включает только данный процесс;

MPI_COMM_NULL — пустой коммуникатор, не содержит ни одного

процесса.

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

Рис.1. Коммуникатор

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

Рис.2. Ранги процессов

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

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

Различные подпрограммы MPI

Подключение к MPI:

int MPI_Init (int *argc, char **argv)

Аргументы argc и argv требуются только в программах на C, где они задают количество аргументов командной строки запуска программы и вектор этих аргументов. Данный вызов предшествует всем прочим вызовам подпрограмм MPI.

Завершение работы с MPI:

int MPI_Finalize ()

После вызова данной подпрограммы нельзя вызывать подпрограммы MPI. MPI_FINALIZE должны вызывать все процессы перед завершением своей работы.

Определение размера области взаимодействия:

int MPI_Comm_size (MPI_Comm comm, int *size)

Входные параметры:

· comm — коммуникатор.

Выходные параметры:

· size — количество процессов в области взаимодействия.

Определение ранга процесса:

int MPI_Comm_rank (MPI_Comm comm, int *rank)

Входные параметры:

· comm — коммуникатор.

Выходные параметры:

· rank — ранг процесса в области взаимодействия.

Время, прошедшее с произвольного момента в прошлом

double MPI_Wtime ()

Двухточечный обмен

Участниками двухточечного обмена являются два процесса: процесс-отправитель и процесс — получатель (рис.3).

Рис. 3. Двухточечный обмен

Стандартная блокирующая передача

int MPI_Send (void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)

Входные параметры:

· buf — адрес первого элемента в буфере передачи;

· count — количество элементов в буфере передачи;

· datatype — тип MPI каждого пересылаемого элемента;

· dest — ранг процесса-получателя сообщения (целое число от 0 до n — 1, где n — число процессов в области взаимодействия);

· tag — тег сообщения;

· comm — коммуникатор;

Стандартный блокирующий прием

int MPI_Recv (void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)

Входные параметры:

· count — максимальное количество элементов в буфере приема. Фактическое их количество можно определить с помощью подпрограммы MPI_Get_count;

· datatype — тип принимаемых данных. Напомним о необходимости соблюдения соответствия типов аргументов подпрограмм приема и передачи;

· source — ранг источника. Можно использовать специальное значение

MPI_ANY_SOURCE, соответствующее произвольному значению ранга. В программировании идентификатор, отвечающий произвольному значению параметра, часто называют «джокером». Это наименование будет использоваться и в дальнейшем.

· tag — тег сообщения или «джокер» MPI_ANY_TAG, соответствующий произвольному значению тега;

· comm — коммуникатор. При указании коммуникатора «джокеры» использовать нельзя.

Выходные параметры:

· buf — начальный адрес буфера приема. Его размер должен быть достаточным, чтобы разместить принимаемое сообщение, иначе при выполнении приема произойдет сбой — возникнет ошибка переполнения;

· status — статус обмена.

Если сообщение меньше, чем буфер приема, изменяется содержимое лишь тех ячеек памяти буфера, которые относятся к сообщению.

Коллективный обмен

Участниками коллективного обмена являются более двух процессов.

Широковещательная рассылка выполняется выделенным процессом, который называется главным (root). Все остальные процессы, принимающие участие в обмене, получают по одной копии сообщения от главного процесса

int MPI_Bcast (void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm)

Параметры этой процедуры одновременно являются входными и выходными:

· buffer — адрес буфера;

· count — количество элементов данных в сообщении;

· datatype — тип данных MPI;

· root — ранг главного процесса, выполняющего широковещательную рассылку;

· comm — коммуникатор.

Схема распределения данных представлена на рис. 4.

Рис.4. Распределение данных при широковещательной рассылке

1.2 Технология OpenMP

OpenMP — это интерфейс прикладного программирования для создания многопоточных приложений, предназначенных в основном для параллельных вычислительных систем с общей памятью. OpenMP состоит из набора директив для компиляторов и библиотек специальных функций. Стандарты OpenMP разрабатывались в течение последних 15 лет применительно к архитектурам с общей памятью. Описание стандартов OpenMP и их реализации при программировании на алгоритмических языках Fortran и C/C++ можно найти в.

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

В настоящее время OpenMP поддерживается большинством разработчиков параллельных вычислительных систем: компаниями Intel, Hewlett-Packard, Silicon Graphics, Sun, IBM, Fujitsu, Hitachi, Siemens, Bull и другими. Многие известные компании в области разработки системного программного обеспечения также уделяют значительное внимание разработке системного программного обеспечения с OpenMP. Среди этих компаний можно отметить Intel, KAI, PGI, PSR, APR, Absoft и некоторые другие. Значительное число компаний и научно-исследовательских организаций, разрабатывающих прикладное программное обеспечение, в настоящее время использует OpenMP при разработке своих программных продуктов. Среди этих компаний и организаций можно отметить ANSYS, Fluent, Oxford Molecular, NAG, DOE ASCI, Dash, Livermore Software, а также и российские компании ТЕСИС, Центральную геофизическую экспедицию и российские научно-исследовательские организации, такие как Институт математического моделирования РАН, Институт прикладной математики им. Келдыша РАН, Вычислительный центр РАН, Научно-исследовательский вычислительный центр МГУ, Институт химической физики РАН и другие.

Принципиальная схема программирования в OpenMP

Принципиальная схема параллельной программы изображена на рис. 5.

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

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

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

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

Синтаксис директив в OpenMP

Все рассматриваемые ниже директивы приведены в синтаксисе языка С/С++.

Основные конструкции OpenMP — это директивы компилятора или прагмы (директивы препроцессора) языка C/C++. Ниже приведен общий вид директивы OpenMP прагмы.

#pragma omp конструкция [предложение [предложение] …]

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

В следующем фрагменте программы показан общий вид основных директив OpenMP.

# pragma omp parallel

private (var1, var2, …)

shared (var1, var2, …)

firstprivate (var1, var2, …)

lastprivate (var1, var2, …)

copyin (var1, var2, …)

reduction (operator: var1, var 2, …)

if (expression)

default (shared | none)

{

[Структурный блок программы]

}

В рассматриваемом фрагменте предложение OpenMP shared используется для описания общих переменных. Как уже отмечалось ранее, общие переменные позволяют организовать обмен данными между параллельными процессами в OpenMP. Предложение private используется для описания внутренних (локальных) переменных для каждого параллельного процесса. Предложение firstprivate применяется для описания внутренних переменных параллельных процессов, однако данные в эти переменные импортируются из главного потока. Предложение reduction позволяет собрать вместе в главном потоке результаты вычислений частичных сумм, разностей и т. п. из параллельных потоков. Предложение if является условным оператором в параллельном блоке. Предложение default определяет по умолчанию тип всех переменных в последующем параллельном структурном блоке программы. Далее механизм работы этих предложений будет рассмотрен более подробно. Предложение copyin позволяет легко и просто передавать данные из главного потока в параллельные.

Рассмотренные в настоящем разделе директивы OpenMP не охватывают весь спектр директив. В следующем разделе будут рассмотрены некоторые из директив OpenMP и механизмов их работы.

Особенности реализации директив OpenMP

В этом разделе рассмотрим некоторые специфические особенности реализации директив OpenMP.

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

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

Пример ветвления во фрагменте программы, написанной на языке C/C++, в зависимости от номера параллельного потока показан в примере ниже.

#pragma omp parallel

{

myid = omp_get_thread_num ();

if (myid == 0)

do_something ();

else

do_something_else (myid);

}

В этом примере в первой строке параллельного блока вызывается функция omp_get_thread_num, возвращающая номер параллельного потока. Этот номер сохраняется в локальной переменной myid. Далее в зависимости от значения переменной myid вызывается либо функция do_something () в первом параллельном потоке с номером 0, либо функция do_something_else (myid) во всех остальных параллельных потоках.

Директивы OpenMP

Теперь перейдем к подробному рассмотрению директив OpenMP и механизмов их реализации.

Директивы shared, private и default

Эти директивы (предложения OpenMP) используются для описания типов переменных внутри параллельных потоков.

Предложение OpenMP

shared (var1, var2, …, varN)

определяет переменные var1, var2, …, varN как общие переменные для всех потоков. Они размещаются в одной и той же области памяти для всех потоков.

Предложение OpenMP

private (var1, var2, …, varN)

определяет переменные var1, var2, …, varN как локальные переменные для каждого из параллельных потоков. В каждом из потоков эти переменные имеют собственные значения и относятся к различным областям памяти: локальным областям памяти каждого конкретного параллельного потока.

Предложение OpenMP

default (shared | private | none)

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

Директива if

Директива (предложение) OpenMP if используется для организации условного выполнения потоков в параллельном структурном блоке.

Предложение OpenMP

if (expression)

определяет условие выполнения параллельных потоков в последующем параллельном структурном блоке. Если выражение expression принимает значение TRUE (Истина), то потоки в последующем параллельном структурном блоке выполняются. В противном случае, когда выражение expression принимает значение FALSE (Ложь), потоки в последующем параллельном структурном блоке не выполняются.

Директива reduction

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

В предложении OpenMP

reduction (operator | intrinsic: var1 [, var2,., varN])

определяется operator — операции (+, —, *, / и т. п.) или функции, для которых будут вычисляться соответствующие частичные значения в параллельных потоках последующего параллельного структурного блока. Кроме того, определяется список локальных переменных var1, var2,., varN, в котором будут сохраняться соответствующие частичные значения. После завершения всех параллельных процессов частичные значения складываются (вычитаются, перемножаются и т. п.), и результат сохраняется в одноименной общей переменной.

В языке C/C++ в качестве параметров operator и intrinsic в предложениях reduction допускаются следующие операции и функции:

· параметр operator может быть одной из следующих арифметических или логических операций: +, —, *, &,^, &&, ||;

· параметр intrinsic может быть одной из следующих функций: max, min;

· указатели и ссылки в предложениях reduction использовать строго запрещено!

Директива for

Директива OpenMP for используется для организации параллельного выполнения петель циклов в программах.

Предложение OpenMP

#pragma omp for

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

Директива sections

Директива OpenMP sections используется для выделения участков программы в области параллельных структурных блоков, выполняющихся в отдельных параллельных потоках.

Описание синтаксиса предложения OpenMP sections приведено в примере ниже.

#pragma omp sections [предложение [предложение …]]

{

#pragma omp section

structured block

[#pragma omp section

structured block

…

]

}

Каждый структурный блок (structured block), следующий за прагмой

#pragma omp sections

выполняется в отдельном параллельном потоке. Общее же число параллельных потоков равно количеству структурных блоков (section), перечисленных после прагмы

#pragma omp sections [предложение [предложение …]]

В качестве предложений допускаютcя следующие OpenMP директивы: private (list), firstprivate (list), lastprivate (list), reduction (operator: list) и nowait.

1.3Технология Posix Threads

Стандарт POSIX допускает различные подходы к реализации многопоточности в рамках одного процесса. Возможны три основных подхода:

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

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

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

Как правило, при этом количество пользовательских нитей в процессе может превосходить количество системных нитей. [9]

Пользовательские нити

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

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

Наиболее известная реализация пользовательских нитей — это волокна (fibers) в Win32. Волокна могут использоваться совместно с системными нитями Win32, но при этом волокна привязаны к определенной нити и исполняются только в контексте этой нити. Волокна не должны исполнять блокирующиеся системные вызовы; попытка сделать это приведет к блокировке нити. Некоторые системные вызовы Win32 имеют неблокирующиеся аналоги, предназначенные для использования в волокнах, но далеко не все. Это резко ограничивает применение волокон в реальных приложениях.

Системные нити

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

В рамках первого подхода, системные нити выступают как подчиненная по отношению к процессу сущность. Идентификатор нити состоит из идентификатора родительского процесса и собственного идентификатора нити. Идентификатор нити локален по отношению к процессу, т. е. нити разных процессов могут иметь одинаковые идентификаторы. Такой подход реализует большинство систем, реализующих системные нити — IBM MVS-OS/390-zOS, DEC VAX/VMS — OpenVMS, OS/2, Win32, многие Unix-системы, в том числе и Solaris. В Solaris и других Unix системах (IBM AIX, HP/UX) системные нити называются LWP (Light-Weight Process, «легкие процессы»).

Solaris 10 использует системные нити, так что каждой нити POSIX Threads API соответствует собственный LWP. Старые версии Solaris использовали гибридный подход, который рассматривается в следующем разделе.

В рамках другого подхода, системные нити являются сущностями того же уровня, что процесс. Иногда все, что объединяет нити одного процесса — это общее адресное пространство. Наиболее известная ОС, использующая такой подход — Linux. В Linux, нити выглядят как отдельные записи в таблице процессов и отдельные строки в выводе команд top (1) и ps (1), имеют собственный идентификатор процесса.

В старых версиях Linux это приводило к своеобразным проблемам при реализации POSIX Threads API; так, в большинстве Unix-систем завершение процесса системным вызовом exit (2) приводит к немедленному завершению всех его нитей; в Linux вплоть до 2.4 завершалась только текущая нить. В Linux 2.6 был внесен ряд изменений в ядро, приблизивших семантику многопоточности к стандарту POSIX. Эти изменения известны как NPT (Native POSIX Threads).

Разрабатываемый лабораторный практикум рассчитан на стандартную семантику POSIX Threads API. При программировании для старых (2.4 и младше) версий ядра Linux необходимо изучить особенности поведения этих систем по документации, поставляющейся с системой, или по другим источникам.

Гибридная реализация

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

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

При планировании пользовательских нитей возникает проблема блокирующихся системных вызовов. Когда какая-то нить вызывает блокирующийся системный вызов, соответствующий LWP блокируется и на некоторое время выпадает из работы. В старых версиях Solaris эта проблема решалась следующим образом: многопоточная библиотека всегда имела выделенную нить, которая не вызывала блокирующихся системных вызовов никогда. Когда ядро системы обнаруживало, что все LWP процесса заблокированы, оно посылало процессу сигнал SIGWAITING. Библиотечная нить перехватывала этот сигнал и, если это допускалось настройками библиотеки, создавала новый LWP. Таким образом, если все пользовательские нити исполняли блокирующиеся системные вызовы, то количество LWP могло сравняться с количеством пользовательских нитей. Можно предположить, что компания Sun отказалась от гибридной реализации многопоточности именно потому, что обнаружилось, что такое происходит со многими реальными прикладными программами. В старых версиях Solaris поддерживался довольно сложный API, позволявший управлять количеством LWP и политикой планирования нитей между ними. Так, можно было привязать нить к определенному LWP. Этот API был частью Solaris NativeThreads и нестандартным расширением POSIX Threads API. В рамках данного курса этот API не изучается. Многие современные Unix-системы, в том числе IBM AIX, HP/UX, SCO UnixWare используют гибридную реализацию POSIX Thread API.

Создание и завершение нитей

В POSIX Thread API нить создается библиотечной функцией pthread_create ().

Параметры этой функции:

· pthread_t * thread — Выходной параметр. Указатель на переменную, в которой при успешном завершении будет размещен идентификатор нити.

· const pthread_attr_t * attr — Входной параметр. Указатель на структуру, в которой заданы атрибуты нити (рассматривается на следующей лекции). Если этот указатель равен

· NULL, используются атрибуты по умолчанию.

· void * (*start_routine) (void*) — Входной параметр. Указатель на функцию, которая будет запущена во вновь созданной нити.

· void *arg — Входной параметр. Значение, которое будет передано в качестве параметра start_routine.

Возвращаемое значение:

· 0 при успешном завершении

· Код ошибки при неудачном завершении

Большинство других функций POSIX Threads API используют аналогичное соглашение о кодах возврата.

Для завершения нити используется функция pthread_exit (). Эта функция всегда завершается успешно и принимает единственный параметр, указатель на код возврата типа void *. Как и в случае с pthread_create (), библиотека никогда не пытается обращаться к значению этого параметра как к указателю, поэтому его можно использовать для передачи скалярных значений.

Другой способ завершения нити — это возврат управления из функции start_routine при помощи оператора return. Поскольку функция start_routine должна возвращать тип void *, все ее операторы return должны возвращать значение. Этот способ практически полностью эквивалентен вызову pthread_exit () с тем же самым значением.

Для ожидания завершения нити и получения ее кода возврата используется библиотечная функция pthread_join (). Эта функция имеет два параметра, идентификатор нити типа pthread_t, и указатель на переменную типа void *, в которой размещается значение кода возврата. Если в качестве второго параметра передать нулевой указатель, код возврата игнорируется.

Если требуемая нить еще не завершилась, то нить, сделавшая вызов pthread_join (), блокируется. Если такой нити (уже) не существует, pthread_join () возвращает ошибку ESRCH.

Когда нить завершается, то связанные с ней ресурсы существуют до того момента, пока какаято другая нить не вызоветpthread_join (). Однако к тому моменту, когда pthread_join завершается, все ресурсы, занятые нитью (стек, thread local data, дескриптор нити) уничтожаются.

В отличие от процессов Unix, где системный вызов wait () может использовать только родитель по отношению к потомкам, любая нить может ждать завершения любой другой нити того же процесса. Если несколько нитей ждут завершения одной и той же нити, которая еще не завершилась, все эти нити блокируются. Однако при завершении нити одна из ожидавших нитей получает код возврата, а остальные ошибку ESRCH.

Если нить пытается ожидать сама себя, она получает ошибку EDEADLK.

Еще одна важная функция, связанная с ожиданием завершения нити — это функция pthread_detach (). Эта функция указывает, что все ресурсы, связанные с нитью, необходимо уничтожать сразу после завершения этой нити. При этом уничтожается и код возврата такой нити — при попытке сделать pthread_join () на нить, над которой перед этим сделали pthread_detach (), возвращается код ошибки EINVAL.

В руководстве по pthread_detach () в системе Solaris 10 сказано, что главное применение pthread_detach () — это ситуация, когда родитель, ожидавший завершения дочерней нити, получает pthread_cancel (). В действительности, существуют и другие применения «отсоединенных» нитей.

Не обязательно делать pthread_detach () на уже запущенную нить; в атрибутах нити (pthread_attr_t) можно указать, что нить следует запускать в уже «отсоединенном» состоянии.

Библиотечная функция pthread_cancel () принудительно завершает нить. В зависимости от свойств нити и некоторых других обстоятельств, нить может продолжать исполнение некоторое время после вызова pthread_cancel (3C).

Атрибуты нитей и управление нитями

При создании нити можно указать блок атрибутов нити при помощи второго параметра функции pthread_create (). Этот блок представляет собой структуру pthread_attr_t.

Стандарт POSIX требует рассматривать эту структуру как непрозрачный тип и использовать для изменения отдельных атрибутов функции просмотра и установки отдельных атрибутов. Для инициализации pthread_attr_t следует использовать функцию pthread_attr_init (). Эта функция имеет единственный параметр — pthread_attr_t *attr. Она устанавливает атрибуты в соответствии с табл.2.

Табл.2. Атрибуты нити.

Кроме этих атрибутов, pthread_attr_t содержит некоторые другие атрибуты. Некоторые из этих атрибутов игнорируются Solaris 10, и введены для совместимости с другими реализациями POSIX Thread API.

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

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

Некоторые из атрибутов, например detachstate и priority, могут быть изменены у уже работающей нити. Для этого используются отдельные функции. Так, detachstate в атрибутах нити изменяется функцией pthread_attr_setdetachstate (), а у исполняющейся нити — функцией pthread_detach (). Pthread_detach () изменяет значение атрибута с JOINABLE на DETACHED; способа изменить этот атрибут с DETACHED на JOINABLE у работающей нити не существует.

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

Перед уничтожением структуры pthread_attr_t необходимо вызвать функцию pthread_attr_destroy ().

1.4 Выводы

В данном разделе проведен анализ основных современных технологий параллельного программирования для разных типов архитектур ЭВМ и различных операционных систем. По результатам анализа определены те технологии параллельного программирования, которые будут представлены для изучения в рамках лабораторного практикума, а именно MPI, OpenMP и Posix Threads. Данные технологии охватывают все основные классы современных параллельных компьютеров, такие как массивно-параллельные системы, симметричные мультипроцессорные системы, системы с неоднородным доступом к памяти и кластерные системы, а также основные операционные системы (Windows и Unix-подобные системы). Обозначены основные директивы и функции вышеупомянутых технологий, которые могут быть предложены для освоения студентами.

2. Практическая часть

2.1 Выбор инструментальных средств

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

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

возможность авторизации студента и преподавателя.

возможность редактирования преподавателем списка пользователей.

возможность фиксации преподавателем действий студентов.

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

возможность проведения вступительного теста.

возможность редактирования преподавателем вопросов, входящих в тест, и вариантов ответа.

банк тестов должен быть устойчивым к взлому студентами.

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

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

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

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

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

Для написания программы было решено использовать язык C++. Данное решение вызвано необходимостью компилировать код на языке C/C++, написанный студентами. Таким образом, и код студентов, и программа, реализующая лабораторный практикум, написаны на едином языке. Программа была разработана в среде программирования Borland C++ Builder XE.

В качестве среды разработки, поддерживающей разработку, компиляцию и исполнение программ, использующих технологию OpenMP, была выбрана среда Microsoft Visual Studio 2008.

К достоинствам данной среды разработки можно отнести то, что данная среда полностью поддерживает параллельные библиотеки MPI, OpenMP и Posix Threads. Существуют и другие среды разработки, поддерживающие вышеуказанные библиотеки (Dev C++, Eclipse CDT), но принимается во внимание факт, что на компьютерах учебных классов обычно установлены операционные системы семейства Windows от компании Microsoft, поэтому Microsoft Visual Studio 2008 требует минимальной настройки для работы с операционной системой. Также следует учесть то, что существует программа поставки бесплатных продуктов Microsoft НИЯУ МИФИ.