6

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(Государственный технический университет)

«МАИ»

БЕЛОУСОВ Ю.А.

МАСШТАБИРОВАНИЕ АЛГОРИТМОВ, РЕАЛИЗУЕМЫХ НА МАЛОРАЗРЯДНЫХ ЭВМ С ДРОБНОЙ АРИФМЕТИКОЙ.

Цикл лабораторных работ по курсу

«БОРТОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ И СИСТЕМЫ».

Утверждено на заседании кафедры 304

Москва 2008 г.

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

ВВЕДЕНИЕ

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

где k - разрядность мантиссы числа (k=n-l, n - разрядность ЭВМ, один разряд используется для представления знака числа).

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

1. Основные понятия и определения.

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

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

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

(1)

где: X - значение реальной величины;

- машинное изображение величины X (машинный код);

- масштаб величины X.

Если некоторая величина X изменяется в пределах заданного диапа­зона

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

;

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

Так для того, чтобы машинное изображение с заданной точностью представляло исходную величину X, необходимо выполнение следующего ус­ловия: половина цены единицы младшего разряда изображения не должна пре­вышать значения машинного изображения предельной ошибки представления величины Х (Х):

(1а)

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

; (2)

Если заданна относительная ошибка представления величины Х – δ, то предельная ошибка представления этой величины Х определяется следующим образом:

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

(2а)

Это неравенство можно преобразовать в равенство, приняв в качест­ве и X их максимальные значения и |Х|_mах, т.е. положив, что мак­симальному (абсолютному) значению масштабируемой величины соответству­ет максимальное значение машинного кода:

; (3)

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

рациональным называется масштаб, который удовлетворяет условиям корректности изображений

L  М  Р; (4)

Невыполнение условия М  Р приводит к переполнению разрядной сетки машины (выход за пределы диапазона машинных чисел). Невыполнение условия L  М приводит к потере точности и в конечном счете к искажению изображения, вплоть до его потери - случая "машинного нуля".

Возможны случаи, когда условие корректности изображений при выборе масштаба не может быть выполнено, т.к. получается, что L > Р. Это означает, что данная величина не может быть корректно (условие (4)) представлена в данной разрядной сетке машины. В этом случае необходимо увеличить разрядность слова (например, на m разрядов), что обеспечивает уменьшение левой границы диапазона масштабов в 2^m раз:

L' = L*2^-m

Все последующие операции, в которых используется данная величина, должны выполняться с увеличенной точностью (над операндами с разрядностью мантиссы k+m).

2. Правила выбора и преобразования масштабов.

Масштабы входных переменных и констант выбираются из условий корректности изображений (4) с учетом выражений (2) и (3). С целью обеспечения более высокой точности вычислений конкретное значение масштабов следует выбирать ближе к правой границе диапазона - Р.

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

Если выполняется некоторая арифметическая операция  над исходными операндами А и В, представленными в машине своими изображениями и с помощью масштабов и ( ),то результат этой операции (С = А  В) будет представлен в машине своим изображением, которое вычисляется по формуле =  , а масштаб результата определяется в зависимости от типа операции по следующим правилам:

а) для операции сложения, вычитания:

= = (5)

(при сложении и вычитании масштабы операндов должны быть равны между собой, масштаб результата равен масштабу операндов).

Если при сложении-вычитании операнды А и В являются исходными величинами, то единый масштаб для этих операндов и результата (А±В) должен выбираться сразу для трех этих величин А, В, (А±В). В этом случае: в формулах (2) и (3) для определения L и Р следует принимать следующие значения:

(6)

где:

(7)

б) для операции умножения:

(8)

(масштаб произведения равен произведению масштабов сомножителей).

Если А и В являются исходными величинами, то масштабы для них вы­бираются по формулам (2), (3) и (4) независимо друг от друга, с проверкой дополнительного условия: машинное изображение минимального абсолютного значения результата - должно быть корректно (с заданной точностью) представлено в данной разрядной сетке машины в соответствии с условием (1а):

(8а)

Если данное условие не выполняется, то это означает, что операция умножения над заданными операндами с выбранной точностью (δ) не может быть выполнена. В этом случае необходимо увеличить разрядную сетку машины на m разрядов:

(8б)

где: - знак ближайшего целого с избытком величины Х.

в) для операции деления:

(9)

(масштаб частного равен частному от деления масштаба делимого на масш­таб делителя).

Если А и В являются исходными величинами, то масштабы для них вы­бираются по формулам (2), (3) и (4) независимо друг от друга, с учетом дополнительного ограниче­ния, вытекающего из второго условия корректности изображения (2а)

(10)

Если данное условие не выполняется, необходимо либо увеличить масштаб делителя - (если это возможно), либо уменьшить масштаб делимого - (в пределах диапазона допустимых значений ). Если для выполнения условия (10) при потребуется выбрать новое значение за пределами диапазона допустимых значений , то это означает, что данную операцию деления при выбранных диапазонах изменения исходных операндов нельзя выполнить с заданной точностью, в связи с чем необходимо увеличить разрядность машины на m разрядов. Значение m выбирается из условия:

(10а)

3. Дополнительные рекомендации по выбору масштабов.

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

а) Масштабирование целесообразно проводить в три этапа:

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

- выбор масштабов величин, определение коэффициентов перемасштабирования;