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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М.В. КЕЛДЫША

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

ФРОЛОВ АНДРЕЙ ПЕТРОВИЧ

АВТОМАТИЗАЦИЯ ПРОГРАММИРОВАНИЯ ВЫЧИСЛЕНИЙ НАД ВЕЩЕСТВЕННЫМИ ЧИСЛАМИ ПОСРЕДСТВОМ ОПЕРАЦИЙ ЦЕЛОЧИСЛЕННОЙ АРИФМЕТИКИ

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

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

Москва 1997

Г0

О л

у 3 ФЕО 1Й?7

Работа выполнена в Институте Прикладной Математики им. М.В. Келдыша РАН.

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

кандидат физико-математических наук Эйсымонт Леонид Константинович.

Официальные оппоненты:

доктор физико-математических наук, профессор Платонов Александр Константинович, кандидат физико-математических наук, доцент Бычков Сергей Павлович.

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

Научно-Лроизводственное Объединение Автоматики и Приборостроения,

Защита состоится "_"_19Э_г. в _часов на заседании диссертационного совета Д 002.40.01 при ИПМ им. М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4., Гл. корпус, Конференц-зал.

С диссертацией можно ознакомиться в читальном зале библиотеки ИПМ им. М.В. Келдыша РАН.

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

Ученый секретарь диссертационного Совета,

кандидат физико-математических наук

Т.А.Полилова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В данной работе предлагается решение проблемы реализации вычислений над вещественными числами на ЭВМ посредством операций целочисленной арифметики. Излагаемый в данной работе материал является одним из результатов, полученных при выполнении комплекса работ по созданию системы программирования языка Пси-Фортран для управляющей СЦВМ космического корабля многоразового использования "Буран".

Предлагаемые методы использования целочисленной арифметики для выполнения действий с вещественными числами актуальны для управляющих СЦВГИ, в которых отсутствует аппаратная реализация операций над числами с фиксированной точкой. В современных условиях актуальность этих методов не становится меньше, это объясняется спецификой использования СЦВМ, наиболее выгодными возможностями их усовершенствования в связи с развитием элементной базы. Кроме того, данные методы чрезвычайно важны при создании программного обеспечения для современных высокоскоростных процессоров с побитовой обработкой информации и мультиконвейерных микропроцессоров. В частности, в настоящее время предложенные методы используются при разработке прграммного обеспечения отечественной мультипроцессорной суперЭВМ, а также оптоэлектронной суперЭВМ с массовым параллелизмом.

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

1. Создание алгоритмических основ построения системы автоматического масштабирования.

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

Научная новизна. В процессе решения поставленных задач получены новые научные результаты, которые выносятся на защиту:

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

2. Разработан алгоритм оптимального выбора масштабов для операций над масштабированными числами в пределах выражения.

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

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

5. Разработана интегрированная система для интервального анализа программ.

6. Предложена технология разработки масштабированных программ. Практическая ценность. Предложенные алгоритмы масштабирования и интервального анализа применялись в системах программирования для языков Пси-Фортран, С-Фортран, СЗ-Фортран, СЗХ-Фортран, использовавшихся при разработке систем космической и авиационной техники. В настоящее время они применяются при разработке ряда компиляторов для перспективных отечественных супер-ЭВМ и высокопроизводительных микропроцессоров.

Апробация работы. Результаты диссертации докладывались на семинаре в ИПМ им. М.В. Келдыша РАИ (под рук. проф. А.К. Платонова), на семинарах в МГУ им. М.В. Ломоносова (под рук. академика РАН Д.Е. Охоцимского и под рук. проф. М.Р. Шура-Бура), на всесоюзной школе по проблемам математического обеспечения и архитектуры БЦВМ (Ташкент, 1988), на конференции "Интервальная математика" (Саратов, 1989).

