Реферат: Линейное программирование симплекс-методом Данцига - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

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

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

Содержание


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
КОП Rx Ry Rz не используется
0 0 0 x x y y z z







NAND Rx,Ry,Rz
КОП Rx Ry Rz не используется
0 0 1 x x y y z z







SHR Rx,Ry
КОП Rx Ry не используется
0 1 0 x x y y









JC address
КОП не использ. address
0 1 1




a a a a a a a a

DEC Rx,Ry
КОП Rx Ry не используется
1 0 0 x x y y









SUB Rx,Ry,Rz
КОП Rx Ry Rz не используется
1 0 1 x x y y z z







LD Rx,address
КОП Rx не исп. address
1 1 0 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 0 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 NAND

COND – условие для определения адреса следующей выполняемой микрокоманды


COND Куда переходим
00 NEXT на следующую микрокоманду
01 DECODE декодирование команды, Address = [KOP]100
10 JMP безусловный переход
11 JC условный переход по переносу (Carry Flag)

JMP ADDRESS – адрес в памяти микропрограмм, куда осуществляется переход


Микрокод


Адрес Микрокоманда Пояснение

0

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 address

28

29

30

Temp0 = NOP(Temp0); JC 30

JMP 62

PC = NOP(IR_LO); JMP 0

организация условного перехода

если условие не выполнилось, то завершить

иначе записать в PC новый адрес из IR_LO


DEC Rx, Ry

36

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, Rz

44

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, address

60

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

Перейти от микропрограммного управления к управлению на основе жесткой логики;

Применить конвейеризацию;

Что-нибудь распараллелить.