Алгоритм решения задач
Содержание
Введение
1 Алгоритм решения функциональной задачи
2 Выбор системы команд специализированной ЭВМ
3 Форматы команд и операндов
4 Содержательные графы микропрограмм операций АЛУ
5 Разработка объединенной микропрограммы работы АЛУ
6 Закодированные алгоритмы микропрограмм
7 Проектирование управляющего автомата
Введение
Целью курсового проектирования является закрепление знаний по курсу: «Организация ЭВМ и систем» , полученных в результате изучения лекционного курса и выполнения лабораторного практикума.
Объектом курсового проектирования является процессор специализированной ЭВМ.
В процессоре выделяют устройство, в котором выполняются все основные (арифметические и логические) операции. Это устройство называют арифметико-логическим устройством (АЛУ). Если все основные операции выполняются за один такт (это имеет место в большинстве современных микропроцессоров), АЛУ является частью операционного автомата процессора; если же некоторые или все основные операции выполняются алгоритмически за много тактов, АЛУ имеет собственное устройство управления.
Разработка процессора специализированной ЭВМ включает в себя следующие этапы:
Разработка алгоритма решения функциональной задачи.
Выбор системы команд специализированной ЭВМ.
Определение форматов команд и операндов.
Разработка алгоритмов микропрограмм выполнения минимально необходимого набора операций АЛУ.
Разработка объединенной микропрограммы работы АЛУ.
Разработка структурной схемы операционного автомата АЛУ.
Разработка управляющего автомата АЛУ.
1 Алгоритм решения функциональной задачи
Укрупненный алгоритм решения поставленной задачи представлен на рисунке 1.1. Алгоритм вычисления функций F приведен соответственно на рисунке 1.2.
Рис.1.1 Укрупненный алгоритм
Для вычисления функции F можно воспользоваться степенным рядом:
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

Нравится материал? Поддержи автора!
Ещё документы из категории информатика:
Чтобы скачать документ, порекомендуйте, пожалуйста, его своим друзьям в любой соц. сети.
После чего кнопка «СКАЧАТЬ» станет доступной!
Кнопочки находятся чуть ниже. Спасибо!
Кнопки:
Скачать документ