лекции (OpenMP), страница 3

В этом случаемодификация x и модификация y потенциально причинно зависимы,так как новое значение y могло зависеть от прочитанного значенияпеременной x. С другой стороны, если два процесса одновременноизменяют значения различных переменных, то между этими событияминет причинной связи.Операции, которые причинно не зависят друг от друга называютсяпараллельными.Причинная модель консистентности памяти определяется следующимусловием: Последовательность операций записи, которыепотенциально причинно зависимы, должна наблюдаться всемипроцессами системы одинаково, параллельные операции записи могутнаблюдаться разными процессами в разном порядке.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.12 из 36Причинная консистентностьP1W(x)aP2R(x)aW(x)bP3R(x)bR(x)aP4R(x)aR(x)bКорректнаяпоследовательностьдля моделипричиннойконсистентностиP1W(x)aНарушение моделипричиннойконсистентностиW(x)cP2R(x)aW(x)bP3R(x)aR(x)cR(x)bP4R(x)aR(x)bR(x)cОпределение потенциальной причинной зависимости может осуществлятьсякомпилятором посредством анализа зависимости операторов программы поданным.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.13 из 36PRAM (Pipelined RAM) и процессорная консистентностьPRAM: Операции записи, выполняемые одним процессором, видны всемостальным процессорам в том порядке, в каком они выполнялись, нооперации записи, выполняемые разными процессорами, могут бытьвидны в произвольном порядке.Записи выполняемые одним процессором могут быть конвейеризованы:выполнение операций с общей памятью можно начинать не дожидаясьзавершения предыдущих операций записи в память.Процессорная: PRAM + когерентность памяти.

Для каждой переменнойX есть общее согласие относительно порядка, в котором процессорымодифицируют эту переменную, операции записи в разные переменные параллельны. Таким образом, к упорядочиванию записей каждогопроцессора добавляется упорядочивание записей в переменные илигруппы.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.14 из 36Слабая консистентность (weak consistency)Пусть процесс в критической секции циклически читает и записываетзначение некоторых переменных. Даже, если остальные процессорыи не пытаются обращаться к этим переменным до выхода первогопроцесса из критической секции, для удовлетворения требованийрассматриваемых ранее моделей консистентности они должнывидеть все записи первого процессора в порядке их выполнения, что,естественно, совершенно не нужно.Наилучшее решение в такой ситуации - это позволить первомупроцессу завершить выполнение критической секции и, только послеэтого, переслать остальным процессам значения модифицированныхпеременных, не заботясь о пересылке промежуточных результатов.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.15 из 36Слабая консистентность (weak consistency)Модель слабой консистентности, основана на выделении средипеременных специальных синхронизационных переменных иописывается следующими правилами:1.Доступ к синхронизационным переменным определяется модельюпоследовательной консистентности;2.Доступ к синхронизационным переменным запрещен(задерживается), пока не выполнены все предыдущие операциизаписи;3.Доступ к данным (запись, чтение) запрещен, пока не выполнены всепредыдущие обращения к синхронизационным переменным.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.16 из 36Слабая консистентность (weak consistency)Первое правило определяет, что все процессы видят обращения ксинхронизационным переменным в определенном (одном и том же)порядке.Второе правило гарантирует, что выполнение процессором операцииобращения к синхронизационной переменной возможно только послевыталкивания конвейера (полного завершения выполнения на всехпроцессорах всех предыдущих операций записи переменных,выданных данным процессором).Третье правило определяет, что при обращении к обычным (несинхронизационным) переменным на чтение или запись, всепредыдущие обращения к синхронизационным переменным должныбыть выполнены полностью.

