Лаб 1 Теория (Теория к лабам 19 страниц по БВМиС)
Описание файла
Файл "Лаб 1 Теория" внутри архива находится в папке "Теория к лабам 19 страниц по БВМиС". Документ из архива "Теория к лабам 19 страниц по БВМиС", который расположен в категории "". Всё это находится в предмете "основы эксплуатации эвм" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "основы эксплуатации эвм" в общих файлах.
Онлайн просмотр документа "Лаб 1 Теория"
Текст из документа "Лаб 1 Теория"
6
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(Государственный технический университет)
«МАИ»
БЕЛОУСОВ Ю.А.
МАСШТАБИРОВАНИЕ АЛГОРИТМОВ, РЕАЛИЗУЕМЫХ НА МАЛОРАЗРЯДНЫХ ЭВМ С ДРОБНОЙ АРИФМЕТИКОЙ.
Цикл лабораторных работ по курсу
«БОРТОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ И СИСТЕМЫ».
Утверждено на заседании кафедры 304
Москва 2008 г.
Рассматриваются теоретические и практические аспекты масштабирования алгоритмов, реализуемых на ЭВМ с дробной арифметикой, ограниченной разрядной сеткой и естественной формой представления чисел (с фиксированной перед старшим значащим разрядом запятой). Детально изучаются три метода масштабирования, анализируются зависимости инструментальной погрешности от разрядности машины.
ВВЕДЕНИЕ
Определенная часть современных ЭВМ представляют собой малоразрядные машины, в которых используется естественная форма представления вещественных величин - форма с фиксированной запятой и так называемая дробная арифметика, т.к. запятая в машинном представлении чисел фиксирована перед старшим значащим разрядом. Это ограничивает диапазон изменения машинных чисел до значений
где k - разрядность мантиссы числа (k=n-l, n - разрядность ЭВМ, один разряд используется для представления знака числа).
Естественно, что такой диапазон машинных изображений не соответствует используемым в алгоритмах диапазонам вещественных величин, которые представляются в принятых единицах измерения: метрах, килограммах, секундах, радианах и т.п., и приводит к необходимости реализации этапа масштабирования алгоритмов в технологическом процессе их подготовки для реализации на машинах с дробной арифметикой.
1. Основные понятия и определения.
Масштабирование - это процесс выбора рациональных масштабов операндов, констант, входных, промежуточных и выходных величин, используемых в арифметических выражениях алгоритма.
Рациональными называются такие масштабы, которые позволяют получать машинные изображения величин с заданной точностью в пределах машинного диапазона чисел.
Переход от реальных величин, представленных в принятых единицах измерения, к их машинным изображениям можно представить в виде:
где: X - значение реальной величины;
- машинное изображение величины X (машинный код);
Если некоторая величина X изменяется в пределах заданного диапазона
и представляется с заданной точностью, определяемой величиной предельной ошибки ∆Х, то для такой величины могут быть определены границы диапазона допустимых значений рационального масштаба
Левая и правая границы диапазона возможных значений определяются исходя из приведенного выше определения рационального масштаба.
Так для того, чтобы машинное изображение с заданной точностью представляло исходную величину X, необходимо выполнение следующего условия: половина цены единицы младшего разряда изображения не должна превышать значения машинного изображения предельной ошибки представления величины Х (Х):
Отсюда следует, что левая граница диапазона допустимых значений определяется следующим образом:
Если заданна относительная ошибка представления величины Х – δ, то предельная ошибка представления этой величины Х определяется следующим образом:
Второе условие, которое следует из определения рационального масштаба и с помощью которого определяется правая граница диапазона возможных значений масштаба - , формулируется следующим образом: величина машинного изображения не должна выходить за пределы машинного диапазона чисел
Это неравенство можно преобразовать в равенство, приняв в качестве и X их максимальные значения и |Х|mах, т.е. положив, что максимальному (абсолютному) значению масштабируемой величины соответствует максимальное значение машинного кода:
С учетом введенных определений левой и правой границ диапазона возможных значений масштабов исходной величины можно сформулировать более строгое определение понятия рационального масштаба:
рациональным называется масштаб, который удовлетворяет условиям корректности изображений
L М Р; (4)
Невыполнение условия М Р приводит к переполнению разрядной сетки машины (выход за пределы диапазона машинных чисел). Невыполнение условия L М приводит к потере точности и в конечном счете к искажению изображения, вплоть до его потери - случая "машинного нуля".
Возможны случаи, когда условие корректности изображений при выборе масштаба не может быть выполнено, т.к. получается, что L > Р. Это означает, что данная величина не может быть корректно (условие (4)) представлена в данной разрядной сетке машины. В этом случае необходимо увеличить разрядность слова (например, на m разрядов), что обеспечивает уменьшение левой границы диапазона масштабов в 2m раз:
L' = L*2-m
Все последующие операции, в которых используется данная величина, должны выполняться с увеличенной точностью (над операндами с разрядностью мантиссы k+m).
2. Правила выбора и преобразования масштабов.
Масштабы входных переменных и констант выбираются из условий корректности изображений (4) с учетом выражений (2) и (3). С целью обеспечения более высокой точности вычислений конкретное значение масштабов следует выбирать ближе к правой границе диапазона - Р.
Масштабы промежуточных и выходных величин вычисляются в соответствии с правилами преобразования масштабов.
Если выполняется некоторая арифметическая операция над исходными операндами А и В, представленными в машине своими изображениями и с помощью масштабов и ( ),то результат этой операции (С = А В) будет представлен в машине своим изображением, которое вычисляется по формуле = , а масштаб результата определяется в зависимости от типа операции по следующим правилам:
а) для операции сложения, вычитания:
(при сложении и вычитании масштабы операндов должны быть равны между собой, масштаб результата равен масштабу операндов).
Если при сложении-вычитании операнды А и В являются исходными величинами, то единый масштаб для этих операндов и результата (А±В) должен выбираться сразу для трех этих величин А, В, (А±В). В этом случае: в формулах (2) и (3) для определения L и Р следует принимать следующие значения:
б) для операции умножения:
(масштаб произведения равен произведению масштабов сомножителей).
Если А и В являются исходными величинами, то масштабы для них выбираются по формулам (2), (3) и (4) независимо друг от друга, с проверкой дополнительного условия: машинное изображение минимального абсолютного значения результата - должно быть корректно (с заданной точностью) представлено в данной разрядной сетке машины в соответствии с условием (1а):
Если данное условие не выполняется, то это означает, что операция умножения над заданными операндами с выбранной точностью (δ) не может быть выполнена. В этом случае необходимо увеличить разрядную сетку машины на m разрядов:
где: - знак ближайшего целого с избытком величины Х.
в) для операции деления:
(масштаб частного равен частному от деления масштаба делимого на масштаб делителя).
Если А и В являются исходными величинами, то масштабы для них выбираются по формулам (2), (3) и (4) независимо друг от друга, с учетом дополнительного ограничения, вытекающего из второго условия корректности изображения (2а)
Если данное условие не выполняется, необходимо либо увеличить масштаб делителя - (если это возможно), либо уменьшить масштаб делимого - (в пределах диапазона допустимых значений ). Если для выполнения условия (10) при потребуется выбрать новое значение за пределами диапазона допустимых значений , то это означает, что данную операцию деления при выбранных диапазонах изменения исходных операндов нельзя выполнить с заданной точностью, в связи с чем необходимо увеличить разрядность машины на m разрядов. Значение m выбирается из условия:
3. Дополнительные рекомендации по выбору масштабов.
Масштабирование является достаточно трудоемким процессом, связанным с большим количеством вычислений, которые выполняются "вне целевой машины", до преобразования алгоритмов в рабочие программы. Задача выбора масштабов не имеет однозначного решения, т.к. определяется совокупностью многих факторов: функциональной сложностью алгоритма, разбросом диапазонов изменения входных величин и точностей их представления. В связи с этим качество масштабирования, которое можно оценить точностью получаемых результатов и количеством дополнительно введенных операций перемасштабирования, в значительной степени определяется искусством разработчика, проводящего масштабирование, и эффективностью использования приводимых ниже рекомендаций:
а) Масштабирование целесообразно проводить в три этапа:
- вычисление диапазонов изменения всех величин алгоритма и границ диапазонов возможных значений масштабов входных величин и констант;
- выбор масштабов величин, определение коэффициентов перемасштабирования;