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

Можно скачать текст статьи в формате html (65 кб)

© 2002 г. А. И. Легалов

Введение

История параллелизма насчитывает уже не один десяток лет. За это время были разработаны, использованы и забыты разнообразные языки параллельного программирования (ЯПП), а также архитектуры параллельных вычислительных систем (ПВС). Можно вспомнить транспьютеры, векторные и матричные процессоры, процессоры потока данных и многие другие. Во многом их уход был обусловлен не столь архитектурными недостатками, сколь ограничениями микроэлектронной технологии, не позволившими, в свое время, осуществить реализацию на едином кристалле, чтобы составить конкуренцию RISC архитектурам. Даже CISC архитектуры смогли выжить только благодаря стараниям корпорации Intel. Так или иначе, в настоящее время на вершине популярности находятся кластерные вычислительные системы, построенные на базе процессоров с традиционной архитектурой. Вполне возможно, что интерес к нетрадиционным параллельным системам со временем вновь возродится, так как современные технологии уже сейчас позволяют реализовать на одном кристалле множество одновременно работающих модулей. Это, в какой-то мере, подтверждается последними разработками ряда компаний, переходящих к производству процессоров, реально поддерживающих многопоточность внутри кристалла.

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

В основе многих ЯПП лежат различные модели параллельных вычислений (МПВ). Например, взаимодействующие последовательные процессы Хоара [Хоар], положили начало языку Оккам [Джоунз]. Широко использовались для создания языков и различные расширения сетей Петри [Котов]. В каждой из МПВ заложены специфические методы порождения и синхронизации параллельных процессов. Следует отметить, что отсутствие общего подхода не позволяет с единых позиций рассматривать параллелизм в различных языках программирования, что является актуальным при создании переносимого и повторно используемого программного обеспечения. Отчасти это связано с тем, что используемые МПВ отражают не все аспекты необходимые для общего анализа архитектур и языков программирования.

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

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

Учет отношений между данными и операциями осуществляется исходя из того, что любая программа разрабатывается для выполнения конкретных вычислений. При этом зависимость момента выполнения операций от наличия аргументов определяется информационным графом решаемой задачи [Ершов]. Корректное выполнение любой операции обработки данных возможно только в том случае, если, в ходе предварительных вычислений, будут сформированы значения всех ее операндов.

Зависимость от ресурсов вычислительных систем связана с тем, что они не являются безграничными. Поэтому, даже в том случае, если программа может использовать бесконечное число вычислительных ресурсов, на нее приходится накладывать ограничения, обуславливаемые архитектурой вычислительной системы. Эти ограничения снижают параллелизм задачи и требуют ввода дополнительных механизмов управления вычислениями.

Зависимость от управляющих воздействий показывает, что выполнение отдельных операций определяется моментом их запуска, который выбирается не только по объективным причинам (готовность аргументов и наличие вычислительных ресурсов). Зачастую программист руководствуется субъективными факторами. Однако, в любом случае, наличие управляющих воздействий, определяющих граф потоков управления, является неотъемлемой частью алгоритма решаемой задачи.

Каждая из представленных составляющих влияет на общую классификацию стратегий управления.

Модель вычислительного процесса

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

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

Определим вычисления, определяющие процесс P и протекающие в вычислительных ресурсах R как обработку операционного пакета I_in, в результате чего формируется выходной пакет I_out. Пусть момент начала вычислений определяется входным управляющим воздействием C_in, а их завершение фиксируется по выдаче вычислительным ресурсом управляющего сигнала C_out. Графическое обозначение этих вычислений представлено на рис. 1. Иерархическая организация вычислений позволяет говорить о том, что процесс можно разделить на более мелкие подпроцессы, каждый из которых может выполняться в отведенной для этого части общих ресурсов. При этом, одни и те же ресурсы могут повторно использоваться при выполнении различных вычислений, разделяясь подпроцессами во времени.

Рис. 1. Процесс как вычисления, протекающие в ресурсе

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

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

Рис. 2. Потоки, определяющие протекание процессов в вычислительной системе

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

Модель процесса

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

P = (I, R, C),

где I = (Iin, Iout) - информационные пакеты, определяющие функцию обработки, ее аргументы и результаты, R - ресурсы вычислительной системы, предоставленные для выполнения процесса обработки данных, C = (C_in,C_out) - сигналы управления, определяющие последовательность действий по обеспечению корректного выполнения процесса и определяющие причинно-следственную или временную привязку. На рис. 3. представлено графическое изображение процесса в соответствии с описанной интерпретацией.

Рис. 3. Потоки, определяющие протекание процессов в вычислительной системе

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

Данные тоже можно разделить на входные и выходные. Входные данные (I_in) определяют операционный пакет, обрабатываемый в ходе выполнения процесса, а выходные данные (I_out) являются результатами его работы. Они образуют результирующий пакет.

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

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

