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

-. — <->

Московский государственный университет им. М.В.Ломоносова Научно исследовательский вычислительный центр

На правах рукописи

ЕГОРОВ Алексей Александрович

УДК 681.3

ЧИСЛЕННАЯ СЕРТИФИКАЦИЯ АЛГОРИТМОВ И ПРОГРАММ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕГАТ

диссертации на соискание ученой, степени кандидата физико-математических наук

МОСКВА 1995

Работа выполнена в Институте вычислительной математик Российской академии наук

Научный руководитель:

доктор физико-математических наук Е.Е.ТЫРТЫШНИК01 Официальные оппоненты:

доктор технических наук, профессор О.Б.АРУШАНЯН кандидат физико-математических наук Ю.М.НЕЧЕПУРЕН

Ведущая организация:

Институт системного программирования РАН

Защита состоится " ^ " _1995 года СУ/1 "

на заседании диссертационного совета К.053.05.84 по адрес] 119889, Москва, ГСП, Ленинские горы, НИВЦ МГУ.

С диссертацией можно ознакомиться в библиотеке НИВЦ N

Автореферат разослан "_" __1995 года.

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

М.Н. ки

Общая характеристика работы

Актуальность темы.

Численное программное обеспечение, производящееся в огромных количествах, должно быть достаточно надежным II эффективным, так как часто используется для принятия довольно ответственных решений. Но, в типичной ситуации, математик-вычислитель приступает к написанию программы в условиях немалой теоретической неопределенности в отношении структурных и численных свойств выбранного алгоритма. Что же является гарантией качества? Такую гарантию может дать только опыт практической эксплуатации. Но практической эксплуатации предшествует период "эксплуатации" исследовательской. Действуя как физики- экспериментаторы, мы можем и должны ставить задачу об экспериментальном изучении свойств наших алгоритмов. Таким образом мы приходим к проблеме численной сертификации алгоритмов и программ.

Цели диссертации.

1. Выработка концепции для основных частей проблемы сертификации.

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

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

Построена концепция основных частей проблемы сертификации.

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

Разработан аппарат получения аналитических формул для характс ристик графа алгоритма и некоторых машиннонезавпсимых характ« ристик реализующей его программы, избавляющий математика от р\ тинных теоретических выкладок.

Исследована проблема адекватности машинных п математически тестов, разработан подход для построения тестов, точных в машпнно арифметике, п предложен способ "лечения"тестов.

Разработаны гибкие и простые средства для моделирования машш ной арифметики.

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

