Учебное пособие саранск издательство свмо 2013 2 удк 004. 42 Ббк з97 Авторский знак о753
 Скачать 6.58 Mb.
|
|
chunk итераций. Освободившиеся нити получают новые порции итераций до тех пор, пока все порции не будут исчерпаны. Последняя порция может содержать меньше итераций, чем все остальные. guided – динамическое распределение итераций, при котором размер порции уменьшается с некоторого начального значения до величины chunk (по умолчанию chunk=1) пропорционально количеству ещё не распределённых итераций, делённому на количество нитей, выполняющих цикл. Размер первоначально выделяемого блока зависит от реализации. В ряде случаев такое распределение позволяет аккуратнее разделить работу и сбалансировать загрузку нитей. Количество итераций в последней порции может оказаться меньше значения chunk. auto – способ распределения итераций выбирается компилятором и/или системой выполнения. Параметр chunk при этом не задаётся. runtime – способ распределения итераций выбирается во время работы программы по значению переменной среды OMP_SCHEDULE. Параметр chunk при этом не задаётся. При распараллеливании цикла следует убедиться в том, что его итерации не имеют зависимостей, и их можно выполнять в любом 63 порядке. Несоблюдение данного требования приведет к получению некорректного результата [6,13]. 3.4.3 Параллельные секции Директива OpenMP sections используется для выделения участков программы в области параллельных структурных блоков, выполняющихся в отдельных параллельных потоках. Данная директива содержит набор структурированных блоков, которые распределяются по потокам в группе. Каждый структурированный блок исполняется один раз одним из потоков в группе. #pragma omp sections опция[[[,] опция] ...] { #pragma omp section структурированный блок #pragma omp section структурированный блок ... } При выполнении этого кода OpenMP сначала создает группу потоков, а затем распределяет между ними обработку итераций цикла, после выполнения которого потоки начинают параллельную обработку оставшихся разделов кода. Если количество разделов программного кода будет больше числа потоков, обработка нескольких разделов будет отложена до тех пор, пока не появятся свободные потоки. В отличие от планирования циклов, распределение нагрузки между потоками при обработке параллельных разделов кода осуществляется и контролируется OpenMP. Программисту остается только выбрать, какие переменные будут общими, а какие – индивидуальными, и предусмотреть выражения уменьшения аналогично сегменту с организацией циклов. Рассмотрим возможные опции данной директивы. private(список) – задаёт список переменных, для которых порождается локальная копия в каждой нити; начальное значение локальных копий переменных из списка не определено. firstprivate(список) – задаёт список переменных, для которых порождается локальная копия в каждой нити; локальные копии переменных инициализируются значениями этих переменных в нити- мастере. lastprivate(список) – переменным, перечисленным в списке, присваивается результат, полученный в последней секции. 64 reduction(оператор: список) – определяется оператор - операции ( +, -, *, / и т. п.) или функции, для которых будут вычисляться соответствующие частичные значения в параллельных потоках последующего параллельного структурного блока; кроме того, определяется список локальных переменных, в котором будут сохраняться соответствующие частичные значения; после завершения всех параллельных процессов частичные значения складываются (вычитаются, перемножаются и т. п.), и результат сохраняется в одноименной общей переменной. nowait – в конце блока секций происходит неявная барьерная синхронизация параллельно работающих нитей: их дальнейшее выполнение происходит только тогда, когда все они достигнут данной точки; если в подобной задержке нет необходимости, опция nowait позволяет нитям, уже дошедшим до конца своих секций, продолжить выполнение без синхронизации с остальными. Перед первым участком кода в блоке sections директива section не обязательна. Какие именно будут задействованы нити для выполнения секции, не специфицируется. Если количество нитей больше количества секций, то некоторые нити не будут задействованы. Если же количество секций больше количества нитей, то некоторые нити выполнят больше одной секции [3,9]. Пример 3.12. #include #include int main() { int n = 0; #pragma omp parallel { #pragma omp sections lastprivate(n) { #pragma omp section { n = 1; } #pragma omp section { n = 2; } #pragma omp section 65 { n = 3; } } printf("Значение n на нити %d: %d\n", omp_get_thread_num(), n); } printf("Значение n в последовательной области: %d\n", n); return 0; } В данном примере опция lastprivate используется вместе с директивой sections. Переменная n объявлена как lastprivate переменная. Три нити, выполняющие секции section, присваивают своей локальной копии n разные значения. По выходе из области sections значение n из последней секции присваивается локальным копиям во всех нитях, поэтому все нити напечатают число 3. Это же значение сохранится для переменной n и в последовательной области. 3.4.4 Задачи Директива task применяется для выделения отдельной независимой задачи. #pragma omp task опция[[[,] опция] ...] структурированный блок Текущая нить выделяет в качестве задачи ассоциированный с директивой блок операторов. Задача может выполняться немедленно после создания или быть отложенной на неопределённое время и выполняться по частям. Размер таких частей, а также порядок выполнения частей разных отложенных задач определяется реализацией [4,5]. Рассмотрим возможные опции данной директивы. if(условие) – порождение новой задачи только при выполнении некоторого условия; если условие не выполняется, то задача будет выполнена текущей нитью и немедленно. untied – опция означает, что в случае откладывания задача может быть продолжена любой нитью из числа выполняющих данную параллельную область; если данная опция не указана, то задача может быть продолжена только породившей её нитью. default(shared | none) – всем переменным в задаче, которым явно не назначен класс, будет назначен класс shared; none означает, что всем переменным в задаче класс должен быть назначен явно. 66 private(список) – задаёт список переменных, для которых порождается локальная копия в каждой нити; начальное значение локальных копий переменных из списка не определено. firstprivate(список) – задаёт список переменных, для которых порождается локальная копия в каждой нити; локальные копии переменных инициализируются значениями этих переменных в нити- мастере. shared(список) – задаёт список переменных, общих для всех нитей. Пример 3.13. struct node { struct node *left; struct node *right; }; extern void process(struct node *); void traverse( struct node *p ) { if (p->left) #pragma omp task traverse(p->left); if (p->right) #pragma omp task traverse(p->right); process(p); } Следующий пример показывает как пройти древовидную структуру используя директиву task. Функция траверс (traverse) должна быть вызвана из параллельной области для различных указанных задач, которые будут выполняться параллельно. Задачи выполняются не в указанном порядке, поскольку здесь не используются директивы синхронизации. Таким образом, предположение, что обход будет сделан в том же порядке, что и в последовательном коде, является неверным. Для гарантированного завершения в точке вызова всех запущенных задач используется директива taskwait. #pragma omp taskwait 67 Нить, выполнившая данную директиву, приостанавливается до тех пор, пока не будут завершены все ранее запущенные данной нитью независимые задачи. Директива taskyield указывает, что текущая задача может быть приостановлена в пользу выполнения других задач. #pragma omp taskyield 3.5 Синхронизация Проблема синхронизации параллельных потоков важна не только для параллельного программирования с использованием OpenMP, но и для всего параллельного программирования в целом. Проблема состоит в том, что любой структурный параллельный блок по определению имеет одну точку выхода, за которой обычно находится последовательный структурный блок. Вычисления в последовательном блоке, как правило, могут быть продолжены, если завершены все процессы в параллельном структурном блоке и их результаты корректно переданы в последовательный блок. Именно для обеспечения такой корректной передачи данных и необходима процедура синхронизации параллельных потоков. Механизм работы синхронизации можно описать следующим образом. При инициализации набора параллельных процессов в программе устанавливается контрольная точка (аналогичная контрольной точке в отладчике), в которой программа ожидает завершения всех порожденных параллельных процессов. Отметим, что пока все параллельные процессы свою работу не завершили, программа не может продолжить работу за точкой синхронизации. А поскольку все современные высокопроизводительные процессоры являются процессорами конвейерного типа, становится понятной и высокая трудоемкость процедуры синхронизации. В самом деле, пока не завершены все параллельные процессы, программа не может начать подготовку загрузки конвейеров процессоров. Вот это и ведет к большим потерям при синхронизации процессов, аналогичных потерям при работе условных операторов в обычной последовательной программе [7,9]. 3.5.1 Директивы barrier и ordered Самый распространенный способ синхронизации в OpenMP – барьер. Он оформляется с помощью директивы barrier. Директива barrier дает всем потокам указание ожидать друг друга перед тем, как они продолжат выполнение за барьером. 68 #pragma omp barrier Нити, выполняющие текущую параллельную область, дойдя до этой директивы, останавливаются и ждут, пока все нити не дойдут до этой точки программы, после чего разблокируются и продолжают работать дальше. Кроме того, для разблокировки необходимо, чтобы все синхронизируемые нити завершили все порождённые ими задачи (task). Пример 3.14. #include #include int main() { int, i, n; #pragma omp parallel { n=omp_get_thread_num(); printf("Работает нить с номером %d\n", n); #pragma omp barrier; printf("Тест закончен\n"); } return 0; } В данном примере вывод номера каждой нити будет происходить в произвольном порядке, а вывод строки «Тест закончен» будет следовать строго после вывода номеров нитей. Директивы ordered определяют блок внутри тела цикла, который должен выполняться в том порядке, в котором итерации идут в последовательном цикле. #pragma omp ordered структурированный блок Блок операторов относится к самому внутреннему из объемлющих циклов, а в параллельном цикле должна быть задана опция ordered. Нить, выполняющая первую итерацию цикла, выполняет операции данного блока. Нить, выполняющая любую следующую итерацию, должна сначала дождаться выполнения всех операций блока всеми нитями, 69 выполняющими предыдущие итерации. Может использоваться, например, для упорядочения вывода от параллельных нитей. Пример 3.15. #include #include int main() { int i, A[10]; for (i=0;i<10;i++) {A[i]=i;} #pragma omp parallel private (i)shared (A) { #pragma omp for ordered for (i = 0; i < 10; i++) { #pragma omp ordered { printf("Значение А[%d]=%d\n", i, A[i]); }}} return 0;} В данном примере в результате использования директивы ordered вывод элементов массива А происходит в порядке возрастания индексов элементов. 3.5.2 Критические секции Этот тип синхронизации используется для описания структурных блоков, выполняющихся только в одном потоке из всего набора параллельных потоков. #pragma omp critical имя[()] структурированный блок В каждый момент времени в критической секции может находиться не более одной нити. Если критическая секция уже выполняется какой- либо нитью, то все другие нити, выполнившие директиву для секции с данным именем, будут заблокированы, пока вошедшая нить не закончит выполнение данной критической секции. Как только работавшая нить выйдет из критической секции, одна из заблокированных на входе нитей войдет в неё. Если на входе в критическую секцию стояло несколько 70 нитей, то случайным образом выбирается одна из них, а остальные заблокированные нити продолжают ожидание. Все неименованные критические секции условно ассоциируются с одним и тем же именем. Все критические секции, имеющие одно и тоже имя, рассматриваются единой секцией, даже если находятся в разных параллельных областях. Побочные входы и выходы из критической секции запрещены [11,14]. Пример 3.16. #include #include int main() { int x; x=0; #pragma omp parallel shared(x) { #pragma omp critcal {x=x+1; printf(“x=%d\n”,x); }} return 0;} В примере переменная x объявлена вне параллельной области, она является общей. В результате выполнения директивы critical каждая нить по очереди увеличит x на 1 и выведет результат на экран. Если есть критическая секция, то в каждый момент времени фрагмент будет обрабатываться лишь какой-либо одной нитью. Остальные нити, даже если они уже подошли к данной точке программы и готовы к работе, будут ожидать своей очереди. Если критической секции нет, то все нити могут одновременно выполнить данный участок кода. С одной стороны, критические секции предоставляют удобный механизм для работы с общими переменными. Но с другой стороны, пользоваться им нужно осмотрительно, поскольку критические секции добавляют последовательные участки кода в параллельную программу, что может снизить её эффективность. 3.5.3 Директива atomic Этот тип синхронизации определяет переменную в левой части оператора присваивания, которая должна корректно обновляться 71 несколькими нитями. В этом случае происходит предотвращение прерывания доступа, чтения и записи данных, находящихся в общей памяти, со стороны других потоков. Отметим, что синхронизация atomic является альтернативой директивы reduction. Применяется эта синхронизация только для операторов, следующих непосредственно за определяющей ее директивой. Синхронизация atomic - очень дорогая операция с точки зрения трудоемкости выполнения программы. Она выполняется автоматически по умолчанию при завершении циклов в параллельном режиме. Для того чтобы ее исключить, следует использовать директиву nowait [3,5]. #pragma omp atomic [read | write | update | capture ]оператор или #pragma omp atomic capture структурированный блок Пример 3.17. #include #include int main() { int x; x=0; #pragma omp parallel shared(x) { #pragma omp atomic x=x++; } printf(“Число нитей %d\n”,x); return 0;} В данном примере директива atomic используется для предотвращения одновременного изменения несколькими нитями значения переменной x. Результатом работы программы является общее количество нитей. 3.5.4 Замки Один из вариантов синхронизации в OpenMP реализуется через механизм замков (locks). В качестве замков используются общие целочисленные переменные (размер должен быть достаточным для 72 хранения адреса). Данные переменные должны использоваться только как параметры примитивов синхронизации. Замок может находиться в одном из трёх состояний: неинициализированный, разблокированный или заблокированный. Разблокированный замок может быть захвачен некоторой нитью. При этом он переходит в заблокированное состояние. Нить, захватившая замок, и только она может его освободить, после чего замок возвращается в разблокированное состояние. Есть два типа замков: простые замки и множественные замки. Множественный замок может многократно захватываться одной нитью перед его освобождением, в то время как простой замок может быть захвачен только однажды. Для множественного замка вводится понятие коэффициента захваченности (nesting count). Изначально он устанавливается в ноль, при каждом следующем захватывании увеличивается на единицу, а при каждом освобождении уменьшается на единицу. Множественный замок считается разблокированным, если его коэффициент захваченности равен нулю. Для инициализации простого или множественного замка используются соответственно функции omp_init_lock() и omp_init_nest_lock(). После выполнения функции замок переводится в разблокированное состояние. Для множественного замка коэффициент захваченности устанавливается в ноль. Функции |