Реферат: Линейное программирование симплекс-методом Данцига
Содержание
1. Постановка задачи
2. Форматы команд и их кодировка
3. Структурная схема процессора
4. Регистры
5. АЛУ
6. Формат микрокоманд
7. Микрокод
8. Кодировка микрокода
9. Примеры выполнения команд
10. Основные сигналы и регистрыпроцессора
11. Примеры программ
12. Определение производительности
Постановка задачи
Синтезировать структуру простогомагистрального процессора с одним АЛУ, выполняющего 8 заданных команд.Разработать формат команд, кодировку команд. Разработать структурную схемупроцессора, функциональные схемы всех блоков процессора, функциональную схемупроцессора в целом с указанием всех шин и управляющих сигналов.
Разработать форматмикрокоманд, организацию управления всеми устройствами процессора, микрокод длякаждой из заданных команд. Привести примеры выполнения каждой команды суказанием значения всех основных сигналов и содержимого основных регистров накаждом такте. Привести 2 примера небольших программ с указанием значенияосновных сигналов и содержимого основных регистров на каждом такте.
Определить максимальнуютактовую частоту процессора. Определить производительность процессора воперациях в секунду (IPS), а также выраженную в числе выполняемых тестовыхпрограмм в секунду. Указать способы повышения производительности процессора.
Характеристика процессора
Простой процессормагистрального типа с одноблочным универсальным АЛУ.
Разрядность регистров РОНи АЛУ процессора — 8 бит.
Число РОН — 4.
Адресуемая память — 256слов.
Устройство управления — микропрограммное с ПЗУ микропрограмм.
Способ выполнения команд– последовательное выполнение или JMP или JC.
Адресация памяти — прямая.
Арифметика вдополнительном коде.
Вариант: 54 = «2 2 23»
Без использованиянепосредственной адресации.
3х-адресные команды.
Операции АЛУ: NOP, ADD + SHRA, NAND.
Состав команд: LD, ST, ADD, SHR + JC, DEC, SUB, NAND.
Форматы команд и ихкодировка
Коды команд
КОП Команда Действие 000 ADD Rx,Ry,Rz Rx=Ry+Rz сложение 001 NAND Rx,Ry,Rz Rx=!(Ry&Rz) И-НЕ 010 SHR Rx,Ry Rx=Ry/2 арифметический сдвиг вправо 011 JC address jmp on carry условный переход по переносу 100 DEC Rx,Ry Rx=Ry-1 декремент (уменьшение на 1) 101 SUB Rx,Ry,Rz Rx=Ry-Rz вычитание 110 LD Rx,address Rx=Mem(address) загрузка из ОЗУ в регистр 111 ST Ry,address Mem(address)=Rx запись из регистра в ОЗУФормат команд
ADD Rx,Ry,Rz
КОП Rx Ry Rz не используется
x x y y z z /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> NAND Rx,Ry,Rz
КОП Rx Ry Rz не используется 1 x x y y z z /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> SHR Rx,Ry
КОП Rx Ry не используется 1 x x y y /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> JC address
КОП не использ. address 1 1 a a a a a a a a /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
DEC Rx,Ry КОП Rx Ry не используется 1 x x y y /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Сокращения:
КОП – код команды
Rx – регистр приемник
Ry – регистр источник 1
Rz – регистр источник 2
address – 8-битный адрес
SUB Rx,Ry,Rz КОП Rx Ry Rz не используется 1 1 x x y y z z /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> LD Rx,address КОП Rx не исп. address 1 1 x x a a a a a a a a /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> ST Rx,address КОП не исп Ry address 1 1 1 y y a a a a a a a a /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> Структурная схема процессора/>/>/>/>
РегистрыНомер При записи (по шине С) При чтении (по шине A и B) 000 Rg0 программно-доступные регистры Rg0 программно-доступные регистры 001 1 Rg1 Rg1 010 2 Rg2 Rg2 011 3 Rg3 Rg3 100 4 Temp0 Temp0 101 5 PC PC 110 6 IR_HI (старшая часть IR) IR константа 1 111 7 IR_LO (младшая часть IR) IR_LO /> /> /> /> /> /> />
При чтении старшей частирегистра команд, на шину A или B поступает единичная константа(00000001). Это вполне допустимо, т.к. старшая часть регистра команд имеет своивыходы из блока регистров: (КОП, Rx, Ry, Rz). Младшая часть регистра команд поступает на шины A или B в неизменном виде, т.к. в некоторых командах процессора вмладшей части регистра команд находиться 8-битный адрес. Единичная константаприменяется при инкрементировании счетчика команд, а также для полученияконстанты -1 = 11111111 (см. микрокод для команды DEC).
Разрядность РОН (регистрыобщего назначения) – 8 бит
Разрядность PC (program counter) – 8 бит
Разрядность IR (регистр команд) – 16 бит (доступнодва регистра по 8 бит)
АЛУ
/>
Структурная схема АЛУ иего связь с другими блоками машины показаны на рисунке. В состав АЛУ входятрегистры Рг1 — Рг7, в которых обрабатывается информация, поступающая изоперативной или пассивной памяти N1, N2, ...NS; логические схемы, реализующиеобработку слов по микрокомандам, поступающим из устройства управления.
Закон переработкиинформации задает микропрограмма, которая записывается в видепоследовательности микрокоманд A1,A2, ..., Аn-1,An. При этом различают два видамикрокоманд: внешние, то есть такие микрокоманды, которые поступают в АЛУ отвнешних источников и вызывают в нем те или иные преобразования информации (нарис. 1 микрокоманды A1,A2,..., Аn), и внутренние, которые генерируются в АЛУ ивоздействуют на микропрограммное устройство, изменяя естественный порядокследования микрокоманд. Например, АЛУ может генерировать признаки в зависимостиот результата вычислений: признак переполнения, признак отрицательного числа,признак равенства 0 всех разрядов числа др. На рис. 1 эти микрокомандыобозначены р1, p2,..., рm.
Результаты вычислений изАЛУ передаются по кодовым шинам записи у1, у2, ..., уs, в ОЗУ.
Функции регистров,входящих в АЛУ:
Рг1 — сумматор (илисумматоры) — основной регистр АЛУ, в котором образуется результат вычислений;
Рг2, РгЗ — регистрыслагаемых, сомножителей, делимого или делителя (в зависимости от выполняемойоперации);
Рг4 — адресный регистр(или адресные регистры), предназначен для запоминания (иногда и формирования)адреса операндов и результата;
Ргб — k индексныхрегистров, содержимое которых используется для формирования адресов;
Рг7 — i вспомогательныхрегистров, которые по желанию программиста могут быть аккумуляторами,индексными регистрами или использоваться для запоминания промежуточныхрезультатов.
Формат микрокоманд
MIR – Microinstruction register – регистр микрокоманд (24 bit) A A MUX B B MUX C C MUX RD WR ALU COND JMP ADDRESS /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
A, B, C – номер регистрадля осуществления чтения (A, B) или записи (C)
A MUX, B MUX, C MUX – откуда брать номер регистра
(0 – из команды IR, 1 – из микрокоманды MIR)
RD – чтение из ОЗУ
При этом адреспамяти берется с шины А, а результат подается на шину С
WR – запись в ОЗУ
При этом адреспамяти берется с шины А, а данные — с шины B
ALU – код операции АЛУ
КОП АЛУ Операция АЛУ 00 NOP 01 ADD 10 SHRA 11 NANDCOND – условие для определения адресаследующей выполняемой микрокоманды
COND Куда переходим 00 NEXT на следующую микрокоманду 01 DECODE декодирование команды, Address = [KOP]100 10 JMP безусловный переход 11 JC условный переход по переносу (Carry Flag)JMP ADDRESS – адрес в памяти микропрограмм, куда осуществляетсяпереход
Микрокод
Адрес Микрокоманда Пояснение1
2
3
IR_HI = NOP(PC); READ
PC = ADD(PC, IR_HI)
IR_LO = NOP(PC); READ
DECODE
чтение старшего слова команды
переход к следующему слову (PC = PC + 1)
чтение младшего слова команды
декодирование считанной команды
ADD Rx, Ry, Rz 4 Rx = ADD(Ry, Rz); JMP 62 сложение содержимого регистров NAND Rx, Ry, Rz 12 Rx = NAND(Ry,Rz); JMP 62 И-НЕ для содержимого регистров SHR Rx, Ry 20 Rx = SHR(Ry); JMP 62 арифметич. сдвиг содержимого регистра JC address28
29
30
Temp0 = NOP(Temp0); JC 30
JMP 62
PC = NOP(IR_LO); JMP 0
организация условного перехода
если условие не выполнилось, то завершить
иначе записать в PC новый адрес из IR_LO
DEC Rx, Ry36
37
38
Temp0 = SHR(IR_HI)
Temp0 = NAND(Temp0, Temp0)
Rx = ADD(Ry,Temp0); JMP 62
Temp0 = 0 (00000001 à 00000000)
Temp0 = -1 (11111111)
Rx = Ry + Temp0 = Ry + (-1)
SUB Rx, Ry, Rz44
45
46
47
48
Temp0 = SHR(IR_HI)
Temp0 = ADD(Temp0, Rz)
Temp0 = NAND(Temp0, Temp0)
Temp0 = ADD(Temp0, IR_HI)
Rx = ADD(Ry, Temp0); JMP 62
Temp0 = 0 (00000001 à 00000000)
Temp0 = 0 + Rz = Rz
инвертировать Temp0 = Rz
Temp0 = (! Rz) + 1
Rx = Ry + (-Rz)
LD Rx, address 52 Rx = NOP(IR_LO); READ; JMP 62 чтение из ОЗУ (шина A – адрес) ST Ry, address60
61
Temp0 = NOP(Ry)
Temp0 = NOP(IR_LO, Temp0); WRITE; JMP 62
Temp0 = Ry (данные на шину B)
запись в ОЗУ
(шина A – адрес, шина B — данные)
End: 62 PC = ADD(PC, IR_HI); JMP 0 увеличение счетчика команд (PC=PC+1)Кодировка микрокода
DEPTH = 64; % количество слов %
WIDTH = 24; % размер слова в битах %
ADDRESS_RADIX = DEC; % система счисления для адреса %
DATA_RADIX = BIN; % система счисления для данных %
CONTENT
BEGIN
[0..63] : 0; % поумолчанию везде нули %
% Инициализация %
0: 101100011101100000000000; % IR_HI = NOP(PC); READ %
1: 101111011011000100000000; % PC = ADD(PC, IR_HI) %
2: 101100011111100000000000; % IR_LO = NOP(PC); READ %
3: 000100011001000001000000; % DECODE %
% ADD Rx, Ry, Rz %
4: 000000000000000110111110; % Rx = ADD(Ry, Rz); JMP 62 %
% NAND Rx, Ry, Rz %
12: 000000000000001110111110; % Rx = NAND(Ry,Rz); JMP 62 %
% SHR Rx, Ry %
20: 000000000000001010111110; % Rx = SHR(Ry); JMP 62 %
% JC address %
28: 100110011001000011011110; % Temp0 = NOP(Temp0); JC 30 %
29: 100110011001000010111110; % JMP 62 %
30:111110011011000010000000; % PC = NOP(IR_LO); JMP 0 %
% DEC Rx, Ry %
36: 110100011001001000000000; % Temp0 = SHR(IR_HI) %
37: 100110011001001100000000; % Temp0 = NAND(Temp0, Temp0) %
38: 000010010000000110111110; % Rx = ADD(Ry,Temp0); JMP 62 %
% SUB Rx, Ry, Rz %
44:110100011001001000000000; % Temp0 = SHR(IR_HI) %
45:100100001001000100000000; % Temp0 = ADD(Temp0, Rz) %
46:100110011001001100000000; % Temp0 = NAND(Temp0, Temp0) %
47:100111011001000100000000; % Temp0 = ADD(Temp0, IR_HI) %
48:000010010000000110111110; % Rx = ADD(Ry, Temp0); JMP 62 %
% LD Rx, address %
52:111100010000100010111110; % Rx = NOP(IR_LO); READ; JMP 62%
% ST Ry, address %
60:000000011001000000000000; % Temp0 = NOP(Ry) %
61:111110011001010010111110; % Temp0 = NOP(IR_LO, Temp0);
WRITE; JMP 62 %
62: 101111011011000110000000; % PC = ADD(PC, IR_HI); JMP 0 %
END;
Примеры выполнениякоманд
Примеры выполнения каждой команды суказанием значения всех основных сигналов и содержимым основных регистров накаждом такте выполнения приведены на электронном носителе.
Основные сигналы и регистры
Сокращение Примечание CLOCK синхронизирующий сигнал C_SEL[2..0] номер регистра выбранного в качестве приемника A_SEL[2..0] номер регистра выбранного в качестве источника 1 B_SEL[2..0] номер регистра выбранного в качестве источника 2 Rx[2..0] номер регистра приемника из IR (регистра команд) Ry[2..0] номер регистра источника 1 из IR (регистра команд) Rz[2..0] номер регистра источника 2 из IR (регистра команд) MIR_A[2..0] номер регистра приемника из MIR (р-ра микрокоманд) MIR_B[2..0] номер регистра источника 1 из MIR (р-ра микрокоманд) MIR_C[2..0] номер регистра источника 2 из MIR (р-ра микрокоманд) AMUXОткуда брать номер регистра (0 – из IR, 1 – из MIR)
Эти сигналы управляют соответствующими мультиплексорами.
BMUX CMUX A_bus[7..0] Данные на шинах источниках, выходящих из блока регистров B_bus[7..0] C_ALU[7..0] Результат выходящий из АЛУ C_RAM[7..0] Данные, считанные из ОЗУ C_bus[7..0] Выбранные данные для записи (С_ALU или C_RAM) RD сигнал чтения из ОЗУ WR сигнал записи в ОЗУ KOP_ALU[1..0] код операции АЛУ (поступает из MIR) COND[1..0] определение следующей микрокоманды (из MIR) CBL_SEL[1..0] результат работы Control Branch Logic (логика управления ветвлением) – определяет следующую микрокоманду CF флаг переноса, поступающий из АЛУ в Control Branch Logic JMP_ADR[5..0] адрес следующей микрокоманды (из MIR) MIR[23..0] полное значение регистра микрокоманд (24 бит) PC программный счетчик (адрес в ОЗУ)Примеры программ
ПРИМЕР 1
DEPTH =256; % Memory depth and width are required %
WIDTH =8; % Enter a decimal number %
ADDRESS_RADIX= DEC; % Address and value radixes are optional %
DATA_RADIX =BIN; % Enter BIN, DEC, HEX, or OCT; unless %
CONTENT
BEGIN
%-------------------%
0:11001000; % LD Rg1, [6] %
1:00000110;
2:11010000; % LD Rg2, [7] %
3:00000111;
4:00011011; % ADD Rg3, Rg1, Rg2 %
5:00000000;
6:00010110; % const 22 (DEC) %
7:00100001; % const 33 (DEC) %
END;
ПРИМЕР 2
DEPTH =256; % Memory depth and width are required %
WIDTH =8; % Enter a decimal number %
ADDRESS_RADIX= DEC; % Address and value radixes are optional %
DATA_RADIX =BIN; % Enter BIN, DEC, HEX, or OCT; unless %
CONTENT
BEGIN
%-----------------%
0:11001000; % LD Rg1, [10] %
1:00001010;
2:01010010; % SHR Rg2, Rg1 %
3:00000111;
4:01100000; % JC 8 %
5:00001000;
6:10010010; % DEC Rg2, Rg1 %
7:00000000;
8:11100010; % ST Rg1, [10] %
9:00001010;
10:00000001; % const= 1 %
END ;
Значения основныхсигналов и содержимое основных регистров на каждом такте выполнения данныхпримеров программ приведены в виде временных диаграмм на электронном носителе.
Определение производительностиСреднее количество микрокоманд привыполнении команды процессора можно приблизительно оценить как 4 + 17/8 + 1 =7 микрокоманд на команду процессора. Таким образом, при максимальной тактовойчастоте в 33,3 МГц средняя производительность процессора составит 4, 7 MOPS (или 33,3 М μops / сек).
Тестовая программа Количество команд процессора Количество микрокоманд Время выполнения, нс N / сек ПРИМЕР 1 3 18 540 1851851 ПРИМЕР 2 5 34 1020 980398Повысить производительностьпроцессора можно одним из следующих способов:
— Увеличитьразрядность шины-приемника с 8 до 16 бит, и считывать команду из ОЗУ не за тритакта, а за один;
— Увеличитьфункциональность АЛУ, при этом можно будет сократить длину микрокода длянекоторых команд (особенно для SUB и DEC);
— Перейти отмикропрограммного управления к управлению на основе жесткой логики;
— Применитьконвейеризацию;
— Что-нибудьраспараллелить.