Проблемно-ориентированная система для матричных вычислений тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. ВОПРОСЫ ПОСТРОЕНИЯ АВТОМАТИЗИРОВАННЫХ СРЕДСТВ

ДОСТУПА К КОМПЛЕКСАМ ПРОГРАММ.

1.1. Принципы конструирования проблемно-ориентированных систем.

1.2. Обзор проблемно-ориентированных языков для вычислительных задач.

1.3. Требования к разрабатываемой системе МОСТ.

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

2.1. Характерные особенности языка МОСТ.

2.2. Базовые конструкции входного языка.

2.2.1. Словарь языка

2.2.2. Имена и числа.

2.2.3. Определение констант

2.2.4. Тип данных. Описания и обозначения переменных

2.2.5. Выражения.

2.2.6. Макросредства.

2.2.7. Предложения действий.

2.2.8. Предложения решения задачи.

2.2.9. Комментарии

2.3. Подпрограммы на языке МОСТ.

2.4. Аппарат расширения - спецпрограммы.

2.4.1. Унифицированный список параметров спецпрограммы

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

2.4.3. Диагностика ошибок в спецпрограммах.

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

2.5» Взаимодействие с языком ФОРТРАН.

2.5.1. Вызов фортранных подпрограмм.

2.5*2. Использование языка МОСТ при проведении расчетов на языке ФОРТРАН

2.6. Ввод-вывод.

2.7. Режим использования языка.

2.8. Архивы данных и подпрограмм.

ГЛАВА 3. ОРГАНИЗАЦИЯ ПРОБЛЕШО-ОРИЕНТИР ОБАННСЙ СИСТЕМЫ МОСТ

3.1. Общая структура системы МОСТ.

3.2. Трансляция языка МОСТ в рабочую программу.

3.2.1. Структура рабочей программы и информационных массивов анализатора.

3.2.2. Обработка предложений языка.

3.3. Динамическое распределение памяти

3.4. Средства выполнения рабочей программы

3.4.1. Интерпретация выражений. Управление размещением данных.

3.4.2. Организация вызовов спецпрограмм и произвольных фортрандах программ

3.4.3. Организация взаимодействия подпрограмм на языке МОСТ.

3.4.4. Организация вызова программ МОСТ из фортранных программ

3.5. Базирование на специализированных библиотеках и комплексах программ.

3.6. Применение системы МОСТ

3.6.1. Опыт использования системы.

3.6.2. Области приложения системы.

ЗАКШЕНИЕ

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

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

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

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

Проблемно-ориентированная система МОСТ реализована на ЭВМ БЭСМ-6 в рамках мониторной системы "Дубна" и операционной системы ДЙСПАК. Программное обеспечение системы написано, в основном, на языке ФОРТРАН, Общий объем реализованного программного обеспечения составляет около 5350 операторов языка ФОРТРАН и около 50 команд автокода МАДЛЕН. Работа проводилась по госбоджетной теме В 8I0492I4 в рамках целевой комплексной научно-технической программы 0.Ц.027, задание 0.5.01, выполняемой по постановлению ГКНТ СССР, ГОСПЛАНа и АН СССР от 12 декабря 1980 г. № 474/250/132.

Система МОСТ включает следующие основные компоненты: функциональное наполнение, входной язык, системное наполнение. Базой для функционального наполнения системы является Библиотека численного анализа на ФОРТРАНЕ, разработанная НИВЦ МГУ ГШ . Входной язык системы представляет собой независимый проблемно-ориентированный язык высокого уровня, удовлетворяющий требованиям к проблемно-ориентированной системе, указанным выше. Системное наполнение организовано в соответствии с принципом модульного программирования и представляет собой комплекс взаимодействующих программных блоков, управляемых монитором. К этим блокам относятся: блок обмена, цроцессор языка МОСТ, процессор спецпрограмм, блок обучения, блок управления архивом пользователя, блок обработки ошибок. Блок обмена обеспечивает работу системы в диалоговом и пакетном режимах. Процессор языка МОСТ организован в виде совокупности транслятора и интерпретатора. Транслятор преобразует исходную программу на языке МОСТ в промежуточное представление - рабочую программу, подлежащее выполнению интерпретатором. Обеспечивается разделение, при необходимости, этапов трансляции и интерпретации во времени, т.е. образование библиотек программ во внутреннем представлении. Интерпретатор осуществляет анализ и выполнение рабочей программы, реализуя при этом специфицированные связи между объектами программы, выполняя все необходимые динамические проверки, размещение и утилизацию временных объектов и определение целевых объектов. Процессор спецпрограмм составляют интерфейсные программы, обеспечивающие взаимодействие процессора языка МОСТ с независимой библиотекой спецпрограмм как средство расширения входного языка системы без изменения языкового процессора. Блок обучения предназначен для знакомства со структурами данных входного языка, операций над ними, с правилами и приемами работы с системой. Блок управления архивом пользователя обеспечивает создание и использование личных библиотек программ на входном или промежуточном языках системы МОСТ и работу личного архива данных. Блок обработки ошибок обеспечивает детальную диагностику ошибок пользователю. Система МОСТ предусматривает использование штатного программного обеспечения ЭВМ БЭСМ-6, например, терминальной системы КРАБ.

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

