Введение к работе
Актуальность теми. Прогресс информационного общества основывается на использовании параллельных и распределенных вычислительных систем, создание качественного программного обеспечения которых продолжает оставаться одной из наиболее трудных областей программирования. Расширение сферы применения таких систем л повышение ответственности принимаемых ими решений привели к тому, что проблема построения правильных, корректных параллельных программ и более общая проблема создания надеиных программ выдвигаются на передний край вычислительной науки благодаря важнейшему социальному заказу.
Природа трудностей параллельного программирования лежит в неадекватности поведения параллельных программ последовательному характеру мышления разработчика: с ростом числа элементов трудность понимания и анализа параллельной системы растет экспоненциально, а не линейно, как впоследовательном случае. Практика программирования, основанная только на здравом смысле, правдоподобных рассуждениях и тщательности построешія модулей я их интерфейсов, обычная при разработке последовательных программ, приводит в случае параллельных систем к скрытым дефектам, проявление которых в ответственных применениях чревато серьезными последствиями.
Возникает парадоксальная ситуация: структурирование системы на простые, понятные подсистемы с яснш интерфейсом, призванное, казалось, упростить понимание проектируемой системы, в случае параллелизма приводит к качественно новым трудностям ее анализа. В параллельных программах возможны новые типы некорректностей, неизвестные в последовательном программирования; дедлоки, ливлоки, пробуксовки - вот типичные примеры из длинного, со временем пополняющегося списка тех некорректностей, которые обусловлены именно параллельным характером работы программ. Положение усугубляется тем, что традиционные сродства повышения надежности последовательных программ - тестирование и отладка - в параллельном программировании совершенно неэффективны.
Решение проблемы связано с разработкой теорий параллелизма, исследованием моделей параллельных процессов, позволяющих на твердой формальной основе проверять отсутствие нежелательных свойств разрабатываемой программной системы л гарантировать наличие у нее требуемых свойств. К настоящему времени в этом направлении уже проведена значительная работа. Исследования Э.Дейкстры, Ч.Хоара, К.Петри, Р.Милнера,
а в нашей стране В.Е.Котова, В.И.Варшавского, Д.А.Поспелова, А.Д.За-кревского, С.А.Юдицкого и других ученых создали теоретический фундамент науки о параллелизме, отделив, в частности, логическую проблему корректности алгоритма функционирования параллельной программы от инженерной проблемы ее производительности.
Однако, задача построения корректішх параллельных программ еще далека от решения. В параллельном программировании используется множество разнородных, связанных с семантикой прикладной области-критериев корректности, созданные инструментальные средства анализа параллельных и распределенных программ неэффективны и ненадежны: они основаны на перестановочной семантике параллелизма, проверяют лишь ограниченный класс структурных некорректностей параллельных программ, верификация параллельных программ во много раз сложнее самих программ. Приемлемая технология параллельного программирования требует единого взгляда на понятие, корректности, создания эффективных приемов и методов построения корректных параллельных програш. Эти задачи и составляют предмет исследования, выполненного в диссертационной работе. Результаты работы имеют существенное значение для создания технологических систем поддержки разработки параллельных и распределенных программ для различных сфер применения, чем и определяется ее актуальность.
Тема работы согласуется с направлениями исследований, проводимых в области информатики как за рубежом, так и в нашей стране. Так, одним из направлений, поддерживаемых Европейской стратегической npo-'J граммой в области информационной технологии ESPRIT , является разработка технологии параллельного программирования. Национальная программа США STARS "Стратегическая компьютерная инициатива" одной из главных целей ставит повышение производительности труда программистов к надежности программного продукта при разработке встроенных систем управления на парачлельша и децентрализованных распределенных вычислительных архитектурах. В нашей стране аналогичные направления исследований поддерживаются общесоюзными программами НИР All СССР (в частности, комплексной целевой программой I.I.6 "Развитие технологии разработки и промышленного производства программных средств вычислительной техники") и ГКНТ СССР ^в частности, общесоюзной программой 0.16.10 "Создание автоматизированных производств", куда входит проблема "Разработка методов синтеза локальных вычислительных сетей низкого уровня с применением микроэвм"). 2
Цель работы заключается в создании методов анализа и синтеза параллельных процессов, позволяющих строить корректные параллельные и распределенные программы._
Для достижения этой цели в работе решались следующие задачи:
выделение и формализация в рамках подходящей формальной модели свойства когерентности (структурной согласованности) коллективов взаимодействующих процессов;
построение методов анализа свойства когерентности заданной совокупности взаимодействующих активностей и конструктивной методики зинтеза таких активностей, согласованно реализующих требуемое поведете;
исследование возможностей разработанного подхода для построения корректных, не содержащих ошибок параллельных алгоритмов в различных областях вычислительной техники,
Методы исследования базируются на использовании элементов общей алгебры, математической логики, теории алгоритмов и автоматов. Научная новизна работы заключается в следующем:
-
Выделено единое понятие структурной согласованности взаимодействующих параллельных активностей - свойство когерентности, заменяющее большое разнообразие существующих "свойств корректности".
-
Проведено теоретическое обобщение в области параллельных процессов, в результате которого построены:
формальная модель параллельных процессов - дерево партитур, рассматривающая процессы "с точки зрения" разработчика программной системы, а не "с точки зрения" ее пользователя. Модель отражает реальное поведение в системе каждого ее компонента;
формализация свойства когерентности в рамках модели партитур. Іоказано, что это свойство является фундаментальным для систем параллельных взаимодействующих активностей: оно гарантирует отсутстаче з системо всех структурных некорректностей (общих и частичных блокировок, ливлоков, пробуксовок, приемов неспециализированных сообщений і т.д.). G другой стороны, если система активностей некогерентна, то
з ней присутствует активность, реальное поведение которой в окружении аругпх активностей системы неэквивалентно тому поведению, которое определил разработчик, задавая ео алгоритм функционирования;
- алгоритм ан&теза свойства когерентности систем взаимодействую
щих процессов, основанный на выяснении влияния окружения на индиви
дуальную активность, а не на переборе всех глобальных достижимых со-
зтояний системы;
- метод синтеза когерентных систем процессов декомпозицией формальной спецификации, задающей требуемое внешнее поведение.
3. Концепция когерентных асинхронных взаимодействующих процессов использована для получения новых теоретических и практических результатов при анализе и синтезе асинхронных систолических структур, протоколов связи, параллельных и распределенных алгоритмов.
Практическая ценность и реализация результатов работы. Концепцию когерентных взаимодействующих процессов можно рассматривать как основу технологии параллельного программирования, позволяющую разрабатывать системы, не содержащие структурных ошибок. Стратегия такой разработки может состоять из создания удовлетворяющего требованию когерентности синхронизационного скелета разрабатываемой системы - ее упрощенной версии, отражающей только потоки управления, параллелизм, синхронизацию и взаимодействие подсистем, л последующем добавлении необходимых операторов преобразования данных, не нарушающих когерентности системы.
В диссертации этот подход применен для решения ряда практических задач и выполнения практических разработок. Показана некорректность нескольких параллельных и распределенных програли, ранее считавшихся корректный и рекомендованных к применению, синтезировано несколько программ (в том числе протоколов связи, распределенных программ), полная корректность которых гарантирована применяемой методикой. Показано также, что построение программы из взаимодействующих, параллельно работающих модулей ведет к упрощению понимания и анализа программы, если совокупность модулей обладает свойством когерентности.
Эффективность использования свойства когерентности при анализе параллельных программ объясняется тем фактором, что неправильное, ошибочное понимание разработчиком существа параллельного алгоритма в первую очередь сказывается на согласованности аспектов взаимодействия процэссов и мокет быть выявлено синтаксически.
Под руководством автора разработан программный комплекс СПРУТ, позволяющий проверять когерентность параллельных програш с учетом их локальных параметров и передаваемых при коммуникации значений. Результаты диссертационной работы использованы в практических разработках нескольких организаций, в том числе:
I. Во ВНИИэлектромаш при построении автоматизированной системы измерений. Реализация программного обеспечения отой АСИ в виде параллельных взаимодействующих процессов, координируемых в соответствии с одшнл из вариантов классической проблемы "читатели-писатели", пооглн-4
лизированном в работе, позволило гарантировать отсутствие структурных ошибок в сложном комплексе программ АСИ;
-
В ОКБ "ИМПУЛЬС" при разработке систем управления специального назначения были использованы метод спецификации процессов л анализ их структурной согласованности, что позволило сократить сроки проектирования и повысить качество-разработки;
-
В Физико-техническом институте т.А.Ф.Ио&фв при построении транспортной станции в стандарте ЕСМА-72 для локальной сети управления физическим экспериментом была использована предлагаемая в работе методика проектирования протоколов и программный комплекс СПРУТ для проверки когерентности системы процессов, специфицированных на этапе логического проектирования. Это позволило существенно сократить сроки проектирования и избавиться от логических ошибок на ранней стадии разработки;
-
В ОКБ "Радуга" на основе предлагаемого в диссертации подхода решен ряд задач создания технологии параллельного программирования для автоматизации разработки протоколов.
Обоснованность и достоверность полученных выводов в рамках разработанной модели обеспечивается формальным доказательством утверзде-ний и теорем, а в применении к реальным программным системам подтверждается следующими исследованиями. Для параллельных программ, для моделей которых была обнаружена некогерентность их сосгазных частей, были найдены сочетания условий, относительные скорости выполнения операций, значения исходных данных, особенности функционирования реального канала связи и т.д., которые приводили к некорректному поведении программ. Метод синтеза когерентных процессов позволял наряду с новыми решениями получить ряд уке известных решений - параллельных и распределенных программ, протоколов связи, верифицированных другими методами и используемых на практике.
Адекватность принятой формальной модели реальным программным системам выполняется, в частности, для программных систем, состоящих из статически определенных параллельно функционирующих последовательных программ, не имеющих общих данных, взаимодействующих через рандеву и описываемых автоматной моделью.-
Апробация работы. Основные результаты докладывались более, чем на 40 конференциях и семинарах в НИИ, Вузах и КБ, в той числе на:
а) Международных семинарах и конференциях: конференции ученых ' соц.стран "Локальные вычислительны» сети", Рига, 1985; Совместном советско-итальянском семинаре "Сети пакетной коммутации ЭВМ: архитекту-
pa сетей и теория протоколов", Ленинград, 1389; международном семинаре "Формальные модели параллельных вычислений", Телави, 1989;
б) Всесоюзных семинарах и конференциях: "Вычислительные сети
коммутации пакетов" ЖШАК'83,*85,'87, Рига; "Локальные вычислитель
ные сети", ЛОКСЕТЬ'88, Рига; "Координация и декомпозиция в сложных
системах", Челябинск, 1986; "Проблемы совершенствования синтеза, тес
тирования, верификации и отладки программ", Рига, 1986; "Технология
программирования", Киев, 1986; "Формальные модели параллельных вычис
лений", Новосибирск, 1987; "Однородные вычислительные системы и сис
толические структуры", 0ССС»Б8, Звенигород; "Параллельное программи
рование и высокопроизводительные системы", Алушта, 1988 и др.;
в) Постоянно действующих семинарах: "Управление на сетях связи",
ЙППИ АН СССР, рук.Лазарев В.Г.; "Теория автоматов", НТО РЭС им.А.С.По
пова, Ленинград, рук.Варшавский В.И.; "Теоретическое программирова
ние", ВЦ СО АН СССР, рук.Котов В.Е.; "Проблемы искусственного интел
лекта", ВЦ АН СССР, рук.Поспелов Д.А.; "Многопроцессорные ВС", ВЦ СО
АН СССР, рук.Миренков Н.Н.; "Программология и ее применение", КГУ,
рук.Редько В.Н.; "Информационные проблемы вычислительных сетей", НСК
АН СССР, рук.Самойлекко СИ. и др.;
г) Семинарах НИИ, Вузов и КБ: ИЭВТ АН Латв.ССР, рук.Кикутс А.Я.,
Куцевалов Д.В.; ИПУ АН СССР, рук.Юдицкий С.А.; ИПМ АН СССР, рук.Илю
шин А.И.; НПО "Красная заря", рук.Колпаков В.В.; ЛЭТИ, каф.АСОИУ, рук.
Советов Б.Я.; ЦНИИ Робототехнических комплексов, рук.Половко А.А.;
ИК АН УССР, рук.Вельбицкий И.В., Цейтлин Г.Е., Ющенко Е.Л. и др. '* Публикации,. По материалам диссертации опубликовано 35 печатных работ.
Структура и объем работы. Диссертация состоит из введения, шести разделов, заключения а приложений. Основное содержание составляет 359 страниц, в том числе 63 .рисунка.
