Алгоритм решения задач

12806
знаков
12
таблиц
7
изображений

Содержание

Введение

1 Алгоритм решения функциональной задачи

2 Выбор системы команд специализированной ЭВМ

3 Форматы команд и операндов

4 Содержательные графы микропрограмм операций АЛУ

5 Разработка объединенной микропрограммы работы АЛУ

6 Закодированные алгоритмы микропрограмм

7 Проектирование управляющего автомата


Введение

Целью курсового проектирования является закрепление знаний по курсу: «Организация ЭВМ и систем» , полученных в результате изучения лекционного курса и выполнения лабораторного практикума.

Объектом курсового проектирования является процессор специализированной ЭВМ.

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

Разработка процессора специализированной ЭВМ включает в себя следующие этапы:

-  Разработка алгоритма решения функциональной задачи.

-  Выбор системы команд специализированной ЭВМ.

-  Определение форматов команд и операндов.

-  Разработка алгоритмов микропрограмм выполнения минимально необходимого набора операций АЛУ.

-  Разработка объединенной микропрограммы работы АЛУ.

-  Разработка структурной схемы операционного автомата АЛУ.

-  Разработка управляющего автомата АЛУ.


1 Алгоритм решения функциональной задачи

Укрупненный алгоритм решения поставленной задачи представлен на рисунке 1.1. Алгоритм вычисления функций F приведен соответственно на рисунке 1.2.

Рис.1.1 Укрупненный алгоритм

Для вычисления функции F можно воспользоваться степенным рядом:

1

 
Функция Arth(x) разлагается [3] в степенной ряд:

Этот ряд сходится при |x|<1,

 Рис.1.3

 
Блок-схема: знак завершения:Блок-схема: решение:Блок-схема: данные:

 

 
Блок-схема: данные:

 

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

 
 

2 Выбор системы команд специализированной ЭВМ

Для двухадресной системы команд без признака засылки основные операции над двумя операндами будут выглядеть так:

,

где

А1 – первый адрес в команде;

А2 – второй адрес в команде;

* - обозначение операции.

Введем обозначение:

N . Наименование операции . X . Y

X – первый операнд и результат операции.

Y – второй операнд (если он не участвует, то ставится -).

Для двухадресной системы команд без признака засылки программа будет выглядеть так:

Часть команд в этой программе имеют два адреса, а часть – один адрес, поэтому и система команд ЭВМ должна состоять из одноадресных и двухадресных команд.

  3 Форматы команд и операндов

Будем считать, что оперативная память (ОП) состоит из 256 ячеек длиной в один байт каждая.

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

Поскольку в данном случае имеются одноадресные команды и двухадресные команды, для их различия введено одноразрядное поле кода длины команды (КДК) и принято считать: КДК=1 - для одноадресных и КДК=0 - для двухадресных команд.

Разряды 5-7 первого байта всех команд здесь не используются. Формат команд приведен на рисунке 3.1.

В качестве операнда будет использоваться 16-разрядное слово, запятая считается фиксированной перед старшим разрядом, а ОП оперирует с однобайтовыми словами. Формат операнда в ОП представлен на рисунке 3.2:

Такой операнд загружается за два обращения к ОП, здесь старшие разряды операнды и знак содержатся в первом байте, а младшие разряды – во втором.

4 Содержательные графы микропрограмм операций АЛУ

Числа представляются в 16-разрядном формате, старший (нулевой) разряд используется для представления знака числа, для операции сложения используется модифицированный дополнительный код, поэтому регистр RG имеет 17 разрядов (0:16) (поле RG(1:16) – для хранения первого слагаемого), регистр RG1 имеет 16 разрядов RG1(0:15) – для второго слагаемого, одноразрядному полю признака переполнения изначально присвоено нулевое значение, при операции сложения слагаемые помещаются по младшим разрядам, результат (сумма) помещается в поле RG(1:16), прибавление константы  означает прибавление 1 к младшему разряду слова.

Содержательный алгоритм сложения представлен на рисунке 4.1:


Рисунок 4.1 – Алгоритм операции сложения

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

Таблица 4.1

Тип Слово Пояснение
ILO RG(0:16) Слагаемое (Сумма)
IL RG1(0:16) Слагаемое
ILO ПП Признак переполнения