Разработаны и реализованы механизма взаимодействия программ на языке МОСТ и независимого программного обеспечения на языке ФОРТРАН. Данные механизмы обеспечивают простое управление режимами спользования подпрограмм на языке МОСТ, допускают как вызов из про-рамм МОСТ произвольных фортранных программ; так и обращение к сис~ еме МОСТ из программ на языке ФОРТРАН. Предложены принципы приме-ения системы в качестве инструментально-базового средства для по-троения пакетов программ различных разделов численного анализа на снове базовой библиотеки»

Практическая ценность работы состоит в реализации программноо> обеспечения проблемно-ориентированной системы МОСТ для матричных вычислений, предназначенной для работы на ЭВМ БЭСМ-6, и разработке на его основе программ решения задач численного анализа для ирокого круга пользователей. Достоинством системы МОСТ в примене-ии к решению задач численного анализа является ее способность су-;ественио уменьшить суммарные затраты на создание и выполнение рограмм, использующих матричные операции. С использованием систе-ы МОСТ, например, был реализован модифицированный марш-алгоритм ешения разностной задачи Дирихле для уравнения Пуассона в прямо-гольнике, получены сравнительные оценки с реализацией на языке 'ОРТРАН.

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

Объем работы. Диссертация состоит из введения, трех глав,

ЗАКЛЮЧЕНИЕ

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

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

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

3. Предложен и обоснован метод реализации входного проблемно-ориентированного языка системы в виде независимого процессора. На основе этого метода на ЭВМ БЭСМ-6 выполнена реализация разработанного языка высокого уровня, которая обеспечила опытную эксплуатацию проблемно-ориентированной системы МОСТ на факультете ВМиК МГУ и в НИВЦ МГУ. Данная реализация обеспечивает расширение языка в указанном выше смысле и применение языка в пакетном и диалоговом режимах.

4. Разработаны и реализованы механизмы взаимодействия программ на языке МОСТ и независимого программного обеспечения на языке ФОР-ГРАН. Данные механизмы обеспечивают гибкое управление режимами использования системы МОСТ при проведении вычислительных расчетов -допускают как вызов из программ МОСТ произвольных фортранных программ, так и обращение к системе МОСТ из программ на языке ФОРТРАН.

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

1. Арушанян О.Б. Центральные проблемы конструирования библиотек программ общего назначения, - В сб. Библиотеки программ. Архитектура и наполнение. - М.: Изд-во Моск. ун-та, 1981, с.3-27.

2. Бабаев И.О., Новиков Ф.А., Петрушина Т.И. Язык Декарт входной язык системы СПОРА. - Прикладная информатика, 1981, № I.

3. Баула В.Г., Гайсарян С.С. Генератор программ: специализированная система программирования. В сб. Численный анализ на ФОРТРАНе, Вып. 8. - М.: Изд-во Моск. ун-та, 1974.

4. Бежанова М.М. Входные языки пакетов прикладных программ. Новосибирск, 1979 (Препринт ВЦ СО АН СССР, № 168).

5. Бежанова М.М. Встроенные проблемно-ориентированные системы. -Новосибирск, 1979 (Препринт ВЦ СО АН СССР, № 205).

6. Бежанова М.М. Пакеты прикладных программ. Новосибирск, 1983.

7. Бежанова М.М. Анализирующая система решения задач на ЭВМ. В кн. Некоторые проблемы вычислительной и прикладной математики.-Новосибирск: Наука, 1975, с. 263 - 272.

8. Бежанова М.М., Москвина Л.А. Система построения и функционирования пакетов прикладных программ. Программирование, 1982, $ 2, с. 59-63.

