Ответы к экзамену (2), страница 4

???Данные,15поступающие на входные точки модуля безусловного кортежа его входов, однозначносвязываются с кортежем входных параметров подпрограммы, сопоставляемой модулю винтерпретации(см. далее). По данным булевского типа, поступающим на условные входы модуля, определяетсянеобходимость применения сопоставленной ему подпрограммы к кортежу данных на безусловныхвходах модуля. Условием этого является значение “истина” на всех условных входах модуля.На рис.

1 приведено графическое изображение модуля с i_м количеством групп входов, у каждойиз них по два кортежа входных точек, один из которых представляет безусловные входы, адругой – условные.ГС в базисе M определяется в виде четверки 〈М', C, Pвх, Pвых〉. Здесь M' – конечноеподмножество модулей из M, C – функция-предикат, задающая связи между выходными ивходными точками модулей: C: OUT × IN → {0, 1}, где IN и OUT – множества всех входных ивыходных точекмодулей из M'. Для in ∈ IN и out ∈ OUT C(out, in) = 1, если существует связь между выходнойточкой out некоторого модуля ГС и входной точкой in другого (возможно, того же самого) модуля; впротивном случае C(out, in) = 0.В определении ГС Pвх ∈ IN* и Рвых ∈ OUT*, обозначают кортежи входных (безусловных) ивыходных (безусловных) точек ГС.

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

Если на пересечении связей точкаотсутствует, они считаются различными.1.2. И н т е р п р е т а ц и я Г С. В интерпретации каждому кортежу безусловных входов каждойгруппы входов каждого модуля ГС сопоставляется подпрограмма на одном из последовательныхязыков программирования (C, C++, ФОРТРАН и др.), причем для описания разных подпрограмммогут использоваться различные языки, в том числе с возможностью задания параллелизма в нихдругими средствами, например, используя MULTITHREADING.

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

Тегирование позволяет устанавливатьоднозначное соответствие между входными данными, генерируемыми в общем случае в видепотоков, и результатами применения к ним ГСПП при одновременном асинхронном выполнениимножества копий подпрограмм различных модулей ГСПП. С этой целью заголовок подпрограммыимеет вид P(integer: tag; t1: x1, t2: x2, …, tm: xm), и переменной tag при инициализациивыполнения подпрограммы присваивается тег, которым были снабжены данные, поступившие набезусловные входы соответствующей этой подпрограмме группы входов модуля. При этом кортеж16входных точек этой группы входных точек модуля и кортеж формальных параметровподпрограммы x1, x2, …, xm с указанными в заголовке их типами имеют одинаковую длину имежду нимиустанавливается поэлементное взаимно однозначное соответствие в порядке перечисленияэлементов кортежей.

Для большей информативности входные точки модуля ГС могутсопровождаться указанием типов поступающих на них данных. При этом типы выходных точексовпадаютс типами связанных с ними входных точек модуля.Модель выполнения ГСПП (см. разд. 3) предполагает возможность одновременного применениякопий подпрограммы любого модуля ко всем кортежам поступивших одинаково тегированныхданных при условии наличия значений истина на всех условных входах модуля с тем же тегом,что и у данных на безусловных входах (фактических параметрах подпрограммы). Для реализациипередачи тегированных данных между модулями ГСПП при ее выполнении, а также дляуправления из подпрограммы модуля потоком входных данных в ЯГСПП введены системныекоманды.Команда WRITE (tag, (номер выхода, переменная), (номер выхода, переменная), …, (номервыхода, переменная)) передает при выполнении подпрограммы на указанные выходы модулязначения, присвоенные указанным переменным, с тегом, присвоенным переменной tag.Команда READ 1 (группа входов, tag, (номер входа, переменная), (номер входа, переменная), …,(номер входа, переменная)) позволяет “прочитать” поступившие на входы группы входов моду_ля данные с тегом tag, присваивая их соответствующим переменным.

Если данные не поступили,выполнение команды READ1 задерживается до момента поступления запрашиваемых данных.Команда READ2 (группа входов, tag, переменная 1, (номер входа, переменная), (номер входа,переменная), …, (номер входа, переменная)) дает возможность подпрограмме проверить посту_пили или нет на входы указанной группы входов модуля данные с тегом tag. При этом, еслиданные поступили, они присваиваются перечисленным в команде переменным и управление воз_вращается подпрограмме. В противном случае переменной “переменная!" присваиваетсязначение ложь (0) и управление возвращается подпрограмме.Команда SAVE ((tag, переменная), (tag, переменная), …, (tag, переменная)) используется дляпередачи управлению результатов выполнения ГСПП, снабжая каждую переменную,идентифицирующую результат, соответствующим тегом.Еще одна системная команда STOP (имя ГСПП, имя модуля) предназначена для контролязавершения ГСПП. Параметры “имя ГСПП”, “имя модуля” позволяют управлению определитьокончание выполнения ГСПП и ссылку на завершающий модуль.Для инициализации ГСПП в реализации языка применяется команда ЕХЕСиТЕ(имя ГСПП,адрес хранения, имя модуля: (вход, (tag, значение), …, (tag, значение)); имя модуля: (вход, (tag,значение), …, (tag, значение)), …, имя модуля: (вход, (tag, значение), …, (tag, значение))).

Здесьпара (вход, (tag, значение)) указывает, на какой вход модуля при инициализации ГСПП должнобыть передано значение с тегом tag.17Завершение выполнения ГСПП контролируется либо по команде STOP, либо по условиюзавершения всех инициализированных подпрограмм модулей и отсутствию готовых длявыполнения новых процессов. Важно отметить, что после выполнения команд WRITE и READ2управление сразу возвращается к следующей за ними команде подпрограммы.

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

В этом случае, выполняя команды READ1 или READ2 с нулевымтегом, управление присваивает переменной tag в списке параметров подпрограммы значениетега считываемого кортежа данных. Таким образом, выполняя команды READ1 и READ2,подпрограмма получает необходимую информацию о данных, к которым она применяется.В заключение отметим, что в реализации ЯГСПП, в частности, созданной среде проектирования,анализа и оптимизации ГСПП [8, 9], ее модули могут снабжаться описательной информацией,касающейся задания типов данных на входах и выходах модулей ГС, особенностей подпрограмммодулей, в частности, используемых в них методов, их вычислительной сложности, применяемогоязыка программирования для описания подпрограмм и т.п.Пример граф-схемной программыРассмотрим пример построения следующей последовательной подпрограммы:beginreal array x, y[l–n];integer n;for i = 1 step 1 until n dobeginx[i] = считать i_e данное(имя носителя, имя файла);y[i] = F(x[i]);print (y[i]);endend,где F(x) = if p(x) then f(x) else F(g(f1(x), f2(x))).Здесь команда “считать” считывает по очереди элементы массива, хранящиеся в виде файла науказанном носителе.На рис.

2 приведена ГС, а ниже дана интерпретация для модулей ГСПП, построенной дляэтой последовательной программы и названной G.18Интерпретация:I(ri): subprogram Sr1(integer tag, n) //при инициализации ГСПП на вход модуля r1real array x[i–n]; real у; //задается значение п с нулевым тегом.beginWRITE(tag, (1, n));for i = 1 step 1 until n dobeginx[i] = считать i_e данное (имя носителя, имя файла);WRITER (2, x[i]));endendend,I(f): subprogram Sf (integer tag, real x)real y;beginy = f(x);WRITE (tag,(1, y));endend,I(p): subprogram Sp (integer tag, real x)integer t1, t2;begint1 = l; t2 = 0;if p(x) then WRITE(tag, (1, t1), (2, t2)) else WRITE(tag, (1, t2), (2, t1));endend,I(f1): subprogram Sf1 (integer tag, real x)beginx = f1(x);WRITE (tag, (1, x));endend,19I(f2): subprogram Sf2 (integer tag, real x)beginx = f2(x);WRITE(tag, (1, x));endend,I(g): subprogram Sg (integer tag, real x1, x2)real y;beginy = g(x1, x2);WRITE(tag, (1, y));endend,I(g1): subprogram Sg1 (integer tag, real x)beginWRITE(tag, (1, x));endendI(g2): subprogram Sg2 (integer tag, real x)beginWRITE(tag, (2, x));endend,I(r2): subprogram Sr2(integer tag, n, real x)beginSAVE(tag, x);for i = 1 step 1 until n_1 dobeginREADl(0, (2, x));SAVE(tag, x);endSTOP(G, r2);endend.Сделаем краткие пояснения для данной ГСПП.

Во-первых, в ней мы попытались полностьювыразить существующий в исходной последовательной программе параллелизм: пространственный(возможность одновременного выполнения функций f, p, f1 и f2) и потоковый, вытекающийиз возможности независимого вычисления элементов y[i] нового массива. Кроме того, в ГСППзначения функций f, f1, и f2 вычисляются подпрограммами соответствующих модулей с упреждением, темсамым увеличивая параллелизм программы.

Поскольку элементы y[i] поступают навход 2 модуля r2 в общем случае в произвольном порядке, запоминаемые командой SAVE значения можнозатем упорядочить, используя теги согласно принятому порядку хранения в памятиэлементов массива.В качестве параметра подпрограммы модуля r1, который должен задать с помощью командыEXECUTE программист перед выполнением ГСПП, используется целочисленная переменная n –размер массива.

Задаваемое значение тега у этой переменной равно 0. Поэтому в подпрограммемодуля r2 перед его первым выполнением в качестве входных параметров применяется значениеn с нулевым тегом и поступившее первым на его вход 2 значение x с произвольным тегом.У повторяющейся команды READ1 в подпрограмме модуля r2 нулевое значение тега позволяетсчитывать со входа 2 поступающие данные с произвольным тегом, обеспечивая таким образомбольшую асинхронность и параллелизм при выполнении ГСПП.

Отметим, что данная ГСПП неимеет выходов, а ее окончание контролируется командой STOP в подпрограмме модуля r2.207. Средства параллельного программирования MPI, планированиевыполнения MPI программ. Сравнение с другими языками и средствамипараллельного программирования (MULTITHREADING, ЯГСПП (см.вопрос 6), и др.)Message Passing Interface (MPI, интерфейс передачи сообщений) — программный интерфейс (API) дляпередачи информации, который позволяет обмениваться сообщениями между процессами, выполняющимиодну задачу. Разработан Уильямом Гроуппом, Эвином Ласком (англ.) и другими.MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельномпрограммировании, существуют его реализации для большого числа компьютерных платформ.Используется при разработке программ для кластеров и суперкомпьютеров.