Структура диссертации, публикации. Диссертация состоит из введения трех глав и заключения. Работа изложена на 199 страницах, содержит 18 рисунков и 4 таблицы. Список литературы содержит 46 наименований. Основные результаты опубликованы в работах [1 -6 ].

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе сначала приводится краткий обзор предшествоваших работ по масштабированию. Затем дается общее рассмотрение предлагаемого в диссертационной работе подхода.

Суть предлагаемого подхода.

При отображении вещественных чисел в ЭВМ обычно используется какой-либо из двух методов:

• отображение с фиксированной относительной погрешностью;

• отображение с фиксированной абсолютной погрешностью.

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

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

При использовании метода отображения с фиксированной абсолютной погрешностью в ЭВМ обычно используется формат представления чисел с фиксированной точкой. Фиксированная точка может располагаться слева от числа, тогда работа ведется с числами, по модулю меньшими 1, либо справа -тогда работа производится с целыми числами. В данной работе используется представление целыми числами.

Целое число, представляющее в ЭВМ вещественное число, называется далее масштабированным числом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее рассматривается формализация масштабированных чисел и алгоритмические основы масштабирования.

Определение 1. Пусть задано положительное вещественное число X и некоторое вещественное число ех. Масштабированной формой представления числа X с точностью не хуже (масштабированным числом) будем называть любое целое число У. удовлетворяющее неравенствам:

|Х-У*р1 <Е)<

М2.*¥ < ех

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

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

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

Обычно в качестве ех берется половина единицы наименьшей значащей цифры числа X, если не применяется явное задание с*.

Из определения 1 видно, что физический смысл Р - это цена младшего разряда масштабированного представления X,

Определим максимальное и минимальное значение Р при условии, что V должно размещаться в разрядной сетке Ь ( без учета знакового разряда).

Расчет максимального значения Р следует из определения 1:

Р|мдх = 2*с:< (1)

Минимальное значение Р определяется используемой разрядной сеткой. Если задана разрядная сетка I, то ясно, что

М<21-1 (2)

таким образом:

|х|/РМ!ы =21-1 (3)

Рм,ы= !Х|/(21-1) (4)

Минимальное количество двоичных разрядов, Ьу, необходимых для представления X в виде масштабированного числа У, можно получить, используя неравенство (2) и максимальное значение масштабного множителя, равное 2*ех:

|х|/(2ч,11)£21у-1 (5)

Следует помнить, что должно быть меньше или равно L. Если это не так, то число X непредставимо в разрядной сетке I. с предельной абсолютной погрешностью ех. Таким образом, имеем дополнительное условие:

Ьу (6)

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

Далее будем использовать следующие обозначения. Пусть А - некоторое вещественное число, тогда 1а1 - обозначает максимальное целое, не превосходящее заданное число А, Га] - обозначает минимальное целое, не меньшее, чем заданное число А.

Пусть теперь Рмах =2их, а Р^ы =22', тогда 11* и 5Х могут быть получены соответственно из (1) и (4) следующим образом:

их=1Лод2£х >1 Эх =Г1од2( | X | /(2й-1))]

(7)

(8)

где 1)х - максимально допустимый масштаб, Эх - минимально допустимый масштаб.

Использование целочисленных приближений в неравенствах (7) и (8) означает, что выбираются предельные значения 1)х и Эх, при которых

2и*<Рмдх .

Определение 3. Пусть имеется максимально допустимый масштаб 1)х и минимально допустимый масштаб Эх, тогда множество целых чисел от Эх до их, обозначаемое [6х, их], будем называть диапазоном масштабов.

Выбирая значения масштабов из диапазона [Эх, их], можно получить все допустимые представления числа X для разрядной сетки при которых не теряются его верные значащие цифры. Если масштаб числа X будет выбран большим, чем их, то это означает, что в масштабированной форме X представляется недостаточно точно - теряются младшие разряды X (потеря точности). Если же масштаб числа X меньше Эх, то это означает, что теряются старшие разряды X (потеря значимости). В определенном смысле диапазон масштабов является аналогом диапазона порядка числа с плавающей точкой. Только он явно не хранится в памяти машины, с ним работает лишь компилятор.

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