Апробация работы. Результаты диссертации обсуждались на с( минарах Института вычислительной математики РАН (Москва, 199^ 95), докладывались на заседании Ученого совета Института вы чист тельной математики (Москва, 1995), на научно-исследовательском с( минаре Института системного программирования РАН и на семиш ре НИВЦ МГУ " Современные проблемы численного анализа" (Москв; 1995).

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

Структура и объем диссертации. Диссертация состоит из вв< дения, трех глав, заключения, списка литературы (48 наименованиг и приложения; изложена на 105 страницах и включает 2 рисунка и таблиц.

Содержание работы

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

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

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

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

Более точно, с алгоритмом связано семейство графов, для которого параметрами являются так называемые "размерные" переменные. На-

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

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

В разделе 1.3 описано использование программной утилиты, разр; ботанной автором, для перевода программы на Фортране в представ» ние с вызовами соответствующих процедур трассировки. Исиользов! ние этой утилиты избавляет пользователя от рутинного переппсываш: исследуемой программы.

В разделе 1.4 описывается метод нахождения формул для характ ристик графа, для случая одной размерной переменной, методом миш мальных невязок. Решение ищем в виде: 5(?г) = с1а,(п), где а,(г — некоторые базисные функции, а сь ..., сь — искомые коэффициент разложения. В качестве базисных функций разумно взять функции виг {пЧп> о, так как это годится для большого количества численны алгоритмов.

В разделе 1.5 приведены примеры формул для характеристик г р. фа алгоритма для программ из пакетов по линейной алгебре ЬАРАС1 ЪШРАСК и др. Сравниваются теоретические оценки и данные, пол; ченные методом трассировки.

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

В разделе 2.1 описано представление чисел с плавающей точкой пр длине мантиссы в в системе счисления с основанием Ь. Это множест! обозначим через р(ь, а). Рассматриваются основные способы округл ния чисел.

В разделе 2.2 описана концепция моделирования машинной арифметики. Под арифметикой компьютера понимается упорядоченное множество {-Р1, {/¿}°=о, {с;}^_0, X}, где Р — множество чисел, /,• : Г*- -> Г — функции на этом множестве, с, £ — выделенные константы множества Р, а X — множество аксиом машинной арифметики. Множеством чисел модельной арифметики будем считать = -Г5(&, я)и{и, о, г}, где ь - длина мантиссы сумматора (дополнительного устройства, на котором проводятся вычисления), а и, о, г — выделенные константы, имеющие смысл машинного нуля, машинной бесконечности и неопределенности. В этом же разделе определены функции отображения результата из сумматора в обычное представление, зависящие от типа аргументов элементарной операции. Если хотя бы один аргумент бинарной операции является выделенной константой, то результат операции определяют аксиомы арифметики. Например, х * 0 = О, х*оо = оо.

Далее описано программное представление чисел машинной арифметики в пакете моделирования арифметики "УМА (как массива целых чисел). Приведены алгоритмы сложения, умножения и деления чисел модельной арифметики. Указан способ изменения алгоритма округления в модельной арифметике. Приведен пример набора аксиом машинной арифметики и указан способ модификации аксиом модельной арифметики.

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

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

В разделе 3.1 приведено формальное описание предметной области — объектов линейной алгебры, задач, тестов. На абстрактном уровне это означает создание каталога объектов, снабженных набором атрибутов. Как сами объекты, так и возможные атрибуты имеют определенную иерархическую структуру. Эта формализация используется для построения базы данных и информационно-поисковой системы для предметной области — линейной алгебры.

В разделе 3.2 исследуется еще одна важная часть проблемы сертифи кации алгоритмов и программ — тестирование алгоритма на разны: тестах на фиксированной ЭВМ. Ядром тестирования служит при это! банк тестов. Банк тестов является набором текстов подпрограмм, на писанных на языке Фортран, каждая из которых по заданным характе ристпкам строит тестовые наборы данных.

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

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

Эта проблема проиллюстрирована на примере задачи решения систе мы линейных алгебраических уравнений с матрицей Гильберта. Оче видно, мы не можем точно ввести в машину ни компоненты самой ма трицы Гильберта, ни компоненты вектора правой части. Следователь но, вместо математически точной системы в компьютере возникне: "машинная" система, а вместо идеального - машинный тест. Тепер] мы не можем утверждать, что математическое решение и точное реше ние машинной системы близки, так как матрица Гильберта суперпло хо обусловлена, и тогда бессмысленно сравнивать решение, полученно! какой—либо аттестуемой программой, с тестовым решением.

Для проверки этой гипотезы был проведен эксперимент: систем, уравнений была решена программой на языке Фортран с двойной точно стью. При сравнении с якобы точным решением была получена огром

— < —

ная относительная погрешность. Затем было получено "точное"' решение машинной системы (было использовано вычисление в модельной арифметике с достаточно большой длиной мантиссы). И как оказалось, настоящая относительная ошибка вполне приемлема.

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

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

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

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

1. Интерфейс пакета УМА, моделирующего машинную арифметику.

2. Работа с утилитой РР конвертирования текстов программ на Фортране.

3. Интерфейс нескольких матричных генераторов.

4. Работа с программой визуализации объектов линейной алгебры.

5. Интерфейс графического пакета программ на Фортране визуализации объектов линейной алгебры.

Основные результаты

Построена концепция проблемы численной сертификации алгоритм« и программ, на основе которой разработаны программные средства д; получения характеристик графа алгоритма методом трассировки р ализующей его программы и разработаны библиотеки программ äj исследования поведения алгоритма на разных тестовых данных и ра личных параметрах машинной арифметики.

Публикации по теме диссертации

1. Егоров A.A. Инструментальные средства численной сертифик ■ции алгоритмов и программ // Научная апробация выпускник! Высшей компьютерной школы.- М.: Изд-во МГУ, 1995.

2. Тыртышников Е.Е., Егоров A.A. Численная сертификация алг ритмов и программ // Матричные методы и алгоритмы.- М.: Iffi РАН, 1993.