Содержательный алгоритм вычитания представлен на рисунке 4.2:

Рисунок 4.2 – Алгоритм вычитания

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

Таблица 4.2

Тип Слово Пояснение
ILO RG(0:16) Уменьшаемое (разность)
IL RG1(0:16) Вычитаемое
ILO ПП Признак переполнения

Содержательный алгоритмы умножения и деления представлены на рисунках 4.3 и 4.4:

Описания слов, использованных в микропрограммах представлены в таблицах 4.3 и 4.4:

Таблица 4.3

Тип Слово Пояснение
ILO RG(0:16) Множитель, произведение
IL RG1(0:16) Множимое
L RG2(0:16) Множитель, произведение
L СТ(1:4) Счетчик циклов

Таблица 4.4

Тип Слово Пояснение
ILO RG(0:16) Делимое, остаток, частное
IL RG1(0:16) Делитель
L RG2(0:16) Частное
L СТ(1:4) Счетчик
ILO ПП Признак переполнения

Содержательные алгоритмы умножения на 2 и нахождения абсолютной величины числа представлены на рисунке 4.5 и 4.6, а описания слов, использованных в микропрограммах – в таблице 4.5 и 4.6:

Рисунок 4.5 – Алгоритм операции «умножение на 2»

Рисунок 4.6 – Алгоритм приведения абсолютной величины числа

Таблица 4.5

Тип Слово Пояснение
ILO RG(2:16) Операнд
ILO ПП Признак переполнения

Таблица 4.6

Тип Слово Пояснение
ILO RG(0:1) Операнд

Содержательный алгоритм микропрограммы специальной функции Arth(x) представлен на рисунке 4.7, здесь до начала выполнения программы регистру RG4 присваивается значение X. Описания слов, использованных в микропрограмме – в таблице 4.7:

Таблица 4.7

Тип Слово Пояснение
ILO RG(0:16)

Переменная x,n,b,a,F множитель, произведение, делимое,

остаток, частное, слагаемое, сумма,

уменьшаемое, разность

IL RG1(0:15)

Переменная F,b,a

константа,

Множимое, делитель, слагаемое, вычитаемое

L RG2(0:16) Множитель, произведение, частное
L RG3(0:15) Переменная F
L RG4(0:15) Переменная x,a,b
L RG5(0:15) Переменная n
L CT(1:4) Счетчик
ILO ПП Признак переполнения

Теперь необходимо составить схему укрупненного алгоритма, используя уже полученную микропрограмму вычисления функции Arth(x). Предполагается, что переменные x1, x2 и x3 перед началом выполнения программы уже будут загружены соответственно в регистры RG4, RG3 и RG5. Данная схема алгоритма представлена на рисунке 4.8:


Рисунок 4.8 – Схема алгоритма

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

Таблица 4.8

Тип Слово Пояснение
ILO RG(0:16)

Переменная x1, x2,X делимое,

остаток, частное,

уменьшаемое, разность

абсолютная величина числа

IL RG1(0:15)

Переменная x2, x3

константа, делитель, вычитаемое

L RG3(0:15) Переменная x2
L RG4(0:15) Переменная x1, X
L RG5(0:15) Переменная x3
 
5 Разработка объединенной микропрограммы работы АЛУ

Процессор состоит из АЛУ и УЦУ.

В объединенном списке микроопераций, используемых в микропрограммах минимального набора операций АЛУ, для унификации формы записи различных операций и форматов одноименных слов следует по сравнению с рисунком 4.3 изменить три микрооперации:

-  для вершины 2 вместо микрооперации RG2 := RG нужно использовать микрооперацию RG2 := RG(1:16).0;