Декомпозиция процесса, определяющего поведения программы, не является безграничной. На самом нижнем уровне можно выделить элементарный вычислительный процесс, который имеет один управляющему вход и один управляющий выход. Поступление сигнала на вход определяет момент запуска процесса. Завершение обработки сопровождается выдачей управляющего сигнала, информирующего о готовности данных. В ходе вычислений элементарный процесс не выдает и не принимает никаких управляющих сигналов. Попытка повторно запустить его в этот момент приведет к ошибке в вычислениях. Подобную ситуацию следует считать запрещенной. Реакция на нее специально не оговаривается. Можно, в этом случае, блокировать повторный доступ, прерывать работу всей системы с указанием причины или повторно инициировать запуск. Предположим также, что каждый элементарный процесс выполняет конкретную операцию F_i, которую можно будет записывать внутри прямоугольника вместо общего обозначения процесса (P). Вместо рисования подсистемы управления ресурсов будем оставлять один конец ресурсной связи свободным. Графическое обозначение элементарного процесса представлено на рис. 4. Подобные процессы далее будем также называть функциональными.

Рис. 4. Элементарный (функциональный) процесс

Моделирование и изучение динамики процессов можно осуществлять на основе механизма продвижения фишек. Этот механизм широко используется в различных моделях вычислений [Деннис, Котов]. Описание различных состояний элементарного процесса показано на рис. 5.

Рис. 5. Продвижение фишек, моделирующее выполнение элементарного процесса

Для того, чтобы запуск элементарного процесса привел к успешному выполнению заданной функции F_i, необходимо предварительное выделение ресурсов R_j, предназначенных для выполнения вычислений и хранения результатов. Предполагается, что аргументы I_in функции F_i хранятся в ресурсах, выделенных для выполнения предшествующих операций (рис. 5а). При этом не важно, в какой последовательности происходит выделение ресурсов и получение исходных данных (рис 6). Запуск определяется управляющим сигналом (рис. 5б), после чего процесс переходит в состояние выполнения вычислений (рис. 5в). В ходе вычислений возможно многократное обращение к исходным данным. Поэтому необходимо, чтобы ресурсы, сохраняющие эти данные, не освобождались во время выполнения вычислений в текущем процессе. Завершение вычислений сопровождается сохранением результатов в ресурсах памяти, доступной другим процессам (рис. 5г). С этого момента аргументы становятся неактуальными, а занимаемые ими ресурсы могут быть использованы в других целях. Окончание вычислений сопровождается сигналом завершения элементарного процесса (рис. 5д), который может быть использован другими процессорами для получения информации о готовности их аргументов. Данные, после выдачи сигнала сохраняются до тех пор, пока выделен ресурс, обеспечивающий их хранение (рис. 5е).

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

ICR-сеть

Взаимодействие множества элементарных процессов можно представить как сеть процессов, с заданными отношениями между информацией, управляющими сигналами и ресурсами (ICR-сеть). Она может рассматриваться как совокупность трех подграфов определяющих: информационный граф, граф управления и граф ресурсов (рис. 7).

Рис. 7. ICR-сеть, описывающая поведение процессов в ресурсах вычислительной системы

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

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

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

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

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

1. Условие готовности данных (Information - условие). Перед запуском процесса на его информационных входах должны присутствовать все необходимые аргументы и функции, составляющие операционный пакет. Отсутствие каких-либо данных к моменту запуска процесса ведет к получению неправильного результата. То есть, если существуют процессы, результаты которых являются аргументами рассматриваемого процесса, то они должны завершиться к моменту запуска текущего процесса.
2. Условие выделения ресурсов (Resource - условие). Выполнение процесса протекает в соответствующих ресурсах, поэтому, перед его запуском, эти ресурсы должны быть определены и предоставлены. Ресурсный вход должен содержать информацию, подтверждающую выделение ресурсов, необходимых для успешного выполнения процесса. В противном случае его запуск просто невозможен.
3. Условия подтверждения использования результатов (Acknowledge - условие). Ресурсы, занимаемые процессом, могут освобождаться или повторно использоваться только после того, как результаты вычислений будут использованы всеми процессами, являющихся приемниками этих результатов в качестве аргументов. В противном случае данные будут потеряны, что приведет к неправильным вычислениям. Необходимость задержки в освобождении ресурсов мотивируется тем, что память, используемая для хранения операндов, является разделяемым ресурсом. В нее записываются результаты вычислений элементарного процесса. Из нее же происходит чтение аргументов, необходимых другим процессам.

Информация о выполнении условий готовности в рассматриваемой модели подтверждается наборами соответствующих управляющих сигналов:

• сигналами готовности элементов операционного пакета;
• сигналами готовности необходимых вычислительных ресурсов;
• сигналами, подтверждающими отсутствие конфликтов при использовании разделяемых ресурсов.

Эти входные сигналы формируются на основе выходных сигналов завершающихся процессов. Завершение элементарного вычислительного процесса одновременно подтверждает готовность результатов и использование им, в качестве своих аргументов, результатов, полученных ранее в процессах - <передатчиках>. Естественно, что при более сложном представлении процессов, схема их взаимодействия и моменты формирования управляющих сигналов тоже будут сложнее.

Моменты выдачи управляющих сигналов и сами принципы их формирования, определяющие наступление соответствующих событий, могут осуществляться одним из следующих способов:

1. Явно, когда при описании взаимодействия процессов (в ходе написания программы) разработчик (программист) сам создает логику порождения и проверки управляющих сигналов, определяет пути и моменты их передачи. Назовем такое формирование управления субъективным (Subjective)
2. Неявно, когда, при описании процессов, механизм управления тем или иным условием готовности просто не задается из расчета, что процессы и так будут выполняться корректно.

Корректность неявного управления процессом может обуславливаться двумя причинами. Первая причина обуславливается тем, что ресурсы ВС организованы таким образом, что всегда поддерживают выполнение заданного условия. Назовем данный принцип формирования управления автоматическим (Automatic). Вторая причина обуславливается тем, что описание взаимодействия процессов может быть сделано так, что, несмотря на отсутствие в ВС механизма автоматической поддержки, условие готовности всегда истинно, поэтому его и не нужно проверять. Этот принцип управления назовем пустым (Empty). Он опирается на дополнительные сведения о работе системы.

Наличие трех условий готовности и трех механизмов их формирования позволяет выделить двадцать семь основных стратегий управления вычислительными системами. Любую из них можно представить в виде трехэлементного вектора условий готовности:

(Information, Resource, Acknowledge),

Каждое из условий готовности процесса может принимать одно из трех допустимых значений:

(Subjective, Automatic, Empty).

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

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

Заключение

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

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

Литература

1. [Деннис] Деннис Д.Б., Фоссин Д.Б., Линдерман Д.П. Схемы потока данных. / Теория программирования. Часть 1. Новосибирск: ВЦ СО АН СССР. 1972. С. 7 - 43.

2. [Джоунз] Джоунз Г. Программирование на языке Оккам: Пер. с англ. - М.: Мир, 1989. - 208 с.

3. [Ершов] Ершов А. П. Введение в теоретическое программирование (беседы о методе). - М.: Наука. Главная редакция физико-математической литературы, 1977. - 288 с.

4. [Котов] Котов В. Е. Сети Петри. - М.: Наука. Главная редакция физико-математической литературы, 1984. - 160 с.

5. [Хоар] Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. - М.: Мир, 1989. - 264 с.

PS

Размышления о стратегиях управления имеют долгую историю. Впервые к этой теме я обратился в начале 80-х, когда занимался анализом различий между процессорами потока данных (ППД) и прочими параллельными вычислительными системами. Да и внутри ППД существовало большое разнообразие решений, проявляющееся как на уровне моделей вычислений, так и на уровне структур. Тогда же появилась и первые публикации по этому поводу, кратко характеризующая 16 основных стратегий [1-2]. После этого был длительный период, связанный с другими работами. Окончательная версия классификации сформировалась в начале 90-х. Она была апробирована в лекциях по "Архитектуре вычислительных и программных систем", читавшихся мною в Ярославском государственном университете. В печатном виде появилась и слегка уточнилась только в 1994 [3-4].

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

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

В какой-то мере, это и мой ответ на вопрос В.С. Любченко о том, что лучше: синхронное или асинхронное. Нельзя четко выбрать из необъятного. Всему свое время, место, класс задач, уровень организации программирования и многое другое.

PS-Литература

1. Водяхо А.И., Легалов А.И. Организация асинхронных вычислений в высокопроизводительных спецпроцессорах. - Изв. ЛЭТИ. Науч. тр./ Ленингр. Электротехн. ин-т им. В.И. Ульянова (Ленина), 1984, вып. 343. Проектирование и применение микропроцессорных систем. с. 20-23.

2. Водяхо А.И., Емелин В.П., Легалов А.И. Стратегии управления вычислительными процессами и их модели. - В кн.: Математическое и программное обеспечение САПР сетевых систем, Йошкар-Ола, 1985, с. 135-142.

3. Легалов А.И. Стратегии управления вычислениями. - В кн.: Проблемы техники и технологий XXI века. Материалы научной конференции. Красноярск, КГТУ, 1994, с. 122-126.

4. Легалов А.И. Управление в вычислительных системах и языках программирования. - В кн.: Проблемы информатизации города: Материалы конференции. Красноярск, 1994, с. 198-202.