[БЕЗ_ЗВУКА] [ЗАСТАВКА] Добро пожаловать в третий модуль нашего курса. В этом модуле мы рассмотрим директивы OpenMP, позволяющие распределить работу между разными потоками и сделать наше программу действительно параллельной. Также мы с вами рассмотрим директивы, позволяющие синхронизировать работу потоков, корректно работать с общими переменными. В этой лекции мы разберем директиву, которая позволяет распределить работу между потоками наиболее часто встречающейся конструкции в программах — это циклы со счетчиком. Давайте рассмотрим простой пример сложения двух векторов. У нас последовательная программа, которая решает данную задачу. Наша задача — ускорить выполнение этой программы за счет параллельности. Время выполнения сложения двух векторов замеряется с использованием функции omp_get_wtime. Если проанализировать как происходит сложение двух векторов, то мы увидим, что ее можно разбить на подзадачи, которые можно выполнять независимо друг от друга. Подзадача — это сложение компонент векторов a и b. Эти подзадачи можно выполнять параллельно, так как результат сложения, например, a1 и b1 никак не зависит от результата сложения a2 и b2 или любых других компонент векторов a и b. Давайте теперь создадим параллельную область с помощью директивы parallel, в которую будет входить код, отвечающий за сложение векторов. С помощью опций данной директивы явно укажем, что переменные a, b и c являются общими. a и b — общие, так как являются исходными данными и нужны будут всем потокам, а c — общая переменная, чтобы по завершению параллельной области получить результат в одном векторе. Если в параллельной области встретится оператор цикла, то, согласно общему правилу, он будет выполнен всеми потоками текущей группы. То есть каждый поток выполнит все итерации данного цикла. В нашем случае каждый поток сложит все компоненты векторов a и b. Нам же необходимо, чтобы каждый сложил только свои части векторов a и b. В OpenMP для распределения итераций цикла между различными потоками можно использовать директиву for. Общий ее вид представлен на экране. Эта директива относится к идущему следом за данной директивой блоку, включающему операторы for. На вид параллельных циклов накладываются достаточно жесткие ограничения. В частности, предполагается, что корректная программа не должна зависеть от того, какой именно поток какую итерацию параллельного цикла выполнит. Нельзя использовать побочный выход из параллельного цикла. Если вы будете следовать этим правилам, то у вас будет все хорошо. Формат параллельных циклов на языке C упрощенно можно представить следующим образом: непосредственно служебное слово for и в круглых скобках целочисленный тип, например переменная i, присвоить инвариант цикла, далее точка с запятой, переменная i и операции сравнения: меньше, больше, равно, меньше или равно и больше или равно. И дальше инвариант цикла: точка с запятой, i, плюс или минус, присваивание и, соответственно, инвариант цикла. Эти требования введены для того, чтобы OpenMP мог при входе в цикл точно определить число итераций и, соответственно, распределить их между потоками. Если директива параллельного выполнения стоит перед вложенными циклами, то директива действует только на самый внешний цикл. Итеративная переменная распределяемого цикла должна быть приватной. Если это не так и она является общей, то при входе в параллельный цикл, она будет сделана приватной. Соответственно, по выходу из данного цикла значение этой переменной будет не определено, если она не указана в опции lastprivate директивы for. Также у данной директивы есть следующие опции: private, firstprivate, reduction, schedule, collapse, ordered и nowait. С первыми тремя опциями вы уже знакомы. Давайте разберем остальные опции. В конце параллельного цикла происходит неявная барьерного синхронизация параллельно работающих потоков. Их дальнейшее выполнение происходит только тогда, когда все они достигнут данной точки. Если в данной задержке нет необходимости, то опция nowait позволяет потокам, уже выполнившим свои итерации, продолжить дальнейшее выполнение с оператора, непосредственно следующего за циклом, без синхронизации с остальными потоками. Другая опция — это опция ordered. Она говорит о том, что в цикле могут встречаться директивы ordered. С использованием директивы ordered определяются блок внутри тела цикла, который должен выполняться в том же порядке, в котором идут итерации в последовательном цикле. Я настоятельно рекомендую всячески избегать подобных ситуаций, так как это фактически делает вашу программу последовательной. Еще одна опция — это collapse. Данная опция указывает, что n последовательно тесновложенных циклов ассоциируется с данной директивой. В этом случае для циклов образуется общее пространство итераций, которое делится между потоками. И последняя опция, но она очень важная, — это опция schedule. Эта опция задает, каким образом итерации цикла распределяются между потоками. В опции schedule параметр type задает следующий тип распределения итераций. Первый тип — static. В этом случае происходит блочно-циклическое распределение итераций цикла. Размер блока задается с помощью значения chunk. Рассмотрим пример. В данном примере первый блок из шести итераций выполняет нулевой поток, второй блок из шести итераций — первый поток. И так далее до последнего потока. Затем распределение снова начинается с нулевого потока. Если значение chunk не указано, то все множество итераций делится на непрерывные куски примерно одинакового размера. Конкретный способ деления зависит от реализации. И полученные порции итераций распределяются между потоками. Второй тип — dynamic. В этом случае происходит динамическое распределение итераций с фиксированным размером блока. Возьмем тот же пример, но изменим тип на динамический. Тогда сначала каждый поток получит шесть итераций. Тот поток, который заканчивает выполнение своей порции итераций, получает первую свободную порцию из шести итераций. Освободившиеся потоки получают новые порции итераций. И до тех пор, пока все не будут исчерпаны. Последняя порция может содержать меньше итераций, чем все остальные. Следующий тип — это guided. В этом случае происходит тоже динамическое распределение итераций, но размер порций уменьшается с некоторого начального значения до величины chunk, пропорционально количеству еще не распределенных итераций, деленному на количеству потоков, выполняющих цикл. Размер первоначально выделяемого блока зависит опять же от реализации. В ряде случаев такое распределение позволяет аккуратнее разделить работу и, соответственно, сбалансировать загрузку потоков. Количество итераций в последней порции может оказаться меньше, чем значение chunk. В качестве типа распределения итераций можно также задать тип auto, в данном случае способ распределения итераций выбирается компилятором или системой выполнения. Параметр chunk при этом не задается. И тип runtime. Если задан тип runtime, то способ распределения итераций выбирается во время работы программы по значению переменной среды окружения OMP_SCHEDULE. Какой тип распределения использовать и какое значение для параметра chunk устанавливать, зависит от того, что вы вычисляете внутри цикла. Но нужно всегда стремиться, чтобы загрузка потоков работы была оптимальной. В этом случае вы достигните максимальной эффективности. Ну что же, мы рассмотрели директиву, которая позволяет распределить итерации цикла по потокам. Давайте теперь вернемся к примеру со сложением векторов. Мы создали параллельную область, и теперь нужно распределить работу между потоками. Вы уже обладаете всеми необходимыми знаниями для этого. Поэтому я прошу вас попытаться самостоятельно доделать эту программу. А затем сравнить время последовательной программы и параллельной. Исходные коды программы вы можете взять в дополнительных материалах к лекции. А в начале следующей лекции я покажу мой вариант параллельной программы. До встречи!