-  для вершины 6 вместо микрооперации RG2(1:15):=R1(RG (15).RG2(1:15)) – использовать микрооперацию RG2(1:15):=R1(RG(16).RG2(1:16);

-  вместо микрооперации RG(0):=1 в вершине 11 – использовать микрооперацию RG(0:1):=11.

Благодаря этим изменениям значение числовой части результата каждой операции присваивается полю RG(2:16) слова RG, а нулевой и первый разряды этого слова используются для представления знака числа. Появляется возможность считать, что перед началом каждой операции над двумя операндами в АЛУ значение первого операнда присваивается полю RG(1:16) слова RG, а значение второго операнда – слову RG1. При выполнении этого условия перед началом сложения и вычитания необходимо произвести присваивание RG(0) := RG(1), перед началом умножения нужно осуществить передачу RG2 := RG(1:16).0, а перед делением – микрооперации RG2(0):= RG(1) и RG(0:1):= 00.

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

Таблица 5.1

Обозначение Лог. Условие Тип операции
X1 RG(0)

Сложение и

Вычитание

X2 RG1(0)
X3 RG(1)
X4 RG2(15) Умножение
X5 CT=0
X6 RG2(1)
X7 RG1(0)ÅRG2(0) Деление
X8 RG2(16) Умножение на «2»
X9 RG(2) Вычисление функции Arth(x)
X10  RG(0:16)

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

Таблица 5.2

Микрооперации Тип операции
Y1 RG(0):=RG(1) Сложение
Y2

RG(2:16):=ù RG(2:16) +

Y3 RG:=RG+RG1(1:15)
Y4

RG:=RG+11.ù RG1(1:15)+

Y5 ПП:=1
Y6 RG1(0):= ù RG1(0) Вычитание
Y7 RG2:=RG(1:16).0 Умножение
Y8 RG:=0
Y9 CT:=1510
Y10 RG2(1:16):=R1(RG(16).RG2(1:16))
Y11 RG(1:16):=R1(0.RG(1:16))
Y12 CT:=CT-1
Y13

RG:=RG+

Y14 RG(0:1):=11
Y15 RG2(0):=RG(1) Деление
Y16 RG(2:16):=L1( RG(2:16).0)
Y17 CT:=0
Y18 RG2(1:16):=0
Y19 RG2(1:16):=L1(RG2(1:16).ù RG(0))
Y20 RG:=RG2(1:15)
Y21 RG(0:1):=00 Выделение абсолютной величины числа
Y22 RG3:=RG4 Вычисление функции Arth(x)
Y23

RG5:=

Y24 RG:=RG4
Y25 RG1:=RG
Y26 RG4:=RG
Y27 RG:=RG5
Y28 RG4:=RG1
Y29

RG1:=

Y30

RG5:=RG5+

Y31 RG:=RG3

В приложениях 1, 2 и 3 приведена соответственно схема объединенной микропрограммы работы АЛУ, закодированная схема объединенной микропрограммы работы АЛУ и структурная схема операционного автомата.

6 Закодированные алгоритмы микропрограмм

Закодированные алгоритмы сложения, вычитания, умножения, деления, умножения на «2» и выделения абсолютной величины числа представлены соответственно на рисунках 6.1, 6.2, 6.3, 6.4, 6.5 и 6.6:

  7 Проектирование управляющего автомата

Формат микрокоманды при вертикальном кодировании имеет формат, представленный на рисунке 7.1:

Формат команды с принудительной адресацией представлен на рисунке 7.2:

Алгорим формирования исполнительного адреса обращения к микропрограммной памяти (МПП) представлен на рисунке 7.3:

Рисунок 7.3 – Алгоритм формирования адреса

В таблице 7.1 приведены все микрооперации, расположенные в микропрограммной памяти, где адрес A0 - переход по «истина»:

Таблица 7.1

Логичеcкий адрес МК в МПП Формат микрокоманды

 

Операционная зона Адресная зона

 

Y X(1..l) A0 A1

 

0 Y0 1

 

1 Y31 2

 

2 Y33 3

 

3 Y15 4

 

4 Y21 5

 

5 Y4 6

 

6 X1 23 7

 

7 Y16

 

8 Y9 9

 

9 Y18 10
10 X1 12 11
11 Y4 13
12 Y3 13
13 Y19 14
14 Y16 15
15 Y12 16
16 X5 17 10
17 Y20 18
18 X8 19 20
19 Y13
20 X7 22 21
21 Y21 24
22 Y14 24
23 Y5 24
24 Y25 25
25 Y24 26
26 Y6 27
27 Y1 28
28 X1 29 30
29 Y2 30
30 X2 32 31
31 Y3 33
32 Y4 33
33 X1 35 34
34 X2 36 38
35 X2 37 36
36 Y5 38
37 Y2 38
38 Y26 39
39 Y21 40
40 Y34 41
41 Y6 42
42 Y1 43
43 X1 44 45
44 Y2 45
45 X2 47 46
46 Y3 48
47 Y4 48
48 X1 50 49
49 X2 51 53
50 X2 52 51
51 Y5 53

 

52 Y2 53

 

53 X1 0 54

 

54 Y22 55

 

55 Y23 56

 

56 Y24 57

 

57 Y25 58

 

58 Y7 59

 

59 Y8 60

 

60 Y9 61

 

61 X4 62 63

 

62 Y3 63

 

63 Y10 64

 

64 Y11 65

 

65 Y12 66

 

66 X5 67 61

 

67 X6 68 69

 

68 Y13 69

 

69 X7 70 71

 

70 Y14 71

 

71 Y26 72

 

72 Y27 73

 

73 X9 75 74

 

74 Y16 76

 

75 Y5 76

 

76 Y6 77

 

77 Y1 78

 

78 X1 79 80

 

79 Y2 80

 

80 X2 82 81

 

81 Y3 83

 

82 Y4 83

 

83 X1 85 84

 

84 X2 86 88

 

85 X2 87 86

 

86 Y5 88

 

87 Y2 88

 

88 Y25 89

 

89 Y24 90

 

90 Y28 91

 

91 Y7 92

 

92 Y8 93

 

93 Y9 94

 

94 X4 95 96

 

95 Y3 96

 

96 Y10 97

 

97 Y11 98

 

98 Y12 99

 

99 X5 100 94

 

100 X6 101 102

 

101 Y13 102

 

102 X7 103 104

 

103 Y14 104

 

104 Y25 105

 

105 Y24 106

 

106 Y28 107

 

107 Y29 108

 

108 Y1 109

 

109 X1 110 111

 

110 Y2 111

 

111 X2 113 112

 

112 Y3 114

 

113 Y4 114

 

114 X1 116 115

 

115 X2 117 38

 

116 X2 118 117

 

117 Y5 119

 

118 Y2 119

 

119 Y25 120

 

120 Y24 121

 

121 X10 122 158

 

122 Y15 123

 

123 Y21 124

 

124 Y4 125

 

125 X1 142 126

 

126 Y16 127

 

127 Y9 128

 

128 Y18 129

 

129 X1 131 130

 

130 Y4 132

 

131 Y3 132

 

132 Y19 133

 

133 Y16 134

 

134 Y12 135

 

135 X5 136 129

 

136 Y20 137

 

137 X8 138 139

 

138 Y13 139

 

139 X7 141 140

 

140 Y21 143

 

141 Y14 143

 

142 Y5 143

 

143 Y30 144

 

144 Y31 145

 

145 Y32 146

 

146 Y1 147

 

147 X1 148 149

 

148 Y2 149

 

149 X2 150 151

 

150 Y3 152

 

151 Y4 152

 

152 X1 154 153

 

153 X2 155 157

 

154 X2 156 155

 

155 Y5 157

 

156 Y2 157

 

157 71

 

158 Y0

 


Информация о работе «Алгоритм решения задач»
Раздел: Информатика, программирование
Количество знаков с пробелами: 12806
Количество таблиц: 12
Количество изображений: 7

Похожие работы

Скачать
45637
13
13

... месяца» равно «Сальдо на начало месяца» - Итого по дебету счета + Итого по кредиту счёта. ЗАКЛЮЧЕНИЕ В ходе выполнения курсовой работы был разработан документ постановка и алгоритм решения задачи «Учёт основных средств для ОАО «Алеся-сервис». В первом разделе данного отчета определено назначение и область применения задачи. Во втором и третьем разделах описана выходная и входная информация, ...

Скачать
41340
0
0

... и обмена выполняется для значений j от n до 2 последовательно, постепенно уменьшая длину неотсортированной части ряда.4.3 Описание игровых моментов при решении задач При изучении раздела информатики «Алгоритмизация и программирование» написание рабочей программы является конечной целью применения игровых методов. Так, изучение структурного типа данных массив происходит более успешно, если ...

Скачать
17151
2
5

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

Скачать
29193
3
0

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

0 комментариев


Наверх