Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Выполнение арифметических операций с фиксированной и плавающей точкой в ЭВМ.
3.1 Сложение
Сложение положительных чисел выполняется в прямом коде.
5 + 1 = 6 +0.101 5 + 4 = 9 +00.101
0.001 00.100
0.011 01.001
истинный знак переполнение
Операция вычитания заменяется сложением с отрицательным числом, представленном в дополнительном коде.
510 = 0.1012 5 – 3 = 2 +0.101
310 = 0.0112 1.101
[0.011]ДК = 1.101 1.010 = +210
Число представляется как:
|
S |
P |
M |
где S – знак; P – порядок; M – мантисса.
Чтобы избежать путаницы с отрицательными порядками, истинный порядок смещается на величину максимального порядка.
Порядок указывает, на сколько разрядов влево или вправо надо сдвинуть истинное число, т.е. S*M*2P.
+
Порядок действий при сложении с плавающей точкой:
Пусть y>x, тогда .
- сдвиг вправо на
Исходные мантиссы Mx и My должны быть нормализованы, т.е. в старшем значащем разряде мантиссы должна быть 1. Модифицированная мантисса M*x денормализована, т.к. она сдвинута на разрядов вправо. Результирующая мантисса M*z может быть денормализованной. Нарушение нормализации M*z может быть:
- влево на 1 разряд;
- вправо на сколько угодно разрядов.
разрядов)
4) коррекция P*z=Py.
5 6 = 30 110
101 n X n(n-1)
110 СЧП РгХ СчЦ -1
000 сумма частичных n-1 0
110 произведений
11110 СМ 0,1(…,1)
X = 110; Y = 101; Z = 11110 n Y
n-1 0
РгZ РгY 0
n-1 0
Zст Zмл
Z
Если младший разряд равен 1, прибавляем к СЧП множимое.
Алгоритм:
Здесь Рг – регистр; РгZ – регистр СЧП; СчЦ – счетчик цикла.
Если прибавить схему управления, то получится аппаратный умножитель.
Всего существует 4 схемы умножения:
Время умножения: Tумн=n(0.5τслож+τсдвига)≈1.5τкор.
Диапазон 1* τкор*n ≤ Tумн ≤ 2* τкор*n.
Операция умножения является длинной, поэтому разработана масса методов по ее ускорению. Существуют аппаратные и программные методы ускорения любых операций, в том числе и умножения:
|
Х[1] |
Х[0] |
Что делать |
|
0 |
0 |
2 сдвига |
|
0 |
1 |
1 сложение + 2 сдвига |
|
1 |
0 |
1 косое сложение + 2 сдвига |
|
1 |
1 |
1 косое сложение + 1 прямое сложение + 2 сдвига или 1 двойное косое сложение + 1 прямое вычитание + 2 сдвига |
Проиллюстрируем прямое и косое сложение:
прямое сложение
косое сложение
двойное косое сложение
Используется в спецпроцессорах. В обычной технике не применяется, т.к. там присутствуют аппаратные умножители.
|
0 |
0 |
0 |
3 сдвига |
|
…………… |
|||
|
1 |
1 |
1 |
(*8-1)+3 сдвига |
Аппаратные методы ускорения умножения.
а) Алгоритм Бута (см. учебник)
б) Пирамидальный умножитель
Схема, формирующая слагаемые в СЧП:
y0 x 8
8
y0 x
z = y0x + 2y1x + 22y2x + 23y3x + 24y4x + 25y5x + 26y6x + 27y7x = YX
СМ – комбинационные сумматоры.
Tумн = 4τкор
3.3.1 Деление с фиксированной точкой
, где x – двойной длины; y,z – одинарной длины.
30:6=5 восстановление остатка
Тдел = nτвыч+ nτсдв+0.5nτслож≈2.5τкор
Операционный автомат деления с фиксированной точкой.
2n x n y
Ø -1
2n-1 n n-1 0 n n-1 0 n
n
+/- знак Sx Sy
возврат в частичн. остатки
Алгоритм: Sz
(-ост.+y)2-y=-2 ост.+y
восстановление остатка
При получении отрицательного остатка в частное записываем 0, отрицательный остаток сдвигаем влево на 1 разряд и в следующем цикле вместо вычитания делаем сложение с y.
Сделать самостоятельно схему деления без восстановления остатка и алгоритм деления без восстановления остатка.
3.3.2 Деление с плавающей точкой
Sz
M*z Mz
P*z Pz
Тдел = 2τкор
2. Определите входное сопротивление схемы, если R1=10 Ом, R2=R3=40 Ом.
(параллельное соединение)
(последовательное соединение)
Итого: Rвх = 30 Ом.
3. Технология модульного программирования. Модули.
Модуль в программировании представляет собой функционально законченный фрагмент программы, оформленный в виде отдельного файла с исходным кодом или поименованной непрерывной его части (например, Active Oberon), предназначенный для использования в других программах. Модули позволяют разбивать сложные задачи на более мелкие в соответствии с принципом модульности. Обычно проектируются таким образом, чтобы предоставлять программистам удобную для многократного использования функциональность (интерфейс) в виде набора функций, классов, констант. Модули могут объединяться в пакеты и, далее, в библиотеки.
Модули могут быть обычными, т. е. написанными на том же языке, что и основная программа, в которой они используются, либо модулями расширения, которые пишутся на отличном от языка основной программы языке. Модули расширения обычно пишутся на более низкоуровневом языке, что позволяет получить выигрыш в скорости выполнения (производительности) программы.
4. Основные понятия и концепция виртуальной памяти. Алгоритм программы страничных прерываний (программный).
Windows - это система со страничной виртуальной памятью. В такой системе содержимое адресного пространства процесса хранится во вторичной памяти и при необходимости происходит постраничная загрузка из вторичной в первичную ( выполняемую ) память.
При создании процессу выделяется виртуальное адресное пространство 4 Гб , хотя в этот момент ни один из адресов в действительности не размещен. Когда процесс нуждается в памяти, то во-первых необходимое адресное пространство резервируется для последующего использования ( при этом в действительности размещения в памяти не происходит ). Когда процессу нужно сохранить информацию, он передает адресное пространство, при этом процессу действительно предоставляется память для хранения информации. Обычно операция передачи приводит к тому, что область на диске ( в страничном файле ) передается процессу. Информация хранится на диске до тех пор пока на нее действительно не ссылается поток.
Подобно всем механизмам виртуальной памяти, когды выполняемый поток ссылается на виртуальный адрес, диспетчер виртуальной памяти гарантирует, что страница, содержащая виртуальный адрес, будет считана из страничного файла и размещена в физической памяти. И диспетчер виртуальной памяти отобразит виртуальный адрес, на который ссылается поток, в физический адрес, где размещена информация.
Диспетчер виртуальной памяти спроектирован так, что большая часть адресного пространства каждого процесса ( обычно половина ) отображается на область, используемую системой в режиме ядра. Для этого существует несколько важных соображений:
Рис. Виртуальная память
Когда поток ссылается на адрес в пользовательском адресном пространстве, система виртуальной памяти загружает требуемую область в физическую память, чтобы поток мог читать или писать по этому виртуальному адресу ссылаясь на соответствующий физический адрес. Такое же отображение имеет место и для системного адресного пространства, но эти ссылки защищены. Системная часть адресного пространства любого процесса отображается наобщую системную область, в отличие от собственной пользовательской части приложения.
5. Пространственное вращение вокруг произвольной оси.
Смотри стр. 34 в pdf-файле.
10. Пространственное вращение вокруг произвольной оси.
Пространственное вращение вокруг произвольной оси. Данную операцию можно в какой-то мере считать универсальной и на ее базе реализовывать все остальные операции в пространстве. Так эта операция не относится к элементарным, ее следует разложить на простейшие. Из них в данном случае потребуются операции переноса и вращения вокруг осей координат. Для того чтобы свести операцию вращения вокруг произвольной оси к эти операциям, необходимо выполнить следующие действия:
• перенести исходную ось вращения таким образом, чтобы она проходила через начало системы координат.
• повернуть перемещаемую ось до совпадения с одной из координатных плоскостей
• в пределах выбранной координатной плоскости осуществить плоский поворот до совпадения с одной из координатных осей
• теперь можно выполнить заданный поворот вокруг оси, которая совмещена с одной из осей координат
• повторение действий в обратном порядке
Рассмотрим поворот на угол γ вокруг произвольной оси. Для этого необходимо выполнить следующие семь шагов:
1. Перенос оси вращения в начало системы координат.
2. Поворот на угол α относительно оси ОХ до пересечения с плоскостью XOZ
3. Поворот на угол β в плоскости XOZ до совмещения с осью OZ
4. Поворот на угол γ вокруг оси OZ
5. Поворот на угол - β вокруг OY
6. Поворот на угол - α вокруг ОХ
7. Перенос оси вращения на прежнее место
Рассмотрим математическое описание данных действий в матричном виде. Будем описывать все производимые действия в виде вложенных преобразований конгруэнтности.
1. Преобразование переноса (прямое и обратное):
2. Поворот на угол α относительно ОХ:
3. Поворот на угол β относительно OY до совмещения с осью OZ :
4. Поворот на угол γ :
Полное преобразование, описывающее поворот в пространстве вокруг произвольной оси:
6. Алгоритмы обхода бинарных деревьев и их применение в трансляции программ и обработке данных.
В трансляции программ – преобразование семантического дерева (где из выражения строится дерево его вычисления, однозначно определяющее порядок операций). Тогда из него можно с помощью двух алгоритмов обхода получить префиксную и постфиксную польскую запись.
T – top, R – right child, L – left child.
Тогда если обход идет как LRT – получаем постфиксную запись, TLR – префиксную.
Так же такие же алгоритмы можно использовать для получения отсортированных значений из бинарных деревьев данных. (Там где левый потомок меньше вершины-родителя, а вершина меньше правого потомка). Сортировкой по возрастанию здесь является обход такого дерева как LTR.
РгХ:=х; РгZ:=z;
РгУ:=у; СчЦ:=n;
РгZ:=РгZ+РгХ
РгZ:=R1[РгZ];
РгУ:=R1[РгУ];
СчЦ:=CчЦ-1;
РгУ[0]
К
СчЦ=0
1
0
0
1
&7
&6
&5
&4
&3
&2
&1
&0
y0 x7 y0 x6 y0 x5 y0 x4 y0 x3 y0 x2 y0 x1 y0 x0
x 8 x7 x6 x5 x4 x3 x2 x1 x0
y0
1y0 y0 y0 y0 y0 y0 y0 y0
y0 x
И
И0
И1
И2
И3
И4
И5
И6
И7
y0 x y1 x y2 x y3 x y4 x y5 x y6 x y7 x
x 8
y
1 y0 y1 y2 y3 y4 y5 y6 y7
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
СМ
СМ
СМ
СМ
СМ
СМ
y0x+2y1x y2x+2y3x y4x+2y5x y6x+2y7x
CМ
x(y0+2y1+22y2+23y3) x(y4+2y5+26y6+27y7)
Блок
нормализации
Х
Mx
My
Px
Py
Mz*
Pz*
Mz
Pz
Sx
Sy
Sz
Рг y
СчЦ
Рг x
Рг z
БН
∑