Реферат: Линейное программирование симплекс-методом Данцига

Содержание

1. Постановка задачи

2. Форматы команд и их кодировка

3. Структурная схема процессора

4. Регистры

5. АЛУ

6. Формат микрокоманд

7. Микрокод

8. Кодировка микрокода

9. Примеры выполнения команд

10. Основные сигналы и регистры процессора

11. Примеры программ

12. Определение производительности

Постановка задачи

Синтезировать структуру простого магистрального процессора с одним АЛУ, выполняющего 8 заданных команд. Разработать формат команд, кодировку команд. Разработать структурную схему процессора, функциональные схемы всех блоков процессора, функциональную схему процессора в целом с указанием всех шин и управляющих сигналов.

Разработать формат микрокоманд, организацию управления всеми устройствами процессора, микрокод для каждой из заданных команд. Привести примеры выполнения каждой команды с указанием значения всех основных сигналов и содержимого основных регистров на каждом такте. Привести 2 примера небольших программ с указанием значения основных сигналов и содержимого основных регистров на каждом такте.

Определить максимальную тактовую частоту процессора. Определить производительность процессора в операциях в секунду (IPS), а также выраженную в числе выполняемых тестовых программ в секунду. Указать способы повышения производительности процессора.

Характеристика процессора

Простой процессор магистрального типа с одноблочным универсальным АЛУ.

Разрядность регистров РОН и АЛУ процессора — 8 бит.

Число РОН — 4.

Адресуемая память — 256 слов.

Устройство управления — микропрограммное с ПЗУ микропрограмм.

Способ выполнения команд – последовательное выполнение или JMP или JC.

Адресация памяти — прямая.

Арифметика в дополнительном коде.

Вариант: 54 = «2 2 2 3»

Без использования непосредственной адресации.

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

КОП

не используется

NAND Rx,Ry,Rz

КОП

не используется

--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--

SUB Rx, Ry, Rz

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

Rx = NOP(IR_LO); READ; JMP 62

чтение из ОЗУ (шина A– адрес)

ST Ry, address

Temp0 = NOP(Ry)

Temp0 = NOP(IR_LO, Temp0); WRITE; JMP 62

Temp0 = Ry (данные на шину B)

запись в ОЗУ

(шина A – адрес, шина B — данные)

End:

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);

продолжение
--PAGE_BREAK--

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)

сигнал чтения из ОЗУ

сигнал записи в ОЗУ

KOP_ALU[1..0]

код операции АЛУ (поступает из MIR)

COND[1..0]

определение следующей микрокоманды (из MIR)

CBL_SEL[1..0]

результат работы ControlBranchLogic(логика управления ветвлением) – определяет следующую микрокоманду

флаг переноса, поступающий из АЛУ в ControlBranchLogic

JMP_ADR[5..0]

адрес следующей микрокоманды (из MIR)

MIR[23..0]

полное значение регистра микрокоманд (24 бит)

программный счетчик (адрес в ОЗУ)

Примерыпрограмм

ПРИМЕР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

540

1851851

ПРИМЕР 2

1020

980398

Повысить производительность процессора можно одним из следующих способов: