Граф-схемное потоковое параллельное программирование (547873), страница 2
Текст из файла (страница 2)
Кроме того, в качестве формального параметра в списке параметровподпрограмме добавляется целочисленный параметр tag, который указывается первым. НаГС этот параметр не изображается, поскольку он выполняет роль идентификации данных,передаваемых между модулями ГСПП в процессе его выполнения.По соглашению, КГВх модуля изображаются на верхней линии его блочногопредставления, а КГВых – на нижней и отделяются друг от друга, как изображено на рис. 1.Также предполагается, что КГВх и КГВых и их входные и выходные точки однозначноидентифицируются своими номерами, присваемыми им в порядке изображения (слеванаправо).int float [] float []КГ Входов 1Назначение:Перемножение матрицintfloat []intКГ Входов 2Назначение:Вычисление определителя матрицыМодуль: Matrixfloat []КГ Входов 3Назначение: Построениеобратной матрицыНазначение: Матричные операцииКГ Выходов 1intfloat []Рис.1.
Графическое изображение модуляГрафическое изображение модуля, которое обязательно сопровождаетсяприписыванием ему имени, также может нести дополнительную информацию, носящуюхарактер комментариев, раскрывающих назначение модуля, назначение подпрограмм,сопоставляемых его КГВх и др. Так, модуль, представленный на рис.1, предназначен длявыполнения операций над вещественными квадратными матрицами, размерность которыхзадается целочисленным параметром; результат вычисления передается на КГВых 1.ГС представляет блочную структуру, построенную из модулей путем соединениявыходов КГВых модуля с входами КГВх другого или этого же модуля, причем типысоединяемых входов и выходов должны совпадать.
В интерпретации такое соединениеназывается информационной связью (ИС), по которой данные соответствующего типапередаются от одного модуля к другому.Возможны связи «один ко многим» и «многие к одному» (см. рис. 2). Первоеозначает, что данные передаются одновременно с выхода модуля на все входы, с которымион связан, а второе – что данные на вход могут поступать с любого из выходов, с которымион связан.(A)(Б)Module_2Module_1Module_1Module_3Module_2Module_3Рис.2. Примеры связей «один ко многим» (А) и «многие к одному» (Б)Для того чтобы связи не перегружали изображаемые ГС, допускается группироватьвходы КГВх и выходы КГВых, соединяя их общей горизонтальной линией, а связи междутакими объединениями соединять одной «обобщенной» ИС при условии, что все связимежду входами и выходами таких групп однозначно могут быть восстановлены (см.
рис. 3).4Различаются межмодульные и свободные (установочные) связи. Последниепозволяют перед выполнением ГСПП задать на соответствующих входах модулей начальныезначения. На рис. 3 у модуля изображены две установочные связи.float int char boolchar int int bool intModule_1Рис.
3. Пример свободной ИСДопускается, что у КГВх модуля может не быть входов. В этом случае подпрограмма,сопоставленная этой КГВх, является подпрограммой без параметров и она начинаетвыполняться вместе с началом выполнения ГСПП и работает как генератор данных,считываемых с некоторого носителя или вырабатываемых подпрограммой самостоятельно(см.
п. 1.3).Забегая вперед, заметим, что в операционной семантике ЯГСПП ИС при выполненииГСПП однозначно сопоставляются буферы, в которых хранятся асинхронно поступающие навходы КГВх модуля данные (фактические параметры соответствующих подпрограмм),которые «вырабатываются» подпрограммами модулей предшественников и направляются навыходы КГВых модуля. При этом механизм тегирования данных (приписывания тегаданным) позволяет обеспечивать однозначность отношения «входные данные – результат»при параллельном выполнении ГСПП (см. п. 1.3)Важным элементом структурирования ГСПП является понятие подсхемы. Понятиеподсхемы в ЯГСПП даёт программисту эффективные средства структуризациипараллельного алгоритма, выражающиеся через его схему, возможность представления ГС ввиде нескольких уровней, отражающих шаги декомпозиции исходной задачи на подзадачипри построении параллельной программы. Графически подсхема строится аналогично схемеи содержательно представляет самостоятельный фрагмент ГСПП, подставляемый вместоодного или нескольких модулей подсхемы более высокого уровня в иерархии «схема –подсхема».На рис.4 приведен пример двухуровневого вложения «схема – подсхема».ВизуальнаяграфическаяразработкаГСППподдерживаетсяспециальноразработанными программными средствами (см.
раздел 2). Примеры программ на ЯГСППприведены в приложении 1.scheme: test1 level: 0А)boolModule_1bool boolchar int boolintintModule_2floatcharboolsubst.sub_1charfloatcharModule_35subscheme: sub1 level: 1subscheme: sub2 level: 2Б)В)charboolbool stringModule_1bool charfloatint bool charboolModule_1char boolstringstringstringchar boolstringsubst.sub_2boolcharfloatModule_3boolboolModule_2boolboolModule_2charboolboolModule_4boolРис.4. Организационная структура ГСА) Основная схема; Б) подсхема sub1; В) подсхема sub2 подсхемы sub1Подстановочный модуль на схеме снабжается описателем subst, за которым после разделителя (точки) записывается имя подставляемой подсхемы.
По соглашению подсхема имеет один начальный модуль с той же самойструктурой и типами входов, что и у подстановочного модуля, и один конечный модуль, структура и типы выходов которого совпадают со структурой и типами выходов подстановочного модуля.1.2 Текстовое представление ГСППГСПП в текстовом представлении есть набор XML – файлов, иерархическиописывающие структуру ГС и ее интерпретацию.
Оно, возможно, окажется более удобнымдля опытного программиста, для человека, привыкшего иметь дело с XML. XML – форматтекстового представления выбран не случайно. Во – первых, XML являетсяобщепризнанным стандартом для описания иерархических конструкций, причем разработаномножество методов работы с ним, а во-вторых, внутреннее представление ГСПП хранитсятоже в формате XML, поэтому наиболее разумным будет и текстовое представлениеописывать в формате XML.Описание структуры ГС находится в отдельном XML-файле, в котором собраны всемодули ГС и связи между ними, а также для каждого модуля в отдельном (уже другом)XML-файле приводится его подробное описание, описание всех его КГВх, КГВых, а такжезадается интерпретация КГВх, т.е.
указание подпрограмм, сопоставленных с каждой КГВх.Если в ГС встречаются подсхемы, то их XML-представления строятся аналогично XMLописанию ГС. Ниже приведён DTD (Document Type Definition) всех XML-описаний ГСПП,который определяет синтаксис текстового представления ГСПП, приведён в приложении 2.Там же приведён пример текстового описания ГС, изображённой на рис. 4.1.3.Операционная параллельная семантика ЯГСПППараллельное выполнение ГСПП представляется как последовательность сменысостояний, каждое из которых характеризуется множеством процессов, индуцируемых привыполнении подпрограмм модулей ГСПП, сопоставляемых в интерпретации ихконъюнктивным группам входов.В потоковой модели вычислений предполагается, что любой имеющийсамостоятельное значение элемент обработки информации (фрагмент программы) впотоковой схеме запускается на выполнение при наличии данных на его входе, причемтолько после завершения начатого процесса он может быть запущен снова, если входнаяочередь данных к элементу не пуста (обычно обработка данных во входной очередивыполняется согласно дисциплине FIFO – первый поступивший обрабатывается первым).6Таким образом, множество процессов ГСПП в любом состоянии, следуя этой потоковойсхеме ее выполнения, не превосходит суммарного количества КГВх всех модулей ГСПП.В модели параллельного выполнения ГСПП реализуются три вида параллелизма:− пространственный, являющийся следствием информационной независимостимодулей ГСПП и, как следствие, процессов выполнения подпрограмм,сопоставляемых их КГВх,− потоковый, о котором сказано выше,− параллелизм множества данных (SIMD – один поток команд, множество потоковданных), т.е.
тот случай параллелизма, когда одна и та же программа модуляодновременно выполняется для разных данных на ее входе.Для того, чтобы обеспечить однозначность между входными и выходнымизначениями при параллельном выполнении ГСПП, используется механизм тегирования. Воперационной семантике языка ГСПП это выражается в том, что при наличии на всех входах(во входных буферах в реализации) конъюнктивной группы входов модуля данных,помеченных соответствующими тегами, параллельно запускаются на выполнение несколькопроцессов, каждый из которых однозначно идентифицируется тегом и сопоставленными емуданными. При передаче результатов от одного модуля к другому теги наследуются, позволяяразделять истории обработки различных данных при параллельном выполнении ГСПП.Перейдем к описанию процесса выполнения ГСПП.1.
Модуль ГСПП считается готовым для выполнения по любой из своих КГВх, еслина всех входах этой КГВх (в соответствующих входам буферах) есть данные, помеченныеодним и тем же тегом.Предполагается, что готовность модулей для выполнения определяется (втеоретическом плане) неким оракулом, который периодически просматривает данные всехКГВх всех модулей и определяет их готовность для выполнения. Практически в реализации(см. раздел 3) программы обслуживания буферов, входящие в состав программногообеспечения для управления параллельным выполнением ГСПП, при каждой записи вбуферы соответствующих КГВх модулей проверяют в них наличие данных с одним и тем жетегом на всех входах КГВх. Если это условие выполняется, индуцируется процесс ссоставным именем <имя модуля>.<номер КГВх>.<имя подпрограммы>.<идентификатортега>, предполагающий применение подпрограммы указанной в этом составном имени, кданным с указанным тегом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
