2006 Ответы на экзаменационные вопросы по ПОД (Lilalbrother), страница 15

Как только P0 выполнит директиву END CRITICAL, одна из заблокированных навходе нитей войдет в секцию. Если на входе в критическую секцию стояло нескольконитей, то случайным образом выбирается одна из них, а остальные заблокированные нитипродолжают ожидание. Все неименованные критические секции условно ассоциируются содним и тем же именем.Частым случаем использования критических секций на практике являетсяобновление общих переменных. Например, если переменная SUM является общей иоператор вида SUM=SUM+Expr находится в параллельной секции программы, то приодновременном выполнении данного оператора несколькими нитями можно получитьнекорректный результат.

Чтобы избежать такой ситуации можно воспользоватьсямеханизмом критических секций или специально предусмотренной для таких случаевдирективой ATOMIC:!$OMP ATOMICSUM=SUM+Expr .Данная директива относится к идущему непосредственно за ней оператору,гарантируя корректную работу с общей переменной, стоящей в левой части оператораприсваивания.Поскольку в современных параллельных вычислительных системах может использоватьсясложная структура и иерархия памяти, пользователь должен иметь гарантии того, что внеобходимые ему моменты времени каждая нить будет видеть единый согласованныйобраз памяти. Именно для этих целей и предназначена директива!$OMP FLUSH [ список_переменных ].Выполнение данной директивы предполагает, что значения всех переменных,временно хранящиеся в регистрах, будут занесены в основную память, все измененияпеременных, сделанные нитями во время их работы, станут видимы остальным нитям,если какая-то информация хранится в буферах вывода, то буферы будут сброшены и т.п.Поскольку выполнение данной директивы в полном объеме может повлечь значительныхнакладных расходов, а в данный момент нужна гарантия согласованного представления невсех, а лишь отдельных переменных, то эти переменные можно явно перечислить вдирективе списком.42.

Графовые модели программ, их взаимосвязь. Граф алгоритма. Критический путьграфа алгоритма.Рассмотрим 4 основные Графовые модели программ: граф управления программы (ГУ),информационный граф программы (ИГ), операционная история (ОИ), информационнаяистория (ИИ).Пример:1 y=b1-a12 x=y3 DO i = 2, n4x = (bi – ci*x)/ai5if (x<y) goto 76y=x7 END DOГраф управления. Каждому оператору исходной программы поставим всоответствие вершину графа — экземпляр преобразователя или распознавателя взависимости от типа оператора. Получим множество вершин, между которыми согласноисходной программе определим отношение, соответствующее передаче управления.

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

Две вершины соединиминформационной дугой, если между какими-нибудь срабатываниями соответствующихоператоров теоретически возможна информационная связь. Информационный граф независит от входных данных. В нем могут быть "лишние" дуги, которые не реализуютсялибо при конкретных входных данных, либо совместно с другими дугами.Операционная история. Теперь предположим, что каким-то образом мыопределили начальные данные программы и наблюдаем за ее выполнением на обычномпоследовательном вычислителе. Каждое срабатывание каждого оператора (а оно необязательно будет единственным) будем фиксировать отдельной вершиной.

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

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

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

Тогда проведем дугу из вершины и в вершину у. Еслисоответствующие операции могут выполняться независимо друг от друга, дугу проводитьне будем. В случае, когда аргументом операции является начальное данное или результатоперации нигде не используется, возможны различные договоренности. Например, можносчитать, что соответствующие дуги отсутствуют.

