Граф-схемное потоковое параллельное программирование (Граф-схемное потоковое параллельное программирование 2), страница 5

п.1.3 - описание операционнойсемантики языка). Блок УП выполняет также команды KILL – “уничтожения” процессов,выполнение которых было инициировано с упреждением и на некотором шаге выполнениякоторых обнаруживается, что их результаты не будут использованы.Блоки, реализующие эти действия, образуют интерпретатор ЯГСПП (рис. 8).3.2.1 Описание работы интерпретатора ГСППКак было сказано в описании инструментальной среды, при разработке ГСППстроится ее внутреннее представление (см. рисунок 8), которое, с одной стороны, являетсямостом между ее графическим и текстовым представлением, а, с другой стороны, служитисходной информацией о ГСПП для интерпретатора.Перед началом выполнения ГСПП это внутреннее представление сначалаинициализируется пользователем через обращение к блоку инициализации ИН путемзадания значений признаков (признаки обозначены на рис.

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

должна ли вместо него подставляться подсхема, и если да, тозаполняется указатель Y на описание этой подсхемы (аналогично для описания модулейподсхемы). В описании входов КГВх модуля этот признак показывает, является ли входустановочным или нет. В описаниях КГВых модуля в таблице приемников выходов КГВых13модулей этот признак указывает, находится ли буфер, сопоставленный КГВх, на том жекомпьютере, начальное размещение на котором указал пользователь, или на другомкомпьютере, идентификатор которого указан в соответствующих полях описаний входовКГВх и приемников выходов КГВых. Это упрощает выполнение команд чтения из буфернойпамяти и записи в нее (команд READ, WRITE и OUT), а также команды CHECK (проверкиданных в буфере), которые “возникают” при выполнении подпрограмм модулей.YИмя ГСППОписание модулей ГСППYИмямодуляПКоличеств КоличествоYо КГВхКГВыхYВход 1П......Вход n ПтипВыход 1...YВыход mДанные на входе nТегСсылка наданные......ТегСсылка наданныеПКоличеств КоличествоYо КГВхКГВыхтип...типДанные на входе 1Ссылка наданные......ТегСсылка наданныеYК описаниюприемников входа mYК описаниюподсхемыК описаниюКГВыхподсхемыY...YК описаниюКГВхподсхемыКол-воYвыходовТег...ИмямодуляОписание выходов КГВых...типОписаниеКГВыхмодуляНомерКГВыхY...П - признакУ - указательИдент.

К - идентиф. компьютераОписаниеподсхемИмяYсхемыОписание КГВх модуляНомер Кол-во "Путь" к П Y Идент.ККГВх входов подпр-меОписание входов КГВхYОписание приемниковвыхода 1ИмямодуляНомерКГВхНомервходаПИдент. К...............ИмямодуляНомерКГВхНомервходаПИдент.

КБуферная память для КГВхРис. 9. Внутреннее представление ГСПППроцесс инициализации выполнения ГСПП осуществляется через блок ИНзаполнением указанных полей внутреннего представления ГСПП значениями, заданнымипользователем, загрузкой его на все компьютеры кластера вместе с блоками управленияпроцессного уровня, выделения начальной памяти для буферов, сопоставляемых КГВхмодулей, и занесения в них данных, “присвоенных” пользователем установочным входаммодулей (см. рисунок 9). Итог всей этой работы – пользовательское приложение, готовое длявыполнения на соответствующем компьютере кластера под управлением его ОС.Рассмотрим более подробно функции блоков управления буферами (УБ) ипроцессами (УП) интерпретатора ГСПП.Блок УБ выполняет следующие функции:− организацию буферов для КГВх, включая формирование запросов к ОС навыделение памяти, ее “чистка” в связи с частичным освобождением при чтенииданных,− выполнение команд чтения, записи или проверки состояния буферной памяти,− определение и идентификацию готовых для выполнения процессов.В начале выполнения ГСПП готовыми для выполнения являются все процессы –подпрограммы, в буферной памяти которых, то есть на всех входах соответствующих имКГВх, есть данные, помеченные одним и тем же тегом (все фактические параметрыподпрограммы).

Начальный запрос на наличие таких процессов (на каждом компьютерекластера) определяется блоком УП путем обращения к блоку УБ. В дальнейшем всякаякоманда записи в буферы (команды WRITE и OUT), которая возникает при выполнении14процесса на компьютере, вызывает обращение к блоку УП, который переадресует ее блокуУБ, если указанные в ней выходы КГВых, на которые передаются данные, связаны с входамиКГВх, буферы которых размещены на данном компьютере (см.

рис. 9, описание выходовКГВых). При этом, выполняя команду записи в буферную память КГВх, блок УБодновременно проверяет в ней наличие на всех ее входах данных с одинаковым тегом. Еслиобнаруживается, что такие данные существуют, то блок УБ передает блоку УПидентификатор готового процесса вместе с тегом и фактическими параметрамиподпрограммы, сопоставленной КГВх. Формат этой информации о новом процессепредопределен выбранным внутренним представлением ГСПП (см. рис. 9, а также описаниеоперационной семантики ЯГСПП) и имеет вид: <имя модуля>:<номер КГВх>.<”путь” кподпрограмме>.<идентификатор тега>.<список фактических параметров>.Одновременно в буферной памяти, память, занятая этой информацией, переводится встатус освобожденной и может использоваться в дальнейшей работе.

Также блок УБ можетпри необходимости затребовать у ОС дополнительную память для хранения записываемых вбуферную память новых данных.На рис.10 и 11 приведены блок-схемы программ выполнения команд READ и WRITE(выполнение команды OUT аналогично выполнению команды WRITE за исключением того,что контекст процесса, в котором она возникает, после ее выполнения уничтожается изанятая им память освобождается).Напомним, что команды READ и WRITE имеют следующий формат заданияпараметров: READ(<номер КГВх>,<тег>,<список входов>,<список переменных>);WRITE(<номер КГВых>,<тег>,<список выходов>,<список переменных>).У команды READ в списке входов перечислены номера входов КГВх, в буфернойпамяти которой необходимо прочитать данные с этими номерами и указанным тегом.

Всписке переменных перечислены имена переменных, которым должны быть присвоенызначения, возвращенные в подпрограмму, в процессе выполнения которой команда READвстретилась.У команды WRITE в списке выходов перечислены выходы КГВых, на которыедолжны быть переданы значения, которые присвоены указанным переменным в процессевыполнения подпрограммы, в которой встретилась команда WRITE. По умолчанию,соответствие входов (выходов) и сопоставляемых им переменных определяется порядком иперечисления тех и других в соответствующих списках. Команда OUT имеет форматпараметров, совпадающий с командой READ.Команда READданетP1даP2нетПеревести команду READв задержанное состояниедо момента поступленияданных (определяетсяблоком УБ)Присвоить значения переменным(считывается из буфернойпамяти), указанным в командеREADВернуть управление (с присвоеннымизначениями переменных) вподпрограмму процесса, которыйиндуцировал команду READПо внутреннему представлению (см.

описаниеКГВх) определить компьютер, на которомнаходятся буферы указанной в команде READКГВхПереслать на этот компьютер (блоку УБ)команду READ для выполненияВыполнить команду READ и возвратитьрезультат ее выполнения (требуемыеданные) блоку УБ на компьютере, откоторого команда была полученаP1: проверка условия, находятся ли буферы КГВх, указанной в команде READ, на этом же компьютереP2: проверка условия, есть ли затребованные данные с указанным в команде READ тегом в буферной памятиРис.10. Блок-схема выполнения команды READ151. По внутреннему представлению (см.

описание выходов КГВых на рис. 9) определить номера КГВхмодулей и номера их входов, на которые командой WRITE передаются значения переменных,перечисленных в списке ее параметров. Перейти к пункту 2.2. Для каждой КГВх и номеров ее входов, на которые должны быть переданы параметры, сформировать“внутренние” команды WRITE1(<номер КГВх>,<тег>,[<значение>’→’<номер входа>]).

Перейти кпункту 3.3. Все сформированные в п.2 команды WRITE1 передать для выполнения блокам УБ на компьютеры, накоторых находятся буфера КГВх. Перейти к пункту 4.4. Завершить процесс выполнения команды WRITE после выполнения блоками УБ всех разосланныхкоманд WRITE1.Рис. 11. Последовательность шагов выполнения команды WRITEВ отличие от команд READ, WRITE и OUT команда CHECK(<номерКГВх>,<тег>,<список входов>,<переменная>) позволяет процессу проверить, есть вбуферной памяти данные с указанным тегом.

Возвращаемым процессу значением,присеваемым переменной в этой команде, является количество данных в буферной памяти сданным тегом.Блок управления процессами (УП) реализует следующие функции:− формирование списка готовых процессов (см. рис 12), в котором помимоидентифицирующей процесс информации и входных данных, необходимых дляобращения к соответствующей подпрограмме, “поддерживается” также дополнительнаяинформация (поле “характеристики”) о состоянии процесса, его приоритете, другиххарактеристиках (времени, затраченным процессом на выполнение и др.);− взаимодействие с ОС, управление выполнением “системных” команд WRITE, READ, OUTи CHECK, возникающих при выполнении процессов (см.

блок-схемы выполнения командWRITE и READ на рис. 10 и 11). Эти команды адресуются сначала блоку УП, которыйреализует их, используя блок УБ;− взаимодействие с блоком планирования (ПЛ);− при назначении процессов на выполнение на процессоре компьютера, с блоком обменаданными между компьютерами при выполнении команд READ и WRITE, если требуемыебуферы размещены на другом компьютере.3.2.2.

Планирование параллельных процессов и управление загрузкойкластераКак следует из п.п. 3.2, управление параллельным выполнением ГСПП на кластереусловно разделено на два уровня: системный и процессный.Схема на рис. 12 показывает, каким образом осуществляется управлениевыполнением ГСПП на процессном уровне.Блок УП вместе с блоком УБ формирует список готовых для выполнения процессов.В этот список включаются процессы, которые блок УБ определяет как готовые при каждойзаписи в разнесённые по компьютерам буферы данных (это происходит при выполнениикоманд write и out), а также процессы, перемещаемые блоком на компьютер с другихкомпьютеров с целью достижения равномерной загрузки кластера.Планировщик ПЛ упорядочивает эти процессы и в соответствии с принятойстратегией часть из них отправляет ОС на выполнение.ОС компьютера организует выполнение стоящих в очереди 1 процессов к процессорукомпьютера. Обычно ОС выполняет процессы в порядке их поступления, выделяя каждомупроцессу фиксированный квант времени (здесь мы не актуализируем другие известные иболее эффективные дисциплины обслуживания процессов на компьютере смногоуровневыми очередями и различными способами квантования).

Выполняясь напроцессоре, процесс либо завершает свое выполнение в течении выделенного кванта,сообщая об этом через команду OUT блоку УП, либо в нем возникают команды WRITE,READ, CHECK, KILL, которые реализуются посредством блока УП, либо процессутребуется обмен данными с дисковой памятью. В последнем случае он попадает в очередь 216к системе обмена оперативная память – диски (оп/д). “Появление” в процессе команд READ,WRITE, OUT, KILL и CHECK, в свою очередь, может приводить к необходимости обменаданными с другими компьютерами, что реализуется путем обращения блока УП к блоку ОБ,который организует очередь 3 соответствующих запросов на обмен к ОС, которая выполняетих в соответствии с принятой в ней схемой межкомпьютерного обмена.Список готовых для выполнения процессовимяпроцессаОБномерКГВХУБУПпуть кподпрограмметегданныехарактеристикиПЛЗавершениепроцессаочередь 3очередь 1Запросы к ОС на обмен сдругими компьютерамиоп/дУправлениепараллельнымипроцессамипроцессорочередь 2исчерпание квантакоманды WRITE, READ, OUT, CHEK, KILLРис.