Такое равенство полезно на практике для контроля правильности расчетов 1-у, 11х И в);.

Выше была рассмотрена техника масштабирования для двоичных масштабирующих коэффициентов, т.е. когда £=2". Такие коэффициенты используются на практике в подавляющем числе случаев. Это объясняется тем, что при таких масштабах операция перемасштабирования - это просто сдвиг масштабированного представления влево или вправо.

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

Ух-Бх = I. -1_¥

(9)

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

Обработка масштабированных недвоичными масштабами чисел обычно производится каким либо из двух способов:

1. Если такие числа участвуют далее в интенсивных вычислениях, то происходит предварительное перемасштабирование этих чисел к двоичным масштабам.

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

Выше было рассмотрено понятие масштабированного числа. Основываясь на этом понятии, далее рассмотрим понятие масштабированного типа данных. Масштабированный тип данных - это новый тип, который могут иметь переменные масштабированной программы. Такие переменные будем называть масштабированными переменными в отличие от переменных других типов (integer, real и т.д.).

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

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

В общем случае при задании масштабированного типа задаются следующие атрибуты:

1. Множество вещественных чисел, отображаемых данным масштабируемым типом. Это множество задается нижней и верхней границей диапазона вещественных чисел, которые будем далее обозначать соответственно Xmin и

ХмАХ-

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

3. Разрядная сетка, в которой допускается размещать масштабированные числа, обозначим ее L.

4. Масштаб масштабированных чисел. Если масштаб явно не задается, то он выбирается по умолчанию.

Перечисленные атрибуты используются при вычислении Эх и их масштабированного типа с использованием соотношений (1)-(9), в которых вместо X в данном случае подставляются МАХ( | Хм,м |, | ХМАХI).

Переменные масштабированного типа описываются обычным образом -вводится переменная и с ней связывается масштабируемый тип. Множество операций для масштабированного типа - это: •бинарные арифметические операции (+,-,*,/); •унарные операции (-.аЬэ); •операции сравнения (<, = ,>,=£,>,<); •операция присваивания. Кроме того, имеется ряд встроенных функций.

Далее в работе описываются правила выполнения операций для масштабированного типа.

Алгоритм масштабирования отдельной арифметической операции.

Постановка задачи

Пусть имеется арифметическая операция ^, представляющая собой сложение, вычитание, умножение или деление над операндами X и У. Получаемый результат операции помещается в переменную Т.

Допустимые диапазоны изменения масштабов X, У и г суть [Бх.их], [Эу.иу], [52,и2], масштабы X, У, г равны соответственно Мх, Му, Мг.

Назовем исполнительными масштабами масштабы Мх', Му' и М2', которые используются для непосредственного выполнения операции г=Х#У. Эти масштабы могут отличаться от Мх, Му, Мг , но не приводят к потере точности или значимости как при перемасштабировании операндов и результата, так и при выполнении операции.

Введем также следующие соотношения: • Мх' = Мх + Му' = Му + Оу

Мг' = М2 + 0г

Величины Ох, [)у и О? будем называть сдвигами масштабов. Для операции # необходимо определить такие 0Х, Оу и что Мх', Му' и Мг', лежали бы в допустимых диапазонах изменения масштабов, а сумма I О* I +1 Оу | +1 Ог | принимала бы минимальное значение.

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

Сложение и вычитание.

Мг' = Мх' = Му

Умножение.

Мг' = Мх' + Му'

Деление.

Мг' = Мх' - Му'

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

Лемма 1. Для выполнимой операции сложения или вычитания масштабированных величин, представленных в одинаковых разрядных сетках 1_, справедливо неравенство:

Зг<МАХ(5х,Зу)+1

Лемма 2. Для выполнимой операции сложения или вычитания масштабированных величин справедливы неравенства:

Мх <и2

Му<и*

Доказательство данных лемм содержится в тексте диссертации.

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

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

