Введение к работе
Актуальность теш. В настоящее время интенсивно развиваются методы формализованных спецификация лрограьм. В теории программирования разработан рад формальные моделей н конструкций, удобных для построения строго обоснованных программных систеы имеете с доказательство» наличия в них тех или иных свойств. К числу известных методов относятся системи алгебраического, логического, композиционного, трансформационного программирования, формализованные технические задания, VDM, Я-технояогия и т.д. Развиваются средства инструментальной поддераки формализованных спецификаций, в той числе алгебраических. Отметим, что к числу первых отечественных языков алгебраического гірограмниравання относится АНАЛИТИК (?*гр-2, СМІ4І0 и др.), созданный в Институте кибернетики км. В.М.Глуикова АН Украины. Получила известность современная система алгебраического програшшрования APS, такта, созданная в Институте кибернетики.
Одно из направлений современного программирования, основанное на использовании алгебраических методов, сформировалось как результат развития теории систем алгоритмических алгебр (САА) В.М.Глуикова. Для описания параллельных вичислений предназначены модифицированные системы алгоритмических алгебр (САА-М). Аппарат САА-М, допускающий . компактное структурное представление схем программ в еидє алгебраических формул, полояен в основу метода многоуровневого структурного проектирования программ (МСПП), разрабатываемого в Институте кибернетики им. В.М.Глушкова АН Украины. Метод МСПП ориентирован на построение иерархических спецификаций классов алгоритмов и программ на основе сочетания алгебры алгоритмов и теории формальных грамматик. В рамках алгеброграмматического подхода формализуется проектирование алгоритмов и программ как выеод в соответствующих грамматических моделях. Семантика классов алгоритмов и программ определяется контекстнозависимыми правилами Еывода и означиванием нетерминальных символов в заключительных продукциях, что соответствует построению интерпретационной алгебры. При этом возникает проблема согласованности уровней проектирования. Инструментальной
'поддерякой МСПП является структурный сшггезатор программ МУЛЬТИПРОЦЕССИСТ, который по многоуровневым спецификациям генерирует программный продукт.
Снижение стоимости разработки прямо связано с отсутствием ошибок при проектировании. Построение согласованных спецификаций на разных уровнях проектирования и проверка свойств спецификаций на каадоы уровне часто позволяет.. обнаружить ошибки на начальных этапах и благодаря этому избежать полного перепроектирования.
Цель и задачи работы. Целью диссертации является:
фошализация ' концепции согласованности спецификаций алгоритмов и программ, заданных на разных уровнях абстракции, при проектировании по методу МСПП;
исследование свойств тупиковости (клинчей, дедлоков, зацикливаний) и фиктивности (невыполняемых итерируемых
'компонент) спецификаций параллельных програші;
- разработка для метода МСПП и его инструментария средств
обнаружения тупиков и фиктивностей в спецификациях параллелыг'х
программ. .
Научная новизна, для метода МСПП введена концепция согласованных спецификаций. Установлены критерии по " согласованности описаний алгоритмов и программ на разных уровнях абстракции.
Исследованы свойства монотонности операторов в соответствующих классах САА-М. Исследована и алгоритмизирована проблема тупиков и фиктивностей в асинхронных параллельных схемах nporpaisu.
Практическая ценность. Концепция согласованности спецификаций ка разных уровнях абстракции представляет практический интерес при проектировании и синтезе программ по методу 'МСПП в связи с повышением надекности программного продукта и ускорением его отладки.
Расширены средства описания логических условий для синхронизации параллельных процессов, что обогащает "изобразительные возможности входного языка системы МУЛЬТИПРОЦЕССКСТ.
В рамках метода МСПП в системе МУЛЬТИПРОЦЕССИСТ реализован . анализатор свойств тупиковости и фиктивности в спецификациях
параллельных алгоритмов и програну. Csu анализатор спроектирован и синтезирован средствами системы МУЛЬТИПРОЦЕССКСТ.
Настоящая работа выполнялась в ранках исследовании по темам:
I.I3.4.5, N ГР0І860045697 "Разработгть теорка и метода автокатизировэшюго производства п^облеиио-оряентироваккых систем";
СИНТЕЗ "Исследование иатемзтическях основ доказательного программирования и трансформационный синтез іиієссов алгоритмов, программ и програшшых систем".
Апробация. Результаты работы докладывались на 7-й (Киев, 1986) ,8-ы (Киев, 1988), 10-н (Алушта, 1РЭ2) " ссдзшарах "Параллельное програшдировакке и высокопроизводительные системы", на семинарах научногб совета АН Украины по проблеме "Кибернетика".
Публикации. По теме диссертации опубликовано 6 работ.. Структура работы. Диссертационная работа состоит из введения четырех глав, заключения и прилонений.
