Ситкевич Т.А., Сюрин В.Н. Параллельные вычислительные среды

Подождите немного. Документ загружается.

уровней и других устройств. Разбиению на частные «э лементар-

ные» работы и отражению их взаимодействия служит к онцеп-

ция программирования на уровне процедур. Эта концепция на-

шла отражение в мощных многомашинных вычислительных

к о мплек сах «Эльбрус», где она реализована аппара тно-программ-

ным способо м. Принцип процедурног о программирования до-

пуск ает фор миров ание любых программных структур со в семи

типами сопо дчинения, в том числе допуск ает в лож енность про-

цедур. Очевидно, что возмо жность явного задания структуры

программы, вклю чающег о указание параметров проце дур, спо-

собству ет авт о матическ о му получению информации для орга-

низации распараллеливания.

Использов анию иерархическ ой структуры алгоритм а, сопо д-

чинению операторов при выполнении программы соответств у-

ет стековый принцип обработки информации. Действительно,

выполнение процедуры в процедуре при описании соо тветств у-

ет переходу на новый лексико-графический уровень. В процес-

се счета требуется прерывание выполнения о дной процедуры,

запо минание на мо мент прерывания всей относящейся к ней

инфор мации и инициализация в лож енной процедуры. Такие

действия равносильны работе со стек ом, где переход на новый

лек сико-графический уровень соответствует понижению пре-

рванног о выполнения процедуры на один уровень, началу вы-

полнения на вершине стек а работ более высокого уровня, а за-

тем обратно му сдвигу для продо лжения выполнения прерван-

ной процедуры. Поскольку число уровней мож ет быть произ-

вольным, то и г лу бина погруж ения в стеке мож ет быть зна чи-

тельной. Преимущественное испо льзование принципа проце-

дурног о программирования для выделения элементарных работ,

выполнение которых в ВС подлежит планированию, поставило

бы программиста в большую зависимость от во змо жностей раз-

биения алгоритм а на процедуры, от предпо лагаемого объем а

процедур, усло жнило бы рабо т у ме ханиз мов распределения ре-

сурсов. Эт о определило целесообразность представления алго -

ритма в виде о дног о или неско льких взаимо действующих про-

цессов. Процессы – логически завершенные, преимущественно

зна чительные по об ъему работы, на к о т орые можно и целесооб-

разно разбить выпо лняемый алг оритм. При фор миров ании про-

цессов основопо лагающими яв ляю тся требования оптимальной

сегментации программ для распределения рабо т между сре дства-

ми ВС и распределения ресурсов ВС в ходе выпо лнения неск о ль -

ких процессов. Порядок выполнения процессов также подчи-

няется стековому принципу. Одновременно между процессами

существу ет два вида зависимости: процессы могут быть явно

зависимыми (в лиять на порядок работы друг друга, поро ждать

и ликвидирова ть друг друга); зависимость мо ж ет реализовыват ь-

ся операционной системой, управляющей ресурсами. В перво м

случае процессы, как правило, объе динены в рамк ах о дной за-

да чи и использ ую т закрепленную за этой зада чей память. Эт о

позволяет строить сложные программные системы. Во в торо м

случае ок азывается возмо жным организация совместных работ

многих пользов ателей. Выпо лнение процессов мо жет чаще всего

происходить и прерываться в стек ов о м порядке: после дний пре-

рван – первый восстанавливается. На это т порядок накладыв а-

ется дисциплина приоритетов. Абсолютизация стек ов ог о прин-

ципа соотв етству ет приро де большинства вычислительных про-

цессов.

СТЕКОВЫЙ ПРИНЦИП ВЫПОЛНЕНИЯ ПРОЦЕДУР

В многопроце ссорной системе одновременно могут

выполняться, т. е. нах о диться в активно м состоянии, неск олько

процессов, но не более числа процессоров. Процесс отображен

элементарной рабо чей программой. Каждая программа форми-

руется из к о манд (то чнее, из м акрок о манд), соответств ующих от-

дельным процедурам. Описания процедур (сегменты процедур)

хранятся отдельно. Существ ует словарь сегментов данной про-

граммы, сформиров анный при трансляции, в к от ором хранятся

указа тели на каждый сег мент. Один из выделенных базовых реги-

стров каждог о процессора (распределение регистров всех про-

цессоров идентично, так как выполнение программы не должно

зависеть от назна ченног о для этог о процессора) во время выпол-

нения программы ук азыв ает на ее слов арь сегмент ов. Номер вы-

полняемой к о манды нах о дится в регистре номера к о манды и со-