Алгоритм масштабирования выражения.

Постановка задачи. Дано арифметическое выражение У=Р(Х1.....Хм), содержащее N переменных и К арифметических операций. Заданы допустимые диапазоны масштабов и масштабы всех переменных выражения - [Б,,^], М, (¡=1,...,1М), а также диапазон допустимых масштабов результата [Зу,1)у] и масштаб результата Му. Также имеются полученные при помощи интервальной

арифметики и арифметики ошибок допустимые диапазоны масштабов для всех результатов арифметических операций - (¡=1 ,.,К).

Требуется найти для каждой из К арифметических операций исполнительные масштабы Мх', М-/ и М?/ (масштабы операндов и результата), которые бы были оптимальны в смысле обеспечения минимума некоторой весовой функции, выражающей суммарное время на перемасштабирование при выполнении всего арифметического выражения.

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

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

Задача выбора оптимального сочетания исполнительных масштабов может быть сведена к поиску кратчайшего пути в некоторой сети. Такая сеть образуется ярусами вершин, каждый ярус соответствует выбираемому исполнительному масштабу результата некоторого подвыражения, содержит столько вершин, сколько значений может принимать данный исполнительный масштаб. Ребра этой сети помечены весами, отражающими затраты на перемасштабирование, связанные с использованием исполнительных масштабов вершин. Исток соответствует исходным масштабам операндов, а сток - всем выбранным масштабам.

Первоначально были использован именно такой подход к построению сети выбора вариантов. Для поиска кратчайшего пути был разработан алгоритм на основе известного алгоритма Ли. Особенность сети не позволила применить во всех ее вершинах свойство алгоритма Ли - фильтрацию, связанную с удалением вариантов путей, которые являются худшими уже для заданной вершины. В связи с этим оценка временной сложности оказалась близкой к С", где С - количество вариантов масштабов в вершине, а п - количество операций. Если считать, что Сип равны 5, то в худшем случае при поиске варианта масштабирования придется запустить базовые алгоритмы~3*10э раз, а при п=10 ~107 раз, тем не менее, данный алгоритм, некоторое время использовался в практически применяемом компиляторе. Отсутствие свойства фильтрации всех

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

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

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

Приведем общее описание алгоритма поиска в древовидной сети выбора масштабов.

Шаг алгоритма.