9. Библиотека программ для решения сеточных уравнений. М.: Изд-во Моск. ун-та, 1984.

10. Богомолов Н.А., Ламзина Т.В. Работа на ФОРТРАНе с двоичной, текстовой и адресной информацией. В сб. Вопросы конструирования библиотек программ. - М.: Изд-во Моск. ун-та, 1980,с. 68-76.

11. Борисов В.М. Методика разработки проблемно-ориентированных языков на примере языка EIGEN. В сб. Автоматизация конструирования библиотек программ. - М.: Изд-во Моск. ун-та, 1979, с.57-71.

12. Веретенов В.Ю. Работа с внешней памятью как устройством прямого доступа в МС "Дубна". М., 1972 (Препринт ИАЭ им.Курчатова).

13. Воеводин В.В. Численные методы алгебры. Теория и алгорифмы. -М.: Наука, 1966.

14. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.

15. Воеводин В.В., Кузнецов Ю.В. Матрицы и вычисления. M.t Наука, 1984.

16. Воеводин В.В., Арушанян О.Б. Структура и организация Библиотеки численного анализа НИЩ МГУ. В сб.: Численный анализ на ФОРТРАНЕ. Вычислительные методы и инструментальные системы. - М.: Изд-во Моск. ун-та, 1979.

17. Глушков В.М. Введение в АСУ. К.: Техника, 1972.

18. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

19. Ершов А.П., Ильин В.П. Пакеты программ технология решения прикладных задач. - Новосибирск, 1978 (Препринт ВЦ СО АН СССР,121..

20. Залеткин С.Ф. Полиалгоритм автоматизированного решения обыкновенных дифференциальных уравнений. В сб. Автоматизация конструирования библиотек программ. - М.: Изд-во Моск. ун-та, 1979, с. 78-97.

21. Интегрированная система программирования. Под общей редакцией Тамма Б.Г. Тр. Ин-та электронных управляющих машин, 1974, вып. 43.

22. Калорин И.Е. Модифицированный марш-алгоритм решения разностной задачи Дирихле для уравнения Пуассона в прямоугольнике. В сб. Разностные методы математической физики. - М.: Изд-во Моск. ун-та, 1980, с. 11-21.

23. Карпов В.Я., Корягин Д.А., Самарский А.А. Принципы разработки пакетов прикладных программ для задач математической физики. -ЖВМ и МФ, 1978, т. 18, № 2, с. 458-467.

24. Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (Приз). М.: Финансы и статистика, 1981.

25. Кнут Д. Искусство программирования для ЭВМ. T.I: Основные алгоритмы. М.: Мир, 1976.

26. В. Козуб Г.Э. Обзор проблемно-ориентированных языков для задач численного анализа. Научный отчет № 3/82. М.: НИВЦ МГУ, 1982.

27. Э. Козуб Г.Э. Проблемно-ориентированный язык широкого назначения для решения задач численного анализа. Научный отчет № 10/82. -М.: НИВЦ МГУ, 1982.

28. Э. Козуб Г.Э. Разработка проблемно-ориентированного языка широкого назначения для решения задач численного анализа. В сб. Методы решения задач математической физики и их программное обеспечение. - М.: Иэд-во Моск. ун-та, 1984, с. III-II3.

29. Е. Козуб Г.Э. Метод организации процессора проблемно-ориентированного языка. В сб. Прикладная математика и математическое обеспечение ЭВМ. - М.: Изд-во Моск. ун-та, 1985, с. 57-59.

30. Козуб Г.Э. Проблемно-ориентированная система MOST для матричных вычислений. В сб. Вопросы конструирования библиотек программ.128.

31. М.: Изд-во Моск. ун-та, 1984, е.72-83.

32. Ко зуб Г.Э. Реализация проблемно-ориентированного языка MOST для матричных вычислений. В сб. Вопросы конструирования библиотек црограмм. - М.: Изд-во Моск. ун-та, 1984, е.,84-94.

33. Козуб Г.Э. Применение цроблемно-ориентированной системы MOST для решения задач численного анализа. В сб. Вопросы конструирования библиотек программ. - М.: Изд-во Моск. ун-та, 1985, 58-65.

34. Корягин Д.А. Об одном подходе к проблеме разработки системного обеспечения пакетов прикладных программ для задач вычислительной физики. Программирование, 1982, № I.

35. Лавров С.С. Синтез программ. Кибернетика, 1982, № 6, с.П-16.

36. Левин Д.Я. Сетл-язык программирования весьма высокого уровня. -Программирование, 1976, № 5, с. 3-9.

37. Левин Д.Я. Система Сетл. Вып. I. Программирование в системе СЕТЛ. Новосибирск, 1978 (Препринт ВЦ СО АН СССР, № 138).

38. Левин Д.Я. Язык сверхвысокого уровня СЕТЛ и его реализация. -Новосибирск: Наука, 1983.

39. Мазный Г.Л. Программирование на БЭСМ-6 в системе "Дубна". М.: Наука, 1978.

40. J. Маргариу Н.А. Язык программирования АПЛ. М.: Радио и связь, 1983.

41. Райе Дд. Матричные вычисления и математическое обеспечение. -М.: Мир, 1984.

42. Юценко Е.А., Перевозчикова О.Л. Об опыте генерации проблемно-ориентированных систем. Кибернетика, 1983, № 4, с. 38-43.

43. Язык программирования АДА (предварительное описание). М.: Финансы и статистика, 1981.

44. Cardenas A.F., Karplus W.J. PDEL a language for partial differential equation. - Comm. ACM, 1970, v.13, N 3, p.184-191.

45. Cohen S., Pieper S.C. The Speakeasy-3 Reference Manual.Level M.U. IBM OS/VS Version. Argonne National Laboratory. Argonne, Illinois, 1977.

46. Goldberg P.C. The Design of Very High Level Languages. In:

47. Comput. Program Synth. Methodol. Proc. Nato. Adv., 1983,p.125-145. 5» Leaunworth B.M., Sammet J.E. Overview of nonprocedural Languages.- SIGPLAN Notices, 1974, v.9, N 4.

48. Khalil U.M., Vlery D.L. LINEAL a System for Numerical Linear Algebra. - The Computer Jornal, 1974, v.17, N 3.

49. Reinfelds J., Eskelson N., Kopetz H., Kratky G. AMTRAH an Interactive Computing System. - In: APIPS Conference Proceedings.- N.J., 1970, v.36, p. 537-541.

50. Rice J.R. On the Constraction of Polialgorithm for Automatic Numerical Analysis. In: Interactive Systems for Experimental Applied Mathematics. - N.J.: Academic Press, 1968,f).301 -313.