Выполнив синхронизацию передобращением к общей переменной, процесс может быть уверен, чтополучит правильное значение этой переменной.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.17 из 36Слабая консистентность (weak consistency)P1W(x)aW(x)bSP2R(x)aR(x)bP3R(x)bSНедопустимаяпоследовательностьсобытийМосква, 2015 г.P1W(x)aW(x)bДопустимаяпоследовательность событийSSP2Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.SR(x)a18 из 36Консистентность по выходу1.2.В системе со слабой консистентностью возникает проблема приобращении к синхронизационной переменной: система не имеетинформации о цели этого обращения - или процесс завершилмодификацию общей переменной, или готовится прочитать значениеобщей переменной.Для более эффективной реализации модели консистентности системадолжна различать две ситуации: вход в критическую секцию и выход изнее.В модели консистентности по выходу введены специальные функцииобращения к синхронизационным переменным:ACQUIRE - захват синхронизационной переменной, информируетсистему о входе в критическую секцию;RELEASE - освобождение синхронизационной переменной, определяетзавершение критической секции.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.19 из 36Консистентность по выходуСледующие правила определяют требования к модели консистентности повыходу:До выполнения обращения к общей переменной, должны бытьполностью выполнены все предыдущие захваты синхронизационныхпеременных данным процессором.Перед освобождением синхронизационной переменной должны бытьзакончены все операции чтения/записи, выполнявшиеся процессоромпрежде.Реализация операций захвата и освобождения синхронизационнойпеременной должны удовлетворять требованиям процессорнойконсистентности (последовательная консистентность не требуется).P1Acq(L)P2W(x)aW(x)bRel(L)Acq(L)R(x)bP3Rel(L)R(x)aМосква, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.20 из 36Модель памяти в OpenMP001Нить001Нить001НитьМосква, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.21 из 36Модель памяти в OpenMP… = i + 3;statici =int1 i = 0;#pragma omp flush (i)i=1#pragma omp flush (i)i =ii =i=+011;Нить001 1Нить001 0… = i + 2; // ?Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.22 из 36Консистентность памяти в OpenMPКорректная последовательность работы нитей с переменной:Нить0 записывает значение переменной - write(var)Нить0 выполняет операцию синхронизации – flush (var)Нить1 выполняет операцию синхронизации – flush (var)Нить1 читает значение переменной – read (var)Директива flush:#pragma omp flush [(list)] - для Си!$omp flush [(list)] - для ФортранМосква, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.23 из 36Консистентность памяти в OpenMP1.2.3.Если пересечение множеств переменных, указанных в операциях flush,выполняемых различными нитями не пустое, то результат выполненияопераций flush будет таким, как если бы эти операции выполнялись внекоторой последовательности (единой для всех нитей).Если пересечение множеств переменных, указанных в операциях flush,выполняемых одной нитью не пустое, то результат выполнения операцийflush, будет таким, как если бы эти операции выполнялись в порядкеопределяемом программой.Если пересечение множеств переменных, указанных в операциях flush,пустое, то операции flush могут выполняться независимо (в любомпорядке).Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.24 из 36Консистентность памяти в OpenMP#pragma omp flush [(список переменных)]По умолчанию все переменные приводятся в консистентное состояние (#pragmaomp flush):при барьерной синхронизации;при входе и выходе из конструкций parallel, critical и ordered;при выходе из конструкций распределения работ (for, single,sections, workshare), если не указана клауза nowait;при вызове omp_set_lock и omp_unset_lock;при вызове omp_test_lock, omp_set_nest_lock,omp_unset_nest_lock и omp_test_nest_lock, если изменилосьсостояние семафора.При входе и выходе из конструкции atomic выполняется #pragma omp flush(x),где x – переменная, изменяемая в конструкции atomic.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.25 из 36Классы переменныхВ модели программирования с разделяемой памятью:• Большинство переменных по умолчанию считаются SHAREDГлобальные переменные совместно используются всеми нитями(shared)• Фортран: COMMON блоки, SAVE переменные, MODULEпеременные• Си: file scope, static• Динамически выделяемая память (ALLOCATE, malloc, new)Но не все переменные являются разделяемыми ...• Стековые переменные в подпрограммах (функциях),вызываемых из параллельного региона, являются private.• Переменные, объявленные внутри блока операторовпараллельного региона являются приватными.• Счетчики циклов, витки которых распределяются междунитями при помощи конструкций for и parallel for.Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.26 из 36Классы переменныхdouble Array1[N];extern double Array1[N];int main() {void work(int *Array, int i) {int Array2[N],i;double TempArray[10];#pragma omp parallelstatic int count;{...int iam = omp_get_thread_num();#pragma omp for}for (i=0;i < N; i++)TempArray, iam, iwork(Array2, i);}Array1, Array2,}TempArray,Array1, Array2,countiam, icountTempArray,iam, iМосква, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.27 из 36Классы переменныхМожно изменить класс переменной при помощи конструкций: shared (список переменных) private (список переменных) firstprivate (список переменных) lastprivate (список переменных) threadprivate (список переменных) default (private | shared | none)Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.28 из 36Конструкция privateКонструкция «private(var)» создает локальную копию переменной«var» в каждой из нитей.• Значение переменной не инициализировано• Приватная копия не связана с оригинальной переменной• В OpenMP 2.5 значение переменной «var» не определено послезавершения параллельной конструкцииsum = -1.0;#pragma omp parallel for private (i,j,sum)for (i=0; i< m; i++){sum = 0.0;for (j=0; j< n; j++)sum +=b[i][j]*c[j];a[i] = sum;}Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.29 из 36Конструкция firstprivate«firstprivate» является специальным случаем «private».• Инициализирует каждую приватную копию соответствующимзначением из главной (master) нити.BOOL FirstTime=TRUE;#pragma omp parallel for firstprivate(FirstTime)for (row=0; row<height; row++){if (FirstTime == TRUE) { FirstTime = FALSE; FirstWork (row); }AnotherWork (row);}Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.30 из 36Конструкция lastprivatelastprivate передает значение приватной переменной, посчитанной напоследней итерации в глобальную переменную.int i;#pragma omp parallel{#pragma omp for lastprivate(i)for (i=0; i<n-1; i++)a[i] = b[i] + b[i+1];}a[i]=b[i]; /*i == n-1*/Москва, 2015 г.Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.31 из 36Конструкция threadprivateОтличается от применения конструкции private:– с private глобальные переменные маскируются– threadprivate переменные сохраняют глобальную областьвидимости внутри каждой нити#pragma omp threadprivate (Var)Если количество нитейVar = 1Var = 2Москва, 2015 г.… = Varне изменилось, токаждая нить получитзначение, посчитанноев предыдущейпараллельной области.… = VarПараллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.32 из 36Конструкция defaultМеняет класс переменной по умолчанию: default (shared) – действует по умолчанию default (private) – есть только в Fortran default (firstprivate) – есть только в Fortran OpenMP 3.1 default (none) – требует определить класс для каждой переменнойitotal = 100;#pragma omp parallelprivate(np,each){np = omp_get_num_threads();each = itotal/np;………}Москва, 2015 г.itotal = 100;#pragma omp parallel default(none)private(np,each) shared (itotal){np = omp_get_num_threads();each = itotal/np;………}Параллельное программирование с OpenMP: OpenMP - модельпараллелизма по управлению © Бахтин В.А.33 из 36Литература…http://www.openmp.org Распределенные системы.