На очередном шаге алгоритма, при обработке очередной операции (т.е яруса сети) для каждого масштаба из диапазона масштабов результата находится взвешенный список масштабов (F, Mz, Мх, Му, IVI'z, М'х, M'y), содержащий значение весовой функции, масштабы операндов и результата и исполнительные масштабы операндов и результата.

Построение производится следующим образом. Для каждого Mz из очередной вершины перебираются все возможные значения вершин - потомков данной вершины в дереве (операндов) Мх и Му. Далее для каждой тройки Mz, Мх, My выполняется базовый алгоритм масштабирования, который определяет исполнительные масштабы M'z, М'х, M'y. На их основе рассчитывается значение весовой функции F, которая равна сумме приращения, вызываемого выбором данных исполнительных масштабов (см. ниже), а также Fx и Fy - значений весовой функции, для фиксированных масштабов операндов Мх и Му, полученных из списков масштабов предыдущих операций (результаты которых являются для данной операции операндами). Далее из построенного взвешенного списка выбираются Мх и Му, дающие минимальное значение функции F. Вы-

бранный элемент списка оптимальных масштабов запоминается в вершине яруса, соответствующей Мг.

Окончание работы алгоритма.

После обработки всех операции выражения, оказываются определенными взвешенные списки масштабов для каждой операции дерева разбора.

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

Расчет приращения весовой функции.

Приращение весовой функции на шаге алгоритма определяется так:

гдеДрх. АруиДРг - приращение веса, связанное с изменением масштабов операндов от исходных к исполнительным и масштаба результата от исполнительного к заданному (временные затраты на выполнение команд перемасштабирования).

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

Приращение 51дп(| АРх| )=0, если величина Др*= 0, т.е. не производится перемасштабирование, в противном случае равна 1. Эти слагаемые введены для учета количества команд сдвига. Конец алгоритма.

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

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

Если Сип равны 5, то для выбора масштабов потребуется произвести 625 запусков базовых алгоритмов (в 5 раз меньше, чем в первоначальном варианте), при п=10 - 1250 (в 104 раз меньше). Разработанный алгоритм обеспечил вполне приемлемую скорость трансляции на практике.

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

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

- исполняемым комментариям;

- встроенным функциям.

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

Исполняемые комментарии.

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

Рассмотрим пункты исполняемых комментариев более подробно.

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

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

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

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

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

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

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

Разработка компилятора со встроенными алгоритмами автоматического выбора масштабов производилась в два этапа. Сначала была разработана версия компилятора без масштабирования, далее в него была введена обработка масштабированных типов и алгоритмы автоматического выбора масштабов.

Введение аппарата автоматического масштабирования в компилятор потребовало его усложнения:

1. В вершины дерева разбора были введены дополнительные атрибуты -границы диапазона масштабов масштабированного типа и текущий масштаб.

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

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

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

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

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

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

Практика показала, что характеристики программ, полученных "впрямую" и оптимизированных по предлагаемой технологии, отличаются в 1.5-2 раза.

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

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

Был выбран метод выполнения программы в режиме интерпретации при помощи интервальной арифметики. Этот метод реализован в виде специального средства, называемого интервальным анализатором.

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

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

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

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

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

Использование в анализаторе интервальной арифметики ставит ряд проблем, связанных с выполнением операций сравнения, индексирования и битовых операций применительно к интервалам.

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

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

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

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

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

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

Если полученный модуль странслировать, то получится отмасштабиро-ванная объектная программа.

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

8 интервальном анализаторе используется арифметика 64-разрядных чисел с плавающей точкой. Для повышения точности вычислений введена также возможность выполнения арифметических операций над машинными числами с управляемой разрядностью (длина мантиссы до 999 десятичных знаков). Арифметические операции над числами с управляемой разрядностью выполняются программно, поэтому скорость вычислений существенно зависит от длины мантиссы; чем длиннее мантисса, тем медленнее выполнение операций.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

2. Разработан алгоритм оптимального выбора масштабов для операций над масштабированными числами в пределах выражения.

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

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

5. Разработана интегрированная систем.а для интервального анализа программ.

6. Предложена технология разработки масштабированных программ.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Задыхайло И.Б., Перегудов В.Г., Фролов А.П., Эйсымонт Л.К. "О проблеме реализации масштабирования в специализированных ЭВМ, ориентированных на языки высокого уровня". Препринт ИПМ им. М.В. Келдыша АН СССР, 1985, N172.

2. Эйсымонт Л.К., Перегудов В.Г., Фролов А.П., Шестаков А.Е. "Эскизный проект системы ПСИ-Фортран, предназначенной для сокращения сроков разработки управляющих программ и повышения их надежности", Отчет ИПМ АН СССР 0-345-87, Москва, 1986.

3. Эйсымонт Л.К, Фролов А.П. "Технология изготовления отдельного модуля на языке ПСИ-Фортран", Отчет ИПМ АН СССР 0-1238, Москва, 1986.

4. Эйсымонт Л.К., Фролов А.П. "Интервальный анализатор языка ПСИ-Фортран", Отчет ИПМ АН СССР 0-313-87, Москва, 1987.

5. Эйсымонт Л.К., Перегудов В.Г., Шестаков А.Е., Фролов А.П. Инструментальная система Пси-Фортран. Материалы Всесоюзной школы по проблемам мат. обеспечения и архитектуры БЦВМ, Ташкент., 1988, с. 97-98.

6. Фролов А.П. Функциональный анализатор языков СЗ-Фортран и Пси-Фортран. Конф. "Интервальная математика", Саратов, 23-25 мая, 1989. с. 5758.