51. Rice J.R. A Polialgorithm for Automatic Solution of Non-Linear Equations. Proc. ACM, 24-th National Conf., 1969, p. 179-183.

52. Rice J.R., Rosen S. Napss: A Numerical Analysis Problem Solving System. Proc. ACM, 21-st Nat. Conf., 1966, p. 51-56.

53. Rice J.R. Napss-like Systems. In: Problem Proc. Natl. Сотр. Conf., 1973, p. 43-47.

54. Rice J.R. Survey on programming language facilities for numerical computation. SIGNUM NEWSLETT, 1981, v.16, N 3, p.14-20.

55. Rice J.R. Programming Languages : Power, Trends and Facilities for Numerical Computation. In: The Relationalship between Numerical Computation and Programming Languages. - Proc. IFIP TC 2 Working Conf., Boulder, 1982, p. 3-13.

56. Schesinger S., Sashkin L. POSE: A Language for Posing Problems to a Computer. Comm. ACM, 1967, v.10, N 5, p. 279-285.

57. Smith B.T., Boyle J.M. Matrix eigensystem routines EISPASK quide. - Lect. Notes in Computer Sci., 1974, v.6, p. 387-410.

58. Smith T.A. APL/ЗбО programming and application, 1976.

59. Symes L.R. Manipulation of Data Structures in Napss. In: APIPS Conf. Proc. - N.J., 1970, v.36, p. 157-164.

60. Symes L.R., Roman R.V. Structure of a Language for a Numerical Analysis Problem Solving System. In: ISEAM, 1968, p. 67-68.

61. Symes L.R., Evaluation of Napss Expressions Involving Poli-algorithms, Functions, Recursion and Untyped Variables. In: Mathematical Software, Ed. J.Rice, 1970^ p.261-275.

62. Tutsch J.H. The Use of Very High Level Languages for Numerical Applications. In: 1-st Annu. Phoenix Conf. Comput. and Commun, Silver Spring, 1982, p. 163-167.

63. Vlery L.D., Khalil H.M. A Survey of Language-Oriented Systems for Numerical Linear Algebra. Computer Jornal, 1974, v.17, N 1, p. 82-88.