Мы будем поступать в зависимости отобстоятельств. Построенный таким образом граф будем называть графом алгоритма.Независимо от способа построения ориентированного графа, те его вершины, которые неимеют ни одной входящей или выходящей дуги, будем называть соответственновходными или выходными вершинами графа.43. Пространство итераций, стандартная линейная форма, линейный класспрограмм.Для нормализованного циклаfor (i=1;…)for(j=1;…)for(k=1;…) T(i,j,k) – тело циклаПространство итерацийСтандартная линейная форма (a,I) + (b,N) + b0Исследуем линейные многогранники: (a,I)+b0<=0, где I=(i,j,k)Параметры цикла – переменные n1, n2 - внешние переменные(a,I)+(b,N)+b0<=0(a,I)+(b,N)+b0 - стандартная линейная формаПрограмма относится к линейному классу программ, если удовлетворяет следующимусловиям:* в программе может использоваться любое число простых переменных и переменных синдексами;* единственным типом исполнительного оператора может быть оператор присваивания,правая часть которого есть арифметическое выражение; допускается любое число такихоператоров;* все повторяющиеся операции описываются только с помощью стандартного цикла for;* допускается использование любого числа условных и безусловных операторовперехода, передающих управление "вниз" по тексту; не допускается использованиепобочных выходов из циклов;* все индексные выражения переменных, границы изменения параметров циклов иусловия передачи управления задаются, в общем случае, неоднородными формами,линейными как по параметрам циклов, так и по внешним переменным программы; всекоэффициенты линейных форм являются целыми числами;* внешние переменные программы всегда целочисленные, и вектора их значенийпринадлежат некоторым целочисленным многогранникам; конкретные значения внешнихпеременных известны только перед началом работы программы и неизвестны в момент ееисследования.44.

Теорема о построении графа алгоритма для линейного класса программ.Теорема (о возможности построения графа алгоритма)Если фрагмент программы принадлежит линейному классу, то для него возможнопостроение графа алгоритма: (N, Δ(N), F(N,Δ))k, гдеN – линейный многогранник в пространстве внешних переменных (непустой)Δ(N) ≠ 0 – линейный многогранник в пространстве итерацийF(N,Δ) – векторная функция, описывающая дуги для вершин из Δ(N); онаописывает координаты поставщика информации для текущей операции.45. Эквивалентные преобразования программ. Преобразования циклов(перестановка, распределение).У эквивалентных программ должны быть изоморфные графы алгоритмов.Перестановка циклов.for (i=0; i<n; i++)for (j=0; j<n; j++)for (j=0;j<n;j++)for (i=0;i<n;i++)a[i,j]=a[i,j]+a[i,j-1]a[i,j]=a[i,j]+a[i,j-1]Данные циклы эквивалентны с точки зрения конечного результатаРаспределение циклов.for (i=0,i<n;++i) {for (i=0,i<n;++i)a[i]=a[i-1]+b;a[i]=a[i-1]+b;c[i]=a[i]+c[i]+e;for (i=0,i<n;++i)}c[i]=a[i]+c[i]+e;46.

Виды параллелизма: конечный, массовый, координатный, скошенный.47. Ярусно-параллельная форма графа алгоритма, высота, ширина. КаноническаяЯПФ.Итак, каждое описание алгоритма порождает ориентированный ациклическиймультиграф. Верно и обратное. Если задан ориентированный ациклический мультиграф,то его всегда можно рассматривать как граф некоторого алгоритма. Для этого каждойвершине нужно поставить в соответствие любую однозначную операцию, имеющуюстолько аргументов, сколько дуг входит в вершину. Поэтому между алгоритмами ирассматриваемыми графами есть определенное взаимное соответствие.Утверждение 4.1Пусть задан ориентированный ациклический граф, имеющий n вершин.

Существует число s < n, для которого все вершины графа можно так пометить одним изиндексов 1, 2, ..., s, что если дуга из вершины с индексом i идет в вершину с индексом j, тоi<j.Выберем в графе любое число вершин, не имеющих предшествующих, и пометимих индексом 1. Удалим из графа помеченные вершины и инцидентные им дуги.Оставшийся граф также является ациклическим. Выберем в нем любое число вершин, неимеющих предшествующих, и пометим их индексом 2. Продолжая этот процесс, в концеконцов, исчерпаем весь граф.