стоит из но мера сег мента и адреса внутри сегмента.

Вычислительный процесс организуется так, что парамет-

ры выпо лняемой процедуры, промежуто чные рез ульта ты и дру-

гие именов анные данные, относящиеся к ней и формир у емые в

ней, нах о дятся в памяти процессора, которая с учето м стекового

принципа выполнения проце дур организ у ется в виде стек а. По

стековому принципу осуществляется динамическое распре-

деление памяти под процедуры. В алгоритмических языках с

б ло чной струк турой переменные по являю тся на основании опи-

саний при вх о де в процедуры и со храняются до выхода из дан-

ной процедуры. Поэтому при вх оде в процедуру должна отво-

диться память для локальных данных, а при вых оде ее нужно

освобожда ть. Так как последова тельность вх одов и выходов

по дчиняется стековой дисциплине, т. е. первым осуществляется

выход из той процедуры, которая была запущена последней, то

и для динамического распределения памяти по д процедуры так-

же целесообразно использов а ть стек. Тогда в памяти каждог о

процессора б удет организован стек, на котором выполняю тся

закрепленные за ним программы. В вершине стека о тражается

выполнение процедуры самого высокого на данный момент

уровня иерархии. По мере поступления вло женных процедур для

выполнения вся информация о прерванных процедурах погру-

жается в стек е на о дин уровень ниж е. Процедуры, не яв ляющи-

еся вло ж енными, выполняются последова тельно на одно м уров-

не стека. При этом, как указывалось выше, кодовые сегменты

процедур о тделены от данных, нах о дящихся в стек е, а доступ к

ним осуществляется с помощью базовых регистров процессо-

ров. Такая организация приво дит к то му, что все процедуры об-

ладаю т свойством повт орной входимости, т. е. о дна и та же про-

це дура мо жет выполняться на стеках разных процессоров, при

этом нет необходимости иметь неско лько копий ее программы.

Это очень в ажно для возможности выполнения программ в мно-

г оканально м режиме, для независимог о выполнения процедур

операционной системы в составе различных программ и т. д.

При это м обеспе чивается контек стная защита данных.

Струк турные связи выполняемой процедуры, рекурсивность

и повт орная входимость обеспе чив аю тся тем, чт о каждой запу-

щенной, но неок онченной процедуре в стек е соответству ет св о я

об ласть прямоадресуемых данных. Адрес на чала этой области

является базой процедуры. Область прямоадресуемых данных

формиру ется на основе об ласти имен данной процедуры, кото-

рую составляю т использ уемые процедурой ее собственные имена

и имена охватывающих процедур в соотв етствии с иерархичес-

кой структ урой. Если процессор располагает собственной опе-

ративной или сверх оперативной памятью доста то чног о об ъем а,

то процедура вызывается на организ ованный в этой памяти стек

процессора вместе с об ластью известности имен, ко т орая зада-

нием зна чения базы превращается в об ласть прямоадресуемых

данных этой проце дуры.

Наиболее удобный естественный и эк оно мичный способ

адресации данных – эт о адресация по номеру уровня вло ж енно-

сти, лек сико-графическому уровню, к о т орый позволяет уста-

новить базу данной процедуры, а также по смещению относи-

тельно базы. База данной процедуры фор мируется в базово м

регистре выполняющег о процессора. Номер этог о регистра ра-

вен номеру лексико-графического уровня. Адресация имен про-

цедуры при ее выпо лнении произв о дится с помощью адресных

пар, состо ящих из значения базы и значения смещения относи-

тельно базы. Для повышения надежности и универсальности

использ уемых ресурсов стеки процессоров могут быть нежест-

ко закреплены за процессорами. В стеке процессора в основном

концентрирую тся устройства памяти процессоров, основные

регистры, над к о торыми произво дятся операции. Операцион-

ные устройства могут быть отделены от собственно процессора

и рассм атрива ться о т дельно. Собств енно процессором остается

устройство управления, ведающее обработкой потока инструк-

ций, и их назна чением для выполнения. Эт о допускает перек о м-

мутацию св язи «процессор – стек процессора» в случае отказов

процессоров, та к как стек отк азавшег о процессора соо тветству-

ет пассивному стек у некоторого процесса. При это м мо жет быть

учтен приоритет решаемых процессорами зада ч.

Для оперативног о продо лжения о дними процессорами ра-

бот, выполнение к о т орых уже начато на др угих процессорах,

целесообразно, чтобы стеки процессоров составляли общую

память, доступную всем процессорам. В то же время эти стеки

должны быть в разных блок ах этой памяти, что должно допус-

кать одновременное обращение, т. е. об еспечив а ть минималь-

ные взаимные поме хи при работе процессоров. Связь с закреп-

ленными за ними стеками процессоры могут осуществлять с

помощью специально выделенных базовых регистров, адреса

ко т орых различимы для специальных к о м анд, ведающих ком-

мутацией, и неразличимы для процессоров: часть адреса такого

регистра является общей для всех процессоров. В частности,

возможна сле дующая процедура продо лжения рабо ты ВС в слу-

чае о тк аза или отклю чения о дног о из процессоров:

1. Прерывается работа г оловног о процессора.

2. За пускается на нем процедура анализа ак тивных процессов.

Данная проце дура находит среди всех ак тивных стеков стек

выполняемог о процесса с минимальным приоритетом. При этом

возможны дв а случая:

процесс из стека отказавшего процессора оказывается в

числе процессов с минимальным приоритетом, тог да это т про-

цесс перево дится в очередь процессов;

минимальным приоритетом обладает ак тивный процесс,

не выполнявшийся на стеке отказавшего процессора; тогда

изменяется со держимое базовог о регистра, выполнявшег о этот

процесс процессора, для подключения его к стеку отказавшег о

процессора; стек прерванног о процесса становится пассивным

и перев о дится в о чередь.

Так как внутри системы накапливаются разнообразные

ф ункции управления (режимами прохождения зада ч, ресурсами,

обеспечения надежности) и слежение за работ ой ВС до лжно

осуществляться с устойчивым периодо м, то о дним из вариан-

тов такого устойчивог о вмеша тельств а управляющих средств

является не то лько назначение о дног о из процессоров управля-

ющим, но и формирование в системе специальног о управляю-

щего стека процессора. После прерывания управляющег о про-

цессора с частот ой, с которой проис хо дит анализ состо яния си-

стемы, осуществляется ко ммутация этого процессора с управ-

ляющим стеком процессора, чтобы избежа ть работы стандарт-

ной процедуры переклю чения на новый вид работ, к о т орая мо-

жет быть значительно более тр удоемкой. В управляющем стек е

процессора рабо ты по управлению могут быть всег да по дг о т ов-

лены (в резуль та те предыдущего вклю чения) к продолж ению с

момента переклю чения на них управляющег о процессора.

Децентрализованное управление ВС мо ж ет производиться

с помощью перио дическ ого включения в состав о череди управ-

ляющег о процесса, объе диняющег о ряд процедур управления.

При каждо м включении этого процесса подг о тавливается его

следующее включение вновь. Очевидно, что такое решение не

обеспе ч ив ает опера тивной и синхронной работы сре дств ВС,

чрева т о воз мо жностью отказа ВС без выхода на процедуры уп-

равления. Подводя итог анализу способов организации управ-

ления вычислительным процессом в ВС, можно выделить три

возмо жности:

управ ление через очередь, при к о т ором управляющий про-

цесс перио дически по дставляется в очере дь и реализу ется про-

це ссором, выбравшим его в соответ ствии с дисциплиной

обслужив ания о чере ди. Такой способ управления приемлем,

например, для таких работ, как реорганизация памяти, оценк а

состо яния средств;

выполнение одним из процессоров ф ункции головног о

или управляющего. Его работа по обслуживанию очереди

периодически прерывается для выполнения функций управле-

ния ВС;

наличие в системе специальног о управляющег о процес-

сора, в силу назначения и исполнения не участвующего в

обслуживании очере ди. В многопроцессорных ВС, совмещаю-

щих различные режимы обработки информации и ну ждающих-

ся в сложно м планировании использования ресурсов, целесо-

образно включение в состав ВС специализированных управля-

ющих процессоров.

При рассмотренной организации вычислительного процес-

са процессоры выступают в ро ли ресурса для активизации сте-

ков процессов, предлагая свое оборудование (налагая ег о) сте-

кам процессов. При это м принципиально возможна коммута-

ция любог о процессора с любым стеком процесса. В это м выра-

жается идея вирт у альных процессоров. Центральное же место в

работе ВС заним аю т, как это и должно быть, процессы, для вы-

полнения к о торых назначаю тся ресурсы. В то же время, поско ль-

ку для активизации процессов необходимы ресурсы, функции

управления ими приходится распре делять между процессорами

и даж е назна чать управляющий процессор.

ФОРМИРОВАНИЕ И СИНХРОНИЗАЦИЯ ПРОЦЕССОВ

Каждый пользова тель формир ует свою зада чу. Задача со дер-

жит один или нес колько в общем случае взаимосвязанных

процессов. При выполнении о дних процессов мож ет быть пре-

дусмотрено ро ждение новых процессов. В рамках одной зада чи

и отведенной для нее памяти обычно операционная система стре-

мится использова ть минимальное число формиру емых стек ов.

Так как стек есть фактически мо дель операционног о устройства

– процессора, то для последовательно выпо лняемых процессов

естественно стремление снизить число фор мир уемых стеков,

обеспечить их преемственность, начиная выполнение новых

процессов на стеках закончившихся процессов или процессов,

их породивших. Распараллеливание для полног о использов ания

ресурсов осуществляется двумя путями:

на основе естественног о с уществования независимых за-

да ч пользов а телей;

на основе существования сложных программных систем,

которые состоят из взаимосвязанных процессов, допускающих

параллельное выполнение.

Разбиение задачи на взаимодействующие проце ссы –

проблем а, связанная не только с оптимальным использованием

ресурсов ВС, но и с разработкой бо льших программных систем,

при к о торой возникает необ х одимость распре деления работ меж-

ду исполнителями для сокращения времени разработки.

Соз дание каждого процесса в основном сводится к организа-

ции стека процесса, т.е. к отве дению памяти по д стек и форми-

рованию шапки стека. В рамках от дельной задачи пользова теля

необходим а эк оно мия памяти и времени формиров ания, поэто-

му стек новог о процесса организуется или на стеке процесса,

ег о породившег о либо закончившего непосредственно перед ним

свое выполнение, или в памяти, отведенной для стеков данной

задачи, если решение то лько начинается.

Не сколько стеков процессов могут формироваться для

распараллеливания задачи. В цело м, в рамк ах о дной задачи мо-

жет быть сформировано ск о лько уго дно процессов. Процессы

став я тся в очередь в соответствии с приоритетом. Приоритет

формиру ется с учето м приоритета зада чи пользов а теля – абсо-

лютный приоритет, а также с учет о м приоритета по сравнению

с приоритетами др угих процессов в рамках данной зада чи – от-

носительный приоритет. Абсолютные и относительные приори-

теты всех процессов могут быть приведены к приоритету про-

цесса выбором такого его значения, при котором приоритет

любого процесса зада чи польз ова теля с меньшим приоритетом

об яза тельно меньше приоритета любог о процесса зада чи с боль-

шим приоритето м.

Окончание каждого процесса мож ет наступить либо при

естественном окончании выполнения последней процедуры,

либо по приказ у «убить процесс», либо при выходе из процесса

по аварийной сит уации. В первых дв ух случаях выпо лнение зада-

чи мож ет продо лжаться, так как зак анчив ается или уничто жает-

ся в перв о м случае лишь часть задачи (данный процесс) или во

в тором случае – данный процесс и процессы, созданные в нем.

В третьем же случае возможно аварийное окончание задачи.

Синхронизация информационно взаимосвязанных процессов

мож ет произво диться с помощью механиз ма семафоров или мат-

рицы следования.

СОВМЕСТНАЯ РАБОТА ПРОЦЕССОРОВ

Рассмотрим самый общий случай ф ункциониров ания ВС

независимо от ее применения, т.е. на данный общий алгоритм

функциониров ания ВС мо жет налагаться любая организация уп-

равления, превращающая ВС в специа лизированную или

отражающая особенности ее использования.

Функции управления ВС могут реализоваться о чередью,

о дним из процессоров или специализиров анным управляющим

процессором. По обеспечиваемой оперативности управления два

последних способа равносильны, поэтому целесообразно раз-

личать два способа управления: с помощью постановки управ-

ляющих процессов в очере дь, когда отсутств уют ж есткие требо-

вания к моменту принятия решения, и с помощью управляюще-

го процессора (считая, что им мож ет быть о дин из процессоров

ВС, решающий и основные задачи из очереди). Управ ляющий

процессор реагирует на сигналы прерывания, поступающие в

жестк ом временно м режиме. По поступлении на управляющий

процессор сигнала прерывания мож е т быть произведена его

перекоммутация на управляющий стек процессора. Обработка

управляющих процессов так же, как и других, произв одится

процессорами, к о т орые их выбрали для выполнения. В г олов е

о чере ди нах о дится процесс с максимальным приоритето м. Вы-

бор процесса из г о ловы очере ди происходит всегда, когда на этом

процессоре заканчивается выполнение процесса или когда та-

кое выполнение необходимо прерва ть. Одним из возмо жных

случаев такого прерывания является случай, когда исчерпался

отрезок времени, определенный системой для выполнения про-

цессов данной зада чи при работе в режиме раз деления времени.

На процессоре произво дится смена стека – нало ж ение на стек

процессора стека процесса из головы о череди. Произво дится

реорганизация очере ди, т.к. прерванный процесс возвращается

в о чередь и должен занять в ней место в соответствии со скор-

ректированным зна чением приоритета.

ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ ВЫЧИСЛЕНИЙ. АЛГОРИТМЫ И ЯЗЫКИ

С уществ у ет два возмо жных подхода к разработк е параллель-

ных мет одов вычислений. Первый основан на исследов ании

существ ующих методов решений сложных задач и их дорабо тк е

для представления в виде, у добно м для выполнения параллель-

ных вычислений. Он обеспечивает преемственность работ и

возмо жность раз деления труд а между специалистами-ма тема-

тиками и специалистами в области вычислительных систем.

Видоизменение мето да вычислений для приспособления к па-

раллельным вычислениям несложно и не требует зна чительных

усилий при доработке. Достоинство такого по дхода заключает-

ся в возмо жности получения быстрог о практического вых ода.

Второй по дхо д связан с разработкой новых мето дов, специаль-

но учитывающих возмо жность выполнения параллельных вы-

числений. Он позволяет более эффективно использова ть осо-

бенности вычислительных систем, приспособленных для выпо л-

нения параллельных вычислительных процессов. Это т путь осо-

бенно удоб ен при подходе к решению новых сло жных задач, для

ко т орых еще нет гот овых методов вычислений. В основе таких

мето дов мож ет лежа ть принцип разбиения задачи на св язанные

по дзада чи с помощью неко т орых регулярных приемов, анало-

гичных мето дам расчленения.

Понятие распараллеливания алг оритма подраз умев ает пред-

ставление алгоритма (программы) в таком виде, чтобы мо жно

было совмещать во времени выполнение отдельных участков

алгоритма (его ветвей). Процесс распараллеливания алгоритма

состоит в выделении ветвей, описании структ уры параллельно-

го процесса и синхронизации выполнения ветвей при ег о реа-

лизации. Для облегчения распараллеливания в нек о торых языках

(например, PL-1) предусмо трены специальные средства для вы-

деления ветвей в алг оритме и синхронизации их. В этом случае

программист в явной форме указыв ает на возможности распа-

раллеливания, а транслятор и операционная систем а машины ре-

ализую т параллельный процесс. Если исх о дный алгоритм запи-

сан на язык е, не имеющем по добных сре дств, то ег о распаралле-

ливание сво дится к сегментации алгоритма и объединению сег-

ментов в ветви по определенным правилам. Эту работу выпо лня-

ет либо программист, либо машина по специальной программе

сегментации. В вычислительной машине могут быть специаль-

ные блоки, предназначенные для сегментации программ.

Основой построения параллельного алгоритм а может слу-

жить как последов а тельный алг оритм, так и задача сама по себ е .

При распараллеливании последов ательного алгоритма наибо-

лее раз у мным представляется праг ма тический по дхо д, т.е. в пос-

ледовательных алг оритмах выяв ляются часто встречаемые эле-

менты, которые за тем трансформ ир уются в параллельную фор-

му. Далее этот по дход иллюстрир у ется на примерах арифмети-

ческих выражений, а такж е на распараллеливании с помощью

перестановок и рекурсий. Очевидно, чт о по крайней мере неко-

торые из этих преобразований могут быть выполнены ав то м а-

тически. Подобный путь исклю чительно важен, поско льк у ок а-

зывается в озмо жным использов ание на параллельных ЭВМ со-

зданног о для обычных машин дорогост о ящего программного

обеспечения. Указанные принципы распараллелив ания относят-

ся к определенным последов а тельным алгоритмам. Эт о соот-

ветств у ет общепринято му в численном анализе последов а тель-

ному характер у мышления. При программировании на парал-

лельных ЭВМ необ ходим параллельный тип мышления. Отме-

тим, что параллельный тип мышления характерен для аналог о-

гибридных вычислений.

Для распараллелив ания асинхронных процессов необх о дим

совершенно иной по дход, поско льк у в эт о м случае разные про-

цессы до лжны выполнять общую рабо т у, но без всякой синхро-

низации извне.

Вычисления арифметических выражений состав ляют осно-

ву численных алг оритмов. Имеется большое число последова-